bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 16쪽 중 3쪽
tional probability P
(
Hash (s) = Hash (s′)|s⁄=
s′) when p tends to one from below.
2.2.10. Hash used for the TON Blockchain. We are using the 256-bit
sha256 hash for the TON Blockchain for the time being. If it turns out to
be weaker than expected, it can be replaced by another hash function in the
future. The choice of the hash function is a congurable parameter of the
protocol, so it can be changed without hard forks as explained in 2.1.21 .
2.3 Blockchain State, Accounts and Hashmaps
We have noted above that any blockchain denes a certain global state, and
each block and each transaction denes a transformation of this global state.
Here we describe the global state used by TON blockchains.
2.3.1. Account IDs. The basic account IDs used by TON blockchains
or at least by its masterchain and Workchain Zeroare 256-bit integers,
assumed to be public keys for 256-bit Elliptic Curve Cryptography (ECC)
for a specic elliptic curve. In this way,
account_id : Account = uint 256 = 2256 (9)
Here Account is the account type , while account_id : Account is a specic
variable of type Account .
Other workchains can use other account ID formats, 256-bit or otherwise.
For example, one can use Bitcoin-style account IDs, equal to sha256 of an
ECC public key.
However, the bit length l of an account ID must be xed during the
creation of the workchain (in the masterchain), and it must be at least 64,
because the rst 64 bits of account_id are used for sharding and message
routing.
19
2.3. Blockchain State, Accounts and Hashmaps
2.3.2. Main component: Hashmaps . The principal component of the
TON blockchain state is a hashmap . In some cases we consider (partially
dened) maps h : 2n 99K 2m. More generally, we might be interested in
hashmaps h : 2n 99K X for a composite type X. However, the source (or
index) type is almost always 2n.
Sometimes, we have a default value empty : X, and the hashmap h :
2n→X is initialized by its default value i↦→ empty .
2.3.3. Example: TON account balances. An important example is given
by TON account balances. It is a hashmap
balance : Account → uint 128 (10)
mapping Account = 2256 into a TON coin balance of type uint 128 = 2128.
This hashmap has a default value of zero, meaning that initially (before the
rst block is processed) the balance of all accounts is zero.
2.3.4. Example: smart-contract persistent storage. Another example
is given by smart-contract persistent storage, which can be (very approxi-
mately) represented as a hashmap
storage : 2256 99K 2256 (11)
This hashmap also has a default value of zero, meaning that uninitialized
cells of persistent storage are assumed to be zero.
2.3.5. Example: persistent storage of all smart contracts. Because
we have more than one smart contract, distinguished by account_id , each
having its separate persistent storage, we must actually have a hashmap
Storage : Account 99K (2256 99K 2256) (12)
mapping account_id of a smart contract into its persistent storage.
2.3.6. Hashmap type. The hashmap is not just an abstract (partially
dened) function 2n 99K X; it has a specic representation. Therefore, we
suppose that we have a special hashmap type
Hashmap (n,X ) : Type (13)
corresponding to a data structure encoding a (partial) map 2n 99K X. We
can also write
Hashmap (n : nat )(X : Type ) : Type (14)
20
2.3. Blockchain State, Accounts and Hashmaps
or
Hashmap : nat → Type → Type (15)
We can always transform h : Hashmap (n,X ) into a map hget (h) : 2n→X ?.
Henceforth, we usually write h[i] instead of hget (h)(i):
h[i] :≡ hget (h)(i) :X ? for any i : 2n, h : Hashmap (n,X ) (16)
2.3.7. Denition of hashmap type as a Patricia tree. Logically, one
might dene Hashmap (n,X ) as an (incomplete) binary tree of depth n with
edge labels 0 and 1 and with values of type X in the leaves. Another way to
describe the same structure would be as a (bitwise) trie for binary strings of
length equal to n.
In practice, we prefer to use a compact representation of this trie, by
compressing each vertex having only one child with its parent. The result-
ing representation is known as a Patricia tree or a binary radix tree . Each
intermediate vertex now has exactly two children, labeled by two non-empty
binary strings, beginning with zero for the left child and with one for the
right child.
In other words, there are two types of (non-root) nodes in a Patricia tree:
Leaf (x), containing value x of type X.
Node (l,s l,r,s r), where l is the (reference to the) left child or subtree,
sl is the bitstring labeling the edge connecting this vertex to its left
child (always beginning with 0), r is the right subtree, and sr is the
bitstring labeling the edge to the right child (always beginning with 1).
A third type of node, to be used only once at the root of the Patricia tree,
is also necessary:
Root (n,s 0,t ), where n is the common length of index bitstrings of
Hashmap (n,X ), s0 is the common prex of all index bitstrings, and t
is a reference to a Leaf or a Node .
If we want to allow the Patricia tree to be empty, a fourth type of (root)
node would be used:
EmptyRoot (n), where n is the common length of all index bitstrings.
21
2.3. Blockchain State, Accounts and Hashmaps
We dene the height of a Patricia tree by
height (Leaf (x)) = 0 (17)
height
(
Node (l,s l,r,s r)
)
= height (l) + len (sl) = height (r) + len (sr)
(18)
height
(
Root (n,s 0,t )
)
= len (s0) + height (t) =n (19)
The last two expressions in each of the last two formulas must be equal. We
use Patricia trees of height n to represent values of type Hashmap (n,X ).
If there are N leaves in the tree (i.e., our hashmap contains N values),
then there are exactly N− 1 intermediate vertices. Inserting a new value
always involves splitting an existing edge by inserting a new vertex in the
middle and adding a new leaf as the other child of this new vertex. Deleting
a value from a hashmap does the opposite: a leaf and its parent are deleted,
and the parent's parent and its other child become directly linked.
2.3.8. Merkle-Patricia trees. When working with blockchains, we want
to be able to compare Patricia trees (i.e., hash maps) and their subtrees,
by reducing them to a single hash value. The classical way of achieving
this is given by the Merkle tree. Essentially, we want to describe a way of
hashing objects h of type Hashmap (n,X ) with the aid of a hash function
Hash dened for binary strings, provided we know how to compute hashes
Hash (x) of objects x : X (e.g., by applying the hash function Hash to a
binary serialization of object x).
One might dene Hash (h) recursively as follows:
Hash
(
Leaf (x)
)
:= Hash (x) (20)
Hash
(
Node (l,s l,r,s r)
)
:= Hash
(
Hash (l). Hash (r). code (sl). code (sr)
)
(21)
Hash
(
Root (n,s 0,t )
)
:= Hash
(
code (n). code (s0). Hash (t)
)
(22)
Here s.t denotes the concatenation of (bit) strings s and t, and code (s) is
a prex code for all bit strings s. For example, one might encode 0 by 10, 1
by 11, and the end of the string by 0. 5
5 One can show that this encoding is optimal for approximately half of all edge labels
of a Patricia tree with random or consecutive indices. Remaining edge labels are likely to
be long (i.e., almost 256 bits long). Therefore, a nearly optimal encoding for edge labels
is to use the above code with prex 0 for short bit strings, and encode 1, then nine bits
containing length l =|s| of bitstring s, and then the l bits of s for long bitstrings (with
l≥ 10).
22
2.3. Blockchain State, Accounts and Hashmaps
We will see later (cf. 2.3.12 and 2.3.14 ) that this is a (slightly tweaked)
version of recursively dened hashes for values of arbitrary (dependent) al-
gebraic types.
2.3.9. Recomputing Merkle tree hashes. This way of recursively den-
ing Hash (h), called a Merkle tree hash , has the advantage that, if one explic-
itly stores Hash (h′) along with each node h′ (resulting in a structure called a
Merkle tree , or, in our case, a MerklePatricia tree ), one needs to recompute
only at most n hashes when an element is added to, deleted from or changed
in the hashmap.
In this way, if one represents the global blockchain state by a suitable
Merkle tree hash, it is easy to recompute this state hash after each transac-
tion.
2.3.10. Merkle proofs. Under the assumption (7) of injectivity of the
chosen hash function Hash , one can construct a proof that, for a given value
z of Hash (h), h : Hashmap (n,X ), one has hget (h)(i) = x for some i : 2n
and x :X. Such a proof will consist of the path in the MerklePatricia tree
from the leaf corresponding to i to the root, augmented by the hashes of all
siblings of all nodes occurring on this path.
In this way, a light node 6 knowing only the value of Hash (h) for some
hashmap h (e.g., smart-contract persistent storage or global blockchain state)
might request from a full node 7 not only the value x =h[i] = hget (h)(i), but
such a value along with a Merkle proof starting from the already known value
Hash (h). Then, under assumption (7), the light node can check for itself
that x is indeed the correct value of h[i].
In some cases, the client may want to obtain the value y = Hash (x) =
Hash (h[i]) insteadfor example, if x itself is very large (e.g., a hashmap
itself). Then a Merkle proof for (i,y ) can be provided instead. If x is a
hashmap as well, then a second Merkle proof starting from y = Hash (x)
may be obtained from a full node, to provide a value x[j] =h[i][j] or just its
hash.
6 A light node is a node that does not keep track of the full state of a shardchain;
instead, it keeps minimal information such as the hashes of the several most recent blocks,
and relies on information obtained from full nodes when it becomes necessary to inspect
some parts of the full state.
7 A full node is a node keeping track of the complete up-to-date state of the shardchain
in question.
23
2.3. Blockchain State, Accounts and Hashmaps
2.3.11. Importance of Merkle proofs for a multi-chain system such
as TON. Notice that a node normally cannot be a full node for all shard-
chains existing in the TON environment. It usually is a full node only for
some shardchainsfor instance, those containing its own account, a smart
contract it is interested in, or those that this node has been assigned to be
a validator of. For other shardchains, it must be a light nodeotherwise
the storage, computing and network bandwidth requirements would be pro-
hibitive. This means that such a node cannot directly check assertions about
the state of other shardchains; it must rely on Merkle proofs obtained from
full nodes for those shardchains, which is as safe as checking by itself unless
(7) fails (i.e., a hash collision is found).
2.3.12. Peculiarities of TON VM. The TON VM or TVM (TON Virtual
Machine), used to run smart contracts in the masterchain and Workchain
Zero, is considerably dierent from customary designs inspired by the EVM
(Ethereum Virtual Machine): it works not just with 256-bit integers, but ac-
tually with (almost) arbitrary records, structures, or sum-product types,
making it more suitable to execute code written in high-level (especially func-
tional) languages. Essentially, TVM uses tagged data types, not unlike those
used in implementations of Prolog or Erlang.
One might imagine rst that the state of a TVM smart contract is not
just a hashmap 2256 → 2256, or Hashmap (256, 2256), but (as a rst step)
Hashmap (256,X ), where X is a type with several constructors, enabling it
to store, apart from 256-bit integers, other data structures, including other
hashmaps Hashmap (256,X ) in particular. This would mean that a cell of
TVM (persistent or temporary) storageor a variable or an element of an
array in a TVM smart-contract codemay contain not only an integer, but
a whole new hashmap. Of course, this would mean that a cell contains not
just 256 bits, but also, say, an 8-bit tag, describing how these 256 bits should
be interpreted.
In fact, values do not need to be precisely 256-bit. The value format
used by TVM consists of a sequence of raw bytes and references to other
structures, mixed in arbitrary order, with some descriptor bytes inserted
in suitable locations to be able to distinguish pointers from raw data (e.g.,
strings or integers); cf. 2.3.14 .
This raw value format may be used to implement arbitrary sum-product
algebraic types. In this case, the value would contain a raw byte rst, de-
scribing the constructor being used (from the perspective of a high-level
24
2.3. Blockchain State, Accounts and Hashmaps
language), and then other elds or constructor arguments, consisting of
raw bytes and references to other structures depending on the constructor
chosen (cf. 2.2.5 ). However, TVM does not know anything about the corre-
spondence between constructors and their arguments; the mixture of bytes
and references is explicitly described by certain descriptor bytes. 8
The Merkle tree hashing is extended to arbitrary such structures: to
compute the hash of such a structure, all references are recursively replaced
by hashes of objects referred to, and then the hash of the resulting byte string
(descriptor bytes included) is computed.
In this way, the Merkle tree hashing for hashmaps, described in 2.3.8 , is
just a special case of hashing for arbitrary (dependent) algebraic data types,
applied to type Hashmap (n,X ) with two constructors. 9
2.3.13. Persistent storage of TON smart contracts. Persistent storage
of a TON smart contract essentially consists of its global variables, pre-
served between calls to the smart contract. As such, it is just a product,
tuple, or record type, consisting of elds of the correct types, correspond-
ing to one global variable each. If there are too many global variables, they
cannot t into one TON cell because of the global restriction on TON cell
size. In such a case, they are split into several records and organized into a
tree, essentially becoming a product of products or product of products of
products type instead of just a product type.
2.3.14. TVM Cells. Ultimately, the TON VM keeps all data in a collection
of (TVM) cells . Each cell contains two descriptor bytes rst, indicating how
many bytes of raw data are present in this cell (up to 128) and how many
references to other cells are present (up to four). Then these raw data bytes
and references follow. Each cell is referenced exactly once, so we might have
included in each cell a reference to its parent (the only cell referencing this
one). However, this reference need not be explicit.
In this way, the persistent data storage cells of a TON smart contract
are organized into a tree, 10 with a reference to the root of this tree kept in
8 These two descriptor bytes, present in any TVM cell, describe only the total number
of references and the total number of raw bytes; references are kept together either before
or after all raw bytes.
9 Actually, Leaf and Node are constructors of an auxiliary type, HashmapAux (n, X).
Type Hashmap (n, X) has constructors Root and EmptyRoot , with Root containing a
value of type HashmapAux (n, X).
10 Logically; the bag of cells representation described in 2.5.5 identies all duplicate
25
2.3. Blockchain State, Accounts and Hashmaps
the smart-contract description. If necessary, a Merkle tree hash of this entire
persistent storage is recursively computed, starting from the leaves and then
simply replacing all references in a cell with the recursively computed hashes
of the referenced cells, and subsequently computing the hash of the byte
string thus obtained.
2.3.15. Generalized Merkle proofs for values of arbitrary algebraic
types. Because the TON VM represents a value of arbitrary algebraic type
by means of a tree consisting of (TVM) cells, and each cell has a well-dened
(recursively computed) Merkle hash, depending in fact on the whole subtree
rooted in this cell, we can provide generalized Merkle proofs for (parts of)
values of arbitrary algebraic types, intended to prove that a certain subtree
of a tree with a known Merkle hash takes a specic value or a value with a
specic hash. This generalizes the approach of 2.3.10 , where only Merkle
proofs for x[i] =y have been considered.
2.3.16. Support for sharding in TON VM data structures. We have
just outlined how the TON VM, without being overly complicated, sup-
ports arbitrary (dependent) algebraic data types in high-level smart-contract
languages. However, sharding of large (or global) smart contracts requires
special support on the level of TON VM. To this end, a special version
of the hashmap type has been added to the system, amounting to a map
Account 99KX. This map might seem equivalent to Hashmap (m,X ), where
Account = 2m. However, when a shard is split in two, or two shards are
merged, such hashmaps are automatically split in two, or merged back, so as
to keep only those keys that belong to the corresponding shard.
2.3.17. Payment for persistent storage. A noteworthy feature of the
TON Blockchain is the payment exacted from smart contracts for storing
their persistent data (i.e., for enlarging the total state of the blockchain). It
works as follows:
Each block declares two rates, nominated in the principal currency of
the blockchain (usually the TON coin): the price for keeping one cell in the
persistent storage, and the price for keeping one raw byte in some cell of the
persistent storage. Statistics on the total numbers of cells and bytes used by
each account are stored as part of its state, so by multiplying these numbers
by the two rates declared in the block header, we can compute the payment
cells, transforming this tree into a directed acyclic graph (dag) when serialized.
26
2.3. Blockchain State, Accounts and Hashmaps
to be deducted from the account balance for keeping its data between the
previous block and the current one.
However, payment for persistent storage usage is not exacted for every
account and smart contract in each block; instead, the sequence number of
the block where this payment was last exacted is stored in the account data,
and when any action is done with the account (e.g., a value transfer or a
message is received and processed by a smart contract), the storage usage
payment for all blocks since the previous such payment is deducted from
the account balance before performing any further actions. If the account's
balance would become negative after this, the account is destroyed.
A workchain may declare some number of raw data bytes per account
to be free (i.e., not participating in the persistent storage payments) in
order to make simple accounts, which keep only their balance in one or two
cryptocurrencies, exempt from these constant payments.
Notice that, if nobody sends any messages to an account, its persistent
storage payments are not collected, and it can exist indenitely. However,
anybody can send, for instance, an empty message to destroy such an account.
A small incentive, collected from part of the original balance of the account
to be destroyed, can be given to the sender of such a message. We expect,
however, that the validators would destroy such insolvent accounts for free,
simply to decrease the global blockchain state size and to avoid keeping large
amounts of data without compensation.
Payments collected for keeping persistent data are distributed among the
validators of the shardchain or the masterchain (proportionally to their stakes
in the latter case).
2.3.18. Local and global smart contracts; smart-contract instances.
A smart contract normally resides just in one shard, selected according to the
smart contract's account_id , similarly to an ordinary account. This is usu-
ally sucient for most applications. However, some high-load smart con-
tracts may want to have an instance in each shardchain of some workchain.
To achieve this, they must propagate their creating transaction into all shard-
chains, for instance, by committing this transaction into the프로젝트로 돌아가기