Catchain Consensus Algorithm of Telegram's TON Blockchain [A Deep Dive]

In our previous review, we made a detailed overview of Telegram Open Network and the specific features in the operation of key nodes (validators) of TON Blockchain. In this article, we will elaborate on one of the key aspects affecting the security and correct operation of the TON blockchain – a protocol allowing to achieve consensus between the network validators that are thoroughly described in the recently released document Catchain Consensus: An Outline authored by Nikolay Durov.

The initial name of the protocol during the first stage of research and development was Catch-chain (a trap blockchain) because essentially it is a separate blockchain for the prevention of malicious events impeding consensus achievement on the main TON blockchain. Later on, its name was shortened to Catchain.

The consensus algorithm of TON is described as tolerant towards system breaches connected with the so-called Byzantine fault. Byzantine Fault Tolerance is a popular buzzword nowadays and it’s important to clarify here what it means.

All distributed ledgers are built to manage a system, and the problem with Byzantine generals formulated by Leslie Lamport, a computer scientist, actually predates cryptocurrency. Imagine several separated Byzantine generals in the middle of the war.

They can send messages to each other but they are still not on the same page with how the war will go on and so they vote. A manipulative person with a decisive vote can send a vote for the attack to some generals and a vote for retreat — to others. Naturally, this only an example but one can imagine the very same problem occurring in the first-gen blockchains.

A truly Byzantine Fault-tolerant blockchain is the one where new blocks (and therefore new actions) are made only after total verified consensus. This consensus prevents the creation of new similar blockchains.

There is a type of blockchains where this is not the case with Bitcoin Cash as perhaps the most notable result. The new blockchains are usually built with Byzantine Fault tolerance to ensure the integrity of the community behind the system and the system itself.

Catchain pertains to the latter type of algorithms in which preliminary agreement occurs before a new block is created, and midway forks are impossible. The Catchain consensus model is based on the already existing algorithm practical Byzantine Fault Tolerance (Hyperledger Fabric, Zilliqa) having increased resistance to Sybil attacks in asynchronous networks and also has similarities with Tendermint (Cosmos) and dBFT algorithms (Neo, Algorand). However, there is a number of principal differences that allow us to call it a separate algorithm type.

Validation rounds

For a particular task of creation of new blocks on one of the TON blockchains (masterchain or one of its active shardchains), a separate group consisting of several validators is created. The members of this group are used to create a private overlay network inside ADNL as well as for the launch of a corresponding sample of the Catchain protocol.

The process of consensus achievement consists of several rounds which occur inside one catchain. At one point in time, there can be several rounds because some stages of a single round can intersect with others.

Every single round ends either with a collective acceptance of a candidate block suggested by one of the members of the process or with the acceptance of a ‘zero candidate’, i.e. without accepting any of the suggested candidates.

The round is considered finished only after a potential candidate collects the signatures of over two-thirds of all validators, and this event can be added into a special CommitSign, after which the process will automatically start to participate in the next round (with a new identifier).

The events of one validation round occur in the following order:

1. At the beginning of each round several validators (from a pre-selected list) suggest their so-called candidate blocks (with latencies depending on priority) and record this fact into a given Catchain using Submit events.
2. As soon as the process gets all the necessary files, it starts validating the candidate and as a result, there occurs one of the events: Approve or Reject for the given candidate.
3. Further on, each validator votes either for the candidate that received more than two-thirds of votes or, unless there is one, for a valid candidate with the highest priority. The voting is done by creating voting events embedded into new messages.
4. In case of every slow attempt (i.e. any other attempt than the first), the process will vote for the candidate that has been pre-approved (by that same process) or for the candidate that was suggested by VoteFor.
5. In case this candidate receives over two-thirds of ‘for’ votes during such an attempt, then the next event PreCommit is created, proving that all other candidates are rejected.If the candidate block gets PreCommits from more than two-thirds of all validators within this attempt, it will be accepted and marked by the event CommitSign with a valid block signature.
6. All the signatures of blocks are registered in the Catchain and are ultimately collected for the creation of a ‘block proof’ (having the signatures of more than two-thirds of the validators for this block). This proof is an outside gateway of the consensus protocol and is distributed in the overlay network of full nodes which sign the new blocks of this shardchain or masterchain. 
7. As soon as a candidate block collects all the CommitSign signatures from more than two-thirds of all validators, the round is considered finished, and the process automatically starts participating in the next round ignoring all events related to other rounds.

Fork prevention

As mentioned above, in blockchains with traditional protection mechanisms using Proof-of-Work and Proof-of-Stake and their hybrids, for a small period, several correct blockchains or forkchains can coexist simultaneously of which one is further selected.

The TON Blockchain system built on the base of small blockchains (multi-blockchains) practically leaves no chances for the occurrence of such events as it uses the blockchain as a means of broadcasting of such messages, i.e. uses the blockchain as a means of broadcasting inside a certain group of processes. However, there exists a very small probability of creation and simultaneous confirmation of several identical blocks.

For prevention of such scenarios, there was created the Catchain protocol that allows to detect forks at the earliest stage of their emergence by way of creation of two (or more) different versions of the same message and sending them to different groups of peers.

The block signatures on Catchain are created in such a way that the confirmation of forks (i.e. proof of their intended creation) becomes extremely simple as in reality a hash of a very small structure (containing a magical number, an ordinal number of the block and the hash of the rest of the message) is signed. As a result, to prove a fork, there are only needed two small structures and two signatures.

As soon as there is a fork found (it usually happens in recursive loading of dependencies of some messages), one group of nodes starts ignoring the messages of a neighbouring group and all of its subsequent messages, as they are not accepted and broadcast elsewhere. Yet, the messages created before the fork was found can be loaded if they are referenced in the messages (blocks) created by the processes that do not know about this fork before they refer to them.

Then another service message containing a corresponding proof of fork is created and broadcast to all the neighbouring nodes. From this moment on, all subsequent messages lose dependence from the messages of a known ‘bad’ node and in case of violation, these messages will be rejected by all the ‘honest’ peers in this group.

Every node stores its copy of the list of ‘bad’ members of the network (the ones that have created at least one fork). This list is constantly updated in case of detection of a new fork. Thus, if the sender is identified as ‘bad’, his or her message will be ignored and rejected.

Conclusion

It is well-known that the Catchain protocol was first developed in December 2018 and tested on 300 nodes distributed all over the world. During the test, the time in which consensus on block creation was achieved constituted 6 seconds.

Later on, in December 2019 there was issued a document that showed that the Catchain protocol was 100% ready. Therefore, a conclusion can be made that all the preliminary tests were successfully passed.

However, it was mentioned in the status section that the complete documentation was only 95% ready, while the final document was only released a year after in February 2020.

Thus, it is logical to conclude that the theoretical part is quite thoroughly worked out and presents a fully completed original consensus model ready for realization in the mainnet.