Gram 백서

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

root shardchain (w,∅)11 of the workchain w and paying a large commission. 12 11 A more expensive alternative is to publish such a global smart contract in the mas- terchain. 12 This is a sort of broadcast feature for all shards, and as such, it must be quite expensive. 27 2.3. Blockchain State, Accounts and Hashmaps This action eectively creates instances of the smart contract in each shard, with separate balances. Originally, the balance transferred in the creating transaction is distributed simply by giving the instance in shard (w,s ) the 2−|s| part of the total balance. When a shard splits into two child shards, balances of all instances of global smart contracts are split in half; when two shards merge, balances are added together. In some cases, splitting/merging instances of global smart contracts may involve (delayed) execution of special methods of these smart contracts. By default, the balances are split and merged as described above, and some special account-indexed hashmaps are also automatically split and merged (cf. 2.3.16 ). 2.3.19. Limiting splitting of smart contracts. A global smart contract may limit its splitting depth d upon its creation, in order to make persistent storage expenses more predictable. This means that, if shardchain (w,s ) with |s|≥ d splits in two, only one of two new shardchains inherits an instance of the smart contract. This shardchain is chosen deterministically: each global smart contract has some  account_id , which is essentially the hash of its creating transaction, and its instances have the same account_id with the rst ≤d bits replaced by suitable values needed to fall into the correct shard. This account_id selects which shard will inherit the smart-contract instance after splitting. 2.3.20. Account/Smart-contract state. We can summarize all of the above to conclude that an account or smart-contract state consists of the following: ˆ A balance in the principal currency of the blockchain ˆ A balance in other currencies of the blockchain ˆ Smart-contract code (or its hash) ˆ Smart-contract persistent data (or its Merkle hash) ˆ Statistics on the number of persistent storage cells and raw bytes used ˆ The last time (actually, the masterchain block number) when payment for smart-contract persistent storage was collected 28 2.4. Messages Between Shardchains ˆ The public key needed to transfer currency and send messages from this account (optional; by default equal to account_id itself). In some cases, more sophisticated signature checking code may be located here, similar to what is done for Bitcoin transaction outputs; then the account_id will be equal to the hash of this code. We also need to keep somewhere, either in the account state or in some other account-indexed hashmap, the following data: ˆ The output message queue of the account (cf. 2.4.17 ) ˆ The collection of (hashes of) recently delivered messages (cf. 2.4.23 ) Not all of these are really required for every account; for example, smart- contract code is needed only for smart contracts, but not for simple ac- counts. Furthermore, while any account must have a non-zero balance in the principal currency (e.g., TON coins for the masterchain and shardchains of the basic workchain), it may have balances of zero in other currencies. In order to avoid keeping unused data, a sum-product type (depending on the workchain) is dened (during the workchain's creation), which uses dierent tag bytes (e.g., TL constructors; cf. 2.2.5 ) to distinguish between dierent constructors used. Ultimately, the account state is itself kept as a collection of cells of the TVM persistent storage. 2.4 Messages Between Shardchains An important component of the TON Blockchain is the messaging system between blockchains. These blockchains may be shardchains of the same workchain, or of dierent workchains. 2.4.1. Messages, accounts and transactions: a bird's eye view of the system. Messages are sent from one account to another. Each transaction consists of an account receiving one message, changing its state according to certain rules, and generating several (maybe one or zero) new messages to other accounts. Each message is generated and received (delivered) exactly once. This means that messages play a fundamental role in the system, com- parable to that of accounts (smart contracts). From the perspective of the Innite Sharding Paradigm (cf. 2.1.2 ), each account resides in its separate account-chain, and the only way it can aect the state of some other account is by sending a message. 29 2.4. Messages Between Shardchains 2.4.2. Accounts as processes or actors; Actor model. One might think about accounts (and smart contracts) as processes, or actors, that are able to process incoming messages, change their internal state and generate some outbound messages as a result. This is closely related to the so-called Actor model , used in languages such as Erlang (however, actors in Erlang are usually called processes). Since new actors (i.e., smart contracts) are also allowed to be created by existing actors as a result of processing an inbound message, the correspondence with the Actor model is essentially complete. 2.4.3. Message recipient. Any message has its recipient , characterized by the target workchain identier w (assumed by default to be the same as that of the originating shardchain), and the recipient account account_id . The exact format (i.e., number of bits) of account_id depends on w; however, the shard is always determined by its rst (most signicant) 64 bits. 2.4.4. Message sender. In most cases, a message has a sender , charac- terized again by a (w′, account_id ′) pair. If present, it is located after the message recipient and message value. Sometimes, the sender is unimportant or it is somebody outside the blockchain (i.e., not a smart contract), in which case this eld is absent. Notice that the Actor model does not require the messages to have an implicit sender. Instead, messages may contain a reference to the Actor to which an answer to the request should be sent; usually it coincides with the sender. However, it is useful to have an explicit unforgeable sender eld in a message in a cryptocurrency (Byzantine) environment. 2.4.5. Message value. Another important characteristic of a message is its attached value , in one or several cryptocurrencies supported both by the source and by the target workchain. The value of the message is indicated at its very beginning immediately after the message recipient; it is essentially a list of (currency_id , value ) pairs. Notice that simple value transfers between simple accounts are just empty (no-op) messages with some value attached to them. On the other hand, a slightly more complicated message body might contain a simple text or binary comment (e.g., about the purpose of the payment). 2.4.6. External messages, or messages from nowhere. Some mes- sages arrive into the system from nowherethat is, they are not generated by an account (smart contract or not) residing in the blockchain. The most 30 2.4. Messages Between Shardchains typical example arises when a user wants to transfer some funds from an account controlled by her to some other account. In this case, the user sends a message from nowhere to her own account, requesting it to generate a message to the receiving account, carrying the specied value. If this mes- sage is correctly signed, her account receives it and generates the required outbound messages. In fact, one might consider a simple account as a special case of a smart contract with predened code. This smart contract receives only one type of message. Such an inbound message must contain a list of outbound messages to be generated as a result of delivering (processing) the inbound message, along with a signature. The smart contract checks the signature, and, if it is correct, generates the required messages. Of course, there is a dierence between messages from nowhere and normal messages, because the messages from nowhere cannot bear value, so they cannot pay for their gas (i.e., their processing) themselves. Instead, they are tentatively executed with a small gas limit before even being sug- gested for inclusion in a new shardchain block; if the execution fails (the signature is incorrect), the message from nowhere is deemed incorrect and is discarded. If the execution does not fail within the small gas limit, the mes- sage may be included in a new shardchain block and processed completely, with the payment for the gas (processing capacity) consumed exacted from the receiver's account. Messages from nowhere can also dene some trans- action fee which is deducted from the receiver's account on top of the gas payment for redistribution to the validators. In this sense, messages from nowhere or external messages take the role of transaction candidates used in other blockchain systems (e.g., Bitcoin and Ethereum). 2.4.7. Log messages, or messages to nowhere. Similarly, sometimes a special message can be generated and routed to a specic shardchain not to be delivered to its recipient, but to be logged in order to be easily observable by anybody receiving updates about the shard in question. These logged messages may be output in a user's console, or trigger an execution of some script on an o-chain server. In this sense, they represent the external out- put of the blockchain supercomputer, just as the messages from nowhere represent the external input of the blockchain supercomputer. 2.4.8. Interaction with o-chain services and external blockchains. These external input and output messages can be used for interacting with 31 2.4. Messages Between Shardchains o-chain services and other (external) blockchains, such as Bitcoin or Ethe- reum. One might create tokens or cryptocurrencies inside the TON Block- chain pegged to Bitcoins, Ethers or any ERC-20 tokens dened in the Ethe- reum blockchain, and use messages from nowhere and messages to nowhere, generated and processed by scripts residing on some third-party o-chain servers, to implement the necessary interaction between the TON Blockchain and these external blockchains. 2.4.9. Message body. The message body is simply a sequence of bytes, the meaning of which is determined only by the receiving workchain and/or smart contract. For blockchains using TON VM, this could be the serial- ization of any TVM cell, generated automatically via the Send() operation. Such a serialization is obtained simply by recursively replacing all references in a TON VM cell with the cells referred to. Ultimately, a string of raw bytes appears, which is usually prepended by a 4-byte message type or message constructor, used to select the correct method of the receiving smart con- tract. Another option would be to use TL-serialized objects (cf. 2.2.5 ) as mes- sage bodies. This might be especially useful for communication between dierent workchains, one or both of which are not necessarily using the TON VM. 2.4.10. Gas limit and other workchain/VM-specic parameters. Sometimes a message needs to carry information about the gas limit, the gas price, transaction fees and similar values that depend on the receiving workchain and are relevant only for the receiving workchain, but not necessar- ily for the originating workchain. Such parameters are included in or before the message body, sometimes (depending on the workchain) with special 4- byte prexes indicating their presence (which can be dened by a TL-scheme; cf. 2.2.5 ). 2.4.11. Creating messages: smart contracts and transactions. There are two sources of new messages. Most messages are created during smart- contract execution (via the Send() operation in TON VM), when some smart contract is invoked to process an incoming message. Alternatively, mes- sages may come from the outside as external messages or messages from nowhere (cf. 2.4.6 ). 13 13 The above needs to be literally true only for the basic workchain and its shardchains; other workchains may provide other ways of creating messages. 32 2.4. Messages Between Shardchains 2.4.12. Delivering messages. When a message reaches the shardchain con- taining its destination account, 14 it is delivered to its destination account. What happens next depends on the workchain; from an outside perspective, it is important that such a message can never be forwarded further from this shardchain. For shardchains of the basic workchain, delivery consists in adding the message value (minus any gas payments) to the balance of the receiving ac- count, and possibly in invoking a message-dependent method of the receiving smart contract afterwards, if the receiving account is a smart contract. In fact, a smart contract has only one entry point for processing all incoming messages, and it must distinguish between dierent types of messages by looking at their rst few bytes (e.g., the rst four bytes containing a TL constructor; cf. 2.2.5 ). 2.4.13. Delivery of a message is a transaction. Because the delivery of a message changes the state of an account or smart contract, it is a special transaction in the receiving shardchain, and is explicitly registered as such. Essentially, all TON Blockchain transactions consist in the delivery of one inbound message to its receiving account (smart contract), neglecting some minor technical details. 2.4.14. Messages between instances of the same smart contract. Recall that a smart contract may be local (i.e., residing in one shardchain as any ordinary account does) or global (i.e., having instances in all shards, or at least in all shards up to some known depth d; cf. 2.3.18 ). Instances of a global smart contract may exchange special messages to transfer information and value between each other if required. In this case, the (unforgeable) sender account_id becomes important (cf. 2.4.4 ). 2.4.15. Messages to any instance of a smart contract; wildcard ad- dresses. Sometimes a message (e.g., a client request) needs be delivered to any instance of a global smart contract, usually the closest one (if there is one residing in the same shardchain as the sender, it is the obvious candidate). One way of doing this is by using a wildcard recipient address, with the rst d bits of the destination account_id allowed to take arbitrary values. In practice, one will usually set these d bits to the same values as in the sender's account_id . 14 As a degenerate case, this shardchain may coincide with the originating shardchain for example, if we are working inside a workchain which has not yet been split. 33 2.4. Messages Between Shardchains 2.4.16. Input queue is absent. All messages received by a blockchain (usually a shardchain; sometimes the masterchain)or, essentially, by an account-chain residing inside some shardchainare immediately delivered (i.e., processed by the receiving account). Therefore, there is no input queue as such. Instead, if not all messages destined for a specic shardchain can be processed because of limitations on the total size of blocks and gas usage, some messages are simply left to accumulate in the output queues of the originating shardchains. 2.4.17. Output queues. From the perspective of the Innite Sharding Paradigm (cf. 2.1.2 ), each account-chain (i.e., each account) has its own out- put queue, consisting of all messages it has generated, but not yet delivered to their recipients. Of course, account-chains have only a virtual existence; they are grouped into shardchains, and a shardchain has an output queue, consisting of the union of the output queues of all accounts belonging to the shardchain. This shardchain output queue imposes only partial order on its member messages. Namely, a message generated in a preceding block must be deliv- ered before any message generated in a subsequent block, and any messages generated by the same account and having the same destination must be delivered in the order of their generation. 2.4.18. Reliable and fast inter-chain messaging. It is of paramount importance for a scalable multi-blockchain project such as TON to be able to forward and deliver messages between dierent shardchains (cf. 2.1.3 ), even if there are millions of them in the system. The messages should be delivered reliably (i.e., messages should not be lost or delivered more than once) and quickly . The TON Blockchain achieves this goal by using a combination of two message routing mechanisms. 2.4.19. Hypercube routing: slow path for messages with assured delivery. The TON Blockchain uses hypercube routing as a slow, but safe and reliable way of delivering messages from one shardchain to another, using several intermediate shardchains for transit if necessary. Otherwise, the validators of any given shardchain would need to keep track of the state of (the output queues of) all other shardchains, which would require prohibitive amounts of computing power and network bandwidth as the total quantity of shardchains grows, thus limiting the scalability of the system. Therefore, it is not possible to deliver messages directly from any shard to every other. 34 2.4. Messages Between Shardchains Instead, each shard is connected only to shards diering in exactly one hexadecimal digit of their (w,s ) shard identiers (cf. 2.1.8 ). In this way, all shardchains constitute a hypercube graph, and messages travel along the edges of this hypercube. If a message is sent to a shard dierent from the current one, one of the hexadecimal digits (chosen deterministically) of the current shard identier is replaced by the corresponding digit of the target shard, and the resulting identier is used as the proximate target to forward the message to. 15 The main advantage of hypercube routing is that the block validity con- ditions imply that validators creating blocks of a shardchain must collect and process messages from the output queues of neighboring shardchains, on pain of losing their stakes. In this way, any message can be expected to reach its nal destination sooner or later; a message cannot be lost in transit or delivered twice. Notice that hypercube routing introduces some additional delays and ex- penses, because of the necessity to forward messages through several interme- diate shardchains. However, the number of these intermediate shardchains grows very slowly, as the logarithm logN (more precisely, ⌈log16N⌉− 1) of the total number of shardchains N . For example, if N ≈ 250, there will be at most one intermediate hop; and for N ≈ 4000 shardchains, at most two. With four intermediate hops, we can support up to one million shard- chains. We think this is a very small price to pay for the essentially unlimited scalability of the system. In fact, it is not necessary to pay even this price: 2.4.20. Instant Hypercube Routing: fast path for messages. A novel feature of the TON Blockchain is that it introduces a fast path for forwarding messages from one shardchain to any other, allowing in most cases to bypass the slow hypercube routing of 2.4.19 altogether and deliver the message into the very next block of the nal destination shardchain. The idea is as follows. During the slow hypercube routing, the message travels (in the network) along the edges of the hypercube, but it is delayed (for approximately ve seconds) at each intermediate vertex to be committed into the corresponding shardchain before continuing its voyage. To avoid unnecessary delays, one might instead relay the message along with a suitable Merkle proof along the edges of the hypercube, without wait- 15 This is not necessarily the nal version of the algorithm used to compute the next hop for hypercube routing. In particular, hexadecimal digits may be replaced by r-bit groups, with r a congurable parameter, not necessarily equal to four. 35 2.4. Messages Between Shardchains ing to commit it into the intermediate shardcha
프로젝트로 돌아가기