Walkthrough the Catchain

29 min readJul 1, 2020

I am the Cat who walks by himself, and all places are alike to me — Rudyard Kipling

Original text from 👉 https://docs.ton.dev/86757ecb2/p/07ddda-walk-through-the-catchain

This document was published on February 05, 2020.

Introduction

This document was created roughly three months ago when TON Labs started to reverse engineer a consensus protocol from publicly released source code of Telegram node as part of TON Labs Node implementation.

We decided to release this document after the author of the protocol, Dr. Nikolai Durov, released a consensus outline 👉 https://test.ton.org/catchain.pdf and we highly recommend everybody read the original.

In this research, we wanted to help other engineers and the general public to gain a better understanding of the underlying protocol, to provide more context by comparing it to other protocols and give more details about practical aspects of Catchain.

TON consensus (dabbed Catchain by its author) is a Proof-of-stake consensus algorithm from a family of Byzantine Fault Tolerant (BFT) algorithms. It includes the consensus algorithm as well as a protocol for message exchange between validator nodes in a network.

BFT consensus is based on Byzantine Generals agreement and describes a problem of reaching a consensus in distributed system when each network participant does not have an information about the whole network and may not trust any of its participants.

Blockchain consensus is a classical example of BFT problem as none of the block producers can be trusted or reachable at any given moment. Consensus lies at the core of any blockchain as it allows network nodes to agree on the next block in the blockchain without trusting each other.

There are generally two classes of POS consensus algorithms. First (CBC Casper, Ouroboros, etc.) when block generation is very easy but forks are allowed with subsequent process of complex agreement on their resolution among the network participants. Catchain belongs to another class — the class of algorithms where block generation agreement is hard but forks are rare or impossible (PBFT, Tendermint, Algorand etc.)

From a life-cycle perspective, the Catchain consensus includes the following stages:

stake-based validator elections
validation session startup
several block generation rounds

Each block generation round has limited time and consists of several attempts. So, if validators fail to agree during all available attempts, the round is skipped and the new block is not committed to the blockchain. In the course of a round, validators exchange messages about block candidates generated by collators, validate these candidates, select vote candidates, vote for them and finally commit the elected block to the blockchain.

To prevent consensus monopolization, the algorithm uses a round-robin role transfer from validator to the validator. So each round and each attempt several validators are assigned to generate blocks and one validator is assigned to propose a block for voting. As validators change roles from an attempt to attempt, the consensus mechanism cannot be blocked by a failure to get a decision from the majority of validators. The key idea here is to make sure that 2/3 of validator votes for a particular block are actually cast. The 2/3 cutoff threshold is a theoretical value that allows making sure that the decision via consensus is made.

To improve the overall network performance, partial cross-node message synchronization is used. It means that any validator only interacts with a randomly selected subset of validators and uses data obtained from them to make a decision during a validation round. This data also includes aggregated transitive data received from other validators and signed by their signatures.

Comparison with other solutions

In order to better understand the Catchain, the TON Labs team researched similar blockchain consensus algorithms, as this makes code reverse engineering much simpler.

TON consensus overall idea is quite similar to PBFT schemes (PBFT, Tendermint, Algorand). The same three-step phase pattern (Block approval, Voting, Pre-committing) may be found in all of them with slight variations. Let us compare some features of some of these protocols with Catchain:

PBFT

Oldest of this family of protocols, first described in 1999 by Miguel Castro and Barbara Liskov [4].

Slot leader is re-elected only if it does not perform well. In comparison, Catchain changes leader each round in determenistic fashion.
One round of block voting requires O(n²) messages (where n = number of nodes). Each node sends a message to all other. Catchain uses a special protocol which greatly reduces the number of messages: the outgoing messages are sent to a small number of neighbors (5 is a default number) and then those neighbors resend them further.

Tendermint

The closest algorithm to Catchain of all discussed in this chapter, described in [3].

As in Catchain, the proposer node is selected in a round-robin fashion each turn.
Tendermint requires only local clocks to compute timeouts. This is different from Catchain, which require globally synchronous clocks. This scheme may make Catchain vulnerable to “eclipse” attack: by manipulating NTP messages one may make a node completely out of sync (blockchain will remain correct, but this particular node will not be able to vote and propose its blocks).
A gossip message-propagation algorithm is implemented, which allows reducing the number of messages to O(n log n) for each voting. Catchain has Catchain overlay protocol for broadcasting messages, which does a similar thing.

Algorand

A smaller subset of voters is elected at each step (a “committee”). These elections are held according to a determined, but secret procedure (only a user knows that she is selected to participate in the committee, but she may prove it to others). Only these committee members participate in voting; thanks to cryptographic measures in place, it does not compromise security.
Requires no synchronous clocks, only the timeout delay should be equal among the nodes.
Algorand also uses gossip message-propagation algorithm, like Catchain. The authors claim that each node, participating in voting process, sends exactly one message during each voting stage.

Ouroboros, CBC Casper

These consensus algorithms [5][6] are quite different: they prefer to build multiple block chains, and forks are made easily. At any given moment there is a set of valid chains, and the algorithms guarantee that any valid transaction is present in any of these chains after generation of R blocks (where R depends on configuration and may be rather big).

This algorithm type requires a lot fewer synchronization messages, yet it takes more resources to handle multiple parallel chains; also new transactions becomes publicly available much later.

Components

The consensus logic is implemented in three core components:

catchain responsible for all communications and blocks delivery between validators;
validator-session responsible for the consensus itself;
validator responsible for a linkage between validator sessions and other TON components. In particular, this component verifies new blocks, interacts with collator nodes when block candidates are generated, commits blocks to the blockchain.

Components are linked on the basis of the dependency inversion principle. See further a detailed description of the validator-session component.

Validator Session Component

Consensus Algorithm Overview

To enable block validation, TON creates a list of validator nodes. This stage takes a fixed period of time configured in zerostate of blockchain. It is called validator session. This session is carried out in several rounds each aiming at generating a signed block.

The list of validators for each validation session is regulated by a specific smart contract that implements the elections logic. Such validation session is established for a number of rounds each of which ends with block committing or round skip. As a result of elections the list of nodes with their respective voting weights is created. The voting weight is in direct proportion to a node stake value, so the larger the stake, the larger its weight. Then the weight is applied in decision making. Validator nodes vote by signing a block candidate with their own private keys. If a block gets at least 2/3 of all the weights (cutoff weight), it automatically wins the particular voting round.

Every round has several stages:

block candidate generation
approval
vote
signing

A round ends once a new signed block appears. To prevent validator conflicts over a new block, each round includes a specific number of fixed-time attempts pre-configured in blockchain zerostate. If no consensus is achieved within the maximum number of attempts, the round is considered failed, the committed block is skipped and will not be written to a blockchain. In general case when validators fail to reach consensus for a few rounds, new validator election can resolve the deadlock.

Each validator node stores the validation session state and synchronizes it with other nodes after each modification (i.e. creates a snapshot). Synchronization is implemented through the Catchain protocol by message broadcasting (i.e. increments to the snapshot are made). The details of synchronization are described below in the Сatchain protocol overview. Note that post-modification synchronization is not applied to all nodes, but to neighbor nodes. This subset is non constant and periodically updated, so this allows to minimize traffic between Catchain nodes and to deliver the node state transitively to all of them. The state validity is controlled through signature verification. The state consists of the current round state and of a list of previous round states (history of previous rounds).

The round state, in turn, consists of the list of attempts and of signatures of the elected commit candidate block (pre-committed block). Finally, each round attempt includes the following steps:

validator nodes exchange block candidates for approval;
primary node for the current attempt sends the candidate block for voting to the rest of nodes (based on node priority computed for this attempt);
validator nodes exchange votes.

It is noteworthy that to avoid deadlocks during voting and candidate generation, node priority is set depending on the number of nodes, round number, attempt number. So for each attempt priority changes and some validators gain privileges for the attempt. For example:

priority to provide candidate blocks from a linked collator (only first validatorSessionOptions::round_candidate can propose a new candidate for approval);
priority as ranging criteria for selecting candidates for approval process;
priority to choose an approved block for voting (only one node can do it).

Also, priority is used to calculate delay in the course of approval process during the round attempt (minimum priority corresponds to smaller delays for approval).

Another evident and important point is that decision of each validator is checked by the rest of validators. Validator node public key is used for signature verification. At the start of each validator session each validator receives information about all other validators including:

the list of validators pre-created by the smart contract so that nodes could be addressed by indexes during the session;
public keys of each validator;
validator weights according to their stakes. Each time a validator receives block candidates, approvals or votes from other validator nodes, it checks the signature (and in some cases priority as specified above) to make sure that:
the sender is authorized to make the decision;
the decision was actually made by the sender.

Consensus Stages

The stages (slots) of a round are following:

Block candidate generation. Each node having block generation priority for the round generates a new block candidate which is requested from collator (see validatorsession::ValidatorSession::Callback::on_generate_slot for details). As soon as the candidate appears, it is sent to other validator nodes (validatorSession.candidate > validatorSession.message.submittedBlock).
Block candidates approval. Blocks from the previous stage are collected at each validator node and processed for approval. The approval process is not related to the consensus itself and is aimed at checking that blocks are not corrupted in terms of the bound data (see validatorsession::ValidatorSession::Callback::on_candidate of callback for details). As soon a block is approved, it is signed for approval by each validator. Then the validatorSession.message.approvedBlock message is broadcast with the round number and the ID of the approving node. So, each validator is aware which node has approved the sent block. The block is considered approved by a node when it receives 2/3 of approval messages.
Voting attempts. Several block voting attempts are carried out. Each attempt is time limited and validators are supposed to fit into the slot. While votes for the current candidate are still accepted past the attempt deadline, it can cause a situation when two attempts result in different votes for multiple candidates, the case is considered further. The block candidate for voting is selected by the attempt’s main validator node and other nodes are notified by validatorSession.message.voteFor message (see ValidatorSessionRoundState::generate_vote_for for details; the main validator node which proposes the block for the attempt is provided by ValidatorSessionDescriptionImpl::get_vote_for_author method). The block selection involves two aspects: a) the node ranges approved blocks by nodes priority for the current attempt, so in each attempt the list is reordered, and b) the main validator node randomly selects a block for voting from this list. Each validator node processes the above-mentioned message and selects a block to vote for. A validator does not have to vote for the proposed block and is free to select another one. So the proposed block is more of a tip to provide an aim and to accelerate voting. Voting implies two things: a) signing block to mark it is voted by a particular validator node, and b) broadcasting this information in a validatorSession.message.vote message to the rest of validators. As soon as any approved block gets at least 2/3 of total validator weights in the course of voting, it becomes the candidate for signing (pre-commit block). Chances are that votes are received after the attempt end. In this case the late votes are processed simultaneously with the new attempt. Generally, votes for each finished attempt may be accepted past deadline; constituting no logical error, it allows finishing the round faster. And, if any of previous attempts ends up getting 2/3 of total weights or more even past its deadline, it still yields a new pre-commit candidate. In case of a conflict where two attempts propose different pre-commit blocks, the latest prevails. It is noteworthy that for performance reasons, a block vote obtained in one attempt is reused on the rest of attempts automatically.
Block committing. As soon as a round attempt yields a pre-committed block, the signing process starts. The validator that gets a pre-committed block in the current round signs it and broadcasts to other validators using a validatorSession_message_commit message (see ValidatorSessionImpl::check_sign_slot and related logic in ValidatorSessionImpl::process_blocks for details). All other validators receive the broadcast, check the sender signature and update their state (see ValidatorSessionRoundState::action(…, validatorSession_message_commit for details). At some moment, a particular validator gets not less than 2/3 signatures from other validators (in terms of validator weights). This leads to a) switching to a new round (increasing the round sequence number by 1), and b) committing the signed block to the blockchain (see validatorsession::ValidatorSession::Callback::on_block_committed for details).

In case of failure to get a signed block during the configured number of attempts (ValidatorSessionOptions::max_round_attempts), a new round starts and the failed one is marked as skipped (see validatorsession::ValidatorSession::Callback::on_block_skipped).

Validator Session Protocol Messages & Structures

Validator session protocol consists of:

incoming events: validatorSession.round.Message ****(which may be one of following sub-types: validatorSession.message.submittedBlock, validatorSession.message.approvedBlock, validatorSession.message.rejectedBlock, validatorSession.message.voteFor, validatorSession.message.vote, validatorSession.message.precommit, validatorSession.message.commit, validatorSession.message.empty), validatorSession.blockUpdate, validatorSession.candidate;
required outgoing query validatorSession.downloadCandidate ****(with validatorSession.candidate ****as an event in subsequent event);
internal structures which may be used in events and queries above.

Main flows:

Consensus stages
Block candidate generation
Round priority validator proposes block candidates using validatorSession.message.submittedBlock message.
Each validator with block-candidate proposal priority can propose block within a limited time slot after the round starts. Blocks proposed outside of the time slot are ignored.
Block candidates approval
After receiving validatorSession.message.submittedBlock each validator starts checking the block for approval. In case of approval validator generates validatorSession.message.approvedBlock, in case of rejection — validatorSession.message.rejectedBlock.
Voting attempts
Validator with a priority to propose block for voting (“vote-for” block) chooses a random block for voting from the list of approved blocks and generates the validatorSession.message.voteFor message.
Validator which receives validatorSession.message.voteFor checks if this message is generated by a validator with "vote-for" block proposing priority. If so, uses the proposed "vote-for" block as a priority block for voting.
In the first voting attempt validator votes on a block which has been received in a validatorSession.message.voteFor message. This is the fastest way of consensus decision-making. Same voting on a block received in the validatorSession.message.voteFor message is carried out after the max number voting attempts. As a result validatorSession.message.vote is generated with a vote on a specific block.
If the attempt is not first and is less than maximum number of voting attempts, a validator chooses a block to vote proposed by another validator with min priority for the round. As a result validatorSession.message.vote is generated with a vote on specific block.
If a validator voted on a block in one of previous round attempts, the validator generates validatorSession.message.vote with the same vote.
When a validator receives the validatorSession.message.votemessage, it checks whether at least 2/3 of voting weights are received for the block in question. If so, the validator generates validatorSession.message.precommit with a block selected as a candidate for committing.
Block committing
When a validator receives the validatorSession.message.precommit message, it checks whether at least 2/3 of voting weights are received for the precommit block proposed in the validatorSession.message.precommit message. If so, the validatorSession.message.commit message is generated with a block for commit and the relevant validator signature.
When a validator receives the validatorSession.message.commit message, it checks whether least 2/3 of voting weights are received to commit the proposed block. If so, block is committed and a new round is started.
If during the maximum number of attempts no block is committed, the round marked as skipped and a new round is started.
Block candidate downloading

To speed up consensus processing there is the validatorSession.downloadCandidate query that can be sent by a validator via broadcast to request a round block-candidate with a specific identifier. A validator makes this query when it has no block candidate for further consensus processing.

2. Internal structures:

validatorSession.config. This structure is configured in the zerostate and contains consensus configuration parameters shared by all validators.

catchain_idle_timeout : double - timeout between consensus iterations calls; each consensus iteration may result with new catchain block generation;
catchain_max_deps : int - maximum number of catchain blocks for merging during consensus iteration;
round_candidates : int - number of block candidates per round of the Block candidate generation stage;
next_candidate_delay : double - delay between block candidate proposing;
round_attempt_duration : int - round attempt duration in milliseconds;
max_round_attempts : int - maximum number of attempts per round;
max_block_size : int - max block size;
max_collated_data_size : int - max size of collated data of the block.

validatorSession.candidateId : is a part of the validatorSession.downloadCandidate query and contains block-candidate hashes.

src : int256 - hash of a public key of the validator that generated the block-candidate;
root_hash : int256 - block root hash;
file_hash : int256 - block file hash;
collated_data_file_hash : int256 - block's collated data hash.

3. Events:

validatorSession.round.Message

validatorSession.message.submittedBlock message is related to the Block candidate generation stage. It informs that a validator generated a new block-candidate and submitted it to Catchain. Each validator has a limited time slot for block-candidate generation (and proposing). This slot is computed according to the node priority which depends on round and current time. During the block generation stage there may be up to round_candidatesblock-candidates. A new candidate may be generated if the current consensus round is not finished (new block is not committed) during round_attempt_duration. The message has the following structure:
round : int - number of the round when new block-candidate appears;
root_hash : int256 - block-candidate root hash;
file_hash : int256 - block-candidate file hash;
collated_data_file_hash : int256 - block-candidate data hash.
Actions: this message has to be generated when a validator generates new block-candidate
validatorSession.message.approvedBlock message is related to the Block candidate approval stage. It informs that a validator approved the block candidate in a specific round. Each validator chooses a list of blocks for approval sorted by node priority. Only blocks that were not approved before are included in the list. The approval itself is performed by a validator (as opposed to a validator session). The block is approved only from specific time (CandidateDecision::ok_from) computed by a validator. Block approval is initiated immediately after block candidate verification and signing. The message has the following structure:
round: int - number of the round when candidate block was approved;
candidate : int256 - hash of block-candidate;
signature : bytes - validator signature.
Actions: this message has to be generated when validator approves one or several block candidates.
validatorSession.message.rejectedBlock message is related to Block candidate approval stage. The message informs that validator has checked the block candidate and rejects it. This message is ignored by consensus itself (has no side effects except of logging if the message has been received by a validator). The message has following structure:
round: int - number of the round when candidate block has been rejected;
candidate : int256 - hash of block-candidate;
reason : bytes - rejection reason (validator specific).
Actions: this message is generated when block verification is failed. The message is not transitive, and should be sent only if the current validator rejects the block-candidate.
validatorSession.message.voteFor message is related to the Voting attempts stage. The message can be sent only by a validator with priority to generate an attempt “vote-for” candidate. The “vote-for” block is selected at random from approved blocks by a validator with a “vote-for” priority for the current attempt.
round : int - number of the round;
attempt : int - number of an attempt where candidate block will be chosen as "vote-for" block;
candidate : int256 - block-candidate hash.
Actions: this message has to be generated if:
a) node has “vote-for” block generation priority for this attempt;
b) node has at least one approved block;
c) node has has no precommitted block;
d) node sent no validatorSession.message.voteFor during this attempt.
validatorSession.message.vote message is related to the Voting attempts stage. The message is sent to inform that a validator votes for a candidate. The message has following structure:
round : int - number of the round;
attempt : int - number of an attempt where validator voted for candidate block;
candidate : int256 - block-candidate hash.
A validator votes for block in one of the following case (the logical OR):
a) a block was voted in one of previous attempts during the round;
b) a block was proposed by a validator with min priority for the round if current attempt is not first one and the maximum number of round attempts was not reached;
c) a block was proposed in validatorSession.message.voteFormessage by a validator with "vote-for" generation priority if attempt is the first or the max attempt number is exceeded (opposite to the case (b) above).
Actions: this message has to be generated if there is no precommitted block during the current attempt and one of validator voting cases triggered.
validatorSession.message.precommit message is related to the Voting attempts stage. The message is sent by each validator to notify that the validator has selected voted block as a precommitted. The precommitted block has to be voted by at lease 2/3 of total validators weight. Note, for some reason telegram’s consensus ignores the case when node precommit block is not equal to candidate for this round and only prints warning to log about such case. The message has the following structure:
round : int - number of the round;
attempt : int - number of an attempt where validator chose candidate block as a block for precommit;
candidate : int256 - block-candidate hash.
Actions: this message has to be generated when all conditions below are met:
a) node has not sent validatorSession.message.precommit in this attempt;
b) there is a block with 2/3 of total validators weight.
validatorSession.message.commit message is related to the Block committing stage. This message informs that validator signed the block candidate as a block to be committed for a round. The message has the following structure:
round: int - number of the round
candidate : int256 - block-candidate hash;
signature : bytes - signature of the validator.
validatorSession.message.empty a special message which is used as a marker to stop generation of messages during synchronization from internal validator state to the list of incremental messages which will be sent to other validators. The message has following structure:
round : int - number of the round where synchronizations takes place;
attempt : int - number of an attempt where synchronization takes place.
Actions: this message has to be generated to indicate there is no additional messages to sync state (in attempt and round).

b. validatorSession.blockUpdate message is the root message for validator session blocks update. It is packed to a payload of catchain.block.data.vector. This message is generated after each consensus iteration and has the following structure:

ts : long - timestamp for block's update generation (unix time, global);
actions : vector validatorSession.round.Message - list of validatorSession.round.Message with incremental updates for consensus state synchronization on other validators;
state : int - state hash after action is applied; it is used like a checksum for sanity checks (computed recursively for session state; not a trivial linear hash of the buffer with actions).

c. validatorSession.candidate message is sent to Catchain as a broadcast when new candidate block appears (after validator on_generate_slot callback). Also, it may be sent at a start of Catchain execution on each validator for all blocks approved this validator approved as candidates to Catchain (from validator get_blocks_approved_by and get_approved_candidate). This message initiates blocks approval if received in a broadcast and has the following structure:

src : int256 - validator which has generated a block-candidate;
round : int - number of a round where block-candidate appears;
root_hash : int256 - root hash of block-candidate;
data : bytes - block-candidate data;
collated_data : bytes - block-candidate collated data.

4. Queries:

validatorSession.downloadCandidate messages is used as broadcast to request a round block-candidate with a specific identifier. A validator generates it, if it has no block candidate for further consensus processing.

Request:

round : int - number of the round where block-candidate appears;
id : validatorSession.candidateId - block-candidate identifier.

Side effect:

validatorSession.candidate - block-candidate is sent as an event during the request processing.

Catchain Component

Catchain Overview

Catchain is a communication protocol between validators. It does not execute the consensus algorithm itself but prepares data required for the decision-making of a higher-level component: validator-session. Essential catchain tasks are:

setting up a network overlay on the top of ADNL ensuring communication between validators;
setting up and updating a list of neighbor nodes for direct communications inside the overlay;
receiving blocks from other validators and sending back decisions of the current validator;
controlling blocks dependencies;
managing an internal database holding current catchain session results
restoring catchain session state after a validator restart;
detecting forks and blaming validators;
maintaining the consensus algorithm.

In general, catchain component provide an operational framework for other elements of the validator-session consensus.

Node Catchain Initialization

Catchain session begins with the creation of the CatchainImpl and the CatChainReceiverImpl objects. The CatChainReceiverImpl configures the ADNL overlay upholding the communication with other validators.

Next step is CatChainReceiverImpl restoring previously received blocks from a RocksDB database instance (see CatChainReceiverImpl::read_db_from and CatChainReceiverImpl::read_block_from_db for the details).

On top, there is always a block with hash=0 acting as a starter block for downloading block predecessors and dependencies. The central processing loops starts after the database reading stage is complete (see CatChainImpl::on_receiver_started and CatChainImpl::send_process for the details). The consensus algorithm initiates new block candidates generation for further approval — the block transfers to the catchain when a new candidate appears. In case there are no blocks, validator awaits for blocks from other validators on the catchain.

Scheduled Actions

Each validator sends results of its work only to several neighbors (currently set to 5) minimizing traffic. Neighborhood randomly changes every 60–120 seconds. Every 2–3 seconds, the system randomly picks a validator from the overall validator list for synchronization. This synchronization is bi-directional:

The validator-initiator sends a list containing delivered blocks heights (including vector timestamps, according to “Catchain Consensus: An Outline”). The validator expects to either receive absent blocks or a fork event notification in response. In the case of confirmed forking, consensus will blame the validator and discard all messages. Only the current validator can verify forking. Validator compares it’s own block heights list with the received list and sends the difference, if any, to the requester. Such a process optimizes network traffic and reduces the average height of delivered blocks while limiting the count of outgoing response messages to 100.
The validator-initiator requests the delivery of all absent dependent blocks generated by a validator-answerer.
Invoking consensus algorithm iteration (will be described below). Each synchronization adds information about states of other validators, making the next consensus iteration possible on the validator.

Blocks Processing

There are several types of blocks in the catchain:

blocks written to a blockchain;
catchain blocks with a state of the particular validator (CatchainReceivedBlock). They are the messages with source validator number identification, consensus algorithm iteration number (height) and consensus increment messages; CatchainReceivedBlock are the temporal sources for consensus blocks creation (CatchainBlock);
CatchainBlock blocks built from several CatchainReceivedBlock blocks(CatchainBlock consists of CatchainReceivedBlock blocks states with maximal known height for a validator ).

The CatchainReceivedBlock block consists of the following:

catchain session identifier (to exclude the case when blocks from the previous catchain session are processed);
number of the block origin source validator;
block height (it is equal to the consensus algorithm iteration number for a particular validator);
fork number (if several forks from the same validator are detected, the chain of blocks is invalidated and the validator is blamed);
previous block sent to other validators (outgoing block);
dependent blocks received by other validators (incoming blocks); note, that an incoming block cannot depend on two blocks from the same source validator; in general, this is a DAG.

The dependent blocks graph allows for:

recursively downloading of all blocks required for the full state of the processed block;
recursively marking a subgraph of blocks as an invalid if forks are detected from a particular source validator.

Each validator contains a list of states of other validators. Each of them stores CatchainReceivedBlock blocks that came from them. Every new incoming CatchainReceivedBlock block is checked regardless of which data channel it came from (directly from the validator or transitively, see CatChainReceiverImpl::validate_block_sync). If the block signature does not match the expected signature of the sender validator, or if the block is invalid, the block is ignored.

The validator checks each catchain validator for forks. Only one fork per validator is allowed. In case when the same validator sends two different blocks with the same height, it is marked as a blamed and all CatChainReceivedBlockImpl corresponding to this validator are invalidated. The validator itself ignore till the end of the current catchain session.

After the CatChainReceivedBlockImpl block is received, its processing is initiated (see CatChainReceiverImpl::receive_block). Then it is recorded to the database. The processing procedure downloads all dependents for the block and further adding the block to a queue of blocks ready to be run. This download procedure is done each 2-3 seconds by synchronization with other validators which are being asked for absent CatChainReceivedBlockImpl blocks.

When any data updates are received (from the database during initialization, when new blocks are received, and while adding new blocks after the work of the consensus algorithm (see CatChainImpl::processing_block)), the CatChainReceivedBlockImpl block execution procedure is launched.

Each validator contains state lists for other validators. Each of them stores CatchainReceivedBlock blocks received from others. Every new incoming CatchainReceivedBlock block is checked regardless of which data channel it came from (directly from the validator or transitively, see CatChainReceiverImpl::validate_block_sync). Validator ignores the block if the block signature does not match the expected signature of the sender validator or if the block is invalid.

The active validator checks each catchain validator for forks. Only one fork per validator is allowed. In case the same validator sends two different blocks with the same height, catchain marks it as blamed and all CatChainReceivedBlockImpl blocks corresponding to this validator are invalidated. Consensus mechanics then ignore the validator itself until the end of the current catchain session.

Receiving the CatChainReceivedBlockImpl block initiates the processing (see CatChainReceiverImpl::receive_block) and creates a database entry. The processing procedure downloads all dependents for the block. At the next step, it adds the block to a queue of blocks ready to be run. The download procedure is done every 2-3 seconds through synchronization with other validators required to provide absent CatChainReceivedBlockImpl blocks.

The CatChainReceivedBlockImpl block execution procedure initiates whenever any data updates are received (from the database during initialization, when new blocks are received, and while adding new blocks after the work of the consensus algorithm (see CatChainImpl::processing_block)).

Block execution includes:

creating a fork from the existing previous block (in this case, blame procedure initialization is possible if the fork already exists);
preliminary procedures for processing the block (pre_deliver);
processing of the block.

Pre-processing of a CatChainReceivedBlockImpl includes checking forks (see CatChainReceivedBlockImpl::pre_deliver).

Block processing (see CatChainReceivedBlockImpl::delivery) includes the following:

deliver_block — notification that the block is ready for this validator. This notification consists of:

Notifying all neighbors about the appearance of a new CatChainReceivedBlockImpl block;
Generating a new CatchainBlock block and placing it on the top of the chain from the validator that sent the corresponding CatChainReceivedBlockImpl block. The CatchainBlock block used in the consensus algorithm is a copy (snapshot) of the corresponding CatChainReceivedBlockImpl block excluding the data used for dependencies downloading process;

dep_delivered — all dependent CatChainReceivedBlockImpl blocks (outgoing dependency) notification. This places dependents into a queue of blocks ready to be run;
block_delivered — internal data update on validator-initiator (CatchainReceivedBlockImpl sender) sent blocks.

CatchainBlock blocks received from the validator are the input for the consensus algorithm. Structurally, this block is very similar to the CatChainReceivedBlockImpl block. However, it contains all the data necessary for further processing (unlike CatChainReceivedBlockImpl, where some data may be missing). Catchain stores a list of the CatchainBlock top blocks — one for each validator — and runs the consensus algorithm periodically by the timer at the beginning of work and on-demand (see CatChainImpl::send_process for the details). The consensus iteration identification for each validator is the height of a block that the consensus algorithm generated. Thus, a pair (validator number, block height) uniquely identifies the block for a particular validator.

Processing consensus results of one validator on another validator might result in two different blocks with the same height and validator numbers. This will result in fork appearance and identification key will extend to (validator number, block height, fork number). However, since catchain does not allow forks, the source validator where forked block originated will be blamed. So the fork number may be skipped and CatchainBlock may be identified identification may using (validator number, block height).

The consensus iteration begins by selecting a random subset from the list of CatchainBlock top blocks (no more than max_dept=4) and passing them to the consensus algorithm described above (see ValidatorSessionImpl::process_blocks). Note that a separate validator sent each such block and there can’t be two blocks from a single validator. These blocks merge within the consensus algorithm, and a new CatchainBlock appears on their basis. Catchain reports this block appearance (see CatchainImpl::processed_block). Adding a new block leads to writing it into the database and creating a CatChainReceivedBlockImpl block from it, further sent to neighbors

Catchain Protocol Messages & Structures

Catchain protocol consists of:

incoming event catchain.blockUpdate;
required outgoing queries catchain.getBlock and catchain.getDifference;
optional outgoing queries (not used in the catchain component itself, but might be sent externally): catchain.getBlocks, catchain.getBlockHistory;
queries responses: catchain.BlockResult, catchain.Sent, catchain.Difference;
internal structures that can be used in all events and queries above.

Main flows:

Validator synchronization request:
validator periodically and randomly updates the list of neighbour validators (see the description above);
validator periodically chooses one random validator from a list of neighbor validators (see description above) and sends to it:
catchain.getDifference request with a list of heights for blocks already delivered to validator-requester;
catchain.getBlock request for a top block's dependencies (in terms of height) which is received but not fully resolved (not all dependencies are received by a validator); validator randomly chooses up to 16 dependencies for a top block and sends a catchain.getBlock request for each of them.
Validator synchronization events processing:
validator receives incoming catchain.blockUpdate events and updates the internal block's data structures.
Validator forks event processing:
validator receives an incoming catchain.differenceFork event, checks the fork proof and marks the counterparty validator that sent fork as blamed; so all data from this validator will be discarded; additionally, the same height block received from this validator (fork block) will be marked as "ill" as well as all dependent blocks from it.
Consensus iteration

each catchain.blockUpdate may lead to the decision where one or several catchain blocks on the top of counter-party validators’ are fully resolved (meaning these blocks will have enough data including dependencies to be used in consensus calculations);
a validator randomly chooses up to CatChainOptions::max_deps(equal to 4 for now) top blocks from different counter-party validators and sends them for further processing to the validator session component;
the validator session component merges such dependencies and gets a new merged state;
according to the new state, the validator session component generates incremental messages that transform the state before the merge (previous block) to a state after merge (new block). This batch of messages is included as a payload to a Catchain structure catchain.block.data.vector and is used as a new Catchain block data: The height of a catchain block is equal to the iteration index increased sequentially after each consensus iteration;
the new Catchain block is stored on the current validator without being immediately sent to other validators, so counter-party validators have to request current validator for blocks update using the catchain.getDifference request to obtain computed blocks (pull model).

Internal structures:

1.catchain.block.dep

This structure provides information about a dependent block. A dependent block is always received from another validator and has the structure described below. Note that this structure does not contain information about the block data, but only its description.

src: int - index of validator that generated the block;
height : int - height of the block on a validator with index src;
data_hash : int256 - block data hash; used in block pre-validation;
signature : bytes - signature done by a validator with index src of the block; needed for pre-validation of the block.

2.catchain.block.data

This structure describes the block with links to the previous block on the validator and dependent blocks used to generate the current one. For the specified (src, height) there can be only one previous block in a Catchain. If forks are detected, the validator that sent the second block candidate for specified (src, height) is marked as blamed and all its data is discarded. The catchain.block.data structure described below:

prev : catchain.block.dep ****- previous block description;
deps : vector of catchain.block.dep - list of dependent blocks used to generate this block.

3.catchain.block

This structure describes a block with a payload.

incarnation : int256 - ID of the Catchain session equal to the hash of the first block used at the start of Catchain session;
src : int - index of the validator that generated the block;
height : int - height of the block on a validator with index src;
data: catchain.block.data - block header with information about the previous block and dependent blocks used to generate the current block.

4.catchain.block.inner.Data

This is a variable structure with one of the following subtypes: catchain.block.data.badBlock, catchain.block.data.fork, catchain.block.data.nop, catchain.block.data.vector. This structure is placed immediately after the catchain.block structure and contains the corresponding block payload.

catchain.block.data.vector
This message contains the internal validator session component data represented by a list of messages specific for a validator session. The catchain.block.data.vector structure is used as a container to distribute consensus algorithm data between validators.
msgs: vector of bytes - internal validator session data (is used as a buffer of bytes for Catchain component).
catchain.block.data.fork
This message contains fork proofs for a specified pair of blocks. When two blocks with different hashes, but the same height are received from a validator with index src, a fork is detected. In this case, the validator in question must be blamed and all incoming data from it must be discarded. All blocks dependent on a detected fork must be discarded.
left : catchain.block.Dep - first known block;
right: catchain.block.Dep - detected fork block.
catchain.block.data.badBlock
Reserved and is not used at the moment
catchain.block.data.nop
Reserved and is not used at the moment

Events:

1. catchain.blockUpdate

This event informs the validator that a specific block is updated. The validator then has to add it to the processing queue, check for forks and check all upstream and downstream block dependencies. Dependency checks may result in one or multiple block status updates. Once fully resolved, a block can be used as a source for state computation of the next consensus iteration. A validator session iteration uses a random subset of fully resolved blocks (blocks having all dependent blocks received and pre-validated by the current validator). This subset contains blocks from different validators for further merging and building a new Catchain block according to the resulting merged state. catchain.blockUpdate has the following structure:

block : catchain.block - block description with a mandatory catchain.block.inner.Data payload.
signature : bytes - block signature performed by a validator (with validator index block.src); used for block pre-validation.

Queries:

1. catchain.getBlock (mandatory)

This query is used by the catchain component to request an absent block from another validator.

Request:
block : int256 - hash of the requested block;
Response — catchain.BlockResult (variadic):
catchain.blockResult - sent if the block is found
block : catchain.block - description of the requested block with catchain.block.inner.Datapayload
catchain.blockNotFound - sent if the block is not found

2.catchain.getBlocks (optional; not used by Catchain component internally)

This query is used to request several blocks from another validator.

Request:
blocks : vector int256 - the list of requested blocks;
Response — catchain.sent:
cnt : int - the number of blocks sent back.
Side effect:
Several catchain.blockUpdate events are sent back to the validator-requester before response.

3.catchain.getDifference (mandatory)

This is the initial request sent by one validator to another one to receive absent blocks. The validator-requester sends а list of delivered heights to the counter-party and expects to get back blocks that were not delivered (difference). Initially, the validator-requester may send a list of zero heights to the counter-party to initiate synchronization of blocks. Also, the catchain.getDifference request should be regularly made to neighbor validators to synchronize with them.

Request:
rt : vector int - the list of heights of blocks already delivered to a validator-requester.
Response — catchain.Difference (variadic):
catchain.difference - sent when no forks are detected (regular case)
sent_upto: vector int - the vector of heights known on a validator-responder; not used in a Catchain component now;
catchain.differenceFork - sent when forks are detected
left : catchain.block.dep - the first known block;
right : catchain.block.dep - the detected fork block.
Side effect:
Several catchain.blockUpdate events sent back to a validator-requester before response catchain.difference.

4.catchain.getBlockHistory (optional, not used by the Catchain component internally)

This query is used to obtain blocks used to build a block with a specified reverse height (number of blocks reverse to the specified block).

Request:
block : int256 - the target block hash;
height : long - the number predecessor blocks of the block;
stop_if : vector int256 - list of block hashes which should stop search if one of them is detected during the history processing.
Response — catchain.sent:
cnt : int - the number of blocks sent back.

References

Pease, Marshall; Shostak, Robert; Lamport, Lesli Reaching Agreement in the Presence of Faults, https://dl.acm.org/doi/10.1145/322186.322188
Yuval Marcus, Ethan Heilman, Sharon Goldberg. Low-Resource Eclipse Attackson Ethereum’s Peer-to-Peer Network, https://eprint.iacr.org/2018/236.pdf
Ethan Buchman, Tendermint: Byzantine Fault Tolerance in the Age of Blockchains, https://atrium.lib.uoguelph.ca/xmlui/bitstream/handle/10214/9769/Buchman_Ethan_201606_MAsc.pdf
Miguel Castro and Barbara Liskov. Practical Byzantine Fault Tolerance, http://pmg.csail.mit.edu/papers/osdi99.pdf
Aggelos Kiayias, Alexander Russell, Bernardo David, Roman Oliynykov. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol, https://eprint.iacr.org/2016/889.pdf
V. Zamfir, “Casper the friendly ghost: A correct by constructionblockchain consensus protocol,” https://github.com/ethereum/research/blob/master/papers/CasperTFG/CasperTFG.pdf
Jing Chen, Silvio Micali. Algorand, https://arxiv.org/pdf/1607.01341.pdf

About TON Labs

Founded in May 2018, the company is focused on developing core infrastructure and open source ecosystem for Free TON.

Visit tonlabs.io for more information.

The content of this article is licensed under a Creative Commons Attribution 4.0 International license.

Free TON is a decentralized blockchain network that was launched by a community of developers and validators on May 7, 2020.

Website 🔷 Telegram 🔷 Twitter 🔷 Facebook 🔷 Reddit 🔷 Linkedin