Safety
Requirement 1
The algorithm can only select a unique result based on the input, and it is impossible to simultaneously select multiple results (without help of encryption).
Answer
Buddy consensus requires both paired nodes to reach a consensus to select the result, and it does not allow both parties to retain different results after successful pairing. When extending the iterative pairing, the consistency principle is followed, and the results already selected by the paired nodes cannot be overturned.
Requirement 2
Only after the result is selected can the nodes know that the result is confirmed.
Answer
The result is only selected when it is accepted by both representative nodes in the buddy consensus. Other nodes can only passively accept the result and cannot influence the selection of the result.
Liveness
Requirement 1
The proposed result can eventually be selected.
Requirement 2
The selected result can eventually be received and trusted by the nodes.
Answer
Buddy consensus requires that the two representative nodes reach a consensus on the selection result, and other nodes passively receive the selected result. There will be no live lock caused by communication delay or loss leading to oscillation in the selection.
As long as the network connection is not lost, the iterative pairing process can ensure that the results selected in each pairing can be reliably delivered to all nodes.
Buddy consensus performance in failure models
Byzantine failure
Byzantine failure refers to the problem that in a communication network with 2M+1 nodes without using crypto technology, malicious nodes can cause inconsistent information that cannot be detected.
In the Buddy consensus pairing process, only two nodes participate, so there is no Byzantine failure problem. During the iterative pairing process, there is a Byzantine failure problem in the data synchronization between the representative nodes and other nodes.
Buddy consensus fault tolerance:
When all nodes participating in Buddy consensus maintain full connectivity, as the number of nodes increases, Buddy consensus can still operate even if 33% of the nodes are malicious in the worst case, and it can still operate if 49% of the nodes are malicious in the best case.
During the local consensus phase, the overall fault tolerance of the consensus will be limited by the application’s extended consensus rules, as the Buddy consensus rules are scalable. For example, if the extended consensus is BFT, then in the best case, the overall fault tolerance of the consensus is 33% allowing for the existence of malicious nodes. If it is POW, then in the worst case, the overall fault tolerance of the consensus allows for 49% malicious nodes.
Solve Byzantine failure
add an asymmetric encryption data verification mechanism to the consensus script. By using technologies such as digital signatures and public key encryption, the integrity and authenticity of messages can be verified, thereby preventing malicious nodes from tampering with information.
Fail-Stop failure
Node failure
If a node fails, the pairing will not be able to run, and the efficiency of iterative pairing will be reduced.
Network failure
Network failure is usually caused by message delay, loss, or network partition, which has a similar effect to node failure.
In Buddy pairing, there are only two participating nodes. Communication delay/loss will reduce the efficiency of consensus or cause timeout failure, but it will not cause oscillation in selection due to live lock.
Failover
Nodes determine whether their neighboring nodes are responsive through heartbeat detection.
If a node is unresponsive during the pairing process, the pairing is terminated. The non-failed node seeks other nodes that can be paired with.
If a representative node is unresponsive during the iterative pairing process, a new representative node needs to be elected. After the election, the pairing can continue, and the unresponsive nodes have no effect on the pairing process. When the failed node recovers, it needs to request consensus data copies from other nodes to maintain data consistency.
In the case of network partition, if one side of the iterative pairing process cannot connect to any node on the other side after a timeout, the consensus cannot continue. The representative nodes on both sides will need to find new buddy consensus partners.
Messaging complexity
In Buddy pairing, pairing requests need to be sent to all neighbors and wait for responses. Two nodes send 2n pairing requests, and each obtains one confirmation from the other to end the pairing preparation. After that, data transmission and pairing are both constant message exchanges, so the messaging complexity of Basic Buddy consensus is O(n).
During iterative pairing, each side of the pairing selects its own leader node. If there are n nodes in total, at least n-2 messages need to be sent to select the leader. After Buddy paired with each other, the consensus result is synchronized to all nodes through at least n-2 messages. This process will stop after undergoing at most log2n pairings. Therefore, the messaging complexity of Multi Buddy is O(n·logn).
Advantages of Buddy Consensus
Convergence efficiency of consensus
Buddy consensus converges quickly, with n nodes able to select one final result from n inputs after log2n pairings. There is no livelock or selection oscillation problem.
The more nodes participating in the Buddy consensus, the greater the throughput of consensus in terms of processing data.
Customizable of consensus rules
Consensus rules can be customized based on the requests sent by applications, and different rules can be used for each pairing. Data consistency rules are the minimum requirement, allowing for maximum algorithm compatibility in pairings. For example, proof of work (POW) can be included in the pairing rules, requiring multiple data blocks to satisfy the POW rule before pairing.
Sharding for scalability
Buddy consensus is a natural sharding algorithm for distributed systems networks.
By combining with state sharding for data block structures such as UTXO, Buddy consensus can achieve computational sharding for both state and transaction data.
By combining Buddy consensus with the Hyperchain structure of Hyperblocks and Local Blocks, Hyperchain can provide dynamic sharding capabilities which is unique compare to other blockchain technology.
Limitations of Buddy Consensus
Operational limitation
Buddy consensus cannot be used by a single node online.
Limitation factors to parallel computing
In order for the parallel computing capabilities of Buddy consensus to be utilized, the application client must be able to partition the input data into subsets that can be efficiently distributed to nodes that can participate in Buddy consensus. The application data payload in the block must also meet the requirements for parallel computation rules for reading and verification. For example, the entangled logical dependencies between multiple trie data in the Ethereum block structure make parallel computation impossible. The UTXO data structure in Bitcoin allows transactions to be partitioned into complementary subsets for parallel computation.
Bandwidth limitation
As the number of nodes participating in consensus increases, the data communication volume will rapidly increase, and network bandwidth becomes a limiting factor. Fortunately, data communication is easily optimized. In the long run, network bandwidth limitations will also be eliminated as communication technology upgrades.