Gram 백서

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