TON Blockchain

Splitting and Merging Shardchains
2.6.29. Consequence of Proof-of-Stake for light nodes. An important
consequence of the Proof-of-Stake approach used by the TON Blockchain is
that a light node (running light client software) for the TON Blockchain does
not need to download the ?headers? of all shardchain or even masterchain
blocks in order to be able to check by itself the validity of Merkle proofs
provided to it by full nodes as answers to its queries.
Indeed, because the most recent shardchain block hashes are included in
the masterchain blocks, a full node can easily provide a Merkle proof that a
given shardchain block is valid starting from a known hash of a masterchain
block. Next, the light node needs to know only the very rst block of the
masterchain (where the very rst set of validators is announced), which (or
at least the hash of which) might be built-in into the client software, and
only one masterchain block approximately every month afterwards, where
newly-elected validator sets are announced, because this block will have been
signed by the previous set of validators. Starting from that, it can obtain the
several most recent masterchain blocks, or at least their headers and validator
signatures, and use them as a base for checking Merkle proofs provided by
full nodes.
2.7 Splitting and Merging Shardchains
One of the most characteristic and unique features of the TON Blockchain is
its ability to automatically split a shardchain in two when the load becomes
too high, and merge them back if the load subsides (cf. 2.1.10). We must
discuss it in some detail because of its uniqueness and its importance to the
scalability of the whole project.
2.7.1. Shard conguration. Recall that, at any given moment of time,
each workchain w is split into one or several shardchains (w, s) (cf. 2.1..
These shardchains may be represented by leaves of a binary tree, with root
(w, ∅), and each non-leaf node (w, s) having children (w, s.0) and (w, s.1).
In this way, every account belonging to workchain w is assigned to exactly
one shard, and everybody who knows the current shardchain conguration
can determine the shard (w, s) containing account account_id: it is the only
shard with binary string s being a prex of account_id.
The shard conguration?i.e., this shard binary tree, or the collection
of all active (w, s) for a given w (corresponding to the leaves of the shard
binary tree)?is part of the masterchain state and is available to everybody
57
2.7. Splitting and Merging Shardchains
who keeps track of the masterchain.22
2.7.2. Most recent shard conguration and state. Recall that hashes
of the most recent shardchain blocks are included in each masterchain block.
These hashes are organized in a shard binary tree (actually, a collection of
trees, one for each workchain). In this way, each masterchain block contains
the most recent shard conguration.
2.7.3. Announcing and performing changes in the shard conguration. The shard conguration may be changed in two ways: either a shard
(w, s) can be split into two shards (w, s.0) and (w, s.1), or two ?sibling? shards
(w, s.0) and (w, s.1) can be merged into one shard (w, s).
These split/merge operations are announced several (e.g., 2
6
; this is a
congurable parameter) blocks in advance, rst in the ?headers? of the corresponding shardchain blocks, and then in the masterchain block that refers
to these shardchain blocks. This advance announcement is needed for all
parties concerned to prepare for the planned change (e.g., build an overlay
multicast network to distribute new blocks of the newly-created shardchains,
as discussed in 3.3). Then the change is committed, rst into the (header of
the) shardchain block (in case of a split; for a merge, blocks of both shardchains should commit the change), and then propagated to the masterchain
block. In this way, the masterchain block denes not only the most recent
shard conguration before its creation, but also the next immediate shard
conguration.
2.7.4. Validator task groups for new shardchains. Recall that each
shard, i.e., each shardchain, normally is assigned a subset of validators (a
validator task group) dedicated to creating and validating new blocks in the
corresponding shardchain (cf. 2.6.. These task groups are elected for some
period of time (approximately one hour) and are known some time in advance
(also approximately one hour), and are immutable during this period.23
However, the actual shard conguration may change during this period
because of split/merge operations. One must assign task groups to newly
created shards. This is done as follows:
22Actually, the shard conguration is completely determined by the last masterchain
block; this simplies getting access to the shard conguration.
23Unless some validators are temporarily or permanently banned because of signing
invalid blocks?then they are automatically excluded from all task groups.
58
2.7. Splitting and Merging Shardchains
Notice that any active shard (w, s) will either be a descendant of some
uniquely determined original shard (w, s0
), meaning that s
0
is a prex of s,
or it will be the root of a subtree of original shards (w, s0
), where s will be
a prex of every s
0
. In the rst case, we simply take the task group of the
original shard (w, s0
) to double as the task group of the new shard (w, s). In
the latter case, the task group of the new shard (w, s) will be the union of
task groups of all original shards (w, s0
) that are descendants of (w, s) in the
shard tree.
In this way, every active shard (w, s) gets assigned a well-dened subset
of validators (task group). When a shard is split, both children inherit the
whole of the task group from the original shard. When two shards are merged,
their task groups are also merged.
Anyone who keeps track of the masterchain state can compute validator
task groups for each of the active shards.
2.7.5. Limit on split/merge operations during the period of responsibility of original task groups. Ultimately, the new shard conguration
will be taken into account, and new dedicated validator subsets (task groups)
will automatically be assigned to each shard. Before that happens, one must
impose a certain limit on split/merge operations; otherwise, an original task
group may end up validating 2
k
shardchains for a large k at the same time,
if the original shard quickly splits into 2
k new shards.
This is achieved by imposing limits on how far the active shard conguration may be removed from the original shard conguration (the one used
to select validator task groups currently in charge). For example, one might
require that the distance in the shard tree from an active shard (w, s) to an
original shard (w, s0
) must not exceed 3, if s
0
is a predecessor of s (i.e., s
0
is a
prex of binary string s), and must not exceed 2, if s
0
is a successor of s (i.e.,
s is a prex of s
0
). Otherwise, the split or merge operation is not permitted.
Roughly speaking, one is imposing a limit on the number of times a
shard can be split (e.g., three) or merged (e.g., two) during the period of
responsibility of a given collection of validator task groups. Apart from
that, after a shard has been created by merging or splitting, it cannot be
recongured for some period of time (some number of blocks).
2.7.6. Determining the necessity of split operations. The split operation for a shardchain is triggered by certain formal conditions (e.g., if for
64 consecutive blocks the shardchain blocks are at least 90% full). These
conditions are monitored by the shardchain task group. If they are met,