Table of Links
-
Key Concepts
2.1 Append-Only Log and 2.2 Virtual Machine State
2.3 Transactions As Curried Functions
2.6 Efficient Representations of State
-
3.1 VM Job Queue and Transaction Order Finality
A. Discrepancy Detection Security Parameters
2.5 Ground Truth
Ground truth for smart contract / blockchain systems is knowing what the current state is supposed to be. This does not mean, however, that we must have an efficient representation of that state, merely that it is computable—efficiently, and unambiguously. We argue that the most natural definition for blockchain system state is based on consensus agreement on the order of all transactions since the genesis state (or since a checkpoint state, see Section 2.7).
Once a transaction’s parameters are logged (has achieved log finality), its execution order relative to earlier logged transactions is determined. Via a simple inductive argument, since the input state is computable by the execution order finality of earlier transactions, the resultant state from this transaction can, in principle, also be computed. We call this “transaction order finality.”
Consensus about the current state is based on states’ natural names, and computing an efficient representation is not necessarily coupled with this decision. Everything else is an optimization.
2.6 Efficient Representations of State
All blockchain-based systems use an append-only log to record ground truth. From those log entries the system determines the consensus reality on the state of one (or more) virtual machines. However, different blockchains handle state differently.
Bitcoin only records transactions in the blockchain blocks. The VM is relatively simple and the state is the number of tokens controlled by public keys— the so-called Unspent Transaction Outputs (UTXOs). The logged messages specify how to transfer tokens using the VM rules, but state is implicit. In contrast, Ethereum also records a representation of the new state that results after all the transactions named within the block are applied to the state from the previous block. This state is recorded via a cryptographic commitment—the “stateRoot”, which is the root hash summary of the Merkle Patricia trie representation of the Ethereum Virtual Machine (EVM) state. Hyperledger [1] takes a Bitcoin-like approach and leaves the interpretation of results—the effect on the VM—to clients.
Note that Bitcoin miners must also have an efficient representation of state, since in order to verify new blocks double spending checks etc must be performed— it is just that this state does not show up on-chain. Availability is separate from permanence: in either case, miners has to either “catch up” by replaying transactions since a checkpoint (more on that later) or obtain a copy from somebody else. Apart from replaying transactions, there is no way for Bitcoin miners to verify state obtained from an untrusted party; Ethereum miners, on the other hand, can readily verify the Merklized data structure (stateRoot).
Rollup systems use an existing underlying blockchain as a security anchor to allow “off-chain” execution, where smart contract code executes in a separate VM (“rollup”), so that many transactions can execute there while requiring fewer (or cheaper) transactions at the underlying blockchain. This is an attractive scaling solution, since (presumably) computation on the rollup is cheaper, and a single underlying blockchain can support multiple rollups. Optimistic rollup designs like Arbitrum [8] commit the transaction order to a bridge contract in the underlying blockchain, computes the resultant state in the rollup, and sends that result to the bridge contract in the underlying blockchain to validate. We will discuss various validation schemes later (see Section 2.10); the key observation here is that transaction order can be determined in a separate step from state computation.
Another way to think of this is that the resultant state from the execution of a transaction t is named once we have the order of all transactions starting from the genesis state up to and including t. We may not yet have computed that state as a data structure that allows the key-value lookup to be performed efficiently, but there is no doubt what that state would be—everyone given its name will arrive at the same abstract mapping, even if its concrete representation— actual choices of data structures—may differ. Bitcoin only names the current state.[3] Ethereum-like systems both name and compute one particular representation of state. Some rollups separate naming from state computation, where the transaction order is committed to the layer 1 blockchain first, and the correct resultant state is computed off-chain, in the layer 2 rollup, and committed to layer 1 at a later time. Other rollups use a mempool design for the rollup, so that the transaction order is determined by rollup nodes rather than in the underlying blockchain, and that order is committed along with the computed state hash. Such a design reduces the number of transactions in the underlying blockchain, trading off reduced transaction processing cost there for tight coupling between transaction order finality and state determination.
The separation of concerns should be explicit. The consensus layer is responsible for making an immutable, append-only log. Its primary purpose is to record the transaction—the calldata—in the order in which they are to be executed. This names the resultant state, and everything else is secondary. Computing and agreeing on this state can come later, as fulfilling a promised value. The result—a correspondence between a named state and the state representation— can be similarly recorded to make state representation sharing easier. That is to say: Bitcoin logs only execution order; Ethereum logs both execution order and an efficient representation of the resultant state in a tightly coupled manner; decoupled layer 2 rollup designs, on the other hand, logs both but separately, so that problems with the validity of the computed state does not necessarily invalidate the committed transaction order.
Note that it is important to calculate state and to reach consensus on it, since blockchains are not closed systems: transfers between rollup and underlying blockchain is an example of external actions that depend on state; in general, any contracts that can cause off-chain effects, such as the shipment of goods, require consensus and state value finality.
In our view, obtaining an equivalent but more efficient representation of a given state is an important optimization. Indeed, committing the transaction execution order yields one sense of finality—transaction order finality, allowing us to name a committed state. Computing the stateRoot and reaching agreement on the result yields a second sense of finality—“state value finality”, allowing us to confidently use the state’s value or representation.
Authors:
(1) Bennet Yee, Oasis Labs;
(2) Dawn Song, Oasis Labs;
(3) Patrick McCorry, Infura;
(4) Chris Buckland, Infura.
This paper is
[3] Though states are realized periodically, when checkpoints are created. See Section 2.7 for more details.