Table of Links
Abstract and 1. Introduction
-
Key Concepts
2.1 Append-Only Log and 2.2 Virtual Machine State
2.3 Transactions As Curried Functions
2.4 Natural Names of State
2.5 Ground Truth
2.6 Efficient Representations of State
2.7 Checkpoints
2.8 Execution Parameters: callData
2.9 Execution Ordering
2.10 Deciding on the Correct State
-
Ideal Layer 2 Design
3.1 VM Job Queue and Transaction Order Finality
3.2 Data Availability and Garbage Collection
3.3 State Finality
3.4 Checkpoint Finality
-
Conclusion and References
A. Discrepancy Detection Security Parameters
2.8 Execution Parameters: callData
When we name states via transaction order, it is a “natural” name as a sequence of state-transformation functions as applied to the genesis or a checkpoint state. The state-transformations must be fully specified, i.e., the transaction data (callData) are function parameters to the transaction call that, when curried, allow us to view the transaction as state transforms.
In order for the commitment of transactions to make sense, it must include all callData for the state to be computed. This is a data availability requirement. Transactions (their callData) does not have to be directly in the blocks, though that is the simplest design choice. If a highly available data repository, i.e., a data availability layer (e.g., IPFS [3]), can be used, then lists of transactions can be stored there and the on-chain data can simply be the name by which the transaction list can be obtained.
Here, feasibility must include some notion of verifying data availability, e.g., signatures from a quorum of availability providers. It is not enough to use a simple content-addressable storage (CAS) without availability guarantees, since otherwise we face the following dilemma when an adversary computes the CAS name without actually making the data available. In such a scenario, we either sacrifice liveness, having to wait indefinitely for the callData to become available, or try to use timeouts and treat unavailable callData as implicit aborted transactions and move on. This latter choice sacrifices finality: a user can nullify their transactions after the transaction’s execution order has been decided—by making their callData unavailable— if the user decides that the execution order is not to their advantage, so until state finality has been reached, transaction order finality does not uniquely specify a resultant state.
Note that Ethereum’s stateRoot has a symmetric CAS availability problem. The state output from a transaction is needed as input to the next transaction, and a lack of availability here means that the new state’s representation cannot be easily computed, destroying liveness.[4]
2.9 Execution Ordering
Execution ordering can be quite important, since any given two state transforming functions might not commute with each other. The notion of “front running” is not new with blockchains but has been unethically (and illegally) practiced in stock and commodities markets [12]. Front-running uses the ability to influence execution ordering results, where additional orders are injected in front of (and often also behind) orders that may move the market. For example, if Trey submits a transaction g to buy a large amount of some commodity, it is likely to cause a price increase (“move the market”). If Fanny knew about his order and can inject in a pair of transactions to sandwich his: the net is a pseudo-conjugate transaction g’ = f; g; f∗ , where f denotes a transaction to buy the same commodity at market price, and f ∗ denotes a “pseudo-inverse” transaction to sell the same amount, at what will be a higher market price, to exit the market and reap profits.[5] In Bitcoin, Ethereum, and most layer 2 rollup designs, the (layer 1) miners choose transactions from a mempool of proposed transactions and can choose and order transactions within the new block in any order that they want.
Ideally, transactions that offer approximately the same gas fees should perhaps be handled on a first-come, first-serve basis, with the order decided based on approximate timestamps. Standard Bitcoin, Ethereum, and rollup designs are all vulnerable to order conjugation, though there are research on ways to maintain fair ordering for some definition of fairness [9, 13, 4].
How to decide on an execution ordering is a largely orthogonal design decision. The scheme used in Bitcoin and Ethereum (v1) is leaderless and probabilistic, since miners can independently choose the transactions to include in the blocks they mine. For L2 rollups with decoupled ordering and state value determination, the transaction order can be determined in many ways: (1) as a “null hypothesis”, in L1 submission order (susceptible to L1 front running); (2) via trusted off-chain schedulers that (fairly) order batches of transactions; (3) via trustless decentralized applications on other blockchains that perform batch scheduling, using commit-reveal of transaction details to prevent biased ordering; etc. The potential design space is large, and exploring this is on-going research.
Authors:
(1) Bennet Yee, Oasis Labs;
(2) Dawn Song, Oasis Labs;
(3) Patrick McCorry, Infura;
(4) Chris Buckland, Infura.
[4] Obviously the input state can be reconstructed by transaction replay, but that is not efficient.
