Overview
Buddy consensus algorithm
The Buddy consensus algorithm is an algorithm designed for parallel consensus derived from the Paxos distributed consensus algorithm and the Buddy memory management algorithm.
The Buddy consensus algorithm process is divided into two parts: pairing and iteration.
Pairing Buddy
Buddy Prepare
Proposing node
1.Broadcast the pairing request (contains pairing conditions, proposal number, node identifier).
2.Listen and collect pairing promises from other nodes.
Add nodes that provide pairing promises to the pairing candidate list.
Responding node
1.Listen for pairing requests and send a pairing promise (contains proposal number, node identifier) if the pairing conditions are met.
Add the proposing node to the pairing candidate list.
2.Listen and receive data blocks from the proposing node.
Note: For local consensus, the pairing conditions include the Hyperchain genesis block, the current Hyperblock on which consensus depends, and the application data payload participating in consensus. Optional information includes application consensus scripts and application chain genesis blocks, etc.
For global consensus, the pairing conditions include the Hyperchain genesis block, the current Hyperblock on which consensus depends, the Local Chain participating in consensus, and the global consensus script.
Buddy Accept
Proposing node
1. Send data blocks to nodes in the pairing candidate list.
2.Listen and receive data blocks sent by nodes in the candidate list.
If a node’s data block and its own data block meet the pairing conditions after calculation, send a pairing confirmation (data block identifier, proposal number).
3.Listen for pairing confirmations from the node.
If the pairing confirmation is received from the node, the pairing is accepted and no longer accept pairings from other nodes.
Responding node
1.Listen and receive data blocks sent by nodes in the candidate list.
If a node’s data block and its own data block meet the pairing conditions after calculation, send a pairing confirmation (data block identifier, proposal number).
2.Listen for pairing confirmations from the node.
If the pairing confirmation is received from the node, the pairing is accepted and no longer accept pairings from other nodes.
Iterating Buddy
Based on successful pairing, the paired nodes can negotiate and select a representative node to execute the extended pairing process.
If the new pairing is successful, continue iterating the process to expand the pairing until the pairing meets the iteration termination condition.
Note: The iteration termination condition can be negotiated and determined by the nodes when pairing. Nodes can compare the latest Local Chain block generation time with the Hyperblock generation time on which consensus depends, and refer to the generation time pattern of past Hyperblocks to determine when to enter global consensus from local consensus or when to end global consensus.
Note: During the pairing process, the task of verifying the pairing data can be distributed to other nodes in the pairing, increasing the decentralization of consensus.
Local consensus
Use buddy consensus to group on-chain data blocks into Local Chains.
Global consensus
Continue to use buddy consensus for multiple Local Chains, and use Hyperblock consensus rules to generate the Hyperblock of current epoch. After the Hyperblock is generated, it is accepted by the participating representative nodes and broadcasted to the paired nodes, which then broadcast it to their neighboring nodes.
Algorithm basic metrics
Assumption
We assume that the Hyperchain network utilizes the most basic block version and default configuration, and we examine the achievable metrics of the algorithm for nodes in a network with a bandwidth of 1 Gbps.
Block size
Hyperblock
In the basic block version, the block header data consists of 226 bytes of fixed data and variable data that varies based on the number of Local Chains. Each additional Local Chain occupies 34 bytes in the block header data. The system is configured to support a maximum of 64 Local Chains (theoretically, this number can be unlimited if the network bandwidth is sufficient), resulting in variable data occupying 2,176 bytes. Thus, the block header data ranges from 260 bytes to 2,402 bytes (approximately 2KB).
The block body data includes 10 bytes of fixed data and variable data that changes depending on the number of blocks in the Local Chain. Each additional block occupies 32 bytes, and typically, within a consensus epoch, each Local Chain can generate 2-1024 blocks. Consequently, the block body data can occupy 74-32,788 bytes (around 32KB).
In total, the Hyperblock data will range from 334 bytes to 35,190 bytes (approximately 35KB).
Local Block
In the basic block version, the block header data will use 156 bytes, and the block body data includes 10 bytes of fixed data and a variable-length payload of application data. Currently, the payload size is limited to between 1 byte and 2,048,000 bytes (2MB). Therefore, the data size of Local Blocks ranges from 167 bytes to 2,048,166 bytes (approximately 2MB).
Theoretical data capacity
Based on the configuration of the basic block version, theoretically, the total data size of Hyperblocks and all Local Blocks generated within a consensus epoch ranges from 668 bytes to 134,226,594,000 bytes (approximately 134GB). The former represents the data size of 1 Hyperblock plus 2 Local Blocks with a payload of 1 byte, and the latter represents the data size of 1 Hyperblock plus 65,535 Local Blocks with a payload of 2MB. However, it is important to note that these configurations are designed to provide sufficient space for future scalability, and in reality, we are limited by network bandwidth and the number of participating nodes. The actual throughput of consensus cannot reach such high data volumes.
Block generation and finalization time
Currently, in the default system configuration, the block generation time for Local Chains varies depending on the extended consensus rules.
For Local Chains using the pure Buddy algorithm, the block generation time is less than 1 second.
For Local Chains with extended POA/BFT/POS consensus rules, the block generation time is generally less than 1 second as well.
For Local Chains with the extended POW consensus algorithm, the block generation time is around 15 seconds. For example, the block generation time for a single chain that provides PARA Coin , which is designed for paying the system gas fee, is set to around 15 seconds.
In the default system configuration, the time limit for the local consensus phase is around 150 seconds, and for the global consensus phase, the block generation time for Hyperblocks is set to around 150 seconds. Therefore, the block generation time for a single consensus cycle is around 300 seconds.
Regarding the finalization of Local Chain blocks, the probability of finalization after 10 blocks is close to 1, approximately 150 seconds.
For Local Chains, the probability of finalization after 2 consensus epochs is close to 1, approximately 600 seconds.
For Hyperblocks, the probability of finalization after 5 consensus epochs is close to 1, approximately 1500 seconds.
Equivalent TPS
In the default system configuration, the TPS (Transactions Per Second) for a POW single chain is around 15, while for POS/POA/BFT single chains, it is approximately 1000.
For a single chain using pure Buddy consensus, without using multiple Local Chain shards to improve performance, the maximum number of blocks a single chain can produce within a consensus epoch is 1024. Assuming each transaction is approximately 500 bytes and considering the block payload limit of 2MB, with a maximum of around 4000 transactions per block, the upper limit of TPS for an unsharded single chain is approximately 13653.
As different single chains within the Hyperchain system may have different transaction data structures, we define equivalent TPS to express the TPS metric for the Hyperchain system.
Equivalent TPS = Sum of TPS for all single chains within the Hyperchain system
For example, let’s assume there is 1 POW single chain, 1 POA single chain, and 1 Buddy single chain in the system. In this case, the upper limit of the system’s equivalent TPS would be 14668.
Consensus security measures
Node validation
Nodes generate node key pairs using elliptic curve algorithms, and use the public key as the unique identifier for the node.
Secure communication transmission
Message transmission can be plaintext or the security mechanism can be opened to allow for node applications to customize.
Data integrity assurance
For messages sent between nodes, the internal data integrity of the message payload is ensured by the application’s custom verification mechanism. The message header must include the node identifier, timestamp, and be signed using the node’s private key.