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