Cartesi Whitepaper

Friday, March 5, 2021
Buy CTSI coin
Save for later
Add to list is a project of OpenBook

Version 1.01 The Core of Cartesi Augusto Teixeira Diego Nehab Abstract of critical importance to all parties and therefore require global con- sensus. Otherwise, for most interactions mediated by the blockchain, Cartesi is a layer-2 platform for the development and deployment of it is perfectly safe to limit access and verification responsibility to scalable decentralized applications. Cartesi DApps are composed of the few parties that can potentially be affected. The blockchain can both blockchain and off-chain components. Off-chain components then be used to provide finality and to guarantee local consensus in run inside Cartesi Nodes that represent the interests of each DApp the rare occasions where a dispute arises between these parties. In user. Cartesi Nodes provide DApp developers with reproducible other words, global consensus is a precious resource that should be Cartesi Machines, where large scale verifiable computations can used with parsimony. In recognition of this fact, layer-2 scalability be run. These verifiable computations are easily integrated into solutions such as plasma, side chains, TrueBit, or state channels smart contracts by powerful primitives that provide strong conflict- move as much data and computation as possible off-chain. Layer-1 resolution guarantees. More precisely, any dispute arising over the and 2 scalability solutions are discussed at some depth in section 2. result of computations run inside Cartesi Machines can be fairly adjudicated at negligible cost on the blockchain. Cartesi Nodes also Computation environment Every computation that can influence allow DApp developers to run native code. Native computations can a transaction, whether performed on-chain or off-chain, must be re- leverage the node’s full processing power, including any available producible by all parties playing a validating role. Reproducible GPUs. Whether performed natively by the node or inside Cartesi computational models must be self-contained and deterministic. In Machines, off-chain components run under a complete Linux oper- other words, the complete state for the computation and the entire ating system that provides the full ecosystem required by complex sequence of modifications to this state must be fully specified and computations. Cartesi enables DApp developers to use all the pro- agreed upon. Sadly, real computing architectures were not designed gramming languages, tools, libraries, software, and services they with these constraints in mind, and therefore are not reproducible. are already familiar with. By moving most of the complex logic of Blockchain platforms solve this problem by employing custom vir- their DApps to portable off-chain components, developers are freed tual machines (VMs) when processing smart contracts. These VMs from the limitations and idiosyncrasies imposed by blockchains. In are reproducible, but also domain specific. On the one hand, they this way, Cartesi empowers developers to select the best run-time offer native support for features useful to smart contracts (e.g., ac- environment in which to host each part of their DApps. counting, rollback, associative memory, authentication, cryptogra- phy etc). On the other hand, they lack valuable features found in 1 Introduction general-purpose architectures (e.g., floating-point arithmetic, virtual memory, interrupts etc). Public blockchains are mechanisms through which networks can The revolution in software capability the world experienced over maintain decentralized consensus over a shared state. Typically, this the last few decades can be attributed to two key factors. The first state holds, among other data, a payment system. The stake held by is an exponential increase in the speed at which modern hardware participants in the resulting economy works as their incentive for platforms can process vast amounts of data. The second, and equally making the state widely available to others and for rejecting invalid important, is the ever-increasing expressive power of software devel- transactions. In this virtuous cycle, the payment system is built on opment environments. Indeed, general-purpose computations do not top of the decentralized consensus, which only functions due to happen in isolation. Rather, they are assembled from inter-dependent incentives created by the payment system itself. Both the payment building-blocks created by a worldwide collaboration of software system and the consensus can then be used for other purposes. developers. These components and services rely on standard-library As new applications for blockchain technology are envisioned, the facilities hosted by an underlying operating system (memory man- demands on the underlying infrastructure are constantly increasing. agement, process management, file systems, networking, etc). It is At the moment, the two major obstacles to widespread adoption of the operating system that ties everything together. Such facilities blockchain technology are its poor scalability and lack of a solid are not available from the free-standing programming languages and development environment. The main contribution of Cartesi to the compilers that typical blockchains offer to smart contract developers. blockchain ecosystem is overcoming both these issues. Reproducibility and scalability concerns have made on-chain com- putation environments very restrictive. To boost productivity and Scalability Currently deployed consensus mechanisms are based widen the scope of blockchain development, we need a reproducible on full redundancy [Nakamoto 2009; Wood 2018]. They require computation model that supports modern operating systems. every transaction to be stored permanently and to be validated by every participant. This inefficiency is the key limiting factor to the growth of the transaction rate, the amount of data involved, and the Cartesi intensity of computations within transactions. High transaction costs and increased latency have become a barrier to many innovative This paper describes Cartesi, a layer-2 platform for the develop- applications that would otherwise benefit from the flexibility that ment and deployment of scalable decentralized applications. Cartesi smart contracts bring to the blockchain. DApps are hybrid, i.e., they include both blockchain and off-chain components. Attempts to improve blockchain scalability can be divided into layer 1 and layer 2 solutions. Layer 1 scalability solutions change The off-chain component runs in a network of Cartesi Nodes (sec- the underlying blockchain infrastructure itself. Examples include tion 6), each representing the interests of a DApp user. The off-chain the optimization of block sizes, sharding, and Delegated Proof of component is further divided into two modalities. Native compu- Stake (DPoS). Because they operate at the infrastructure level, these tations run directly in the host hardware. Although native compu- solutions are burdened by the requirement of preserving global con- tations have access to the node’s full processing power (including sensus. Certain aspects of the state, such as the payment system, are GPUs), the computations are not reproducible, at least not a pri- 1

Version 1.01 ori. Reproducible computations run instead inside Cartesi Machines applications access to the tools, libraries, services, and software they that are controlled by the Cartesi Node. These are general, fully are already familiar with, Cartesi chose to support Linux. A realistic self-contained Linux systems, that run on a deterministic RISC-V ISA, such as RISC-V, is much better suited for this purpose. architecture (section 3). Nodes interact with Cartesi Machines by means of a well-defined host interface (section 4). One of the differences of greatest consequence is in how Cartesi aligns the interest in off-chain computations with the responsibility Within the blockchain, a Cartesi DApp can specify reproducible off- for their execution. In TrueBit, there is no such alignment. A smart chain computations to be performed over large amounts of off-chain contract posts the computation to a pool of untrusted parties and data (section 5). Cartesi Nodes can automatically follow these speci- waits for one of them to perform it off-chain and post the result fications to perform the computations off-chain. DApp developers back. In this sense, TrueBit can be seen as a means for increasing can instruct the nodes to submit results or verify and dispute results the computational power of individual smart contracts. Cheating is submitted by others. From the blockchain’s perspective, undisputed prevented with a complex incentive layer that rewards pool members computations take negligible resources. Even in case of disputes, the for successively disputing incorrect results. To keep the members settlement cost is only the logarithm of the storage and time required engaged, computations with incorrect results must be artificially during the computation. Off-chain, Cartesi Nodes never experience injected by the incentive layer. This inefficiency is a fundamental more than twice the space and time required by the computation. In part of the design of TrueBit. Conversely, Cartesi can be seen as a this way, Cartesi virtually eliminates the gap in storage and com- way for off-chain computations to be endorsed by a smart contract. putation power between smart contracts and traditional computer All parties that could be affected by this endorsement are responsible programs. for performing the computation off-chain and, if needed, starting a dispute. Although the ensuing verification can be outsourced to Moving computations off-chain brings several advantages beyond a dispute resolution market (see section 6.2), there is no built-in scalability. Cartesi Machines enable DApp developers to use all the inefficiency and no need for an incentive layer. programming languages, tools, libraries, software, and services they are already familiar with. Moreover, the way in which computations The large storage requirements of real-world computations pose a are formulated is agnostic to the underlying blockchain. By isolating significant challenge that TrueBit does not address. Explicit repre- all the complex smart-contract logic into reproducible off-chain com- sentations of code and data do not fit within the blockchain. Instead, putations, developers can make their DApps more portable across a Cartesi Machine, together with its code and data, are represented different blockchains. on-chain by a hash of its state. This arrangement allows for complex The focus of this document is the core of Cartesi. It includes the transactions built from several rounds of off-chain computations to full specification for the Cartesi Machine, the host interface for con- be fully specified. The states themselves are only ever known ex- trolling it, the blockchain interface for specifying complex off-chain plicitly off-chain, by interested parties. Some applications can face computations, and the Cartesi Node interface for performing and data availability issues to which Cartesi offers a range of original verifying these computations. Higher-level tools, interfaces, and a solutions [Teixeira and Nehab 2019a]. variety of use cases built on top of this core functionality will be de- Finally, Cartesi is committed to making off-chain computations scribed in a future document [Teixeira and Nehab 2019a]. Detailed portable across different blockchain platforms. documentation on all interfaces, as well as the development environ- ment for Cartesi Nodes and Cartesi Machines will be available from the Cartesi SDK [Teixeira and Nehab 2019b]. 2.1 Other related technologies 2 Related work New blockchain technologies emerge at such a high rate that any attempt at a comprehensive survey is doomed to become obsolete The work most closely related to Cartesi is TrueBit [Teutsch and before it is even published. Nevertheless, some general trends merit Reitwießner 2017]. The connection between Cartesi and Truebit discussion. Specific examples cited in the discussion should be seen comes from the fact that both technologies move intensive compu- as representatives of entire categories, rather than exhaustive lists. tations off-chain and then, within the blockchain, use a verification game [Feige and Kilian 1997] to efficiently settle disputes regarding Layer-1 scalability solutions The scalability trilemma put forth the results of these computations. Despite this similarity, many other by Buterin [2018a] poses that no simple workaround can improve design decisions set these two technologies apart. transaction throughput without reducing the decentralization or se- curity of a blockchain. On the one hand, requiring higher throughput TrueBit is based on WebAssembly [2018], a VM ISA designed by from nodes raises their operating cost, which centralizes power in a W3C Community Group to support efficient web applications.1 the hands of the few players that can afford them. On the other, In contrast, Cartesi is based on RISC-V [Waterman and Asanović fragmenting consensus into independent chains makes each of them 2017a,b], an open ISA designed in UC Berkley for implementation more vulnerable to 51% attacks. by native hardware. The WebAssembly and RISC-V ISAs are of similar complexity. The key difference is their position in relation to The two leading proposals for breaking the trillema are refinements applications and the operating system. WebAssembly was designed of these two ideas. Delegated Proof of Stake (e.g., Larimer [2017]) to sit between applications and the underlying operating system. requires a small number of powerful nodes to validate every single RISC-V is instead meant to sit under the operating system and the transaction. However, these nodes are democratically elected by all applications it supports. TrueBit’s choice is consistent with a focus parties that hold a stake in the blockchain. The alternative proposal on extending the computational power of smart contracts, which is to split the state and history into multiple shards that are verified tend to operate under severely restricted environments. Real-world independently [Buterin 2018b]. These shards are then connected to applications, however, cannot exist in isolation. They depend on a main chain in a way that reduces the odds of successful attacks. rich, complex run-time environments that are invariably built on top of a modern operating system. To give developers of decentralized Both ideas are expected to significantly improve the throughput of transactions processed by the blockchain. They must nevertheless 1 It was originally based on the LLVM back-end for an obscure Myricom achieve universal consensus among nodes on each transaction. This NIC embedded processor design used internally at Google. imposes a super-linear global cost as computation sizes grow. 2

Version 1.01 Cartesi, on the other hand, is designed to achieve local (instead of very different from Cartesi’s. Future applications may wish to com- universal) consensus over its computations. More precisely, only bine both technologies by running part of their native computations affected parties are required to perform the computation, while inside hardware enclaves within Cartesi Nodes, or by running an any possible dispute among them can be resolved in logarithmic entire Cartesi Node inside a hardware enclave. time. This design allows for intensive computations to be performed off-chain only by the impacted participants, who still enjoy strong Zero knowledge proofs Another approach to enable private and conflict resolution guarantees. scalable computations on the blockchain is to use general purpose In this way, DPoS and sharding are orthogonal to Cartesi. Cartesi zero-knowledge proof systems such as zk-SNARKS [Blum et al. benefits from the faster and cheaper transactions provided by the 1988; Bitansky et al. 2012] or zk-STARKS [Ben-Sasson et al. 2018]. underlying infrastructure. Conversely, the blockchain benefits from These systems achieve verifications in a fast, non-interactive and Cartesi’s ability to specify and adjudicate large-scale realistic com- private manner. However, the computations that can be specified putations. within these models are very restrictive as they are derived from arithmetic circuits without control flow. Therefore, they are not Layer-2 scalability solutions Various solutions have been pro- Turing complete and cannot run arbitrary code. posed on the second layer to increase blockchain scalability in terms In off-chain environments, this technology is reaching maturity of transaction throughput, such as Plasma or State Channels. These through projects such as Pinocchio [Parno et al. 2013] and lib- developments have particularities of their own, but are generally snark [Ben-Sasson et al. 2013]. Meanwhile, zero-knowledge proofs designed to register large amounts of transactions off-chain, which have first appeared in blockchain technology with privacy coins, are only committed on-chain in order to reach finality or in the case where shielded addresses protect the identities of parties involved of a dispute. A common requirement of these solutions is that the in a transaction [Miers et al. 2013; van Saberhangen 2013]. In the blockchain should be able to resolve any dispute that may arise (after Metropolis (Byzantium) fork, Ethereum introduced zk-SNARKS a Plasma exit, or when a channel is closed). These exit mechanisms primitives into its virtual machine and some libraries have already impose strong limitation on the maximum transaction size that either started to be developed [Schaeffer 2018]. In this context, Cartesi Plasma or State Channels can handle. So for example, if two parties can accelerate this development by bringing more mature off-chain disagree on an off-chain transaction that requires a large computa- implementations of zk-SNARKS, such as Pinocchio or libsnark, tion to be completed, they would be unable to settle who is correct directly into the blockchain. on the main chain. Cartesi can greatly improve these technologies, as it allows both a Compilers and Virtual Machines Besides the scalability solu- Plasma chain or a State Channel to specify full Cartesi computations tions mentioned above, several projects try to provide different within its transactions. And in case a dispute lifts the computation languages for developers to write smart contracts in, such as Vyper, to the main chain, the settlement can still be efficiently and safely LLL, Bamboo, etc. Although these projects provide a welcome set resolved. of languages and tools for the development of smart contracts, they do not fully alleviate the most fundamental restrictions that currently Reputation solutions Several projects intend to bring large scale hamper blockchain development. The main reason being that all and flexible computations to the blockchain by relying on a system these languages run on a free standing environment and therefore of redundancy, reputation, and verification (e.g., SONM [2018], they do not offer the advantages that come with Cartesi’s underlying Golem [2016], and iExec [2017]). Although all these systems have operating system, as described in section 3 below. different designs, the main idea is that computations are sent to a pool of off-chain providers, who submit their results independently. If someone challenges the presented results, a randomly assigned 3 Cartesi Machine specification verifier decides on the correct outcome. The Cartesi Machine is a self-contained and deterministic computa- Although these systems have a built-in reputation mechanism to tional model that can host modern operating systems. Real-world discourage misbehavior, it is not yet clear whether they are resistant computations happen inside operating systems for good reasons. to collusions or bribing in case the outcome of a computation can Developers are trained to use toolchains that operate at the highest have financial consequences. Cartesi gives instead mathematical possible abstraction level for any given job. These toolchains isolate guarantees on its dispute resolutions. them from irrelevant hardware details and even from the particulars of a given operating system. Inventing an ad-hoc new architecture Trusted execution environment Several projects are integrating would then require the porting of a toolchain and operating sys- enclaves (e.g., Intel’s SGX, ARM’s TrustZone, or AMD’s SEV) with tem. Instead, Cartesi Machines are based on a proven architecture the blockchain [TEEX 2018; Song et al. 2018; Enigma 2018; Cheng for which a standard toolchain and operating system are already et al. 2018]. In a nutshell, enclaves are hardware-supported features available. that allow user-level code to create an execution environment whose privacy and integrity is protected even from processes running at On the other hand, off-chain computations performed by Cartesi higher privilege levels. Machines must be verifiable by a blockchain. The blockchain must Computations running inside enclaves are not, a priori, reproducible. therefore host a reference implementation of the entire architec- Using remote attestation in lieu of verification is equivalent to trust- ture. If it is ever to be trusted, this implementation must be easily ing the hardware manufacturer. Whether this level of centralization auditable. To that end, both the architecture and the implementa- is justifiable or not depends on the application at hand, the manu- tion must be open and relatively simple. Together, these require- facturer’s competence, and on the potential for conflicts of interest. ments point to RISC-V. The RISC-V ISA is based on a minimal Even setting these issues aside, privacy is not always guaranteed, 32-bit integer instruction set to which several extensions can be as recent attacks show [Weichbrodt et al. 2016; Brasser et al. 2017; added [Waterman and Asanović 2017a]. Orthogonally, operand and Moghimi et al. 2017; Lee et al. 2017]. address-space widths can be extended to 64-bits (or even 128-bits). Additionally, the standard defines a privileged architecture [Water- Enclaves may yet play an important role in the future of blockchain man and Asanović 2017b] with features commonly used by modern technology. However, their threat model and security guarantees are operating systems, such as multiple privilege levels, paged-based 3

Version 1.01 Table 1: Instruction counts by extension. Entries in the form x + y refer to 32- and 64-bit variants of the same facility. Integer Mul/Div Atomics Privileged Total Figure 1: The iflags register gives the current privilege level, 47+12 8+5 11+11 5 71+28=99 and specifies whether the machine is temporarily idle waiting for interrupts, or has been permanently halted. Table 2: The processor state. Memory-mapped to the lowest 512 bytes in physical memory for external read-only access. protection. Sv48 provides a 48-bit protected virtual address space, Offset State Offset State divided into 4KiB pages, organized by a four-level page table. This set of features creates a balanced compromise between the simplic- 0x000 x0 0x160 misa ity demanded by a blockchain implementation and the flexibility 0x008 x1 0x168 mie expected from off-chain computations. ··· ··· 0x170 mip 0x0f8 x31 0x178 medeleg There are a total of 99 instructions, out of which 28 simply narrow 0x100 pc 0x180 mideleg or widen, respectively, their 64-bit or 32-bit counterparts. Table 1 0x108 mvendorid 0x188 mcounteren breaks down the instruction count for each extension. This being a 0x110 marchid 0x190 stvec RISC ISA, most instructions are very simple and can be simulated in 0x118 mimplid 0x198 sscratch a few lines of high-level code.2 In fact, the only complex operation 0x120 mcycle 0x1a0 sepc is the virtual-to-physical address translation. Instruction decoding is 0x128 minstret 0x1a8 scause particularly simple due to the reduced number of formats (only 4, 0x130 mstatus 0x1b0 stval all taking 32-bits). 0x138 mtvec 0x1b8 satp The entire processor state fits within 512 bytes, which are divided 0x140 mscratch 0x1c0 scounteren into 64 registers, each one holding 64-bits. Most of these registers 0x148 mepc 0x1c8 ilrsc† are defined by the RISC-V ISA, and consist of 32 general-purpose 0x150 mcause 0x1d0 iflags† integer registers and 26 control and status registers. The remaining 0x158 mtval are Cartesi-specific. The processor makes its entire state available, † Cartesi-specific state. externally and read-only, by mapping individual registers to the lowest 512 bytes in physical memory. The adjacent 1.5KiB are reserved for future use. The entire mapping is given in table 2. virtual-memory, timers, interrupts, exceptions and traps, etc. Im- The registers whose names start with i are Cartesi-specific, and plementations are free to select the combination of extensions that have the following semantics. The layout for register iflags can better suit their needs. be seen in figure 1. PRV gives the current privilege level, I is set to 1 when the processor is idle (i.e., waiting for interrupts), and H RISC-V was born of research in academia at UC Berkeley. It is now is set to 1 to signal the processor has been permanently halted. maintained by its own independent foundation. Larger corporations, Register ilrsc holds the reservation address for the LR/SC atomic including Google, Samsung, and Tesla, have recently joined forces memory operations. with the project [Tilley 2018]. The platform is supported by a vibrant community of developers. Their efforts have produced an extensive Default initialization fills the state with the following values: software infrastructure, most notably ports of the Linux operating system and the GNU toolchain [RISC-V 2018d]. It is important to • PRV in iflags is set to 3 (for the Machine privilege level); keep in mind that RISC-V is not a toy architecture. It is suitable for • misa is set to RV64IMASU; direct native hardware implementation, which is indeed currently • SXL and UXL in mstatus are set to 2 (for 64-bits); commercialized by SiFive Inc. This means that, in the future, Cartesi • pc starts at 0x1000 (pointing to ROM); will not be limited to emulation or binary translation off-chain. • marchid is set to cartesi␣ in ASCII. The Cartesi Machine can be separated into a processor and a board. mvendorid is used to test for matching on-chain and off-chain The processor performs the computations, executing the traditional implementations. mimplid is incremented with each update to a fetch-execute loop while maintaining a variety of registers. The matching pair. The remaining default state is set to zero. board defines the surrounding environment with an assortment of memories (ROM, RAM, flash) and devices. To make verification 3.2 The board possible, Cartesi Machines map their entire state to physical mem- ory in a well-defined way. This includes the internal states of the The interaction between board and processor happens through de- processor, the board, and of all attached devices. Fortunately, this vices mapped to the processor’s physical address space. Table 3 modification does not limit the operating system or the applications shows this mapping. There are 64KiB of ROM starting at address it hosts in any significant way. 0x1000, where execution starts. The central role of this ROM is holding the devicetree [DTSpec 2017] describing the system hard- 3.1 The processor ware. In addition, a bootstrap program at ROM-base sets register x10 to 0 (the value of mhartid), x11 to point to the devicetree, and then Following RISC-V terminology, Cartesi Machines implement the jumps to RAM-base at 0x80000000. This is where the entry point RV64IMASU ISA. The letters after RV specify the extension set. of the boot image is expected to reside. Finally, a number of addi- This selection corresponds to a 64-bit machine, Integer arithmetic tional physical memory ranges can be set aside for flash-memory with Multiplication and division, Atomic operations, as well as the devices. These will typically be preloaded with file-system images. optional Supervisor and User privilege levels. In addition, Cartesi Machines support the Sv48 mode of address translation and memory 2 The x86 ISA defines at least 2000 (potentially complex) instructions. 4

Version 1.01 Table 3: Physical memory layout for a Cartesi Machine. Physical address Mapping 0x00000000–0x000003ff Processor shadow 0x00000800–0x00000Bff Board shadow 0x00001000–0x00010fff ROM (Bootstrap & Devicetree) Figure 2: Physical Memory Attributes. The istart and ilength 0x02000000–0x020bffff Core Local Interruptor of each range are aligned to a 4KiB boundary. The 12 LSBs of each 0x40000000–0x40007fff Host-Target Interface 64-bit word give attributes for the range. 0x80000000–* RAM *–* Flash 0 (Disk 0) ··· ··· *–* Flash 7 (Disk 7) Two non-memory devices are mapped to the address space. The Core Local Interruptor (or CLINT) controls the timer interrupt. The active addresses are 0x0200bff8 and 0x02004000, respectively mapped to registers mtime and mtimecmp. The CLINT issues a value of mcycle. (Note that, since the machine can be occasionally hardware interrupt whenever mtime equals mtimecmp. To ensure idle, minstret does not track mcycle.) reproducibility, the processor’s clock and the timer are locked by a constant frequency divisor of 100. In other words, mtime is incre- The only salient Cartesi-specific modification pertains to the halting mented once for every 100 increments of mcycle. The Host-Target of the machine. When field H in iflags is set to 1, no further state Interface (HTIF) mediates communication with the external world. transitions are allowed. The condition is set explicitly when HTIF is Its active addresses are 0x40000000 (tohost) and 0x40000008 instructed to halt the machine. (fromhost). It halts the machine when tohost is written to with bits 63–48 set to 0 and bit 0 set to 1. (Bits 47–1 can be set to an 3.4 The Linux port arbitrary exit code.) It also works as a rudimentary communications port during interactive sections. Setting up a Linux system from scratch involves a variety of steps. The physical memory mapping is described by Physical Memory Unlike stand-alone systems, embedded systems are not usually self- Attribute records (PMAs). Each PMA consists of 2 64-bit words. hosting. Instead, components are built in a separate host system, The first word gives the start of a range and the second word its on which a cross-compiling toolchain for the target architecture length. Since the ranges must be aligned to 4KiB page boundaries, has been installed. The key components are the GNU Compiler the lowest 12-bits of each word are available for attributes. Figure 2 Collection and the GNU C Library. This infrastructure can be found shows the meaning of each attribute field. The M, IO, and E bits in the RISC-V GNU toolchain repository [RISC-V 2018a]. Building are mutually exclusive, and respectively mark the range as memory, this infrastructure is the first step. I/O mapped, or excluded. Bits R, W, and X grant read, write, and execute permissions, respectively. Finally, the IR and IW bits mark The toolchain can then be used to cross-compile the Linux kernel. the range as idempotent for reads and writes, respectively. Kernel sources can be found in the RISC-V Linux repository [RISC- V 2018b]. The kernel runs in supervisor mode, on top of a Supervisor The board supports a total of 32 PMAs, and makes them available, Binary Interface (SBI) provided by a machine-mode shim: the Berke- read-only, starting at offset 2KiB in physical memory. Another 2KiB ley Boot Loader (BBL). BBL can be found in the RISC-V Proxy are reserved for future use. PMA 0 describes RAM, and PMAs 16– Kernel repository [RISC-V 2018e]. The BBL is linked against the 23 describe flash devices 0–7. These PMAs are user-configurable Linux kernel and this resulting boot image is preloaded into RAM. during initialization and read-only thereafter. (The RAM istart The SBI provides a simple interface through which the kernel inter- field is hard-coded to 0x80000000.) Together, these records bound acts with CLINT and HTIF. Besides implementing the SBI, the BBL the maximum amount of storage accessible during computations. also installs a trap that catches invalid instruction exceptions. This mechanism can be used to emulate floating-point instructions (See 3.3 The state transition function section 4.3). After installing the trap, BBL switches to supervisor mode and cedes control to the kernel entry point. A computation is a sequence of machine states s0 , s1 , . . . , sh , gov- erned by a transition function step such that The final step is the creation of a root file-system. This process starts with a skeleton directory in the host system containing a si+1 = step(si ). (1) few subdirectories (sbin, lib, var, etc) and text files (sbin/init, etc/fstab, etc/passwd etc). Tiny versions of many common Here, s0 is the initial state and sh is a halting state. The previous UNIX utilities (ls, cd, rm, etc) can be combined into a single sections described the state space and the transition function for binary [Vlasenko 2018]. Target executables often depend on shared Cartesi Machines in great detail. libraries provided by the toolchain (lib/, lib/, and Recall the state consists of the value of each word in the entire 64-bit lib/ Naturally, these libraries must be copied to the root address space of the Cartesi Machine. In practice, it takes vastly file-system. Once the root directory is ready, it is copied into an fewer than 264 bytes to represent a state. Only regions described in actual file-system image (e.g., using gene2fs). table 3 must be defined explicitly. All remaining values are implicitly filled with zeros. These steps can be automated. Cartesi’s SDK makes a preconfigured host environment available to developers in the convenient form of a The RISC-V ISA manuals [Waterman and Asanović 2017a,b] spec- Docker container. Complex Linux systems can be built with the help ify the state transitions corresponding to the execution of each in- of Sifive’s fork of Buildroot [Petazzoni 2018], or RISC-V’s port of struction. This means that states are well defined between executed the Yocto project [RISC-V 2018c]. The environment in the container instructions. Since all instructions can be implemented in O(1) time, enables developers to customize the boot image and the root file- Cartesi defines each state transition to take exactly 1 cycle. The index system according to the needs of their applications. Thousands of of a given state in the sequence can be read from the corresponding packages are available for installation. 5

Version 1.01 [email protected] { m = machine{ device_type = "memory"; ram { reg = <0x0 0x80000000 0x0 0x8000000>; ilength = 0x8000000, }; backing = "boot-image.bin" }, [email protected] { #address-cells = <0x2>; rom = { #size-cells = <0x2>; bootargs = "root=/dev/mtdblock0 rw", compatible = "mtd-ram"; } bank-width = <0x4>; reg = <0x80 0x0 0x0 0x4000000>; flash0 = { [email protected] { label = "root", label = "root"; istart = 0x8000000000, reg = <0x0 0x0 0x0 0x4000000>; ilength = 0x4000000, }; backing = "root-file-system.bin", }; shared = true } chosen { } bootargs = "root=/dev/mtdblock0 rw"; }; Figure 4: The initialization of the off-chain machine automatically generates the devicetree of figure 3. Figure 3: Partial devicetree for a simple setup with 128MiB of RAM and a 64MiB flash device to be mounted as the root file-system. filled automatically or loaded from a backing file. Initialization returns a machine handle that can be manipulated thereafter. The root file-system image is installed as a flash device. Additional flash devices can be used to store the inputs to the computation, or machine = machine{ ram ::= { to receive its outputs. The devicetree in ROM is used to inform processor = processor , ilength = word , Linux of the location of each flash device, the amount of RAM, rom = rom , backing = path and any kernel parameters. Figure 3 shows the relevant devicetree ram = ram , } snippet. The first section specifies 128MiB of RAM starting at the flash0 = drive , 2GiB boundary. The middle section adds a 64MiB flash device, ... drive ::= { flash7 = drive , istart = word , starting at the 512GiB boundary. The mtd-ram driver exposes the clint = clint , ilength = word , device as /dev/mtdblock0 under Linux’s virtual file-system. The htif = htif , backing = path , last section, giving the kernel parameters bootargs, specifies the } shared = bool , device to be mounted as root. label = string processor ::= { } After completing its own initialization, the kernel eventually cedes x0 = word , control to /sbin/init. In Cartesi DApps, this is typically a shell x1 = word , clint ::= { script that invokes the appropriate sequence of commands for per- ... mtime = word , pc = word mtimecmp = word forming the desired computation. The kernel passes to /sbin/init } | { } | { as command-line parameters all arguments after the separator ␣-␣ backing = path backing = path in bootargs. These can be used to define additional parameters for } } the computation to be performed. Upon completion, /sbin/init uses HTIF to halt the machine with an optional exit code. This rom ::= { htif ::= { can be used as part of the computation output. Arbitrarily complex bootargs = string fromhost = word , } | { tohost = word inputs, parameters, and outputs can be passed as flash devices. backing = path } | { } backing = path } 4 Cartesi Machines off-chain Figure 4 shows a sample machine call for the devicetree in figure 3. Off-chain implementations of Cartesi Machines serve two purposes. Their main role is the execution of the computation itself. The sec- The machine runs until mcycle exceeds a limit value. The func- ondary role is supporting the settlement of disputes over the results tion then returns false if the machine is halted, or true otherwise. of computations. To provide these services, off-chain implementa- bool = machine :run{limit = word } tions of Cartesi Machines must expose a programmable interface. The machine can create a snapshot of its current state. This is a lightweight operation. It causes subsequent calls to run to modify 4.1 The scripting interface the state under a copy-on-write policy. At a future time, a rollback operation can restore the snapshot state. Restoring the state lifts The instantiation of a machine can only happen after the initial the copy-on-write policy. Consecutive calls to snapshot cause values for its entire physical address space have been defined. The the previously snapshot state to be committed to memory. Calls physical memory layout is parameterized by the total amount of to rollback without a previously snapshot state have no effect: RAM, and by the starts and lengths of all flash devices. PMAs are automatically initialized from these parameters. The initial contents machine :snapshot() of RAM (e.g., with the boot image) and of the flash devices (e.g., the machine :rollback() root file system), are given by backing files. The backing files for The machine provides read-only access to its memory contents. To flash devices can be shared, in which case modifications to physical that end, invoking word(address) returns the value of a given memory are saved to the file mapped to the corresponding memory 64-bit (aligned) word in the address space: location. Values that are not explicitly defined are default-initialized. In particular, the devicetree and the bootstrap in ROM can be either word = machine :word{address = word } 6

Version 1.01 To backup the contents of the memory range associated to any facilities. It is distributed as a library and scriptable in the Lua component of the machine state, simply choose a file to store it: programming language according to the interface described above. bool = machine :backup{ Backing files for RAM and file-system images take advantage of processor = path , the host’s support for sparse files. Only non-zero blocks take disk rom = path , space. This enables the entire state of the machine to be specified ram = path , flash0 = path , in a convenient and compact form. The snapshot and rollback ... mechanism, as well as the shared attribute for backing files, are flash7 = path , built on top of the host’s support for virtual memory, using child clint = path , processes and memory-mapped files with copy-on-write semantics. htif = path , This makes them at the same time very simple to implement and } very efficient. The machine exposes its entire state as a Merkle tree [Merkle 1979]. The functionality for Merkle tree inspection requires additional (For more on Merkle trees, see section 5.) It returns a proof that a tar- support. For storage efficiency, the Merkle tree is maintained in its get node belongs to the Merkle tree, given its address and depth: PATRICIA form [Morrison 1968]. For time efficiency, the tree is proof = machine :prove{ updated only when needed, in a lazy fashion. Each PMA range has address = word , a bitmap of dirty pages associated to it. Pages of physical memory depth = word are marked dirty in the TLB whenever they are written to. When the } TLB entry for a dirty page is evicted, the corresponding bit is saved to the bitmap. When the proof function is called, it first updates the proof ::= { address = word , Merkle tree. The update proceeds bottom up, by visiting only the depth = word , nodes that subtend the dirty pages. After the update, all bitmaps and root = hash , TLB entries are marked clean. siblings = {hash1 , ..., hashdepth }, target = hash For simplicity, the emulator follows a tight loop decoding and execut- } ing each instruction in turn. Other RISC-V emulators are based on the same approach [Waterman and Lee 2011; Bellard 2017]. In the The entries used for the initialization of individual devices can also future, the emulator will avoid repeated decoding of hot execution be queried from their base address. The hash of the node at the traces [Tröger et al. 2011]. It is possible to translate these traces to address and depth is returned along with the entry. If the base the host instruction set for even better performance [Bellard 2018]. address does not correspond to any device, or if the range length However, the additional gains must be weighted against the reduced implied by the depth causes it to overlap with more than one device, portability and significantly increased complexity. an error is reported: slice = machine :slice{ device ::= 4.3 Floating-point support address = word , processor | depth = word rom | Floating-point operations are prevalent off-chain (except, perhaps, in } ram | the context of embedded devices). Therefore, programmers expect drive | them to be available. If Cartesi hopes to bring a sense of normalcy to slice ::= { clint | hash = hash , htif blockchain development, it must support floating-point operations. type = string , The difficulty is guaranteeing reproducibility. device = device } Different floating-point implementations can disagree subtly when ostensibly performing the same operation on the same operands. The step function advances the machine 1 cycle, logging every Some of these differences arise from laxities in the IEEE 754-1985 single access to the state along the way. All accesses are 64-bit standard. Although many of these have been tightened in the 2008 aligned. Each log entry specifies the operation (read or write), revision, several details remain unspecified. These include, but the address, and the word read or written. In addition, each entry are not limited to, underflows, the sign of zero, operations involv- includes the proof produced by a corresponding call to proof for ing infinity or NaNs, and the quantum for the rounding of certain the address prior to the access. recommended operations (e.g., sin, log etc). Moreover, hardware implementations often take performance shortcuts that violate the log = machine :step() standards they claim to adhere to. This leads to inconsistencies even log ::= {access1 , access2 , ..., accessk } across successive generations of the same architecture. access ::= { These issues argue strongly against adding floating-point support to operation = read | write, any verifiable computation model. Accordingly, most blockchains read = word , wisely omit them entirely [Nakamoto 2009; Wood 2018; NEO’s VM written = word , 2017; Cardano’s VM 2017]. The only way to guarantee consensus is proof = proof } to emulate floating-point operations with a consistent software layer based on integer operations. Unlike floating-point operations, these The importance of functions prove, slice, and step, and the are portable across different architectures. convenience of this interface will become clear in section 5. In the RISC-V ISA, floating-point support is defined by extensions F and D (respectively for single- and double-precision). Together, 4.2 Reference implementation these extensions augment the ISA with 32 floating-point registers, 1 control-status register, 30 new instructions, and 1 new instruction Cartesi’s reference off-chain implementation is based on software format. The specification adheres strictly to the IEEE 754-2008 emulation. The emulator is written in C/C++ with POSIX depen- standard [IEEE 2008]. Furthermore, it is limited to the required dencies restricted to the terminal, process, and memory-mapping arithmetic operations that are fully specified. 7

Version 1.01 There are many options for adding floating-point support to Cartesi. his DApp. Charlie, however, trusts neither Alice nor Bob. Naturally, In the first two approaches, the ISA does not include the F or D Alice and Bob do not trust each other either. extensions. Therefore, they require no changes to the blockchain and off-chain implementations. Cartesi’s role is to support Charlie’s work. To that end, Cartesi offers a variety of primitives that Charlie uses to mediate the potentially Emulation by RISC-V code: traps When a RISC-V machine adversarial interactions between Alice and Bob. Some primitives does not support floating-point instructions, it raises a machine- require no interaction, and can be evaluated autonomously in the level illegal-instruction exception whenever one is found. The idea blockchain from their inputs. The interesting primitives, however, is to use an exception handler installed by BBL to emulate the are those that, though completely defined by their inputs, can only corresponding floating-point instruction using RISC-V integer in- be evaluated off-chain. By construction, when using a Cartesi DApp, structions. This process is transparent to the supervisor and user Alice and Bob always agree on the inputs to such primitives. Without levels, which work as if the ISA supported floating-point operations loss of generality, Bob evaluates the primitive off-chain and submits natively. the result. Alice is then given the chance to accept or reject Bob’s result. Undisputed results can be used by Charlie’s DApp for the Emulation by RISC-V code: compiler Alternatively, the com- purpose of his choice. In case of rejection, Cartesi engages with piler can be instructed to target a RISC-V ISA that does not include Alice and Bob in a dispute resolution protocol that arbitrates in favor floating-point operations. It substitutes them with calls to emulation of the party with just cause. This adjudication always completes routines it provides itself. The resulting binaries do not include within a few interactions and at a negligible computational cost to floating-point instructions at all. This method is more efficient than the blockchain. Cartesi automates most of this process in a way that using traps because it avoids the exception and decoding overhead. is extremely convenient to Charlie. The next two approaches add the F or D extensions to the ISA. The most important of these primitives is the Cartesi Machine. Smart Naturally, this means the off-chain machine must implement all contracts cannot afford to store the states for a Cartesi Machine RISC-V floating-point instructions. Furthermore, the blockchain within the blockchain, let alone perform the implied computations. verifier must include a perfectly matching implementation. After all, the costs in terms of processing power and storage capacity would both be prohibitive. To solve these problems, Cartesi uses Emulation by native integers In this approach, floating-point cryptographic hashes to concisely represent machine states in the instructions are still emulated off-chain. However, the emulation blockchain. From the blockchain’s perspective, a computation is now uses native integer instructions, rather than RISC-V integer simply a pair of hashes corresponding to the initial and final states of instructions. There are several high-quality open-source soft-float the machine. The contents of the memory subtended by such hashes implementations from which to choose [Bellard 2016; Houser 2017]. are known only off-chain. Cartesi defines a variety of additional This makes the off-chain machine even faster. primitives that allow smart contracts to conveniently manipulate the contents of the states corresponding to these hashes. Native off-chain floating-point The next step in performance comes from using native floating-point instructions off-chain. Ob- 5.1 Machine state representation by hashes taining reproducible results from two distinct fully conforming IEEE 754-2008 implementations requires the cooperation between Merkle trees [Merkle 1979] are binary trees where each node con- language standards, compilers, and, most regrettably, users. The tains a hash. In Cartesi, Merkle trees are based on the keccak hash prospects are improved in Cartesi’s context, since the reference im- function [Dworkin 2015].3 Let s be a Cartesi Machine state, giving plementation controls all these components and can fully specify the entire contents of its 64-bit address space. The Merkle tree m any omissions in the standard. These corner cases include, but are for s, or, equivalently, its root node, is not limited to, underflows, the sign of zero, and operations involv- ing infinity or NaNs. Even with the added overhead, this approach m = merkle(s). (2) should be the fastest one off-chain. The tree is built up from its leaves in the following way. First, the At present, the emulator makes the first two options available, that is, state is partitioned into 261 64-bit words. The tree leaves contain floating-point is emulated by RISC-V integer instructions. Support the hashes for these words. Since there is no chance for ambiguity, for the next two alternatives is planned for the future, when demand we can simplify notation by identifying each node in the tree with for faster floating-point grows. the associated hash. Then, internal nodes v in the tree are built from their two children u1 and u2 by the relation 5 Cartesi Machines in the blockchain v = keccak(u1 , u2 ). (3) Here, keccak computes the hash of the concatenation of two input Recall that Cartesi is a platform for the development of decentralized hashes. The procedure builds a tree of depth 61. The set of nodes applications. Cartesi DApps enable parties that do not trust each at depth d partition the state into 2d ranges with 264−d bytes each. other to enter into a binding contract in the blockchain that depends Each node can therefore be identified by its depth and the starting on the results of off-chain computations. It is convenient to use the address a for its range, which is aligned to a 264−d boundary. characters Alice and Bob to represent these parties. Note that Alice and Bob are roles, not people. They may even represent competing Figure 5 shows a sample machine state s. It has the special property collective interests. In fact, both roles will be played automatically that devices have been aligned to nodes in m. For example, node v4 by Cartesi Nodes that defend the interests of whomever controls subtends everything in the machine apart from the flash devices. It the off-chain computer where the node runs. Cartesi DApps are covers the shadows of the processor and the board, the ROM, the therefore a collaboration between a set of smart contracts running CLINT and HTIF devices, and the RAM. Nodes v0 –v3 and v5 each in the blockchain, and the off-chain software running on Alice’s cover an independent flash device. and Bob’s nodes. As a general rule, the same DApp developer is responsible for the smart contracts and the Dapp specific off-chain 3 This eases integration with the Ethereum blockchain. Like Ethereum, software. The role of DApp developer will be played by Charlie. Cartesi assumes there is no practical way to engineer collisions for the keccak Alice and Bob trust Charlie, otherwise they would not engage with hash function. 8

Version 1.01 Moreover, given a valid proof for v in m, the same procedure can be used to attest that a root hash m0 results from replacing v in m with any given node v 0 . These verifications are very efficient, each requiring only d applications of the keccak hash. We are now ready to define the first two Cartesi primitives v = slice(m, a, d) and m0 = splice(m, a, d, v 0 ). (7) In the absence of disputes, slice returns v and splice returns the result m0 of replacing v in m with v 0 . To successfully defend these results in disputes, one can simply present siblings(m, a, d) and v to the blockchain. For convenience, Cartesi defines two additional primitives w = read(m, a) ⇔ keccak(w) = slice(m, a, 61), and (8) m0 = write(m, a, w0 ) = splice m, a, 61, keccak(w0 )  (9) for directly manipulating words, rather than hashes. Disputes can be resolved once the blockchain receives siblings(m, a, 61) and w. 5.2 The verification game The verification game [Feige and Kilian 1997] is a protocol that Figure 5: The way in which the blockchain and off-chain represen- allows an arbiter with limited computational resources to referee a tations for a machine state relate to each other. game between two computationally unlimited players. Its use in con- junction with Merkle trees was introduced by Canetti et al. [2011], and the application to blockchains first appeared in TrueBit [Teutsch and Reitwießner 2017]. In this scenario, the blockchain is the “ref- Think of s as the initial state for some machine. In this case, the eree”, and the “game” is between a “player” Bob that defends a result ROM will contain the devicetree describing the hardware, and RAM for an off-chain computation, and a “player” Alice that disputes it. will be preloaded with the Linux kernel. The particular choice of commands listed in /sbin/init in the root file-system (flash 0) Let s0 be the initial state for the computation, and sn its final state. decides what the machine does. It can, for example, perform an Recall that si+1 = step(si ) and mi = merkle(si ). The verification arbitrary computation over an input file-system (flash 1), and store game is the dispute resolution mechanism for Cartesi’s primitive results in an output file-system (flash 3). The computation can even mn = compute(m0 , n) = merkle step(n) (s0 ) .  be informed by the contents of an additional independent parameter (10) file-system (flash 2). It is divided into two stages. The first stage finds a single step of Now assume s halts in state s0 . From the blockchain’s perspective, computation on which Alice and Bob disagree. The final stage running m until it halts can be seen as the evaluation of an arbitrary effectively computes the step that follows. If it matches the state function v20 = f (v0 , v1 ). Here, v20 is the node in m0 = merkle(s0 ) proposed by Bob, he wins the dispute. Otherwise, Alice wins. that corresponds to v2 in m. Consider a library of hashes f , each corresponding to a different useful function. For example, one The disagreement step The interval [i, j], for i < j, is said to such function could decrypt the input file-system v0 into the output be a disagreement interval if the following two conditions are met: file-system v20 , taking a key from the parameter file-system v1 . To specify this computation in terms of Cartesi Machines with a single 1. Bob has sent to the blockchain hashes mi and mj , claiming hash m, a smart contract must build m from its components f , v0 , they correspond to merkle(si ) and merkle(sj ); and v1 . Once it receives m0 , it must be able to settle disputes over 2. Alice has manifested to the blockchain that she agrees with mi whether m indeed halts as m0 . Finally, it must be able to verify that but disagrees with mj . if v10 is the node in m0 that corresponds to v1 in m. A disagreement step is a disagreement interval where j − i = 1. The following property of Merkle trees is the foundation for all these When Alice disputes that mn = compute(m0 , n), the range [1, n] operations: Given a node v, its depth d in tree m, and the starting becomes the initial disagreement interval. A partition contract can address a for the associated memory range, it is possible to verify find the disagreement step with an interactive binary search, starting that v is indeed part of m. To see this, consider the path from v to m from [1, n]. At iteration `, the contract starts with a disagreement wd = v, wd−1 , . . . , w1 , w0 = m. (4) interval [i` , j` ]. It requests from Bob the hash mk` = merkle(sk` ), where k` is the middle point between i` and j` . Knowing Bob’s mk` , Then, given the siblings ui for every node wi in the path: Alice then chooses between [i`+1 , j`+1 ] = [i` , k` ] or [k` + 1, j` ] as ( the next disagreement interval. This continues until Alice selects an keccak(ui , wi ), if a ∧ 264−i , interval with length one. wi−1 = (5) keccak(wi , ui ), if ¬(a ∧ 264−i ). The procedure finishes after O(log n) interactions between Alice, Bob, and the partition contract.4 Any party that fails to react within For this reason, the sequence a pre-determined deadline looses the verification game by timeout. siblings(m, a, d) = (u1 , u2 , . . . , ud ) (6) At iteration `, Alice and Bob must independently obtain the state sk` for the machine. If the machine is always started from scratch, the serves as proof for the claim that v is at address a and depth d in m. To verify this, simply compute p0 from (5) and compare with m. 4 This can be reduced by changing to an n-ary search. 9

Version 1.01 total incurred off-chain computation is O(n log n). However, by several machines that exchange data with each other. An empty preserving a snapshot of si` , they can bring the cost down to O(n). DAG is first initialized with a call to: Settling the dispute At this point, the blockchain has found the dag = dag() disagreement step [i, i + 1], where i ∈ {0, . . . , n − 1}. It knows Each DAG vertex corresponds to a primitive. A primitive’s inputs both mi and mi+1 according to Bob. Alice agrees with mi , but dis- come from the outputs of its children vertices. The primitive’s output putes mi+1 . To decide the party with just cause, the blockchain must can in turn serve as input to one or more primitives. effectively compute m0i+1 = merkle step(si ) and compare it with Bob’s mi+1 . However, the blockchain does not have unrestricted Primitives are divided into two categories. Disputable primitives access to si . All it has is the root hash mi = merkle(si ). behave as future values promised to Alice by Bob. Their outputs are Alice is expected to post her off-chain state access log for step(si ) to set by Bob, and must be accepted or disputed by Alice. Disputable a memory manager contract. Off-chain, these accesses progressively primitives can only appear as internal vertices in the expression modify the state si = (si )0 into (si )1 , (si )2 , . . . until after the DAG. They are the read, write, slice, splice, step, and compute kth and last access it becomes (si )k = si+1 . All machine steps primitives described in sections 5.1 and 5.2. take O(1) time to simulate and number k of accesses is always small. Constant primitives have their outputs set by Charlie. They are are Entry j in the log, for j ∈ {1, . . . , k}, contains implicitly accepted by both Alice and Bob throughout their interac- 1. An operation oj for the access (read or write); tions with Charlie’s DApp. These primitives potentially represent 2. An address aj for the access; large chunks of data and the availability of their contents has to be 3. The word rj at aj in (si )j−1 ; guaranteed by Charlie, possibly with help from our data availability 30. In case of writes, the word wjat aj in (si )j ; primitives. Naturally, word, hash, string, and id literals are constants. 4. The siblings (mi )j−1 , aj , 61 . Cartesi’s blob, resource, and machine primitives, described below, are also constant. Only constant primitives can appear as DAG The blockchain implementation for the step function is hosted by leaves. an emulator contract. Alice’s off-chain implementation must match this blockchain implementation down to the order in which the state Cartesi supported constant and future types are: accesses are logged. As a benefit of this restriction, the blockchain implementation can read and write to the state as if its whole contents constant ::= word | hash | string | id disputable ::= word-future | hash-future were available. During its execution, the reference step function issues a sequence of state accesses to the memory manager. As long Constant primitives accept only constants as input. In contrast, as the accesses match Alice’s log, everything works transparently. disputable primitives accept both constants and disputables: Formally, as the reference step function performs k0 accesses, the word-type ::= word | word-future memory manager progressively updates mi = (m0i )0 to (m0i )1 , hash-type ::= hash | hash-future (m0i )2 , . . . , until it reaches (m0i )k0 . Access j, for j ∈ {1, . . . , k0 }, contains the following information Constant primitives Blob primitives represent arbitrary binary 1. An operation o0j for the access (read or write); data stored in the blockchain. The provided hash gives the output. 2. An address a0j for the access; It must match the root hash for a Merkle tree built from the data, 3. In case of writes, the word wj0 to be written. padded with zeros to 264−depth bytes: As each access is processed, the memory manager: hash = dag :blob{ hash = hash , • Checks that j ≤ k, o0j = oj , and a0j = aj ; depth = word , data = string • Checks that rj = read (m0i )j−1 , aj with the siblings. } Then, for a read access, the memory manager: Resource primitives describe files stored off-chain. Files are assumed • Sets (m0i )j = (mi )j−1 ; to be available from the given uri. The download-size can be • Returns rj to the emulator contract. used to bound, a priori, the total data transfer requirements. Only the first range-length bytes of the file are considered. This bounds For writes, the memory manager: the memory required to map it into the machine state. The provided hash output must match the root hash for a Merkle tree built from • Checks that wj0 = wj ; the first range-length bytes of the corresponding file, padded with • Sets (m0i )j = write (m0i )j−1 , aj , wj ) with the siblings. zeros or truncated to 264−depth bytes: At any point, if a check fails, Alice loses the dispute. If, however, hash = dag :resource{ k = k0 and mi+1 6= (m0i )k0 , Alice wins the dispute. hash = hash , depth = word , range-length = word , 5.3 Cartesi Machines as one of many primitives download-size = word , uri = string Cartesi primitives are made available to Charlie through a functional } programming interface. The goal is isolating the primitives from the idiosyncrasies of specific smart contract programming languages Machine primitives are used to describe Cartesi Machine states. The and blockchains. The syntax itself is not important. What matters is specification follows the scripting interface described in section 4.1. the semantics associated to each primitive. The only the difference is that backing files are given as paths. Instead, they are resource constants. The provided hash output Charlie can use this interface to build expression DAGs that represent must correspond to the root Merkle tree hash for the corresponding complex composite computations. The computations can involve Cartesi Machine state: 10

Version 1.01 hash = dag :machine{ word-future = dag :if{ hash = hash , condition = word-type , processor = processor , if-true = word-type , rom = rom , if-false = word-type ram = ram , } flash0 = drive , ... The hash primitive builds a 256-bit hash by the concatenation of its flash7 = drive , 64-bit component words: clint = clint , htif = htif hash-future = dag :word4(word-type , word-type , } word-type , word-type ) To help with Merkle tree construction, hashes can be built from Disputable primitives The compute primitive executes a Cartesi words and from the concatenation of two hashes: Machine. The initial-state gives the value of m0 and steps the value of n, so that the future value is compute(m0 , n). Steps hash-future = dag :keccak(word-type ) therefore bounds, a priori, the amount of computation required: hash-future = dag :keccak(hash-type , hash-type ) hash-future = dag :compute{ For completeness, hashes can also be tested for equality and used as initial-state = hash-type , input for a conditional: steps = word-type } word-future = dag :eq(hash-type , hash-type ) word-future = dag :neq(hash-type , hash-type ) The Merkle tree manipulation primitives slice, splice, read, and hash-future = dag :if{ write are available as: condition = word-type , hash-future = dag :slice{ if-true = hash-type , root = hash-type , if-false = hash-type address = word-type , } depth = word-type } DAG and vertex interfaces Charlie must define the identity of the players for the roles of Alice and Bob. Recall that Bob proposes hash-future = dag :splice{ a result and Alice can object or accept it: root = hash-type , address = word-type , dag :proposing-role{id = id , stake = word } depth = word-type , dag :objecting-role{id = id , stake = word } target = hash-type } The stake argument gives the price for buying Alice’s or Bob’s word-future = dag :read{ position. It measures what is at stake for each of them depending on root = hash-type , the results of the computation. Charlie sets this value to facilitate address = word-type Alice and Bob to delegating their roles (section 6.2). } Primitive creation functions return: hash-future = dag :write{ root = hash-type , vertex ::= constant | disputable address = word-type , word = word-type A DAG may contain multiple disconnected sub-DAGs. To specify } or retrieve the root vertex for the DAG, Charlie invokes: Cartesi also provides a variety of simple primitives that increase the dag :root(vertex ) expressive power of expressions. Disputes over such primitives can This value can be later obtained by anyone that calls: be settled within the blockchain directly from their inputs. Several binary operations on words have the signature: vertex = dag :root() word-future = dag :bin-op (word-type , word-type ) The primitive for any vertex can be queried: and mirror the RISC-V ISA.They can be divided into arithmetic: primitive = vertex :primitive() primitive ::= word | hash | string | add, sub, mul, mulh, mulhu, mulhsu, blob | resource | machine | div, divu, rem, remu, sll, srl, sra; read | write | slice | splice | add | sub | ... | geu | if | bitwise: word4 | keccak | keccak-hh | eq-hh | if-hh or, and, xor; Likewise, the children can be obtained by name or index: and comparisons: vertex = vertex :child-by-index(word ) vertex = vertex :child-by-name(string ) eq, ne, lt, ltu, ge, geu. Together, the primitive and child functions enable the entire Signed integers are represented by two’s complement. Boolean sub-DAG reachable from a vertex to be traversed. values are returned as words where 1 means true and 0 means false. Conversely, when a Boolean value is expected by a conditional, 0 is The DAGs and vertices can change state during their lifetimes: considered false and any other value is considered true. dag-state ::= undefined | proposed | accepted | objected | sustained | overruled Conditionals are available as ternary if primitives whose output is set to if-true if condition is true, and if-false otherwise: vertex-state ::= undefined | proposed | accepted 11

Version 1.01 Constant vertices are always in the accepted state. At construction, the DAG and all its disputable vertices are in the undefined state. These states can be obtained from the DAG and vertex objects: dag-state = dag :state() vertex-state = vertex :state() Proposing the value of any vertex changes its state to proposed: Figure 6: Expression DAG corresponding to the decryptor example. Constant vertices corresponding to literal values have been omitted vertex :propose-hash(hash ) for brevity. Variable names are shown in gray. vertex :propose-word(word ) To start a proposal, Bob first invokes: An example The following example illustrates the power of the dag :start-proposal() expression DAG interface: Then, he proposes the output value for the root vertex. Finally, he d = dag() completes the proposal with a call to: decryptor = library{ dag :finish-proposal() hash = decryptor-machine-hash, dag = d This changes the DAG to the proposed state. } input = d:resource{ The value proposed for any vertex can be checked with a call to: hash = input-hash, depth = decryptor-flash-1-depth, word = vertex :proposed-word() uri = hash = vertex :proposed-hash() } To accept the proposed root for the DAG, Alice calls: key = d:blob{ hash = password-hash, dag :accept() depth = decryptor-flash-2-depth, data = password This changes the DAG state to accepted. } To object to the root value for the DAG, Alice invokes: loaded-decryptor = d:splice{ root = d:splice{ dag :start-objection() root = decryptor, address = decryptor-flash-1-addr, target = input and then proposes a new, distinct value for the root vertex. There }, are now two cases to consider. If all immediate children of the root address = decryptor-flash-2-addr vertex are in the accepted state, the dispute can be settled by the root target = key primitive resolution protocol. To that end, Alice simply calls: } dag :finish-objection() executed-decryptor = d:compute{ initial-state = loaded-decryptor, This changes the DAG to the objected state while the protocol is steps = 10*2^32 } completed. If Alice succeeds, the DAG is changed to the sustained state. Otherwise, it is changed to the overruled state. iflags = d:read{ root = executed-decryptor, If, however, there are any proposed or undefined children, she must address = machine-processor-iflags-addr, first propose values for all vertices in the sub-DAG reachable from } the root. Only then can she call: tohost = d:read{ root = executed-decryptor, dag :finish-objection() address = machine-htif-tohost-addr } This changes the DAG to the objected state. Bob must now find a vertex, accessible from the root, for which he accepts all inputs but halted = d:neq(d:and(iflags, 1), 0) objects to the output. To specify this vertex, Bob gives its path from done = d:eq(d:srl(d:and(tohost, d:srl(-1, 16)), 1), 0) success = d:and(halted, done) the root. He also must specify a distinct value for its output: d:root(success) dag :defend-word(path , word ) dag :defend-hash(path , hash ) In the example, Charlie defines an expression DAG with root success. path ::= {vertex1 , vertex2 , ..., vertexk } The implied computation starts with a decryptor machine, available from an off-line library (not shown). Charlie can install his own If the vertex is undefined, Alice’s dispute is declared ill-formed library of pre-defined machines in the Cartesi Node, or use a library and Bob wins immediately. If the path is invalid, Bob’s defense of machine specifications created and stored remotely by another is declared ill-formed and Alice wins immediately. Otherwise, the developer. Either way, the hash constant ensures machines that have primitive dispute resolution protocol is engaged. been tampered with can be easily identified. Next, input and key flash devices are spliced into the decryptor machine. This loaded- With this setup, arbitrarily complex expressions behave just like decryptor is run for at most 2*2^32 steps, and results in an executed- disputable Cartesi primitives: they have agreed-upon inputs and decryptor. The corresponding state is then probed. Inspection of come equipped with a dispute resolution procedure for their output. the processor’s iflags register tells if the machine is halted. The 12

Version 1.01 value stored in the payload of HTIF’s tohost register tells if the To download the data for all constant nodes in the main sub-DAG machine halted after it was done decrypting. Figure 6 shows the and verify the computed hashes match the declared hashes: corresponding DAG, with literal values (i.e., strings, words, and download-status = off-dag :download{timeout = word } hashes) omitted. download-status ::= accepted | failed | timedout Charlie oversees Alice’s and Bob’s interaction with the DAG and its vertices. After all, Charlie is responsible for the blockchain DApp Once download is complete, all vertices in the main sub-DAG can component where these objects live. Charlie’s software acting on be evaluated with a single call to: Alice or Bob’s behalf can issue events that trigger reactions from the Cartesi Nodes representing Alice and Bob. These reactions are also off-dag :evaluate() under Charlie’s control, since he is in charge of the off-chain DApp The upload method submits results back to the blockchain. It also components installed in their nodes. He must, as usual, protect his isolates DApp developers from the details of any potential dispute: DApp against attacks by rogue users. Cartesi simplifies part of this process by encapsulating access control in all DAG operations. off-dag :upload{fee = word } The fee argument is used for role delegation (section 6.2). 6 The Cartesi Node Let v be the root for the main sub-DAG. The upload method checks The Cartesi Node is the software and hardware infrastructure that whether the role being played is proposing or objecting. The propos- hosts the off-chain components of Cartesi DApps. Each user that ing role only acts if v is undefined in the blockchain. In that case, wishes to interact with a Cartesi DApp must have a Cartesi Node at it proposes the value it obtained off-chain for v. The objecting role his disposal. Cartesi Nodes will initially be made available as Docker only acts if a value for v has been proposed to the blockchain. If the containers to be run on a computer under the user’s responsibility. value matches what it obtained off-chain, it accepts the value. This Future plans include their distribution as a multi-platform library is how the overwhelming majority of interactions will play out. If, that developers can link to an executable for users to install as a however, the proposed value for v in the blockchain does not match self-contained DApp. the value computed off-chain, the objecting role starts a dispute. The ensuing interactions between the blockchain and the Cartesi Nodes DApps can include native off-chain components that access the full of both proposing and objecting roles are automatically handled by storage and computational power of the hardware where the node is Cartesi the platform. installed. In addition, all nodes contain a reference implementation of the Cartesi Machine that DApps can control to perform verifiable With the exception of the compute primitive, disputes can be settled computations. Finally, nodes contain the infrastructure necessary for right away. Compute primitives require multiple interactions with the interaction of off-chain and blockchain DApp components.5 the blockchain. If a party cannot guarantee the responsiveness of his Cartesi Node throughout a dispute, he could lose by default At the core level, the Cartesi platform gives DApp developers the judgement. To minimize this risk, Cartesi offers another convenience freedom to combine native code, reproducible Cartesi Machines, to DApp developers: the dispute delegation market. and the blockchain’s API in any way they see fit. Given the fast pace in which novel applications for blockchain technology appear, this 6.2 Dispute delegation market seems to be the only way to avoid restraining developers’ creativity. Nevertheless, we can foresee a variety of common tasks, challenges, A principal party can delegate potential disputes to a proxy by set- and patterns that are likely to arise when using the Cartesi platform. ting the fee argument of the upload method to a non-zero value. With time, the Cartesi platform will encapsulate these into a set of This causes Cartesi to advertise the disputed DAG in the dispute higher-level interfaces built on top of the core [Teixeira and Nehab delegation market. The advertising principal is notified as soon as a 2019a]. The core includes only facilities for the automated execution proxy purchases a dispute. Proxy candidates own Cartesi Nodes on and verification of Cartesi Machines. which Cartesi’s dispute proxy DApp has been enabled. Users of the proxy DApp are in the business of collecting fees for defending the 6.1 Off-chain expression DAGs interests of principal parties that are unwilling to conduct their own disputes. Off-chain DApp components need to interact with existing block- chain DAGs. After all, the computations implied by such DAGs The proxy DApp download an advertised DAG, computes its value must be performed off-chain within the Cartesi Node. These inter- off-chain, and checks if it matches the value proposed to the block- actions are mediated by off-chain representations for DAGs, which chain by the role for sale. If so, it can purchase the role for the stake can be automatically built from a blockchain instance with a call to: specified in the DAG. This amount will be returned if and only if the proxy wins the ensuing dispute. In that case, the proxy is also off-dag = off-dag(dag ) rewarded the fee. If the proxy fails in the dispute, the stake is instead sent to the principal party. Off-chain DAGs provide DApps with a high-level interface that completely encapsulates typical use cases. Guarantees Cartesi guarantees that an honest party can always Bounds for the data transfer, memory, and computation requirements win any dispute in which it is involved. This is a strong guarantee, for the main sub-DAG can be obtained from: but it is also the only guarantee. In the absence of disputes, the value for the DAG is defined to be whatever the interested parties bounds = off-dag :bounds() proposed and accepted. It is therefore perfectly reasonable to act on the accepted value, whether or not it is indeed the true result of bounds ::= { data = word, the computation defined by the DAG. Any unsatisfied party has the memory = word, responsibility of contesting the value. compute = word } Disputed values, however, may or may not be useful. The situation is truly exceptional: At least one of the parties is being dishonest, 5 In the case of Ethereum, a light client. perhaps even both are. The proper way forward must be decided 13

Version 1.01 by the DApp developer. One potentially useful bit of information should not be immediately passed to the proxy party. Other usability is whether the objection was overruled or sustained. Note that even constructs will be described to facilitate file transfers and reduce this bit is only true when at least one of the parties is honest. gas costs. Together, these facilities will bring the user experience of Cartesi DApps closer to that of current centralized solutions. Whenever a principal party wishes to delegate a dispute to a proxy, it has no way to guarantee its interests will be defended in good faith. The only solution is to align the interests of the principal and The Cartesi SDK A variety of higher-level APIs that encapsulate proxy. This is why proxy roles must be purchased by the principal’s typical uses for the core will be available with the release of the stake in the dispute. If the proxy is honest and wins the dispute on Cartesi SDK. These will include the usability and data availability the principal’s behalf, the only cost to the principal is the fee. He solutions described above, as well as the containers for the Cartesi may receive further benefits from the contract where the dispute Node and for the development of Cartesi Machines. In time, the APIs originated. If the proxy loses the dispute, whether on purpose or by available within the SDK will greatly reduce the size and complexity negligence, the principal keeps the stake. His interest in the original of DApps blockchain components. In turn, this will significantly contract becomes moot. increase the portability of DApps to multiple blockchains. The Cartesi SDK will be distributed in open source and extensively Naturally, no proxy will ever buy disputes from principals playing documented [Teixeira and Nehab 2019b]. dishonest roles. They are, as they should, on their own defending their interests. Even honest principals may fail to sell disputes if the fee is too low or the stakes too high. To guarantee service availability Extensions to the Cartesi Machine Cartesi Machines can be to honest principals, Cartesi will maintain a number of nodes with extended with two exciting new devices. The dehashing device the dispute proxy DApp installed. These nodes will be configured gives applications the power to traverse hash pointer data structures. to purchase, up to a maximum stake, advertised disputes that are Programs running inside a Cartesi Machine can use the dehashing profitable but have not found a proxy within a preset deadline. device to read the contents of a block given only its hash. Although this operation is impossible in general, it becomes possible when the universe of allowed blocks is known by all parties in advance. 7 Future work The most direct application is to blockchains themselves. When a Cartesi Machine is running, the dehashing device queries a hash The focus of this document on the core functionality, and on the table, preloaded in the host, for the block that matches the hash. If a interfaces DApps use to directly specify, control, and verify off-chain dispute arises, any party can propose the block as proof it matches the computations. The Cartesi platform will offer several additional required hash. In this way, the dehashing device enables blockchain components built over the core, or extending its reach. These will be introspection. Parties can enter into contracts that depend on the described in more detail in future publications [Teixeira and Nehab entire state of the blockchain where the contracts are themselves 2019a,b]. defined. This has a variety of valuable applications, notably in futures markets. Data availability Cartesi remedies the severe storage limitations of the blockchain by keeping on-chain only Merkel tree hashes of Another planned device is the timely data port. The port enables off-chain data. As mentioned in section 5.2, Cartesi assumes that all reproducible communication between Cartesi Machines by tying the parties involved in a verification role have access to these data. In data packets entering or leaving the machine to the value of mcycle certain applications, this is difficult to guarantee. In particular, the at the event. DApps can schedule packet delivery to happen at a risk for data withholding attacks, where one of the parties submits a given future mcycle. Cartesi Machines can also be rolled back to hash to the blockchain while refusing to make this data available to the mcycle for delivery. The timely data port breaks new ground in others, must be mitigated. the progress towards the Web 3.0. It will enable DApps that involve the direct collaboration between multiple Cartesi Machines. The problem of data availability is a major concern in the design of blockchain consensus algorithms [Buterin 2012]. However, the issue becomes much simpler in the context of local consensus. Teixeira Crowd disputes It is possible to envision applications that involve and Nehab [2019a] provide several design patterns for dealing with many independent participants, each with some stake in the results data availability during verification. Data channels, device encryp- of an off-chain computation. In such cases, it is vital to prevent a tion, and the data ledger ensure availability in all scenarios likely to coordinated crowd of dishonest participants from using sequential be encountered by Cartesi DApps. disputes over an honest result as a denial-of-service attack on the contract. We have developed a variant of the verification game that Usability One of the key barriers to the wide adoption of block- enables any honest participant to defend his result against an entire chain technology is the inconvenience experienced by DApp users. crowd at negligible cost. When demand becomes apparent, the Although the literature on usability of centralized applications still Cartesi platform will be extended to support this variant. applies to decentralized ones, blockchain idiosyncrasies have not yet been fully addressed from the perspective of user experience. Teixeira and Nehab [2019a] describe several design patterns for the 8 Conclusions development of simple and intuitive DApps. This paper laid the foundations on which the Cartesi platform stands. As an example, Cartesi will offer an automatic infrastructure for trad- Cartesi’s mission is to help DApp developers build ever more com- ing tokens. This will free the users from concerns over the different pelling products to their clients. As any paradigm shift, the block- tokens used inside each DApp. A system for outsourcing deferred chain brings both opportunity for real innovation and the risk of actions will also be provided. This will enable users to turn their ma- “wheel reinvention”. In a direct application of the principle of least chines off even when engaged in a protocol that requires interacting astonishment, Cartesi’s core enables developers to leverage pre- with the blockchain within strict deadlines. In this situation, a proxy existing knowledge and tools to boost their productivity. The re- party will act on the users’ behalf in exchange for a fee. (Much like maining components of the Cartesi platform, described in a future the dispute delegation market described in section 6.2.) The use of document [Teixeira and Nehab 2019a], will help developers unleash cryptographic time-locks [Rivest et al. 1996] will also accommodate their creativity when taking advantage of the blockchain’s unique situations in which the user must reveal a secret in the future that potentials. 14

Version 1.01 References H OUSER , J. 2017. Berkeley softfloat. Webpage. http://www. Release 3d. B ELLARD , F. 2016. Softfp library. Webpage. https://bellard. IEEE, C. S. 2008. Standard for floating-point arithmetic, IEEE Std org/softfp/. 754-2008. B ELLARD , F. 2017. Riscvemu. Source code. https://bellard. I E XEC ,T. 2017. Blockchain-based decentralized cloud org/riscvemu/. computing. English.pdf. B ELLARD , F. 2018. A generic and open source machine emulator and virtualizer. Webpage. L ARIMER , D. 2017. Dpos consensus algorithm - the missing white paper. B EN -S ASSON , E., B ENTOV, I., H ORESH , Y., and R IABZEV, M. consensus-algorithm-this-missing-white-paper. 2018. Scalable, transparent, and post-quantum secure computa- tional integrity. IACR Cryptology ePrint Archive, 2018:46. L EE , S., S HIH , M.-W., G ERA , P., K IM , T., K IM , H., and P EINADO , M. 2017. Inferring fine-grained control flow inside sgx enclaves B EN -S ASSON , E., C HIESA , A., T ROMER , E., and V IRZA , M. with branch shadowing. In 26th USENIX Security Symposium, 2013. Succinct non-interactive zero knowledge for a von neu- USENIX Security, 16–18. mann architecture. Cryptology ePrint Archive, Report 2013/879. M ERKLE , R. C. 1979. Secrecy, Authentication, and Public Key Systems. PhD thesis, Stanford University. B ITANSKY, N., C ANETTI , R., C HIESA , A., and T ROMER , E. 2012. From extractable collision resistance to succinct non- M IERS , I., G ARMAN , C., G REEN , M., and RUBIN , A. D. 2013. interactive arguments of knowledge, and back again. In Pro- Zerocoin: Anonymous distributed e-cash from bitcoin. http: ceedings of the 3rd Innovations in Theoretical Computer Science // Conference, ITCS ’12, New York, NY, USA. ACM, 326–349. M OGHIMI , A., I RAZOQUI , G., and E ISENBARTH , T. 2017. ISBN 978-1-4503-1115-1. CacheZoom: How SGX amplifies the power of cache attacks. 2090236.2090263. In International Conference on Cryptographic Hardware and B LUM , M., F ELDMAN , P., and M ICALI , S. 1988. Non-interactive Embedded Systems, 69–90. zero-knowledge and its applications. In Proceedings of the Twen- M ORRISON , D. R. 1968. Patricia—Practical Algorithm To Retrieve tieth Annual ACM Symposium on Theory of Computing, STOC Information Coded in Alphanumeric. Journal of the ACM, 15(4): ’88, New York, NY, USA. ACM, 103–112. ISBN 0-89791-264-0. 514–534. NAKAMOTO , S. 2009. Bitcoin: A peer-to-peer electronic cash B RASSER , F., M ÜLLER , U., D MITRIENKO , A., KOSTIAINEN , system. Whitepaper. K., C APKUN , S., and S ADEGHI , A.-R. 2017. Software grand NEO’ S VM. 2017. OpCodes. Source code. https://github. exposure: SGX cache attacks are practical. In 11th USENIX com/neo-project/neo-vm/blob/master/src/neo- Workshop on Offensive Technologies. vm/OpCode.cs. B UTERIN , V. 2012. A note on data availability and erasure cod- PARNO , B., H OWELL , J., G ENTRY, C., and R AYKOVA , M. 2013. ing. Pinocchio: Nearly practical verifiable computation. In 2013 IEEE note-on-data-availability-and-erasure-coding. Symposium on Security and Privacy, 238–252. B UTERIN , V. 2018. On sharding blockchains. Wiki. https:// P ETAZZONI , T. 2018. Buildroot. Website. https://buildroot. org. B UTERIN , V. 2018. Sharding. GitHub repository. https: RISC-V. 2018. GNU toolchain. GitHub repository. https:// // C ANETTI , R., R IVA , B., and ROTHBLUM , G. N. 2011. Practical RISC-V. 2018. Linux. GitHub repository. delegation of computation using multiple servers. In Proceed- riscv/riscv-linux. ings of the ACM Conference on Computer and Communications Security, 445–454. RISC-V. 2018. Poky: port of the Yocto project. GitHub repository. C ARDANO ’ S VM. 2017. IELE OpCodes. Source code. RISC-V. 2018. Project home. GitHub repository. https:// semantics/blob/master/ C HENG , R., Z HANG , F., KOS , J., H E , W., H YNES , N., J OHNSON , RISC-V. 2018. Proxy Kernel. GitHub repository. https:// N. M., J UELS , A., M ILLER , A., and S ONG , D. X. 2018. Eki- den: A platform for confidentiality-preserving, trustworthy, and R IVEST, R. L., S HAMIR , A., and WAGNER , D. A. 1996. Time-lock performant smart contract execution. CoRR, abs/1804.05141. puzzles and timed-release crypto. DTS PEC . 2017. Devicetree specification., Freescale S CHAEFFER , T. 2018. Zokrates. Semiconductors, IBM, Linaro, and ARM. http://devicetree. JacobEberhardt/ZoKrates. org. S ONG , C., W U , S., L IU , S., FANG , R., and L I , Q.-L. 2018. Dis- DWORKIN , M. J. 2015. SHA-3 standard: Permutation-based hash tributed cloud computing in trusted hardware. https://ankr. and extendable-output functions. Technical report. network/. E NIGMA , T. 2018. Enigma documentation. SONM, T. 2018. Sonm documentation. https://docs.sonm. protocol/. com/. F EIGE , U. and K ILIAN , J. 1997. Making games short. In Proceed- TEEX, T. 2018. TEEX—TEE-enabled eXecution platform for ings of STOC, 506–516. public blockchain. G OLEM , T. 2016. The golem project. T EIXEIRA , A. and N EHAB , D. 2019. Cartesi design patterns. crowdfunding/Golemwhitepaper.pdf. 15

Version 1.01 Whitepaper. To appear. T EIXEIRA , A. and N EHAB , D. 2019. The Cartesi SDK. To appear. T EUTSCH , J. and R EITWIESSNER , C. 2017. A scalable verification solution for blockchains. Whitepaper. https://people.cs.∼teutsch/papers/truebit.pdf. T ILLEY, A. 2018. Google, Tesla get behind chal- lenge to Arm chip design. The Information. https: // get-behind-challenge-to-arm-chip-design. T RÖGER , J., M IHO ČKA , D., and K EPPEL , D. 2011. Fast mi- crocode interpretation with transactional commit/abort. In 4th Workshop on Architectural and Microarchitectural Support for Binary Translation, San Jose, CA. http://www.emulators. com/docs/amas-bt2011.pdf. VAN S ABERHANGEN , N. 2013. Cryptonote v 2.0. V LASENKO , D. 2018. Busybox. Website. WATERMAN , A. and A SANOVI Ć , K. 2017. The RISC-V Instruction Set Manual, volume I: User-Level ISA. RISC-V Foundation. Version 2.2. WATERMAN , A. and A SANOVI Ć , K. 2017. The RISC-V Instruc- tion Set Manual, volume II: Privileged Architecture. RISC-V Foundation. Version 1.10. WATERMAN , A. and L EE , Y. 2011. Spike, a RISC-V ISA simula- tor. GitHub repository. isa-sim. W EBA SSEMBLY , C. G. 2018. WebAssembly specification, release 1.0. html. W EICHBRODT, N., K URMUS , A., P IETZUCH , P., and K APITZA , R. 2016. AsyncShock: Exploiting synchronisation bugs in Intel SGX enclaves. In European Symposium on Research in Computer Security, 440–457. W OOD , G. 2018. Ethereum: A secure decentralised generalised transaction ledger. Yellowpaper. https://ethereum.github. io/yellowpaper/paper.pdf. Byzantium version e94ebda – 2018-06-05. 16