The Arbitrum protocol may require a party to provide 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. A one-step proof must provide enough information, beyond the preconditions, to enable the Verier to emulate the single instruction that will be executed. Because the state of the VM is organized as a Merkle Tree, and the starting state hash of the VM, which is just the root hash of that Merkle Tree, is given as a precondition, the proof need only expand out enough of the initial state Merkle tree to enable the Verier to emulate execution of the single instruction, compute the unique assertion that results from executing that one instruction given the preconditions, and verify that it matches the claimed assertion. A one-step proof expands out any parts of the state tree that are needed by the Verier. For example, sup-

Messages and the Inbox Messages can be sent to a VM in two ways: a key can send a message by putting a special message delivery transaction on the blockchain; and another VM can send a message by using the send instruction. A message logically has four elds: data, which is an AVM value (marshaled into a byte array on the blockchain); a non-negative amount of currency, which is to be transferred from the sender to the receiver; and the identities of the sender and receiver of the message. Every VM has an inbox whose hash is tracked by the Verier. An empty inbox is represented as the AVM value None. A new message M can be appended to a VMs inbox by setting the inbox to a 2-tuple (prev, M), USENIX Association

27th USENIX Security Symposium 1361 where prev is the previous state of the inbox. A VM can execute the inbox instruction which pushes the current value of the VMs inbox onto the VMs stack. A VMs managers track the state of its inbox, but the Verier only needs to track the hash of the inbox, because that is all that will be needed to verify a one-step proof of the VM receiving the inbox contents. If the VM later processes the inbox contents, and a one-step proof of some step of that processing is needed, the managers will be able to provide any values needed. Because the inbox instruction gives the VM an inbox state that may be a linked list of multiple messages, programmers may wish to buffer those messages inside the VM to provide an abstraction of receiving one message at a time. The Arbitrum standard library provides code to do this as well as track when new messages have arrived in the inbox.

4.4 Extensions In this section, we describe extensions to Arbitrums design that may prove useful, particularly when the Arbitrum Verier is implemented as a public blockchain. Off-chain progress Arbitrum allows VMs to perform orders of magnitude more computation than existing systems at the same on-chain cost. However, usage of VMs frequently depends on communication between a VMs managers and the VM itself. In our prior description of Arbitrums protocol, this communication had to be onchain and thus was limited by the speed of the consensus mechanism. Arbitrum is compatible with state-channel and sidechain techniques, and there are several constructions that allow managers to communicate with a VM and unanimously advance a VMs state off-chain. We present details of one such construction in the extended version of this paper.