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프로젝트로 돌아가기