State (Machine) Proofs
State proofs are a critical primitive of the blockchain stack that enable things like trustless bridges, off-chain light clients that can access on-chain data in a permissionless and secure manner as well as modular blockchains architectures where the execution layer can be decoupled from the consensus layer.
Written by
Published on
Do not index
Do not index
State proofs are a critical primitive of the blockchain stack that enable things like trustless bridges, off-chain light clients that can access on-chain data in a permissionless and secure manner as well as modular blockchains architectures where the execution layer can be decoupled from the consensus layer.
To understand how state proofs enable these functionalities, and more importantly, what they actually prove, it is necessary to first understand blockchains as state machines.
Blockchains as State Machines
In a generalised blockchain model, we can describe a blockchain with blocks as a state machine. To create new blocks, we apply a state transition function to the state at block height with a transaction list , which results in some new state . This can be more formally expressed as follows:
This transactions list can be seen as a list of database transactions , where the state represents a key-value database. These transactions may create, update or delete items in this key-value database. It's important to note that in this state machine model, our state transition function returns a new copy of the database. This means that the output of a successful transition is fed into the input for the next state transition. Therefore, at every new block is a corresponding state that describes the current state of the blockchain database after applying the list of transactions .
Data verifiability is blockchain’s main value proposition. Which is why In order to arrive at the latest (trusted) state of the blockchain, it is necessary for blockchain nodes to re-apply all the transactions that have been made since the genesis block. By re-applying each transaction, each participant is able to produce the new state of the blockchain. This mechanism is what allows blockchains to be considered a tamper-proof database that can be trusted by all participants.
There may potentially be multiple state transitions for a given block, as you can see in the diagram: , , all have multiple state transitions. This is where the role of a consensus algorithm aka fork choice rule comes into play.
The role of consensus in a blockchain is to tell us which sequence of state transitions are final or can be trusted. They do so by employing a combination of game theoretic and cryptographic protocols to ensure that the network will always agree on one history of state transitions and not more.
So we see now that the existential role of a blockchain is to provide a database that is backed by a sequence of valid state transitions. But there's a problem with our current model, you see our state transition function always returns a new copy of the full database. Implementing a blockchain using this model would be prohibitively expensive. This is because we'd have to copy over the full state db for every new block, even parts of the state that haven’t changed.
To address this problem, we need to optimize the size of the data needed for our state transition function, Effectively making it sub-linear to the size of the full database. i.e . (where is the size of the full state). One solution is to leverage a "state diff", which would only include the parts of the state that have changed, rather than copying the entire state database for every state transition. This would bring significant space and time savings associated with running a blockchain node.
This state diff means our state transition produces less data and is as a result more efficient to compute. In order to achieve this state diff, we’ll need to leverage a different kind data structure for our blockchain state, let’s take a detour into commitment schemes.
Cryptographic commitment schemes
A cryptographic commitment scheme is one of the most powerful cryptographic primitives in a protocol developer’s toolbox. Formally, a cryptographic commitment scheme allows a committer commit to some message , producing a succint commitment , where Such that the committer can later on reveal the message to a verifier who only has the commitment and the verifier can validate that the message does indeed correspond to the commitment .
A commitment scheme should satisfy two security properties:
- Hiding. Receiving a commitment to a message should give no information to the verifier about ;
- Binding. The committer cannot “cheat” in the second phase and send a different message that corresponds the commitment .
Now given this primitive we can use this scheme to commit to our state , such that:
The current scheme is a great starting point, but we need more. Specifically, we need a scheme that supports partial reveals. By supporting partial reveals, we can commit to some data and produce a proof for only a portion of that data, which can later be verified against a commitment to the full data. With this scheme, we can reduce the size of the data needed for our state transition function while still being able to verify the authenticity of that data.
Given some data :
And another set , where . (i.e is a subset of ). A partial reveal scheme provides us the following algorithms:
Given these algorithms we can modify our initial state transition function like so:
where:
The commitment to the state .
The set of values in the set that would be modified by the transaction set .
The state proof for the existence of the set in the original state .
The set of transaction which operate of the key-values in .
In this new scheme, Instead of taking the full state db as an input, our state transition function takes a commitment to the full state db, the values that will be modified by the transactions, a proof for these values corresponding to the commitment, and finally the actual transaction list. But instead of returning a new copy of the state-db, it only returns a commitment to the new state.
This approach prevents redundant data copying during state transitions, resulting in a faster runtime for our blockchain than if we copied the entire state database every time. And indeed this is how most modern blockchains are implemented.
There are many ways to implement a commitment scheme that supports partial reveals for our state, but the most robust and widely used method is a Merkle tree.
Merkle trees
A Merkle tree is a powerful data structure that enables efficient verification of large amounts of data. Specifically, a Merkle tree can be thought of as a cryptographic hash-function whose pre-image is a virtual tree. As such, the root node of this structure is cryptographically dependent on all internal data and its root hash can be used as a secure identity for the data stored in the tree. Merkle trees also support partial reveals for subsets of the original data through multi-proofs.
However, it's important to note that Merkle trees only support flat lists of data. In other words, a Merkle tree on its own cannot be used to encode key-value pairs. To take advantage of the Merkle tree’s support for partial reveals for key-value data, we need to combine the conventional Merkle tree structure with another tree structure that allows for key-value encoding.
Patricia Trie
A PATRICIA Trie, also known as a radix trie, is a kind of -ary search tree which is used for efficiently looking up items in a database. It achieves an search complexity by encoding the keys in the trie nodes along the path to the data. Unlike conventional tries, a Patricia trie only creates a node for each unique prefix of its keys. This reduces the amount of memory required to store the trie and allows for faster lookups.
Patricia tries were first described by Donald R. Morrison in 1968 and have since been used in a variety of applications, including IP routing tables and spell checkers. They are a powerful data structure that can greatly improve the efficiency of searching and retrieving data from large databases.
Merkle-Patricia Trie
The Merkle-Patricia trie was invented by Dr. Gavin Wood, co-founder of Ethereum. It was first described in the Ethereum yellow paper. This data structure combines the PATRICIA and Merkle trees into a single tree, which has the ability to store key-value items while still allowing for merkle proofs. Where, represents the arity of each node and represents the number of leaves in the tree. The yellow paper prescribes an arity of 16, but using other arities is also possible.
The yellow paper describes 3 kinds of Merkle-Patricia nodes:
Leaf Nodes
.svg&optimizer=image&quality=80&width=280)
A leaf node can be thought of a 2-item tuple, whose first item corresponds to the bytes in the key not already accounted for by the accumulation of keys in the branch & extension nodes traversed from the root. The second item corresponds to the actual value held at the leaf node. The hash of a leaf node is gotten by concatenating it’s partial key with the hash of it’s value and taking the hash of this concatenation.
Extension Nodes
An extension node serves as a key accumulation node for keys that would’ve otherwise been encoded into deeply nested branch nodes. Much like the leaf node it is a 2-item tuple, it’s first item hold the key bytes shared by its child node, but its second item points to another (usually a branch) node in the trie. The hash of an extension node is gotten by concatenating it’s partial key with the hash of it’s child node and taking the hash of this concatenation.
Branch Nodes
A branch node on the other hand is a 17-item tuple, where the first 16 items in the tuple correspond to all the possible nibble ( or half a byte) values which hold the hash of a node at those positions, while the 17th item holds a possible value. The hash of a branch node is gotten by concatenating of the hash of all its children nodes and taking the hash of this concatenation. This is also the reason why the merkle-patricia trie has merkle proofs, as you’d need to include the hash of all sibling nodes in all the branch nodes along the path to the leaf node.
Compact Merkle Patricia Proofs
The merkle-patricia trie was further modified for substrate and polkadot, resulting in more compact state proofs by eliminating extension nodes. Instead, partial keys were introduced to branch nodes. This means that branch nodes can hold accumulated partial keys, which eliminates the need for a dedicated extension node. With this modification state proofs are effectively compacted and less nodes are required in state proofs.
Applications
Now that we have a comprehensive understanding of state proofs and the underlying concept of blockchains as a verifiable state machine, we can now delve into the various applications of state proofs.
Modular Blockchain Architecture
As alluded to in the previous section, the consensus and the state machine are two separate sub-protocols in the blockchain stack. But conventionally, they’ve been combined into one monolithic protocol. However, ongoing research and development has demonstrated that significant scalability improvements can be achieved by separating the two protocols. In this new approach, a single consensus layer is responsible for coming to consensus about the state of multiple concurrent state machines, rather than just one.
This allows for many benefits, such as higher transaction throughput and, as a result, faster processing of transactions. Additionally, the separation of the two protocols allows for greater flexibility in network design, enabling developers to create more specialised blockchains for application specific purposes, aka app-chains.
This modular design was first pioneered by Dr Gavin Wood as far back as 2016 in his revolutionary whitepaper for the Polkadot network. This design facilitates the provision of consensus by a blockchain to other blockchains by validating it’s state transitions through the use of state proofs.
Polkadot Parachains and Optimistic L2s on Ethereum both use state proofs to achieve parallel state machines running on a single consensus layer. In this new architecture, the state machines commit their blocks, which include the commitment to the new & old state, as well a state proof for the parts of the state modified by the block. This state proof is also referred to as state witness or proof-of-validity depending on who you ask.
In the case of Polkadot, the Polkadot relay chain re-executes parachain blocks with their given state proofs to ensure that only blocks with valid state transitions are finalized by the Polkadot network. This is accomplished using sub-protocols referred to as Availability & Approval.
On the other hand, Ethereum doesn't re-execute optimistic L2 blocks. Instead, it relies on off-chain parties to re-execute the blocks. If an L2 block is posted to Ethereum with a state commitment that doesn't match the actual value calculated after its blocks are executed off-chain, the L2 block can be challenged. This is done by forcing its re-execution on-chain, so that its real state root maybe derived. Unfortunately, this is also why withdrawals from optimistic L2s take at least 7 days. The reason for the delay is to mitigate any censorship attacks that may arise, and give honest parties enough time to challenge invalid L2 blocks.
However, with the rise of Proofs of Computational Integrity Schemes, it becomes possible to enforce valid state transitions by producing a proof that the state transition was executed correctly off-chain. This allows the consensus layer to verify a succinct proof that validates the state transition. Formally:
Where is the proof of computational integrity.
This would scale blockchains even further as the consensus layer no longer needs to be aware of the state proof or the actual transactions behind the transition. Many teams are actively working on this problem, but seeing as this is a relatively new technology, we should not expect robust implementations anytime soon.
Light clients
Light clients allow for computationally constrained environments such as mobile phones, IOT devices or even another blockchain to read (the state trie) and write (submit transactions, this only works for off-chain light clients) to a blockchain network. An offchain light client achieves this by connecting directly to the p2p network of blockchain nodes rather than relying on centralized or even worse “decentralized” RPC providers.
A light client, unlike full nodes, does not track the state transitions of the blockchain network. This greatly reduces the amount of data it needs to download and store. Instead, light clients only track the blockchain's block headers & consensus proofs, which are usually small enough to be validated. They use these headers & consensus proofs as a source of truth for the latest finalized state of the blockchain, Given that a blockchain header contains a commitment to the blockchain state.
In order to read the blockchain state in a trustless manner, light clients can request state proofs for the items in the state trie that they care about from full nodes who actually maintain the full blockchain state. By validating the state proofs of the items against the state root inside of a verified block header they are able to securely access blockchain data backed by the full blockchain security.
Unfortunately, light clients today are essentially parasites since their state proof requests add extra networking and computing load on full nodes. This is because full nodes must traverse the state trie in order to serve these requests. Therefore, if we want to maintain a healthy blockchain network, especially in a future where millions of people will use light clients to access the blockchain state, it is necessary to introduce a light client data incentivization protocol that incentivizes full nodes to respond to these requests.
Trustless Bridges
Trustless bridges enable the secure transfers of data and assets between two separate blockchain networks. These bridges rely on the security assumptions of the sending blockchain by observing and verifying its consensus proofs on the receiving blockchain using a light client. This eliminates the need for attesters, oracles, or other kinds of trusted intermediaries.
In order to achieve this transfer, the outgoing assets and/or data are stored in the state trie of a connected blockchain. This allows us to obtain state proofs for the transfer, which can then be verified by the counterparty blockchain. Once verified, these state proofs are used to authorise the minting of the transferred assets, or the delivery of cross-chain messages.
Interoperability allows for users to leverage the unique features of different blockchain networks. For instance, a user might want to transfer their assets from a public blockchain network to a private blockchain network. Where their assets can be shielded and the transactions encrypted in such a way that they are obfuscated to the external world.
Trustless bridges also allow for competitive protocols to accumulate user assets and provide better services to users. This competition drives innovation and motivates blockchain networks to improve and differentiate themselves from others. Additionally, trustless bridges promote collaboration between different blockchain networks, by enabling developers to create more specialized blockchains for application-specific purposes.
Summary
In conclusion, I’ve shown how state proofs are critical primitive for security, interoperability and scalability. As such, ongoing research and development is seeking to make them even more efficient and concise. This will not only improve the performance of blockchains, but also make them more accessible to a wider range of users. In an upcoming article, we will delve deeper into these developments and explore their potential impact on the future of blockchain technology.
References
Written by
.png%3Ftable%3Dblock%26id%3Dc2ac4acc-a499-44ce-998a-c01c4d1aca94%26cache%3Dv2&optimizer=image&quality=80&width=280)