Page 1 of 19Free preview · 1–5

About this document

This paper, published in the proceedings of the 27th USENIX Security Symposium in 2018, presents Arbitrum, a consensus-agnostic system for scalable, private smart contracts. Contract managers agree on virtual-machine execution off-chain, while verifiers track commitments and resolve disagreements through a bisection protocol ending in a one-instruction proof. Correct execution relies on at least one honest manager and timely access to the verifier. The paper describes the protocol and virtual-machine architecture, evaluates a Go prototype, and analyzes Sybil-related weaknesses in repeated participation games used to incentivize verification. It also discusses privacy limitations and proposed zero-knowledge extensions.

Free preview text

The first 5 pages, shown as text so search engines and readers can find this document.

Page 1

Open access to the Proceedings of the 27th USENIX Security Symposium is sponsored by USENIX.Arbitrum: Scalable, private smart contracts Harry Kalodner, Steven Goldfeder, Xiaoqi Chen, S. Matthew Weinberg, and Edward W. Felten, Princeton University https://www.usenix.org/conference/usenixsecurity18/presentation/kalodner This paper is included in the Proceedings of the 27th USENIX Security Symposium. August 15–17, 2018 • Baltimore, MD, USA 978-1-939133-04-5

Page 2

Arbitrum: Scalable, private smart contracts Harry Kalodner Princeton University Steven Goldfeder Princeton University Xiaoqi Chen Princeton University S. Matthew Weinberg Princeton University Edward W. Felten Princeton University Abstract We present Arbitrum, a cryptocurrency system that sup- ports smart contracts without the limitations of scala- bility and privacy of systems previous systems such as Ethereum. Arbitrum, like Ethereum, allows parties to create smart contracts by using code to specify the be- havior of a virtual machine (VM) that implements the contract’s functionality. Arbitrum uses mechanism de- sign to incentivize parties to agree off-chain on what a VM would do, so that the Arbitrum miners need only ver- ify digital signatures to confirm that parties have agreed on a VM’s behavior. In the event that the parties can- not reach unanimous agreement off-chain, Arbitrum still allows honest parties to advance the VM state on-chain. If a party tries to lie about a VM’s behavior, the veri- fier (or miners) will identify and penalize the dishonest party by using a highly-efficient challenge-based proto- col that exploits features of the Arbitrum virtual machine architecture. Moving the verification of VMs’ behavior off-chain in this way provides dramatic improvements in scalability and privacy. We describe Arbitrum’s protocol and virtual machine architecture, and we present a work- ing prototype implementation. 1 Introduction The combination of digital currencies and smart con- tracts is a natural marriage. Cryptocurrencies allow par- ties to transfer digital currency directly, relying on dis- tributed protocols, cryptography, and incentives to en- force basic rules. Smart contracts allow parties to cre- ate virtual trusted third parties that will behave according to arbitrary agreed-upon rules, allowing the creation of complex multi-way protocols with very low counterparty risk. By running smart contracts on top of a cryptocur- rency, one can encode monetary conditions and penalties inside the contract, and these will be enforced by the un- derlying consensus mechanism. Ethereum [31] was the first cryptocurrency to support Turing-complete stateful smart contracts, but it suffers from limits on scalability and privacy. Ethereum requires every miner to emulate every step of execution of every contract, which is expensive and severely limits scalabil- ity. It also requires the code and data of every contract to be public, absent some type of privacy overlay feature which would impose costs of its own. 1.1 Arbitrum We present the design and implementation of Arbitrum, a new approach to smart contracts which addresses these shortcomings. Arbitrum contracts are very cheap for ver- ifiers to manage. (As explained below, we use the term verifiers generically to refer to the underlying consensus mechanism. For example, in the Bitcoin protocol, Bit- coin miners are the verifiers.) If parties behave according to incentives, Arbitrum verifiers need only verify a few digital signatures for each contract. Even if parties be- have counter to their incentives, Arbitrum verifiers can efficiently adjudicate disputes about contract behavior without needing to examine the execution of more than one instruction by the contract. Arbitrum also allows contracts to execute privately, publishing only (saltable) hashes of contract states. In Arbitrum, parties can implement a smart contract as a Virtual Machine (VM) that encodes the rules of a con- tract. The creator of a VM designates a set of managers for the VM. The Arbitrum protocol provides an any-trust guarantee: any one honest manager can force the VM to behave according to the VM’s code. The parties that are interested in the VM’s outcome can themselves serve as managers or appoint someone they trust to manage the VM on their behalf. For many contracts, the natural set of managers will be quite small in practice. Relying on managers, rather than requiring every ver- ifier to emulate every VM’s execution, allows a VM’s managers to advance the VM’s state at a much lower cost USENIX Association 27th USENIX Security Symposium 1353

Page 3

to the verifiers. Verifiers track only the hash of the VM’s state, rather than the full state. Arbitrum creates incen- tives for the managers to agree out-of-band on what the VM will do. Any state change that is endorsed by all of the managers (and does not overspend the VM’s funds) will be accepted by the verifiers. If, contrary to incen- tives, two managers disagree about what the VM will do, the verifiers employ a bisection protocol to narrow the disagreement down to the execution of a single instruc- tion, and then one manager submits a simple proof of that one-instruction execution which the verifiers can check very efficiently. The manager who was wrong pays a substantial financial penalty to the verifiers, which serves to deter disagreements. Parties can send messages and currency to a VM, and a VM can itself send messages and currency to other VMs or other parties. VMs may take actions based on the mes- sages they receive. The Verifier tracks the hash of the VM’s inbox. The architecture of the Arbitrum VM and protocol are designed to make the task of resolving disputes as fast and simple for the verifiers as possible. Details of the design appear later in the paper. Arbitrum dramatically reduces the cost of smart con- tracts. If participants behave according to their incen- tives, then verifiers will never have to emulate or verify the behavior of any VM. The only responsibility of ver- ifiers in this case is to do simple bookkeeping to track the currency holdings, the hash of a message inbox, and a single hashed state value for each VM. If a participant behaves irrationally, it may require the verifiers to do a modest amount of extra work, but the verifiers will be (over-)compensated for this work at the expense of the irrational party. As a corollary of the previous principle, Arbitrum VMs can be private, in the sense that a VM can be created and execute to completion without revealing the VM’s code or its execution except for the content and timing of the messages and payments it sends, and (saltable) hashes of its state. Any manager of a VM will neces- sarily have the ability to reveal information about that VM, but if managers want to maintain a VM’s privacy they can do so. Arbitrum is consensus-agnostic, meaning that it as- sumes the existence of a consensus mechanism that publishes transactions, but the Arbitrum design works equally well with any consensus mechanism, including a single centralized publisher, a quorum-based consensus system, or Nakamoto consensus as used in Bitcoin [26]. Additionally, an existing smart contract system can serve as this consensus mechanism assuming it can encode Ar- bitrum’s rules as a smart contract. In this paper, we refer to the consensus entity or system as the Verifier (and the participants in the said consensus system as the verifiers). 1.2 Structure of the paper The remainder of the paper is structured as follows. In section 2 we discuss the difficulties of implementing smart contracts efficiently, and we present the Participa- tion Dilemma, a new theoretical result on participation games showing that one approach to incentivize smart contract verification may not work. In section 3 we de- scribe Arbitrum’s approach, and in section 4 we provide more details of Arbitrum’s protocol and virtual machine architecture, which together allow much more efficient and privacy-friendly verification of the operations of vir- tual machines implementing smart contracts. Section 5 describes our implementation of Arbitrum and provides some benchmarks of performance and the sizes of proofs and blockchain transactions. Section 6 surveys related work, and section 7 concludes the paper. 2 Why Scaling Smart Contracts is Difficult Supporting smart contracts in a general and efficient way is a difficult problem. In this section we survey the draw- backs of some existing approaches. 2.1 The Verifier’s Dilemma The most obvious way to implement smart contract VMs is to have every miner in a cryptocurrency system emu- late every step of execution of every VM. This has the advantage of simplicity, but it imposes severe limits on scalability. The high cost of verifying VM execution may mani- fest as the Verifier’s Dilemma [22]. Because transactions involving code execution by a VM are expensive to ver- ify, a party that is supposed to verify these transactions has an incentive to free-ride by accepting the transactions without verifying them, in the hope that either (1) misbe- havior is deterred by other parties’ doing verification, or (2) any discrepancies will not be detected by other po- tential verifiers because they also do not perform verifi- cation. This can lead to an equilibrium in which some transactions are accepted with little or no verification. Conversely, in a scenario in which all miners are hon- estly doing the verification, a miner can exploit this by including a time-consuming computation that will take the other miners a significant amount of time to verify. While all of the other miners are doing the verification, the miner that included this computationally heavy trans- action can get a head-start on mining the next block, giv- ing it a disproportionate chance of collecting the next block reward. This dilemma exists because of the high cost of verifying VM execution. 1354 27th USENIX Security Symposium USENIX Association

Page 4

2.2 The Participation Dilemma One approach to scaling verification (as used in, e.g., TrueBit [30]) relies on participation games, a mecha- nism design approach that aims to induce a limited but sufficient number of parties to verify each VM’s execu- tion. These systems face what we call the Participation Dilemma, of how to prevent Sybil attacks in which a sin- gle verifier, who may or may not be honest, claims to be multiple verifiers, and in doing so can drive other veri- fiers out of the system. 2.3 Participation Games In this section we prove new formal barriers to ap- proaches based on participation games. The idea is that players will “participate” in a costly process. Consider the following game: • There are n players, who may pay 1 to participate. • Participating player i chooses a number of Sybils si ≥ 1. Non-participating players set si = 0. • Player i receives reward si · f (∑ j s j), where f : N → R+ is a reward function. In the context of this paper, think of participating as “verifying a computation.” It costs something to ver- ify the computation, but once you’ve verified it, you can claim to have verified it from any number of additional Sybils for free, and these Sybils are indistinguishable from “real” verifiers. The goal would then be to design a participation game (i.e. a reward function f (·)) such that in equilibrium, no player has any incentive to Sybil, and a desired number of players participate, so that the apparent number of verifiers equals the actual number of separate players who were verifiers. The authors of TrueBit correctly observe that the fam- ily of functions fc(m) = c · 2−m make great candidates for participation games. Specifically, for any target k of participating players, the participation game with re- ward function f (m) = (2k + 0.5) · 2−m has a unique (up to symmetry) pure Nash equilibrium where every player has si ∈ {0, 1}, and exactly k players participate. In fact, an even stronger property holds: it is always a best re- sponse for any player to set si ≤ 1!1 We call such reward functions One-Shot Sybil-Proof (formal definition in Ap- pendix A). This initially makes participation games seem like a promising avenue for verifiable smart contracts, as One-Shot Sybil-proof reward functions exist. However, a problem that prior work fails to resolve is that smart contract verification is a repeated game. In repeated games, there are numerous other equilibria that 1That is, no matter what the other players do, player i is strictly happier to set si = 1 than si > 1. don’t project onto Nash equilibria of their one-shot vari- ants. For intuition, recall the classic prisoner’s dilemma:2 if the game is only played once, then the unique Nash equilibrium is for both players to defect (and defecting is even a strictly dominant strategy). However, in the repeated prisoner’s dilemma, there are numerous other equilibria including the famous Tit-For-Tat, and Grim Trigger strategies [29]. We discuss the formal model for repeated games (which is standard, but not the focus of this paper) in Appendix A. But the point is that repeated games allow for players to sacrifice the present in order to save for the future. For example, the following is an equilibrium of the repeated participation game with f (m) = (4.5) · 2−m. Player one uses the strategy: set s1 = 2 in all rounds. Player i > 2 sets si = 0 in all rounds. Player 2 uses the strategy: if in either of the previous two rounds, ∑ j6 =2 s j ≤ 1, set s2 = 1. Otherwise, set s2 = 0. Note that all players aside from player 1 are certainly best responding. They currently get utility zero (because player 1 sets s1 = 2 every round, and they therefore all set si = 0). If they instead participated in any round, they would get negative utility. Player 1 on the other hand, is also best responding! This is because if they decreased their number of Sybils in any round, it would cause player 2 to participate in the next two rounds (for- mal proof in appendix). Note that this equilibrium is not at all unnatural: play- ers > 1 are simply reacting to what the market looked like in the previous rounds. Player 1 is staying one step ahead of the game and realizing that no matter what, there are going to be two participants in equilibrium, so player 1 might as well be all of them rather than share the reward. In fact, this is not a property specific to the reward function c · 2i, but any reward function. Theorem 1. Every One-Shot Sybil-Proof participation game admits a Nash equilibrium where only one player participates. In Appendix A, we provide a proof of Theorem 1, as well as a discussion of possible outside-the-box defenses. These defenses seem technically challenging (perhaps impossible) to implement, but we are are not claiming this provably. However, simulations do indicate that the cost to implement these defenses scales linearly with the computational power of a single player, which may ren- der them impractical (if they are indeed even possible). As a result, approaches based on this type of partici- pation game, including those proposed in prior work [30, 32], appear to be unable to prevent Sybil attacks that un- dermine confidence in the verification of smart contracts. 2There are two players. Both get payoff 1 if they both defect, and payoff 2 if they both cooperate. If one cooperates and the other defects, the defector gets 4 and the cooperator gets 0. USENIX Association 27th USENIX Security Symposium 1355

Page 5

3 Arbitrum System Overview In this section we give an overview of the design of Ar- bitrum. 3.1 Roles There are four types of roles in the Arbitrum protocol and system. The Verifier is the global entity or distributed proto- col that verifies the validity of transactions and publishes accepted transactions. The Verifier might be a central en- tity or a distributed multiparty consensus system such as a distributed quorum system, a worldwide collection of miners as in the Nakamoto consensus protocol [26], or itself a smart contract on an existing cryptocurrency. Be- cause the Arbitrum design is agnostic as to which type of consensus system is used, for brevity we use the singular term Verifier for whatever consensus system is operating. A key is a participant in the protocol that can own cur- rency and propose transactions. A key is identified by (the hash of) a public key. It can propose transactions by signing them with the corresponding private key. A VM (Virtual Machine) is a virtual participant in the protocol. Every VM has code and data that define its behavior, according to the Arbitrum Virtual Machine (AVM) Specification,which is included in the extended version of this paper. Like keys, VMs can own currency and send and receive currency and messages. A VM is created by a special transaction type. A manager of a VM is a party that monitors the progress of a particular VM and ensures the VM’s cor- rect 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 (the hash of) its public key. 3.2 Lifecycle of a VM An Arbitrum VM is created using a special transaction, which specifies the initial state hash of the VM, a list of managers for the VM, and some parameters. As de- scribed below, the state hash represents a cryptographic commitment to the VM’s state (i.e., its code and initial data). Any number of VMs can exist at the same time, typically with different managers. Once a VM is created, managers can take action to cause that VM’s state to change. The Arbitrum protocol provides an any-trust guarantee: any one honest manager can force the VM’s state changes 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 (1) the assertion’s preconditions hold, (2) the VM is not in a halted state, and (3) 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. Unanimous assertions are signed by all managers of that VM. If a unanimous assertion is eligible, it is imme- diately accepted by the Verifier as the new state of the VM. Disputable assertions are signed by only a single man- ager, and that manager attaches a currency deposit to the assertion. If a disputable assertion is eligible, the asser- tion is published by the Verifier as pending. If a time- out period passes without any other manager challenging the pending assertion, the assertion is accepted by the Verifier and the asserter gets its deposit back. If another manager challenges the pending assertion, the challenger puts down a currency deposit, and the two managers en- gage in the bisection protocol, which determines which of them is lying. The liar will lose its deposit. A VM continues to advance its state as described above, until the VM reaches a halted state. At this point no further state changes are possible, and the Verifier and managers can forget about the VM. 3.3 The Bisection Protocol The bisection protocol begins when a manager has made a disputable assertion and another manager has chal- lenged that assertion. Both managers will have put down a currency deposit. At each step of the bisection protocol, the asserter bi- sects the assertion into two assertions, each involving half as many steps of computation by the VM, and the challenger chooses which half it would like to challenge. They continue this bisection protocol until an assertion about a single step (i.e., the execution of one instruc- tion by the VM) is challenged, at which point the asserter must provide a one-step proof that the Verifier can check. The asserter wins if they provide a correct proof; other- wise the challenger wins. The winner gets their deposit back and also takes half of the loser’s deposit. The other half of the loser’s deposit goes to the Verifier. The bisection protocol is carried out via a series of blockchain transactions made by the asserter and chal- lenger. At each point in the protocol a party has a lim- ited time interval to make their next move, and that party loses if they fail to make a valid move by the deadline. The Verifier only needs to check the facial validity of the moves, for example, checking that a bisection of an as- sertion into two half-sized assertions is valid in the sense that the two resulting assertions do indeed compose to yield the original assertion. 1356 27th USENIX Security Symposium USENIX Association

Tags

Doxxly editorial guide

Arbitrum: Scalable, private smart contracts: summary, contents and background

This guide helps you understand the scope of Arbitrum: Scalable, private smart contracts before or alongside reading the original document. It is based on the catalogue record, credited creator, source, classification and topics shown on this page. It does not replace the original work and does not invent claims about passages that Doxxly cannot verify.

Summary and overview

Arbitrum: Scalable, private smart contracts is a 19-page documentcredited to Quill N. Northcote. This paper, published in the proceedings of the 27th USENIX Security Symposium in 2018, presents Arbitrum, a consensus-agnostic system for scalable, private smart contracts. Contract managers agree on virtual-machine execution off-chain, while verifiers track commitments and resolve disagreements through a bisection protocol ending in a one-instruction proof. Correct execution relies on at least one honest manager and timely access to the verifier. The paper describes the protocol and virtual-machine architecture, evaluates a Go prototype, and analyzes Sybil-related weaknesses in repeated participation games used to incentivize verification. It also discusses privacy limitations and proposed zero-knowledge extensions. It appears in the Technology & Security collection, which groups it with other material that readers may use for comparison and further study.

The item can be approached in several ways. A reader looking for a quick orientation can begin with the free five-page preview, inspect the page structure and use the metadata to judge relevance. Someone undertaking deeper research can work through the complete file, search its indexed text, record useful page references and compare its treatment of Arbitrum, Smart contracts, Blockchain scalability, Privacy, Virtual machines, Mechanism design, Sybil attacks, USENIX Security 2018 with the related resources linked below.

Rather than reducing the work to a single claim, this page treats it as a source that should be read in context. The title, creator, publication source, licence and format all help explain what kind of evidence it may offer. Readers should distinguish the original author's statements from Doxxly's catalogue description, and should cite the original edition when using the material in academic, professional or published work.

Key topics and reader takeaways

The catalogue connects this document with Arbitrum, Smart contracts, Blockchain scalability, Privacy, Virtual machines, Mechanism design, Sybil attacks, USENIX Security 2018. These terms offer practical entry points rather than a substitute for close reading. Start by identifying the definitions, examples, arguments, tables or visual explanations attached to each topic. Then note where the creator draws connections, makes distinctions or moves from background material to a conclusion, recommendation, calculation or narrative development.

A useful reading method is to separate description from interpretation. First record what the item actually presents: names, headings, figures, formulas, quotations or stated propositions. Next consider why those details matter within the whole work. Finally compare them with another source from the same subject area. This process helps turn a long digital file into evidence that can be evaluated rather than merely skimmed.

Table of contents and reading guide

The following is an editorial content guide based on the verified catalogue topics. It is not represented as the original author's formal table of contents. Use it to organise notes while moving through the 19 pages in the player.

  1. Part 1

    Arbitrum

    Use this section of the reading guide to identify how Arbitrum appears in Arbitrum: Scalable, private smart contracts, note important terms, and connect the subject to the wider purpose of the work.

  2. Part 2

    Smart contracts

    Use this section of the reading guide to identify how Smart contracts appears in Arbitrum: Scalable, private smart contracts, note important terms, and connect the subject to the wider purpose of the work.

  3. Part 3

    Blockchain scalability

    Use this section of the reading guide to identify how Blockchain scalability appears in Arbitrum: Scalable, private smart contracts, note important terms, and connect the subject to the wider purpose of the work.

  4. Part 4

    Privacy

    Use this section of the reading guide to identify how Privacy appears in Arbitrum: Scalable, private smart contracts, note important terms, and connect the subject to the wider purpose of the work.

  5. Part 5

    Virtual machines

    Use this section of the reading guide to identify how Virtual machines appears in Arbitrum: Scalable, private smart contracts, note important terms, and connect the subject to the wider purpose of the work.

  6. Part 6

    Mechanism design

    Use this section of the reading guide to identify how Mechanism design appears in Arbitrum: Scalable, private smart contracts, note important terms, and connect the subject to the wider purpose of the work.

  7. Part 7

    Sybil attacks

    Use this section of the reading guide to identify how Sybil attacks appears in Arbitrum: Scalable, private smart contracts, note important terms, and connect the subject to the wider purpose of the work.

  8. Part 8

    USENIX Security 2018

    Use this section of the reading guide to identify how USENIX Security 2018 appears in Arbitrum: Scalable, private smart contracts, note important terms, and connect the subject to the wider purpose of the work.

When a heading in the original differs from this guide, follow the original heading in your citation. Page numbers can also vary between editions. Doxxly's direct page field is useful for navigation, but formal references should include the title, creator, source and edition details available in the file itself.

About Quill N. Northcote

Doxxly credits Quill N. Northcote as the author or creator of Arbitrum: Scalable, private smart contracts. This page does not add an unverified biography, job title or institutional affiliation. The attribution is preserved so readers can distinguish the creator from the hosting library and follow the original record when an external author link is available.

Author context matters because a work reflects a particular purpose, audience and point of view. Before relying on the material, consider what the creator set out to explain, when the source was produced and whether later research or revised guidance should also be consulted. For literature and philosophy, compare translations and editions; for technical material, check whether a newer version has superseded the one shown here.

About the source organisation

The recorded source for this item is usenix.org. Doxxly provides access and discovery tools but does not claim to be the original publisher unless explicitly stated. Source links, creator attribution and the recorded Publicly available file collected for editorial review licence are displayed to help readers assess provenance and permitted use.

Provenance is especially important for reports, standards, presentations and working spreadsheets. Check the original source for amendments, supporting files and current policy. A trustworthy research workflow keeps the source URL with any notes or downloaded copy, verifies important figures against the original, and avoids treating an archived document as automatically current.

Visit usenix.org

How to read and use this document

Begin with the title and opening pages, then use the guide above to decide whether to read sequentially or move to a particular topic. The Doxxly player provides previous and next navigation, a direct page field, zoom steps, fit-to-width and fit-to-page modes, rotation and fullscreen. These controls are useful when a page contains small type, a wide table, an image, a scanned layout or a dense sequence of notes.

The first five pages are open to every visitor. A plan unlocks the complete item and full-document search. Search is best used for distinctive names, technical terms or short phrases; broad words can produce too many possible contexts. When you find a useful passage, read the surrounding pages so that a sentence, chart or formula is not separated from its explanation.

If downloading is enabled, members can obtain the original PDF file. Keep the original format when formulas, slide sequencing, pagination or layout carries meaning. Respect the Publicly available file collected for editorial review terms displayed on this page, and use the rights-report link if you believe the attribution or availability needs review.

Research questions to consider

As you read Arbitrum: Scalable, private smart contracts, ask which audience the creator addresses, what problem or idea organises the work, what evidence is presented, and which assumptions remain unstated. Note whether important terms are defined consistently and whether examples represent a broader pattern or a narrow case. For quantitative material, record units, time periods, formulas and data sources. For interpretive material, separate the creator's language from your own summary.

A second set of questions concerns relevance today. Which parts remain durable, which depend on their historical or institutional setting, and what would need confirmation from a newer source? Following the tags and the Technology & Security collection can reveal useful comparisons. Agreement between sources can strengthen confidence, while disagreement can point to changing definitions, methods, evidence or priorities.

Finally, decide what you need from the item: background knowledge, a quotation, a worked example, a model, a visual explanation or a starting bibliography. That purpose should guide the depth of reading and the notes you keep. Doxxly helps locate and navigate the source; careful interpretation remains the reader's responsibility.

Explore more Technology & Security resources

Frequently asked questions about Arbitrum: Scalable, private smart contracts

Practical answers about reading, downloading and understanding this document on Doxxly.

More in Technology & Security