Catchain Component

Catchain Overview

Catchain is a communication protocol between validators. It does not implement the consensus algorithm itself, but prepares data for decision of a higher level component: validator-session. Catchain key tasks are:

• setting up an network overlay on the top of ADNL for communication between validators;
• setting up and updating a periodically updated list of neighbor nodes list used 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 that stores results of the current catchain session, restoring catchain session state after a validator restart;
• detecting forks and blaming validators;
• maintaining the consensus algorithm.

In general, the catchain component provides an operation framework for other components of the validator-session consensus.

Catchain Initialization in a Node

Catchain session begins from creation of the Catchain object which creates Receiver object. Receiver configures an ADNL overlay for communication with other validators. Then the receiver starts reading blocks from a RocksDB database (see ReceiverImpl::read_db_from and ReceiverImpl::read_block_from_db for the details). On top there is always a block with hash=0 which is used as a start block for downloading block predecessors and dependencies. After database reading the main processing loops are started which consists from preprocessing of each particular block (CatchainProcessor::send_preprocess) and processing of blocks (CatchainProcessor::send_process). Preprocessing means restoring a consensus state for each block based on increments which it contains. Processing means merging several consensus states together (for network performance reasons) and creating new consensus block based on them for sending to other validators. The consensus algorithm initiates generation of new block candidates for further approval. When a new candidate appears, the block is sent to the catchain. If there are no blocks, a validator waits for blocks from other validators in the catchain.

Scheduled Actions

To minimize traffic, each validator sends results of its work only to several its neighbors (now the number is set to 5). Changing of neighborhood happens randomly every 60-120 seconds. Moreover, every 2-3 seconds a validator is picked at random from the overall validator list for synchronization. This synchronization is bi-directional:

• The validator-initiator sends its list of delivered blocks heights. The validator expects to receive absent blocks in response or a fork event notification. If forking is confirmed by the current validator, then the source validator that sent the fork will be blamed and all its messages will be discarded. When a validator receives a synchronization request, it compares its own blocks heights with block heights of a validator-initiator and sends the difference back to the requester. This allows optimizing network traffic usage to minimize the average height of delivered blocks from all validators and to limit the count of outgoing response message to 100.
• The validator-initiator requests all absent dependent blocks generated by a validator-answerer.
• Invocation of consensus algorithm iteration (will be described below). Each synchronization adds information about states of other validators so new consensus iteration may be executed on the validator to process state update and send it back to neighbor validators.

Blocks Processing

There are several types of blocks in the catchain:

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

The ReceivedBlock block has following structure:

• catchain session identifier (to exclude the case when blocks the previous catchain session are processed);
• number of the source validator that generated the block;
• block height (actually, 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:

• recursively downloading all blocks required for the full state of the processed block;
• recursively marking a sub graph 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 ReceivedBlock blocks that came from them. Every new incoming ReceivedBlock block is checked regardless of which data channel it came from (directly from the validator or transitively). 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 ReceivedBlock corresponding to this validator are invalidated. The validator itself ignore till the end of the current catchain session.

After the ReceivedBlock block is received, its processing is initiated (see Receiver::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 ReceivedBlock 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 CatchainProcessor::processed_block)), the ReceivedBlock block execution procedure is launched.

Block execution includes:

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

Pre-processing of a ReceivedBlock includes the checking of forks (see ReceivedBlock::pre_deliver). Block processing (see ReceivedBlock::delivery) includes the following:

• deliver_block - notification of the block readiness for this validator. This notification includes following:
  1. notification of all neighbors about the appearance of a new ReceivedBlock block;
  2. generating of the new Block block and placing it on the top of the chain from the validator which sent the corresponding ReceivedBlock block. In fact, the Block block, that is used in the consensus algorithm, is a copy (snapshot) relative to the corresponding ReceivedBlock block, excluding the data which was needed for dependencies downloading process;
• dep_delivered - notification of all dependent ReceivedBlock blocks (outgoing dependency). This leads to the placing of dependents to a queue of blocks ready to be run;
• block_delivered - update of internal data on received blocks for the state of the validator that sent the incoming block ReceivedBlock.

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

In the case of processing the consensus results of one validator on the another validator, it is possible that two different blocks will be received with the same height and validator numbers. This leads to the fork appearance, so the identification key extends up to (validator number, block height, fork number). However, because the catchain does not allow forks, the source validator which sent forked block will be blamed. So the fork number may be skipped and Block identifiation may be done only using (validator number, block height).

The consensus iteration begins by selecting a random subset from the list of Block top blocks (no more than max_deps=4) and passing them to the consensus algorithm described above (see validator_session::SessionProcessor::process_blocks). Note, each of such block is received from a separate validator, and the case in which more than one block from one validator is sent to a consensus algorithm iteration is fully excluded. In the consensus algorithm, these blocks are merged, and a new Block is built on their basis, the appearance of which is reported by catchain (see CatchainProcessor::processed_block). Adding a new block leads to writing it to the database and creating a ReceivedBlock block from it, which will be 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 may 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:

1. 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 neighbour validators (see description above) and sends to it:
     • catchain.getDifference request with a list of heights for blocks which have been 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.
2. Validator synchronization events processing:
   • validator receives incoming catchain.blockUpdate events and updates internal blocks data structures.
3. Validator forks event processing:
   • validator receives an incoming catchain.differenceFork event, checks the fork proof and marks the counterparty validator which sent fork as blamed; so all data from this validator will be discarded; also, block for the same height received from this validator (fork block) will be marked as "ill" as well as all dependent blocks from it.
4. Consensus iteration
   • each catchain.blockUpdate may lead to decision that one or several catchain blocks laying on the top of counter-party validators' are fully resolved (so these blocks will have enough data including dependencies to be used in consensus calculations);
   • a validator randomly chooses up to Options::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 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 which is done by a validator with index src of the block; is 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 is 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 from 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 is used to inform a 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 anew 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 Catchain component internally)
      • This query is used to obtain blocks used to build a block with a specified reverse height (number of blocks backwards 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.