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 3 Ideal Layer 2 Design The ideal rollup design allows efficient (off-chain) verifiable computation with fast finality. Here, efficiency means: • Reduced replicated computation. We do not want to use resources, e.g., use an enormous amount of electricity, when it is unnecessary for the required level of security. Reduced replication should also reduce the cost per transaction, making the system more scalable from an economic perspective. • High confidence in results. This is the converse to replication: users should be able to trust the results from the verified computation, even though the replication factor might be lower. • High throughput. The overall system throughput should be high, so that the system will perform well with a high workload. • Low latency. Proposed transactions should not have to wait too long in queues. Users should have reasonable confidence that once a transaction is accepted, it will have the desired/expected effect. What an “ideal” design might look like depends on other factors, such as the expected workload. For example, as systems become more capable, will applications need to run larger transactions that have a high gas limit? What is the distribution of execution times? With a design that separates transaction order finality and state finality, as long as the average transaction processing rate is sufficient, the system should be able to tolerate occasional high execution time transactions, since users will primarily care about transaction order finality, assuming that the expensive transaction do not interfere or interact with most users’ contracts’ state. This is still an area of research and some design constraints are unknown. We present a sketch of an “ideal” design below. 3.1 VM Job Queue and Transaction Order Finality The ideal rollup design uses “instant” finality of a PoS blockchain (e.g. Tendermint, Eth2) to obtain transaction order finality. That is, transaction proposals are essentially jobs entered into the virtual machine job queue; once entered into the queue, its order is final. This implies that the transaction callData cannot be validated with full virtual machine semantics, since that requires close coupling between the log and the virtual machine. One extreme design choice is to allow arbitrary messages to be logged to target the VM’s job queue, and rely on the cost of logging to deter denial-of-service attacks. This means, however, that the cost of VM execution to verify and discard ill-formed message (e.g., unsigned, unparseable, nonexistent contract entry points, etc) must be included as part of the cost of message handling. Message posting has to cost something in order to prevent denial-of-service attacks. This means some checks must already be done at the underlying blockchain: the message itself must be signed, and it must authorize payment from the EOA to minimally pay for the message posting itself, as well as a (limited) payment authorization for the VM execution (gas limit). Since signature check is effectively a sunk cost, an alternative is to perform some very simple verification of proposed transactions: • Transaction authorization: valid signature on the proposal. • EOA account has enough tokens to pay for message posting. • (Optional) EOA account has enough tokens to pay for the maximum gas payment, using an lower-bound estimate from the queue of transactions for which state finality has not been reached. The contract call parameters (callData) is just opaque bytes at this point. All signed transaction proposals with these basic checks are considered “well-formed transactions” (WFTs). Note that we do not perform contract entry point-specific type checks or other per-contract pre-condition checks at the bridge. Well-formedness does not imply that the message makes sense. WFTs that do not pass message format checks will simply be aborted with the sender charged a small gas fee: in our formalism, this means that the interpretation is that tc returns with its input state. The same thing applies for other pre-conditions: those would be checked by the contract code (e.g., the equivalent of require checks in Solidity) and similarly cause the transaction to be aborted. This conforms with the decoupled nature of the system design: the bridge contract does not know what (possibly new) contracts have been instantiated on the rollup, and doing typechecking would be impractical. Contract invocations in Ethereum-like blockchains are internally structured as essentially remote procedure calls, with a message that must be (partially) parsed to identify the intended entry point and discover the type signature, and then to further parse and typecheck the rest of the message. While it might be reasonable to say that the message encoding is architecturally fixed and performed by the rollup VM, it is feasible—as is done by Solidity for the EVM—to perform this in the contract code itself (in Solidity’s case, in the language runtime which performs the RPC dispatch). Since different contract language runtimes could, in principle, require completely different data serialization formats, performing message format verification in the bridge is infeasible without knowing details about how each contract’s RPC message receiver/demultiplexor is implemented. The simplest design is to view the bridge contract as accepting WFTs and require runtime checking for rollup-specific, contract-language specific, or contractspecific pre-conditions. The arrival order at the job queue maintained by the bridge contract does not necessarily specify the execution order. Clearly, as long as a rollup allows transaction proposers to offer variable gas fees (as opposed to a fixed market rate as a gating threshold), jobs will need to be sorted by gas price. And while using gas price as the primary key and arrival order as the secondary key might approximate a “fair” order, it allows a frontrunner to trivially creating pseudoconjugate transactions by proposing a pair of transactions at a slightly higher and slightly lower gas fee. More research is needed here, especially since implementing an approximate fair scheduler will introduce additional latency to the transaction processing. Authors:
(1) Bennet Yee, Oasis Labs;
(2) Dawn Song, Oasis Labs;
(3) Patrick McCorry, Infura;
(4) Chris Buckland, Infura. This paper is available on arxiv under ATTRIBUTION 4.0 INTERNATIONAL license. Table of Links Abstract and 1. Introduction 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 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 Key Concepts 2.1 Append-Only Log and 2.2 Virtual Machine State 2.1 Append-Only Log and 2.2 Virtual Machine State 2.3 Transactions As Curried Functions 2.3 Transactions As Curried Functions 2.4 Natural Names of State 2.4 Natural Names of State 2.5 Ground Truth 2.5 Ground Truth 2.6 Efficient Representations of State 2.6 Efficient Representations of State 2.7 Checkpoints 2.7 Checkpoints 2.8 Execution Parameters: callData 2.8 Execution Parameters: callData 2.9 Execution Ordering 2.9 Execution Ordering 2.10 Deciding on the Correct State 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 Ideal Layer 2 Design Ideal Layer 2 Design 3.1 VM Job Queue and Transaction Order Finality 3.1 VM Job Queue and Transaction Order Finality 3.2 Data Availability and Garbage Collection 3.2 Data Availability and Garbage Collection 3.3 State Finality 3.3 State Finality 3.4 Checkpoint Finality 3.4 Checkpoint Finality Conclusion and References Conclusion and References Conclusion and References A. Discrepancy Detection Security Parameters A. Discrepancy Detection Security Parameters 3 Ideal Layer 2 Design The ideal rollup design allows efficient (off-chain) verifiable computation with fast finality. Here, efficiency means: • Reduced replicated computation. We do not want to use resources, e.g., use an enormous amount of electricity, when it is unnecessary for the required level of security. Reduced replication should also reduce the cost per transaction, making the system more scalable from an economic perspective. • High confidence in results. This is the converse to replication: users should be able to trust the results from the verified computation, even though the replication factor might be lower. • High throughput. The overall system throughput should be high, so that the system will perform well with a high workload. • Low latency. Proposed transactions should not have to wait too long in queues. Users should have reasonable confidence that once a transaction is accepted, it will have the desired/expected effect. What an “ideal” design might look like depends on other factors, such as the expected workload. For example, as systems become more capable, will applications need to run larger transactions that have a high gas limit? What is the distribution of execution times? With a design that separates transaction order finality and state finality, as long as the average transaction processing rate is sufficient, the system should be able to tolerate occasional high execution time transactions, since users will primarily care about transaction order finality, assuming that the expensive transaction do not interfere or interact with most users’ contracts’ state. This is still an area of research and some design constraints are unknown. We present a sketch of an “ideal” design below. 3.1 VM Job Queue and Transaction Order Finality The ideal rollup design uses “instant” finality of a PoS blockchain (e.g. Tendermint, Eth2) to obtain transaction order finality. That is, transaction proposals are essentially jobs entered into the virtual machine job queue; once entered into the queue, its order is final. This implies that the transaction callData cannot be validated with full virtual machine semantics, since that requires close coupling between the log and the virtual machine. One extreme design choice is to allow arbitrary messages to be logged to target the VM’s job queue, and rely on the cost of logging to deter denial-of-service attacks. This means, however, that the cost of VM execution to verify and discard ill-formed message (e.g., unsigned, unparseable, nonexistent contract entry points, etc) must be included as part of the cost of message handling. Message posting has to cost something in order to prevent denial-of-service attacks. This means some checks must already be done at the underlying blockchain: the message itself must be signed, and it must authorize payment from the EOA to minimally pay for the message posting itself, as well as a (limited) payment authorization for the VM execution (gas limit). Since signature check is effectively a sunk cost, an alternative is to perform some very simple verification of proposed transactions: • Transaction authorization: valid signature on the proposal. • EOA account has enough tokens to pay for message posting. • (Optional) EOA account has enough tokens to pay for the maximum gas payment, using an lower-bound estimate from the queue of transactions for which state finality has not been reached. The contract call parameters (callData) is just opaque bytes at this point. All signed transaction proposals with these basic checks are considered “well-formed transactions” (WFTs). Note that we do not perform contract entry point-specific type checks or other per-contract pre-condition checks at the bridge. Well-formedness does not imply that the message makes sense. WFTs that do not pass message format checks will simply be aborted with the sender charged a small gas fee: in our formalism, this means that the interpretation is that tc returns with its input state. The same thing applies for other pre-conditions: those would be checked by the contract code (e.g., the equivalent of require checks in Solidity) and similarly cause the transaction to be aborted. This conforms with the decoupled nature of the system design: the bridge contract does not know what (possibly new) contracts have been instantiated on the rollup, and doing typechecking would be impractical. Contract invocations in Ethereum-like blockchains are internally structured as essentially remote procedure calls, with a message that must be (partially) parsed to identify the intended entry point and discover the type signature, and then to further parse and typecheck the rest of the message. While it might be reasonable to say that the message encoding is architecturally fixed and performed by the rollup VM, it is feasible—as is done by Solidity for the EVM—to perform this in the contract code itself (in Solidity’s case, in the language runtime which performs the RPC dispatch). Since different contract language runtimes could, in principle, require completely different data serialization formats, performing message format verification in the bridge is infeasible without knowing details about how each contract’s RPC message receiver/demultiplexor is implemented. The simplest design is to view the bridge contract as accepting WFTs and require runtime checking for rollup-specific, contract-language specific, or contractspecific pre-conditions. The arrival order at the job queue maintained by the bridge contract does not necessarily specify the execution order. Clearly, as long as a rollup allows transaction proposers to offer variable gas fees (as opposed to a fixed market rate as a gating threshold), jobs will need to be sorted by gas price. And while using gas price as the primary key and arrival order as the secondary key might approximate a “fair” order, it allows a frontrunner to trivially creating pseudoconjugate transactions by proposing a pair of transactions at a slightly higher and slightly lower gas fee. More research is needed here, especially since implementing an approximate fair scheduler will introduce additional latency to the transaction processing. Authors: (1) Bennet Yee, Oasis Labs; (2) Dawn Song, Oasis Labs; (3) Patrick McCorry, Infura; (4) Chris Buckland, Infura. Authors: Authors: (1) Bennet Yee, Oasis Labs; (2) Dawn Song, Oasis Labs; (3) Patrick McCorry, Infura; (4) Chris Buckland, Infura. This paper is available on arxiv under ATTRIBUTION 4.0 INTERNATIONAL license. This paper is available on arxiv under ATTRIBUTION 4.0 INTERNATIONAL license. available on arxiv available on arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

Clearly

How Layer 2 Rollups Handle Data Availability and Garbage Collection Efficiently

Blockchain Consensus Mechanisms, Once and For All: PoW, PoS, and Rollups

EScholar Technologies

Too Long; Didn't Read

CTA: Download the FREE AI Productivity Shift report

The Components of an Ideal Layer 2 Rollup Design

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

Smart Cards, IPv6 Packets, and the Future of Post-Quantum Security

What Happens After You Hit ‘Send’ on Blockchain

How Blockchain Defines ‘Truth’

Making Sense of Blockchain Execution and Transaction Order

Understanding CallData in Blockchain Transaction Execution

Smart Cards, IPv6 Packets, and the Future of Post-Quantum Security

What Happens After You Hit ‘Send’ on Blockchain

How Blockchain Defines ‘Truth’

Making Sense of Blockchain Execution and Transaction Order

Understanding CallData in Blockchain Transaction Execution

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps