Block and Transaction-level Validation of qPoS State Transitions
This week I spent almost all of my time writing code to validate qPoS instructions at both the transactional and block level. These instructions specify registry state transitions. During this process I had to make many design decisions, essentially finalizing in very concrete terms how the registry interacts with the UTXO blockchain. I spend most of today’s update discussing transactional ordering, which is of paramount importance to validation.
–––––
Conceptualizing qPoS State Transitions as Instructions
Before I begin reviewing this week’s work, I think it will be helpful to provide a conceptual framework for understanding how qPoS state transitions are applied to the registry. Examples of state transitions are: adding a new staker, crediting a staker’s pubkey with a block reward, disabling a staker, and so on. In writing code this week, I had to distill the essence of each qPoS state transition into a declaration, meaning a type of data structure that only specifies attributes and their values.
As an example, consider the simplest qPoS state transition of setting the state of a staker to be enabled or disabled. I’ll give a representation as a picture, so that non-programmers can understand it.
Hopefully I have made this image easy enough to understand. At its essence, “SET STATE” is an instruction that says to enable the staker that is identified by the number 42. You can see how this instruction describes a state transition, where the staker #42 will undergo a transition from a disabled state to an enabled state upon the execution of this instruction.
–––––
Data Structure Hierarchy Determines qPoS Ordering
Blockchain Transactional Ordering (Is not Hierarchical)
With state transitions, order matters. The XST blockchain already has a hierarchy in place to organize the ordering of spending transactions, but it has very little to do with how data structures are organized. Instead of inferring transaction order from data organization, XST transactions are ordered using pointers. Each XST spending transaction involves the simultaneous destruction and creation of money, such that the amount created does not exceed the amount destroyed. The created money points back to the destroyed money such that it is impossible to spend any money that has new money pointing back to it. A depiction of a hypothetical transaction will help:
Again, hopefully this figure is easy to interpret. It is a spending transaction where 3 XST of old money (called an “input”) is destroyed and 3 XST of new money (“outputs”) is created. Here the new money is split between two outputs differing in value. While this may not be the most precise representation of the actual data structures, the arrows are meant to represent that the transaction points back to old money that is destroyed (spent). Notice the critical feature of this spending transaction (and any valid spending transaction) is that the total money created is no greater than the total money destroyed. We can see why this feature is important: it precludes the creation of new money simply by spending old money. Note that new money is not spent yet, and such outputs are called “unspent transaction outputs”, or UTXOs.
The destruction and creation of inputs and outputs allows spenders to order transactions, eliminating any ambiguity when interpreting the state of the blockchain ledger. However, the qPoS registry does not rely on this type of order as a matter of efficiency. Most significantly, in the UTXO model, determining whether a spending transaction is valid requires the process of (1) searching through the transaction database for its inputs, (2) ensuring they haven’t been spent, (3) tallying them up, and then (4) ensuring their total is no greater than the amount being spent. This searching and tallying takes a lot of computational resources as well as file I/O, which is very slow.
Blockchain Data Structures are Hierarchical
In contrast, the registry relies on explicit ordering of instructions (like the SET STATE instruction represented above). This explicit ordering comes from the blockchain structure itself.
At the top level is the ordering of blocks within the blockchain. This ordering is easy to understand: Block 1 precedes Block 2, and Block 2 precedes Block 3, etc. This ordering is not only temporal (in the Stealth blockchain), but is explicitly specified using pointers, where Block 3 points back to Block 2, and Block 2 points back to Block 1. Pictorially, this looks like:
At the middle level, transactions are ordered within blocks, each transaction having an index. Transactions in a blockchain begin with index 0, and increase by 1 with each transaction.
At the bottom level, within individual transactions, are transaction outputs. Each transaction output specifies a state transition where old money (belonging to a set of accounts A) is destroyed and new money of equal or lesser value is created (belonging to a set of accounts B). Notice in the depiction above (of the 3 XST spending transaction) that each output has an index (index 0, index 1).
qPoS State Changes Use Blockchain Hierarchy for Ordering
Although explicit ordering defined by the hierarchical data structure of blocks, transactions, and outputs doesn’t direct the state of the blockchain, it is useful in qPoS to interpret the registry state because it makes the ordering of any qPoS instructions unambiguous. Specifically qPoS instructions (like SET STATE, depicted above) are ordered according to the hierarchy: (1) qPoS instructions specified by outputs of lower index are executed by qPoS instructions specified by outputs of higher index, (2) qPoS instructions in transactions of lower index are executed before qPoS instructions in transactions of higher index, and (3) qPoS instructions in blocks of lower number are executed before qPoS instructions in blocks of higher number.
As an aside, you might notice here that I mentioned that qPoS instructions are specified at the level of outputs. The reason is that outputs are the bearers of the Script programs (discussed in last week’s dev update), and these programs specify qPoS state transitions.
–––––
Summary of This Week’s Progress
Since this update is getting kind of long, I’m going to summarize this week’s work as a list. I will try to keep it terse, although it represents a lot of progress and a huge step towards a working qPoS platform.
- I finalized the structure of qPoS Script programs that are specified in transaction outputs. I have discussed these programs today in terms of “instructions”, but I generally refer to them as “qPoS transactions”, as I will below. I also refer to these as programs by the opcodes that characterize them (eg. TX_PURCHASE1, TX_CLAIM, TX_ENABE, etc.). I will present these structures in next week’s update and once qPoS is in testnet, add them to the Whitepaper.
- I wrote full transaction-level validation for all qPoS transactions (TX_PURCHASE1, TX_PURCHASE3, TX_SETOWNER, TX_SETDELEGATE, TX_SETCONTROLLER, TX_ENABLE, TX_DISABLE, and TX_CLAIM. All validation takes into account not only the state of the registry, but interactions between different qPoS transactions. For example, a transaction where TX_SETOWNER precedes TX_SETDELEGATE will be invalidated because the owner will have changed before the delegate can be set. Many other potentially invalid interactions exist.
- I wrote the full block-level validation for all qPoS transactions (listed above). Again, this includes interactions. The main loop of block-level validation gathers all valid qPoS transactions, keeping their transactional ordering as well as output ordering. Block-level checks include (a) ensuring the same alias is not registered for two different stakers, (b) ensuring key changing operations are not attempted on the same staker in two different transactions (preventing block-level ordering conflicts), and (c) gathering claims by public key and ensuring the total claim does not exceed the relevant balance in the registry ledger.
–––––
Hondo