bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 16쪽 중 2쪽
be automatically
punished by losing part or all of its stake, or by being suspended from the
set of validators for some time. After that, the validators should reach con-
sensus on the choice of the next block, essentially by an ecient variant of
the BFT (Byzantine Fault Tolerant; cf. 2.8.4 ) consensus protocol, similar to
PBFT [4] or Honey Badger BFT [11]. If consensus is reached, a new block
is created, and validators divide between themselves the transaction fees for
the transactions included, plus some newly-created (minted) coins.
Each validator can be elected to participate in several validator subsets;
in this case, it is expected to run all validation and consensus algorithms in
parallel.
After all new shardchain blocks are generated or a timeout is passed, a
new masterchain block is generated, including the hashes of the latest blocks
of all shardchains. This is done by BFT consensus of all validators. 2
More detail on the TON PoS approach and its economical model is pro-
vided in section 2.6 .
2 Actually, two-thirds by stake is enough to achieve consensus, but an eort is made to
collect as many signatures as possible.
10
2.1. TON Blockchain as a Collection of 2-Blockchains
2.1.16. Forks of the masterchain. A complication that arises from our
tightly-coupled approach is that switching to a dierent fork in the master-
chain will almost necessarily require switching to another fork in at least
some of the shardchains. On the other hand, as long as there are no forks
in the masterchain, no forks in the shardchain are even possible, because no
blocks in the alternative forks of the shardchains can become canonical by
having their hashes incorporated into a masterchain block.
The general rule is that if masterchain block B′ is a predecessor of B,
B′ includes hash Hash (B′w,s) of (w,s )-shardchain block B′w,s, and B includes
hash Hash (Bw,s), then B′w,s must be a predecessor of Bw,s; otherwise, the
masterchain block B is invalid.
We expect masterchain forks to be rare, next to non-existent, because
in the BFT paradigm adopted by the TON Blockchain they can happen
only in the case of incorrect behavior by a majority of validators (cf. 2.6.1
and 2.6.15 ), which would imply signicant stake losses by the oenders.
Therefore, no true forks in the shardchains should be expected. Instead,
if an invalid shardchain block is detected, it will be corrected by means of
the vertical blockchain mechanism of the 2-blockchain (cf. 2.1.17 ), which
can achieve this goal without forking the horizontal blockchain (i.e., the
shardchain). The same mechanism can be used to x non-fatal mistakes in
the masterchain blocks as well.
2.1.17. Correcting invalid shardchain blocks. Normally, only valid
shardchain blocks will be committed, because validators assigned to the
shardchain must reach a two-thirds Byzantine consensus before a new block
can be committed. However, the system must allow for detection of previ-
ously committed invalid blocks and their correction.
Of course, once an invalid shardchain block is foundeither by a validator
(not necessarily assigned to this shardchain) or by a sherman (any node
of the system that made a certain deposit to be able to raise questions about
block validity; cf. 2.6.4 )the invalidity claim and its proof are committed
into the masterchain, and the validators that have signed the invalid block are
punished by losing part of their stake and/or being temporarily suspended
from the set of validators (the latter measure is important for the case of an
attacker stealing the private signing keys of an otherwise benign validator).
However, this is not sucient, because the overall state of the system
(TON Blockchain) turns out to be invalid because of the invalid shardchain
block previously committed. This invalid block must be replaced by a newer
11
2.1. TON Blockchain as a Collection of 2-Blockchains
valid version.
Most systems would achieve this by rolling back to the last block before
the invalid one in this shardchain and the last blocks unaected by messages
propagated from the invalid block in each of the other shardchains, and
creating a new fork from these blocks. This approach has the disadvantage
that a large number of otherwise correct and committed transactions are
suddenly rolled back, and it is unclear whether they will be included later at
all.
The TON Blockchain solves this problem by making each block of
each shardchain and of the masterchain (horizontal blockchains) a small
blockchain (vertical blockchain) by itself, containing dierent versions of
this block, or their dierences. Normally, the vertical blockchain consists
of exactly one block, and the shardchain looks like a classical blockchain.
However, once the invalidity of a block is conrmed and committed into a
masterchain block, the vertical blockchain of the invalid block is allowed to
grow by a new block in the vertical direction, replacing or editing the invalid
block. The new block is generated by the current validator subset for the
shardchain in question.
The rules for a new vertical block to be valid are quite strict. In par-
ticular, if a virtual account-chain block (cf. 2.1.2 ) contained in the invalid
block is valid by itself, it must be left unchanged by the new vertical block.
Once a new vertical block is committed on top of the invalid block, its
hash is published in a new masterchain block (or rather in a new vertical
block, lying above the original masterchain block where the hash of the invalid
shardchain block was originally published), and the changes are propagated
further to any shardchain blocks referring to the previous version of this block
(e.g., those having received messages from the incorrect block). This is xed
by committing new vertical blocks in vertical blockchains for all blocks
previously referring to the incorrect block; new vertical blocks will refer
to the most recent (corrected) versions instead. Again, strict rules forbid
changing account-chains that are not really aected (i.e., that receive the
same messages as in the previous version). In this way, xing an incorrect
block generates ripples that are ultimately propagated towards the most
recent blocks of all aected shardchains; these changes are reected in new
vertical masterchain blocks as well.
Once the history rewriting ripples reach the most recent blocks, the new
shardchain blocks are generated in one version only, being successors of the
newest block versions only. This means that they will contain references to
12
2.1. TON Blockchain as a Collection of 2-Blockchains
the correct (most recent) vertical blocks from the very beginning.
The masterchain state implicitly denes a map transforming the hash of
the rst block of each vertical blockchain into the hash of its latest version.
This enables a client to identify and locate any vertical blockchain by the
hash of its very rst (and usually the only) block.
2.1.18. TON coins and multi-currency workchains. The TON Block-
chain supports up to 232 dierent cryptocurrencies, coins, or tokens,
distinguished by a 32-bit currency_id . New cryptocurrencies can be added
by special transactions in the masterchain. Each workchain has a basic cryp-
tocurrency, and can have several additional cryptocurrencies.
There is one special cryptocurrency with currency_id = 0, namely, the
TON coin (cf. Appendix A). It is the basic cryptocurrency of Workchain
Zero. It is also used for transaction fees and validator stakes.
In principle, other workchains may collect transaction fees in other to-
kens. In this case, some smart contract for automated conversion of these
transaction fees into TON coins should be provided.
2.1.19. Messaging and value transfer. Shardchains belonging to the
same or dierent workchains may send messages to each other. While the
exact form of the messages allowed depends on the receiving workchain and
receiving account (smart contract), there are some common elds making
inter-workchain messaging possible. In particular, each message may have
some value attached, in the form of a certain amount of TON coins and/or
other registered cryptocurrencies, provided they are declared as acceptable
cryptocurrencies by the receiving workchain.
The simplest form of such messaging is a value transfer from one (usually
not a smart-contract) account to another.
2.1.20. TON Virtual Machine. The TON Virtual Machine , also ab-
breviated as TON VM or TVM , is the virtual machine used to execute
smart-contract code in the masterchain and in the basic workchain. Other
workchains may use other virtual machines alongside or instead of the TVM.
Here we list some of its features. They are discussed further in 2.3.12 ,
2.3.14 and elsewhere.
TVM represents all data as a collection of (TVM) cells (cf. 2.3.14 ).
Each cell contains up to 128 data bytes and up to 4 references to other
cells. As a consequence of the everything is a bag of cells philosophy
13
2.1. TON Blockchain as a Collection of 2-Blockchains
(cf. 2.5.14 ), this enables TVM to work with all data related to the TON
Blockchain, including blocks and blockchain global state if necessary.
TVM can work with values of arbitrary algebraic data types (cf. 2.3.12 ),
represented as trees or directed acyclic graphs of TVM cells. However,
it is agnostic towards the existence of algebraic data types; it just works
with cells.
TVM has built-in support for hashmaps (cf. 2.3.7 ).
TVM is a stack machine. Its stack keeps either 64-bit integers or cell
references.
64-bit, 128-bit and 256-bit arithmetic is supported. All n-bit arithmetic
operations come in three avors: for unsigned integers, for signed inte-
gers and for integers modulo 2n (no automatic overow checks in the
latter case).
TVM has unsigned and signed integer conversion from n-bit to m-bit,
for all 0≤m,n≤ 256, with overow checks.
All arithmetic operations perform overow checks by default, greatly
simplifying the development of smart contracts.
TVM has multiply-then-shift and shift-then-divide arithmetic oper-
ations with intermediate values computed in a larger integer type; this
simplies implementing xed-point arithmetic.
TVM oers support for bit strings and byte strings.
Support for 256-bit Elliptic Curve Cryptography (ECC) for some pre-
dened curves, including Curve25519, is present.
Support for Weil pairings on some elliptic curves, useful for fast imple-
mentation of zk-SNARKs, is also present.
Support for popular hash functions, including sha256 , is present.
TVM can work with Merkle proofs (cf. 5.1.9 ).
TVM oers support for large or global smart contracts. Such smart
contracts must be aware of sharding (cf. 2.3.18 and 2.3.16 ). Usual
(local) smart contracts can be sharding-agnostic.
14
2.2. Generalities on Blockchains
TVM supports closures.
A spineless tagless G-machine [13] can be easily implemented inside
TVM.
Several high-level languages can be designed for TVM, in addition to the
TVM assembly. All these languages will have static types and will support
algebraic data types. We envision the following possibilities:
A Java-like imperative language, with each smart contract resembling
a separate class.
A lazy functional language (think of Haskell).
An eager functional language (think of ML).
2.1.21. Congurable parameters. An important feature of the TON
Blockchain is that many of its parameters are congurable . This means that
they are part of the masterchain state, and can be changed by certain special
proposal/vote/result transactions in the masterchain, without any need for
hard forks. Changing such parameters will require collecting two-thirds of
validator votes and more than half of the votes of all other participants who
would care to take part in the voting process in favor of the proposal.
2.2 Generalities on Blockchains
2.2.1. General blockchain denition. In general, any (true) blockchain
is a sequence of blocks , each block B containing a reference blk-prev (B) to
the previous block (usually by including the hash of the previous block into
the header of the current block), and a list of transactions . Each transaction
describes some transformation of the global blockchain state ; the transactions
listed in a block are applied sequentially to compute the new state starting
from the old state, which is the resulting state after the evaluation of the
previous block.
2.2.2. Relevance for the TON Blockchain. Recall that the TON Block-
chain is not a true blockchain, but a collection of 2-blockchains (i.e., of
blockchains of blockchains; cf. 2.1.1 ), so the above is not directly applicable
to it. However, we start with these generalities on true blockchains to use
them as building blocks for our more sophisticated constructions.
15
2.2. Generalities on Blockchains
2.2.3. Blockchain instance and blockchain type. One often uses the
word blockchain to denote both a general blockchain type and its specic
blockchain instances , dened as sequences of blocks satisfying certain condi-
tions. For example, 2.2.1 refers to blockchain instances.
In this way, a blockchain type is usually a subtype of the type Block ∗ of
lists (i.e., nite sequences) of blocks, consisting of those sequences of blocks
that satisfy certain compatibility and validity conditions:
Blockchain ⊂ Block ∗ (1)
A better way to dene Blockchain would be to say that Blockchain is a
dependent couple type , consisting of couples (B,v ), with rst component B :
Block ∗ being of type Block ∗ (i.e., a list of blocks), and the second component
v : isValidBc (B) being a proof or a witness of the validity of B. In this way,
Blockchain ≡ Σ(B:Block ∗)isValidBc (B) (2)
We use here the notation for dependent sums of types borrowed from [16].
2.2.4. Dependent type theory, Coq and TL. Note that we are using
(Martin-Löf) dependent type theory here, similar to that used in the Coq 3
proof assistant. A simplied version of dependent type theory is also used in
TL (Type Language) , 4 which will be used in the formal specication of the
TON Blockchain to describe the serialization of all data structures and the
layouts of blocks, transactions, and the like.
In fact, dependent type theory gives a useful formalization of what a proof
is, and such formal proofs (or their serializations) might become handy when
one needs to provide proof of invalidity for some block, for example.
2.2.5. TL, or the Type Language. Since TL (Type Language) will be
used in the formal specications of TON blocks, transactions, and network
datagrams, it warrants a brief discussion.
TL is a language suitable for description of dependent algebraic types ,
which are allowed to have numeric (natural) and type parameters. Each
type is described by means of several constructors . Each constructor has a
(human-readable) identier and a name, which is a bit string (32-bit integer
by default). Apart from that, the denition of a constructor contains a list
of elds along with their types.
3 https://coq.inria.fr
4 https://core.telegram.org/mtproto/TL
16
2.2. Generalities on Blockchains
A collection of constructor and type denitions is called a TL-scheme . It
is usually kept in one or several les with the sux .tl .
An important feature of TL-schemes is that they determine an unambigu-
ous way of serializing and deserializing values (or objects) of algebraic types
dened. Namely, when a value needs to be serialized into a stream of bytes,
rst the name of the constructor used for this value is serialized. Recursively
computed serializations of each eld follow.
The description of a previous version of TL, suitable for serializing arbi-
trary objects into sequences of 32-bit integers, is available at https://core.
telegram.org/mtproto/TL . A new version of TL, called TL-B , is being de-
veloped for the purpose of describing the serialization of objects used by the
TON Project. This new version can serialize objects into streams of bytes
and even bits (not just 32-bit integers), and oers support for serialization
into a tree of TVM cells (cf. 2.3.14 ). A description of TL-B will be a part
of the formal specication of the TON Blockchain.
2.2.6. Blocks and transactions as state transformation operators.
Normally, any blockchain (type) Blockchain has an associated global state
(type) State , and a transaction (type) Transaction . The semantics of a
blockchain are to a large extent determined by the transaction application
function:
ev_trans ′ : Transaction × State → State ? (3)
Here X ? denotes Maybe X, the result of applying the Maybe monad to
type X. This is similar to our use of X∗ for List X. Essentially, a value
of type X ? is either a value of type X or a special value ⊥ indicating the
absence of an actual value (think about a null pointer). In our case, we use
State ? instead of State as the result type because a transaction may be invalid
if invoked from certain original states (think about attempting to withdraw
from an account more money than it is actually there).
We might prefer a curried version of ev_trans ′:
ev_trans : Transaction → State → State ? (4)
Because a block is essentially a list of transactions, the block evaluation
function
ev_block : Block → State → State ? (5)
can be derived from ev_trans . It takes a block B : Block and the previous
blockchain state s : State (which might include the hash of the previous
17
2.2. Generalities on Blockchains
block) and computes the next blockchain state s′ = ev_block (B)(s) : State ,
which is either a true state or a special value ⊥ indicating that the next
state cannot be computed (i.e., that the block is invalid if evaluated from the
starting state givenfor example, the block includes a transaction trying to
debit an empty account.)
2.2.7. Block sequence numbers. Each block B in the blockchain can be
referred to by its sequence number blk-seqno (B), starting from zero for the
very rst block, and incremented by one whenever passing to the next block.
More formally,
blk-seqno (B) = blk-seqno
(
blk-prev (B)
)
+ 1 (6)
Notice that the sequence number does not identify a block uniquely in the
presence of forks .
2.2.8. Block hashes. Another way of referring to a block B is by its hash
blk-hash (B), which is actually the hash of the header of block B (however,
the header of the block usually contains hashes that depend on all content of
block B). Assuming that there are no collisions for the hash function used
(or at least that they are very improbable), a block is uniquely identied by
its hash.
2.2.9. Hash assumption. During formal analysis of blockchain algorithms,
we assume that there are no collisions for the k-bit hash function Hash :
Bytes ∗→ 2k used:
Hash (s) = Hash (s′)⇒s =s′ for any s, s′∈ Bytes ∗ (7)
Here Bytes ={0... 255} = 28 is the type of bytes, or the set of all byte
values, and Bytes ∗ is the type or set of arbitrary (nite) lists of bytes; while
2 ={0, 1} is the bit type, and 2k is the set (or actually the type) of all k-bit
sequences (i.e., of k-bit numbers).
Of course, (7) is impossible mathematically, because a map from an in-
nite set to a nite set cannot be injective. A more rigorous assumption would
be
∀s,s′ :s⁄=s′,P (Hash (s) = Hash (s′)) = 2−k (8)
However, this is not so convenient for the proofs. If (8) is used at most N
times in a proof with 2−kN < ϵfor some small ϵ (say, ϵ = 10−18), we can
18
2.3. Blockchain State, Accounts and Hashmaps
reason as if (7) were true, provided we accept a failure probability ϵ (i.e., the
nal conclusions will be true with probability at least 1−ϵ).
Final remark: in order to make the probability statement of (8) really
rigorous, one must introduce a probability distribution on the set Bytes ∗ of
all byte sequences. A way of doing this is by assuming all byte sequences
of the same length l equiprobable, and setting the probability of observing a
sequence of length l equal to pl−pl+1 for some p→ 1−. Then (8) should be
understood as a limit of condi프로젝트로 돌아가기