Cartesi 백서

Cartesi

원문

bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 5쪽 중 3쪽

it (aligned) word in the address space: word = machine :word{address = word } 6 V ersion 1.01 To backup the contents of the memory range associated to any component of the machine state, simply choose a file to store it: bool = machine :backup{ processor = path , rom = path , ram = path , flash0 = path , ... flash7 = path , clint = path , htif = path , } The machine exposes its entire state as a Merkle tree [ Merkle 1979]. (For more on Merkle trees, see section 5.) It returns a proof that a tar- get node belongs to the Merkle tree, given its address and depth: proof = machine :prove{ address = word , depth = word } proof ::= { address = word , depth = word , root = hash , siblings = { hash1,. . . , hashdepth}, target = hash } The entries used for the initialization of individual devices can also be queried from their base address. The hash of the node at the address and depth is returned along with the entry. If the base address does not correspond to any device, or if the range length implied by the depth causes it to overlap with more than one device, an error is reported: slice = machine :slice{ address = word , depth = word } slice ::= { hash = hash , type = string , device = device } device ::= processor | rom | ram | drive | clint | htif The step function advances the machine 1 cycle, logging every single access to the state along the way. All accesses are 64-bit aligned. Each log entry specifies the operation (read or write), the address, and the word read or written. In addition, each entry includes the proof produced by a corresponding call to proof for the address prior to the access. log = machine :step() log ::= { access1, access2,. . . , accessk} access ::= { operation = read | write, read = word , written = word , proof = proof } The importance of functions prove, slice, and step, and the convenience of this interface will become clear in section 5. 4.2 Reference implementation Cartesi’s reference off-chain implementation is based on software emulation. The emulator is written in C/C++ with POSIX depen- dencies restricted to the terminal, process, and memory-mapping facilities. It is distributed as a library and scriptable in the Lua programming language according to the interface described above. Backing files for RAM and file-system images take advantage of the host’s support for sparse files. Only non-zero blocks take disk space. This enables the entire state of the machine to be specified in a convenient and compact form. The snapshot and rollback mechanism, as well as the shared attribute for backing files, are built on top of the host’s support for virtual memory, using child processes and memory-mapped files with copy-on-write semantics. This makes them at the same time very simple to implement and very efficient. The functionality for Merkle tree inspection requires additional support. For storage efficiency, the Merkle tree is maintained in its PA TRICIA form [Morrison 1968]. For time efficiency, the tree is updated only when needed, in a lazy fashion. Each PMA range has a bitmap of dirty pages associated to it. Pages of physical memory 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 Merkle tree. The update proceeds bottom up, by visiting only the nodes that subtend the dirty pages. After the update, all bitmaps and TLB entries are marked clean. 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 future, the emulator will avoid repeated decoding of hot execution traces [Tröger et al. 2011]. It is possible to translate these traces to the host instruction set for even better performance [ Bellard 2018]. However, the additional gains must be weighted against the reduced portability and significantly increased complexity. 4.3 Floating-point support Floating-point operations are prevalent off-chain (except, perhaps, in the context of embedded devices). Therefore, programmers expect them to be available. If Cartesi hopes to bring a sense of normalcy to blockchain development, it must support floating-point operations. The difficulty is guaranteeing reproducibility. Different floating-point implementations can disagree subtly when ostensibly performing the same operation on the same operands. Some of these differences arise from laxities in the IEEE 754-1985 standard. Although many of these have been tightened in the 2008 revision, several details remain unspecified. These include, but are not limited to, underflows, the sign of zero, operations involv- ing infinity or NaNs, and the quantum for the rounding of certain recommended operations (e.g., sin, log etc). Moreover, hardware implementations often take performance shortcuts that violate the standards they claim to adhere to. This leads to inconsistencies even across successive generations of the same architecture. These issues argue strongly against adding floating-point support to any verifiable computation model. Accordingly, most blockchains wisely omit them entirely [ Nakamoto 2009; Wood 2018; NEO’s VM 2017; Cardano’s VM 2017]. The only way to guarantee consensus is to emulate floating-point operations with a consistent software layer based on integer operations. Unlike floating-point operations, these are portable across different architectures. In the RISC-V ISA, floating-point support is defined by extensions F and D (respectively for single- and double-precision). Together, these extensions augment the ISA with 32 floating-point registers, 1 control-status register, 30 new instructions, and 1 new instruction format. The specification adheres strictly to the IEEE 754-2008 standard [ IEEE 2008]. Furthermore, it is limited to the required arithmetic operations that are fully specified. 7 V ersion 1.01 There are many options for adding floating-point support to Cartesi. In the first two approaches, the ISA does not include the F or D extensions. Therefore, they require no changes to the blockchain and off-chain implementations. Emulation by RISC-V code: traps When a RISC-V machine does not support floating-point instructions, it raises a machine- level illegal-instruction exception whenever one is found. The idea is to use an exception handler installed by BBL to emulate the corresponding floating-point instruction using RISC-V integer in- structions. This process is transparent to the supervisor and user levels, which work as if the ISA supported floating-point operations natively. Emulation by RISC-V code: compiler Alternatively, the com- piler can be instructed to target a RISC-V ISA that does not include floating-point operations. It substitutes them with calls to emulation routines it provides itself. The resulting binaries do not include floating-point instructions at all. This method is more efficient than using traps because it avoids the exception and decoding overhead. The next two approaches add the F or D extensions to the ISA. Naturally, this means the off-chain machine must implement all RISC-V floating-point instructions. Furthermore, the blockchain verifier must include a perfectly matching implementation. Emulation by native integers In this approach, floating-point instructions are still emulated off-chain. However, the emulation now uses native integer instructions, rather than RISC-V integer instructions. There are several high-quality open-source soft-float implementations from which to choose [ Bellard 2016; Houser 2017]. This makes the off-chain machine even faster. Native off-chain floating-point The next step in performance comes from using native floating-point instructions off-chain. Ob- taining reproducible results from two distinct fully conforming IEEE 754-2008 implementations requires the cooperation between language standards, compilers, and, most regrettably, users. The prospects are improved in Cartesi’s context, since the reference im- plementation controls all these components and can fully specify any omissions in the standard. These corner cases include, but are not limited to, underflows, the sign of zero, and operations involv- ing infinity or NaNs. Even with the added overhead, this approach should be the fastest one off-chain. At present, the emulator makes the first two options available, that is, floating-point is emulated by RISC-V integer instructions. Support for the next two alternatives is planned for the future, when demand for faster floating-point grows. 5 Cartesi Machines in the blockchain Recall that Cartesi is a platform for the development of decentralized applications. Cartesi DApps enable parties that do not trust each other to enter into a binding contract in the blockchain that depends on the results of off-chain computations. It is convenient to use the characters Alice and Bob to represent these parties. Note that Alice and Bob are roles, not people. They may even represent competing collective interests. In fact, both roles will be played automatically by Cartesi Nodes that defend the interests of whomever controls the off-chain computer where the node runs. Cartesi DApps are therefore a collaboration between a set of smart contracts running in the blockchain, and the off-chain software running on Alice’s and Bob’s nodes. As a general rule, the same DApp developer is responsible for the smart contracts and the Dapp specific off-chain software. The role of DApp developer will be played by Charlie. Alice and Bob trust Charlie, otherwise they would not engage with his DApp. Charlie, however, trusts neither Alice nor Bob. Naturally, Alice and Bob do not trust each other either. 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 adversarial interactions between Alice and Bob. Some primitives require no interaction, and can be evaluated autonomously in the blockchain from their inputs. The interesting primitives, however, are those that, though completely defined by their inputs, can only be evaluated off-chain. By construction, when using a Cartesi DApp, Alice and Bob always agree on the inputs to such primitives. Without loss of generality, Bob evaluates the primitive off-chain and submits 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 purpose of his choice. In case of rejection, Cartesi engages with Alice and Bob in a dispute resolution protocol that arbitrates in favor of the party with just cause. This adjudication always completes within a few interactions and at a negligible computational cost to the blockchain. Cartesi automates most of this process in a way that is extremely convenient to Charlie. The most important of these primitives is the Cartesi Machine. Smart contracts cannot afford to store the states for a Cartesi Machine within the blockchain, let alone perform the implied computations. After all, the costs in terms of processing power and storage capacity would both be prohibitive. To solve these problems, Cartesi uses cryptographic hashes to concisely represent machine states in the blockchain. From the blockchain’s perspective, a computation is simply a pair of hashes corresponding to the initial and final states of the machine. The contents of the memory subtended by such hashes are known only off-chain. Cartesi defines a variety of additional primitives that allow smart contracts to conveniently manipulate the contents of the states corresponding to these hashes. 5.1 Machine state representation by hashes Merkle trees [Merkle 1979] are binary trees where each node con- tains a hash. In Cartesi, Merkle trees are based on the keccak hash function [Dworkin 2015].3 Let s be a Cartesi Machine state, giving the entire contents of its 64-bit address space. The Merkle tree m for s, or, equivalently, its root node, is m = merkle(s). (2) The tree is built up from its leaves in the following way. First, the state is partitioned into 261 64-bit words. The tree leaves contain the hashes for these words. Since there is no chance for ambiguity, we can simplify notation by identifying each node in the tree with the associated hash. Then, internal nodes v in the tree are built from their two children u1 and u2 by the relation v = keccak(u1,u 2). (3) Here, keccak computes the hash of the concatenation of two input hashes. The procedure builds a tree of depth 61. The set of nodes at depth d partition the state into 2d ranges with 264d bytes each. Each node can therefore be identified by its depth and the starting address a for its range, which is aligned to a 264d boundary. Figure 5 shows a sample machine state s. It has the special property that devices have been aligned to nodes in m. For example, node v4 subtends everything in the machine apart from the flash devices. It covers the shadows of the processor and the board, the ROM, the CLINT and HTIF devices, and the RAM. Nodes v0–v3 and v5 each cover an independent flash device. 3This eases integration with the Ethereum blockchain. Like Ethereum, Cartesi assumes there is no practical way to engineer collisions for the keccak hash function. 8 V ersion 1.01 Figure 5: The way in which the blockchain and off-chain represen- tations for a machine state relate to each other . Think of s as the initial state for some machine. In this case, the ROM will contain the devicetree describing the hardware, and RAM will be preloaded with the Linux kernel. The particular choice of commands listed in /sbin/init in the root file-system (flash 0) decides what the machine does. It can, for example, perform an arbitrary computation over an input file-system (flash 1), and store results in an output file-system (flash 3). The computation can even be informed by the contents of an additional independent parameter file-system (flash 2). Now assume s halts in state s0. From the blockchain’s perspective, running m until it halts can be seen as the evaluation of an arbitrary function v02 = f (v0,v 1). Here, v02 is the node in m0 = merkle(s0) that corresponds to v2 in m. Consider a library of hashes f , each corresponding to a different useful function. For example, one such function could decrypt the input file-system v0 into the output file-system v02, taking a key from the parameter file-system v1.T o specify this computation in terms of Cartesi Machines with a single hash m, a smart contract must build m from its components f , v0, and v1. Once it receives m0, it must be able to settle disputes over whether m indeed halts as m0. Finally, it must be able to verify that if v01 is the node in m0 that corresponds to v1 in m. The following property of Merkle trees is the foundation for all these operations: Given a node v, its depth d in tree m, and the starting address a for the associated memory range, it is possible to verify that v is indeed part of m. To see this, consider the path from v to m wd = v, w d1,. . . ,w 1,w 0 = m. (4) Then, given the siblings ui for every node wi in the path: wi1 = ( keccak(ui,w i), if a ^ 264i, keccak(wi,u i), if ¬(a ^ 264i). (5) For this reason, the sequence siblings(m, a, d)=( u1,u 2,...,u d) (6) 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. 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 v0. 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, v0). (7) In the absence of disputes, slice returns v and splice returns the result m0 of replacing v in m with v0. 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)= splicem, 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 allows an arbiter with limited computational resources to referee a 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- eree”, and the “game” is between a “player” Bob that defends a result for an off-chain computation, and a “player” Alice that disputes it. Let s0 be the initial state for the computation, and sn its final state. Recall that si+1 = step(si) and mi = merkle(si). The verification game is the dispute resolution mechanism for Cartesi’s primitive mn = compute(m0,n )= merkle step(n)(s0). (10) It is divided into two stages. The first stage finds a single step of computation on which Alice and Bob disagree. The final stage effectively computes the step that follows. If it matches the state proposed by Bob, he wins the dispute. Otherwise, Alice wins. The disagreement step The interval [i, j], for i<j , is said to be a disagreement interval if the following two conditions are met: 1. Bob has sent to the blockchain hashes mi and mj , claiming they correspond to merkle(si) and merkle(sj ); 2. Alice has manifested to the blockchain that she agrees with mi but disagrees with mj . A disagreement step is a disagreement interval where j i =1 . When Alice disputes that mn = compute(m0,n ), the range [1,n ] becomes the initial disagreement interval. A partition contract can find the disagreement step with an interactive binary search, starting from [1,n ]. At iteration `, the contract starts with a disagreement 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` , 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 interval with length one. The procedure finishes after O(log n) interactions between Alice, Bob, and the partition contract. 4 Any party that fails to react within a pre-determined deadline looses the verification game by timeout. At iteration `, Alice and Bob must independently obtain the state sk` for the machine. If the machine is always started from scratch, the 4This can be reduced by changing to an n-ary search. 9 V ersion 1.01 total incurred off-chain computation is O(n log n). However, by preserving a snapshot of si` , they can bring the cost down to O(n). Settling the dispute At this point, the blockchain has found the disagreement step [i, i +1 ], where i 2 {0,...,n 1}. It knows both mi and mi+1 according to Bob. Alice agrees with mi, but dis- putes mi+1. To decide the party with just cause, the blockchain must effectively compute m0i+1 = merklestep(si) and compare it with Bob’s mi+1. However, the blockchain does not have unrestricted access to si. All it has is the root hash mi = merkle(si). Alice is expected to post her off-chain state access log for step(si) to a memory manager contract. Off-chain, these accesses progressively modify the state si =( si)0 into (si)1, (si)2,... until after the kth and last access it becomes (si)k = si+1. All machine steps take O(1) time to simulate and number k of accesses is always small. Entry j in the log, for j 2 {1,...,k }, contains 1. An operation oj for the access (read or write); 2. An address aj for the access; 3. The word rj at aj in (si)j1; 30. In case of writes, the word wj at aj in (si)j ; 4. The siblings (mi)j1,a j , 61 . The blockchain implementation for the step function is hosted
프로젝트로 돌아가기