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. This paper is available on arxiv under ATTRIBUTION 4.0 INTERNATIONAL license. [4] Obviously the input state can be reconstructed by transaction replay, but that is not efficient. 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 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. data availability data availability layer 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. g pseudo-conjugate transaction 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. 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 [4] Obviously the input state can be reconstructed by transaction replay, but that is not efficient.

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

Ethereum

How Swap Volume and Gas Fees Impact CBDC Exchange Costs

What Happens When You Swap 1 Million Euros in CBDCs?

EScholar Technologies

Too Long; Didn't Read

CTA: Download the FREE AI Productivity Shift report

Understanding CallData in Blockchain Transaction Execution

About Author

Comments

TOPICS

THIS ARTICLE WAS FEATURED IN

Related Stories

Untitled Story

5 Ways to Measure Privacy Risks in Text Data

What Happens After You Hit ‘Send’ on Blockchain

How Blockchain Defines ‘Truth’

Making Sense of Blockchain Execution and Transaction Order

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

5 Ways to Measure Privacy Risks in Text Data

What Happens After You Hit ‘Send’ on Blockchain

How Blockchain Defines ‘Truth’

Making Sense of Blockchain Execution and Transaction Order

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

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps