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.

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 $B_1, B_2, B_3 \dots B_n$ as a state machine. To create new blocks, we apply a state transition function to the state $S_i$ at block height $B_i$ with a transaction list $T_i$ , which results in some new state $S_{i+1}$ . This can be more formally expressed as follows:

transition(S_i, T_i) = S_{i+1}

This transactions list $T_i$ can be seen as a list of database transactions $\{t_1, t_{2}, t_{3} \dots t_n\}$ , where the state $S_i$ 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 $B_i$ is a corresponding state $S_i$ that describes the current state of the blockchain database after applying the list of transactions $T_i$ .

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.

Each block holds a new state.

There may potentially be multiple state transitions for a given block, as you can see in the diagram: $B_3$ , $B_4$ , $B_5$ all have multiple state transitions. This is where the role of a consensus algorithm aka fork choice rule comes into play.

Consensus is denoted by the blocks marked as green.

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 $< O(n)$ . (where $n$ 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 $m$ , producing a succint commitment $c$ , where $c < m.$ Such that the committer can later on reveal the message $m$ to a verifier who only has the commitment $c$ and the verifier can validate that the message $m$ does indeed correspond to the commitment $c$ .

A commitment scheme should satisfy two security properties:

Hiding. Receiving a commitment $c$ to a message $m$ should give no information to the verifier about $m$ ;
Binding. The committer cannot “cheat” in the second phase and send a different message $m^{\prime} \not = m$ that corresponds the commitment $c$ .

Now given this primitive we can use this scheme to commit to our state $S_i$ , such that:

commit(S) = C_{s} \\

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 $S$ :

S = \{s_1, s_2, s_3 \dots s_n\}\\

And another set $P$ , where $P \subseteq S$ . (i.e $P$ is a subset of $S$ ). A partial reveal scheme provides us the following algorithms:

Commit(S) = C_{s} \\ Prove(S, P) = \pi \\ Verify(C_s, P, \pi) \in \{true, false\}

Given these algorithms we can modify our initial state transition function like so:

transition(C_{S_i}, P, \pi, T_i) = C_{S_{i+1}}

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 blockchain state, but the most robust and widely used method is the Merkle-Patricia trie.

Blockchain State Commitments

A blockchain state commitment is a commitment to the entire state of the blockchain at any arbitrary block height. This commitment is generated by merkleizing (typically with a Merkle-Patricia trie) all key-value storage items on chain and computing the root of this tree. The state commitment is always included in the block header as a way to prove the state of the blockchain at any given block height.

Header of an ethereum block — Header for the ethereum block 19883335

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 $^{[1]}$ . 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 $^{[2]}$ .

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 $^{[3]}$ 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:

ProveTransition(C_{S_i}, P, \pi, T_i) = (C_{S_{i+1}}, \pi\prime) \\ Verify(C_{S_i}, C_{S_i + 1}, \pi\prime) \in \{true, false\}

Where $\pi\prime$ 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.

Trust-free Bridges

Trust-free 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.

References

$^{[1]}$ G. Wood, “Polkadot: Vision for a heterogeneous multi-chain framework,” Whitepaper, 2016

$^{[2]}$ Pepyakin, Parachains Consensus Explainer

$^{[3]}$ Alex Gluchowski, Nearly-zero cost attack scenario on Optimistic Rollup