Перейти к основному содержимому

Infinity Sharding Paradigm

Understanding Split Merge in TON Blockchain​

The TON (Telegram Open Network) Blockchain introduces innovative concepts for blockchain scalability and efficiency. One such concept is the Split Merge functionality, integral to its blockchain architecture. This short article explores the key aspects of Split Merge in the TON Blockchain, focusing on its role within the Infinite Sharding Paradigm (ISP).

Infinite Sharding Paradigm (ISP) and its Application​

ISP underpins the TON Blockchain's design, treating each account as part of its separate "accountchain." These accountchains are then aggregated into shardchain blocks for efficiency. The state of a shardchain comprises the states of all its accountchains. Thus, a shardchain block essentially is a collection of virtual blocks of accounts assigned to it.

  • ShardState: Approximated as Hashmap(n, AccountState), where n is the bit length of the account_id.
  • ShardBlock: Approximated as Hashmap(n, AccountBlock).

Each shardchain, or more precisely, each shardchain block, is identified by a combination of workchain_id and a binary prefix s of the account_id.

Algorithm for deciding whether to split or merge​

Validators decide whether to split or merge shards in the following way:

  1. For each block, block size, gas consumption and lt delta are calculated.
  2. Using these values, blocks can be considered overloaded or underloaded.
  3. Each shard keeps underload and overload history. If enough recent blocks were underloaded or overloaded, want_merge or want_split flag is set.
  4. Validators merge or split shards using these flags.

1. Assessment of the current state of the block​

Each block has the following parameters. They are used to determine overload and underload.

  1. Block size estimation - not an actual block size, but an estimation calculated during collation.
  2. Gas consumption - total gas consumed in all transactions (excluding ticktock and mint/recover special transactions).
  3. Lt delta - difference between start and end lt of the block.

2. Block limits and classification​

Block limits are loaded from the configuration parameters 22 and 23. Each of the three parameters has three limits: underload, soft, hard:

  1. Block size: 128/256/512 KiB.
  2. Gas consumption: 2M/10M/20M in basechain, 200K/1M/2.5M in masterchain.
  3. Lt delta: 1000/5000/10000. Also, there is a medium limit, which is equal to (soft + hard) / 2.

We classify the three parameters (size, gas, and lt delta) into categories:

  • 0 - underload limit is not reached.
  • 1 - underload limit is exceeded.
  • 2 - soft limit is exceeded.
  • 3 - medium limit is exceeded.
  • 4 - hard limit is exceeded.

Block classification is max(Classification of size, Classification of gas, Classification of lt delta). For example: if classification of size is 2, classification of gas is 3, classification of lt delta is 1, then the final block classification is 3.

  • When classification of the block is 0 (underload), the block is inclined to merge with its sibling.
  • When classification of the block is 2 (soft limit reached), collator stops processing internal messages. The block is inclined to split.
  • When classification of the block is 3 (medium limit reached), collator stops processing external messages.

3. Determination of overload or underload​

After classifying the block, collator checks overload and underload conditions. Size of the outbound message queue and status of dispatch queue processing is also taken into consideration.

  • If the block class is ≥ 2 (soft) and message queue size ≤ SPLIT_MAX_QUEUE_SIZE = 100000 then the block is overloaded.
  • If limit for total processed messages from dispatch queue was reached and message queue size ≤ SPLIT_MAX_QUEUE_SIZE = 100000 then the block is overloaded.
  • If the block class is 0 (underload) and message queue size ≤ MERGE_MAX_QUEUE_SIZE = 2047 then the block is underloaded.
  • If message queue size is ≥ FORCE_SPLIT_QUEUE_SIZE = 4096 and ≤ SPLIT_MAX_QUEUE_SIZE = 100000 then the block is overloaded.

4. Deciding whether to split or merge​

Each block keeps underload and overload history - it is a 64-bit mask of the underload/overload status of the last 64 blocks. It is used to decide whether to split or merge.

Underload and overload history has a weight, which is calculated as follows: one_bits(mask & 0xffff) * 3 + one_bits(mask & 0xffff0000) * 2 + one_bits(mask & 0xffff00000000) - (3 + 2 + 1) * 16 * 2 / 3 (here one_bits is the number of 1-bits in a mask, and the lower bits correspond to the most recent blocks).

When underload or overload history has a non-negative weight, the flag want_merge or want_split is set.

5. Final decision​

Validators decide to split or merge shards using want_split and want_merge flags and workchain configuration parameters.

  • If the shard has depth < min_split then it will split.
  • If the shard has depth > max_split then it will merge.
  • Shards with depth min_split cannot merge, shards with depth max_split cannot split.
  • If the block has want_split flag, the shard will split.
  • If the block and its sibling have want_merge flag, the shards will merge.

Shards split and merge in split_merge_delay = 100 seconds after the decision is made.

Messages and Instant Hypercube Routing (Instant Hypercube Routing)​

In the infinite sharding paradigm, each account (or smart-contract) is treated as if it were itself in a separate shardchain. Interaction between accounts occurs solely through the sending of messages, which is part of the actor model where accounts act as actors. An efficient messaging system between shardchains is critical to the operation of the TON blockchain. A feature of TON is Instant Hypercube Routing, which enables fast delivery and processing of messages between shardchains, ensuring that messages created in a block of one shardchain are processed in the next block of the target shardchain, regardless of their number in the system.

Sharding Example​

In the provided graphic scheme:

  • Shards of a workchain are divided by time and denoted in dashed line.
  • Blocks 222, 223, and 224 relate to the masterchain block with seqno=102. Here, 222 is in one shard, while 223 and 224 are in another.
  • If a split or merge event happens, the affected shards pause until the next masterchain block.

In summary, Split Merge in TON Blockchain is a complex yet efficient mechanism that enhances scalability and interaction within the blockchain network. It exemplifies TON's approach to resolving common blockchain challenges, emphasizing efficiency and global consistency.

Sharding Details​

Split and Non-Split Parts of Shardchain​

A shardchain block and state are divided into two parts:

  1. Split Part: Complies with the ISP form, containing account-specific data.
  2. Non-Split Part: Involves data pertaining to the block's interaction with other blocks and the outside world.

Interaction with Other Blocks​

The non-split parts are crucial for ensuring global consistency, reduced to internal and external local consistency conditions. They are significant for:

  • Message forwarding between shardchains.
  • Transactions involving multiple shardchains.
  • Delivery guarantees and validation of a block's initial state against its predecessor.

Inbound and Outbound Messages​

Key components of the non-split part of a shardchain block include:

  • InMsgDescr: Descriptions of all messages imported into the block (i.e., either processed by the transaction included in the block or forwarded to the output queue, in the case of a transient message traveling along a path dictated by Hypercube Routing).
  • OutMsgDescr: Descriptions of all messages exported or generated by the block (i.e. either messages generated by a transaction included in the block, or transit messages with a destination not belonging to the current shardchain, forwarded from InMsgDescr).

Block Header and Validator Signatures​

The block header, another non-split component, contains essential information like workchain_id, binary prefix of account_ids, block sequence number (defined as the smallest non-negative integer greater than the sequence numbers of its predecessors), logical time, and unixtime generation. It also contains a hash of the immediate predecessor of the block (or its two immediate predecessors in the case of a preceding shardchain merge event), hashes of its initial and final states (i.e., the states of the shardchain immediately before and immediately after the current block is processed), and a hash of the most recent masterchain block known at the time the shardchain block was generated. Validator signatures are appended to the unsigned block, forming the signed block.

Outbound Message Queue​

OutMsgQueue in the shardchain state is a critical non-split part. It contains undelivered messages included in OutMsgDescr, either by the last shardchain block leading to this state or by one of its predecessors. Initially, each outgoing message is included in the OutMsgQueue and stored there, until they are processed or delivered to their destination.

Shard Split and Merge Mechanics​

In the context of dynamic sharding, shard configurations may change due to split and merge events. These events are synchronized with the masterchain block. For instance, if a split or merge occurs, the affected shards wait for the next masterchain block before proceeding.

See Also​