TLDR
This paper (and whitepaper) describes an Optimistic rollup, an L2 scaling solution for smart contracts that recently launched on the Ethereum blockchain. The protocol uses mechanism design to incentivize an agreement off-chain on the VM execution. Malicious behavior is penalized by a loss of deposit after a challenge is resolved in a multi-round game. Any honest party can raise a dispute to correct potentially fraudulent activity in an efficient manner and advance the VM state on-chain.
Core Research Question
How do we scale blockchains with smart contracts using an off-chain solution?
Citation
[PAPER] Arbitrum: Scalable, private smart contracts. Harry Kalodner, Steven Goldfeder, Xiaoqi Chen, S. Matthew Weinberg, and Edward W. Felten, Princeton University
[WHITEPAPER] Arbitrum: Fast, Scalable, Private Smart Contracts. OFFCHAIN LABS
Links
https://www.usenix.org/conference/usenixsecurity18/presentation/kalodner
Arbitrum’s Team Ask Me Anything on Reddit
Background
Layer-2: collective term for solutions designed to help scale the transactional throughput of applications by handling transactions off the underlying blockchain (layer 1).
consensus: protocol for users (nodes) to come to an agreement on the shared history of transactions
Verifier: It describes the underlying consensus use. Arbitrum is consensus agnostic and uses the term to express that they can work with permissionless or premissionned chains.
verifiers: The term generically refers to the underlying consensus mechanism participants. For example, in the Bitcoin protocol, Bitcoin miners are the verifiers.
validators/managers: A manager [PAPER] of a VM is a party that monitors the progress of a particular VM and ensures the VM’s correct behavior. When a VM is created, the transaction that creates the VM specifies a set of managers for the VM. A manager is identified by its public key. [WHITEPAPER] uses the term validators.
VM: Taking the blockchain as an operating system, Arbitrum uses VM to refer to smart contracts/Dapps.
The Arbitrum compiler [WHITEPAPER] takes a group of contracts written in Solidity, compiles and links them together into a single executable file that can run on the Arbitrum Virtual Machine (AVM) architecture.
Ethbridge: Dapp running on Ethereum. Its job is to serve as a bridge between Ethereum and Arbitrum. Anyone in Ethereum-land can call the EthBridge to interact with Arbitrum-land, for example to launch an Arbitrum VM, to make a call to a contract running on Arbitrum, or to send ether or any token to an Arbitrum VM. The EthBridge’s other important job is to referee disputes between validators.
AnyTrust guarantee: Arbitrum guarantees correct execution as long as any one validator of a Dapp acts honestly. Most other approaches require majority-honest or two-thirds-honest assumptions, or else require moving the entire state of a contract to the main chain in case of a dispute.
bisection protocol: the dispute resolution protocol of Arbitrum between two validators, a challenger and an asserter, with the L1 as referee.
Summary
-
Why scaling is hard
- Verifier dilemma: The problem is the high cost of verifying VM execution. Either verifiers end up accepting the transactions without verifying them because they expect everyone will do the same or others will do the hard work in their stead. Or they honestly verify the incoming transactions which make them vulnerable to time-consuming computation that can slow them in the block producing race.
- participation game: A mechanism design approach that aims to induce a limited but sufficient number of parties to verify each VM’s execution. These systems face the Participation Dilemma, of how to prevent Sybil attacks in which a single verifier claims to be multiple verifiers, and in doing so can drive other verifiers out of the system. Prior works to Arbitrum fail to resolve this problem since smart contract verification is a repeated game and in those, there are numerous other equilibria that do not project onto Nash equilibria of their one-shot variants. For example, the case where only one player participates is a Nash-equilibrium.
- Arbitrum: An L2 protocol in the Optimistic Rollup family to improve scaling on an L1 blockchain like Ethereum.
- In Arbitrum, parties can implement a smart contract by instantiating a Virtual Machine (VM) that encodes the rules of a contract. The creator of a VM designates a set of validators for the VM.
- The Arbitrum protocol provides an AnyTrust guarantee: Any honest validator can force the VM to behave according to the VM’s code. Parties that are interested in the VM’s outcome can serve as validators themselves or appoint someone they trust to manage the VM on their behalf. Parties can send messages and currency to a VM, and a VM can send messages and currency to other VMs or other parties. VMs may take actions based on the messages they receive. The Verifier also tracks the hash of the VM’s inbox. Arbitrum also allows contracts to execute privately, publishing only contract states.
- Relying on validators, rather than requiring every verifier (here, miners) to emulate every VM’s execution, allows a VM’s validators to advance the VM’s state at a much lower cost to the verifiers. Verifiers track only the hash of the VM’s state, rather than the full state. Arbitrum creates incentives for the validators to agree on what the VM will do off-chain. Any state change that is endorsed by all of the validators will be accepted by the verifiers.
- If, contrary to incentives, two validators disagree about what the VM will do, the verifiers employ a bisection protocol to narrow the disagreement down to the execution of a single instruction, and then one manager submits a simple proof of that one-instruction execution which the verifiers can check very efficiently. The liar must then pay a substantial financial penalty to the verifiers, which serves to deter disagreements.
-
The Arbitrum VM has been designed to make checking one-step proofs fast and simple. In particular, the VM design guarantees that the space to represent a one-step proof and the time to generate and verify such a proof are bounded by small constants, independent of the size and contents of the program’s code and data.
-
Assumptions: It is assumed that users will only pay attention to a VM if they agree that the VM was initialized correctly and have some stake in its correct execution. By Arbitrum’s Anyrust assumption, parties should only rely on the correct behavior of a VM if they trust at least one of the VM’s managers. One way to have a validator you trust is to serve as a manager yourself.
-
One key assumption that Arbitrum makes is that a validator will be able to send a challenge or response to the Verifier within the specified time window. In a blockchain setting, this means the ability to get a transaction included in the blockchain within that time. While critical, this assumption is standard in cryptocurrencies, and risk can be mitigated by extending the challenge interval (which is a configurable parameter of each VM).
-
Two factors help alleviate denial of service (DoS) attacks against honest validators. First, if a DoS attacker cannot be certain of preventing an honest validator from submitting a challenge, the risk of incurring a penalty may still be enough to deter a false assertion. Second, because each manager is only identified by a public key, a validator can use replication to improve its availability, including the use of “undercover” replicas whose existence or location is not known to the attacker in advance. Lastly, a motivated malicious manager can indefinitely stall a VM by continuously challenging all assertions about its behavior. The attacker will lose at least half of every deposit, and each such loss will delay the progress of the VM only for the time required to run the bisection. We assume that the creators of a VM will set the deposit amount for the VM to be large enough to deter this attack.
Method
- VM lifecycle:
- The Arbitrum protocol recognizes two kinds of actors: (public) keys and VMs. An actor is deemed to have taken an action if it is signed by the corresponding private key.
- An Arbitrum VM is created using a special transaction, which specifies the initial state hash of the VM, a list of validators for the VM, and parameters such as the length of the challenge period. The state hash represents a cryptographic commitment to the VM’s state.
- Once a VM has been created, validators can take action to cause that VM’s state to change. The Arbitrum protocol provides an AnyTrust guarantee: any one honest validator can force a VM’s state change to be consistent with the VM’s code and state, that is, to be a valid execution according to the AVM Specification.
- An assertion states that if certain preconditions hold, the VM’s state will change in a certain way. An assertion about a VM is said to be eligible if the assertion’s preconditions hold, the VM is not in a halted state, and the assertion does not spend more funds than the VM owns. The assertion contains the hash of the VM’s new state and a set of actions taken by the VM, such as sending messages or currency. Note that for each VM, the Verifier tracks the hashed state of that VM, along with the amount of currency held by the VM, and a hash of its inbox.
Unanimous assertions are signed by all validators of that VM. If a unanimous assertion is eligible, it is immediately accepted by the Verifier as the new state of the VM.
Disputable assertions are signed by only a single validator, and that validator attaches a currency deposit to the assertion. If a disputable assertion is eligible, the assertion is published by the Verifier as pending. If a timeout period passes without any other validator challenging the pending assertion, the assertion is accepted by the Verifier and the asserter gets their deposit back. If another validator challenges the pending assertion, the challenger puts down a deposit, and the two validators engage in the bisection protocol, which determines which of them is lying. The liar will lose their deposit.
- Bisection protocol: If a validator challenges an assertion, the challenger must put their deposit in escrow. The asserter and the challenger engage in a game, via a public protocol, to determine who is correct. The party who wins the game will recover their deposit, and will take half of the losing party’s. The other half of the loser’s deposit will go to the Verifier, as compensation for the work required to referee the game.
The game is played in alternating steps. After a challenge is registered, the asserter is given a pre-specified time interval to bisect its previous assertion. If the previous assertion involves N steps of execution in the VM, then the two new assertions must involve \lfloor N/2 \rfloor and \lceil N/2\rceil steps, respectively, and the two assertions must combine to be equivalent to the previous assertion. If no valid bisection is offered within the time limit, the challenger wins the game. After a bisection is offered, the challenger must challenge one of the two new assertions, within a pre-specified time interval. The two players alternate moves. At each step, a player must move within a specified time interval, or lose the game.
After a logarithmic number of bisections, the challenger will challenge an assertion that covers a single step of execution. At this point the asserter must offer a one-step proof, which establishes that in the asserted initial state, and assuming the preconditions, executing a single instruction in the VM will reach the asserted final state and take the asserted publicly visible actions, if any. This one-step proof is verified by the Verifier. See Figures.
Description of the Bisection Protocol from [PAPER]
- The VM uses a stack-based architecture. Its state is organized hierarchically. This allows a hash of a VM’s state to be computed in Merkle Tree fashion, and to be updated incrementally. The VM architecture ensures that instructions can only modify items near the root of the state tree and that each node of the state tree has a maximum degree of eight.
- The state of a VM contains the following elements:
- an instruction stack, which encodes the current program counter and instructions;
- a data stack of values;
- a call stack, used to store the return information for procedure calls;
- a static constant, which is immutable; and
- a single mutable register which holds one value.
- Instruction Stack: Arbitrum maintains an “instruction stack” which holds the instructions in the remainder of the program. To advance, the Arbitrum VM pops the instruction stack to get the next instruction to execute, halting if that stack is empty. Jump and procedure call instructions change the instruction stack, with procedure call storing the old instruction stack (pushing a copy of the instruction stack onto the call stack) so that it can be restored on procedure return. This approach allows a one-step proof to use constant space and allows verification of the current instruction and the next instruction stack value in constant time.
- A VM interacts with other parties by sending and receiving messages. A message consists of a value, an amount of currency, and the identity of the sender and receiver.
- Preconditions, Assertions, and One-Step Proofs: Each assertion is accompanied by a set of preconditions consisting of a hash of the VM’s state before the asserted execution, a hash of the VM’s inbox contents, an optional lower bound on the VM’s currency balance, and optional lower and upper bounds on the time (measured in block height). An assertion will be ignored as ineligible unless all of its preconditions hold. Still, parties may choose to store an ineligible assertion in the hope that it becomes eligible later.
- In addition to preconditions, an assertion contains the following components: the hash of the machine state after the execution, the number of instructions executed, and the sequence of messages emitted by the VM.
- A one-step proof, which is a proof of correctness, assuming a set of preconditions, for an assertion covering the execution of a single instruction. It must provide enough information, beyond the preconditions, to enable the Verifier to emulate the single instruction that will be executed.
- Because the state of the VM is organized as a Merkle Tree, whose root hash is given as a precondition, the proof only needs to expand out enough of the initial state Merkle tree to enable the Verifier to emulate the execution of the single instruction. It verifies that the result matches the claimed assertion.
- Messages are sent to a VM by users (with their keys) by putting a special message delivery transaction on the blockchain; and by other VMs using the
send
instruction. A message logically has four fields: data (an AVM value), a non-negative amount of currency and the identities of the sender and receiver of the message. - A VM’s validators track the state of its inbox, but the Verifier need only track the inbox’s hash, because that is all that will be needed to verify a one-step proof of the VM receiving the inbox contents.
Results
Scalability. This is the key feature of Arbitrum. Validators can execute a VM indefinitely, paying only negligible transaction fees that are small and independent of the complexity of the code they are running. If participants follow incentives, all assertions should be unanimous and disputes should never occur,but even if a dispute does occur, the Verifier can efficiently resolve it at little cost to honest parties (but substantial cost to a dishonest party).
AnyTrust Guarantee. Arbitrum guarantees correct execution as long as any one validator of a dapp acts honestly—even if all of the other validators collude to (try to) cheat.
Privacy. Arbitrum’s model is well-suited for private smart contracts. Absent a dispute, no internal state of a VM is revealed to the Verifier. Further, disputes should not occur if all parties execute the protocol according to their incentives. Even in the case of a dispute, the Verifier is only given information about a single step of the machine’s execution but the vast majority of the machine’s state remains opaque to the Verifier.
Interoperability. Arbitrum is interoperable with Ethereum. A Dapp written in Solidity can be compiled using the open source Arbitrum compiler to generate Arbitrum-ready code. Users can also transfer Ether or any other Ethereum-based token back and forth between Ethereum and Arbitrum.
Flexibility. Unanimous assertions provide a great deal of flexibility as validators can choose to reset a machine to any state that they wish and take any actions that they want – even if they are invalid by the machine’s code. This requires unanimous agreement by the managers, so if any one manager is honest, this will only be done when the result is one that an honest validator would accept–such as winding down a VM that has gotten into a bad state due to a software bug.
Discussion and Key Takeaways
Arbitrum is a L2 protocol that aims to fix many issues on L1, specifically on Ethereum. As it is today, Ethereum cannot scale because requiring miners to emulate every smart contract is expensive, and this work must be duplicated by every miner. It has no privacy which then has to come as an overlay. Solutions based on Zero Knowledge could help but they are expensive to run so the throughput would be limited to a few transactions per block. Finally there is an inflexibility of Ethereum-style smart contracts since deviation from the code is not possible. This is possible in Arbitrum as long as all of the VM’s honest managers agree to it.
By making disputes relatively cheap to resolve, and imposing a substantial penalty on the loser, Arbitrum strongly disincentivizes attempts to cheat. Even if a dispute occurs this doesn’t impose a huge on-chain impact. In the common case, validators will agree and progress will occur off-chain, with only occasional touches to the main chain.
To demonstrate Arbitrum’s efficiency, the authors measured the throughput of an Arbitrum VM which performs iterative SHA-256 hashing. They evaluated its performance on an early 2013 Apple MacBook Pro, 2.7GHz Intel Core i7. They were able to attain 970,000 hashes per second. Comparatively, using native code on the same machine, they made 1,700,000 hashes per second, while Ethereum is only capable of processing approximately 1600 hashes per second due to its gas limit.
Arbitrum’s performance advantage extends further. The Verifier is capable of handling large
numbers of VMs simultaneously. Instantiating many copies of the Iterated Hashing VM, the authors measured that the Verifier node running on the test machine was capable of processing over 5000 disputable assertions per second. This brings the total possible network throughput up to over 4 billion hashes per second, compared to 1600 for
Ethereum.
Implications and Follow-ups
Extensions
- Zero Knowledge: Arbitrum provides privacy as long as none of the validators reveal the offchain data. If there is a challenge, they still have to reveal a small portion of the state (such as during the bisection protocol) which can contain sensitive information. The authors propose using a zero knowledge protocol to implement the one step proof. While zero-knowledge proofs could in theory be used to prove the correctness of the entire state transition (and not just a single step), doing this for complex computations was not feasible with the tools available at that time.
- Reading the base chain: As described, Arbitrum VMs do not have the ability to directly read the underlying blockchain. This could be easily solved by extending the VM instruction set to allow a VM to read the blockchain directly. To do so, the authors would create a canonical encoding of a block as an Arbitrum tuple, with one field of that tuple containing the tuple representing the previous block in the blockchain. This would allow a VM that had the tuple for the current block to read earlier blocks. The precondition of an assertion would thus specify a recent block height, and the VM would have a special instruction that pushes the associated block tuple to the stack. In order to be able to verify a one-step proof of this instruction, the Verifier just needs to keep track of the Arbitrum tuple hash of each block.
- Arbitrum VM enables the use of different Virtual Machines other than the Ethereum Virtual Machine. This will help support bigger smart contracts and also multi-language supports like C/C++, Python, Go and Rust. This in turn might help with the adoption of ZK-rollups where developers have to write applications in special purpose and new languages.
Applicability
After 3 years of development, Arbitrum was finally released on Ethereum’s mainnet.