In general, important characteristics in a blockchain system are decentralization, scalability, and security. These three characteristics are called “blockchain trilemma.” Decentralization guarantees the reliability of transaction details between nodes even if there is no subject with intermediary authority when transactions occur. Scalability causes performance degradation despite an increase in the number of participating nodes. Security is that transaction details are not altered by malicious attacks. In addition, the distributed consensus algorithm is a protocol in which all nodes participating in the blockchain store the same data.
In general, Proof-of-Work (PoW) distributed consensus algorithm provides high security for block verification, but is poor at scalability. The number of transactions per second (TPS) in the block performance evaluation is up to 7 TPS. It takes about 10 minutes for the nodes to reach an agreement.
Oh et al. proposed a distributed consensus algorithm among Decentralized Agents (BADA) [13–15]. In the BADA distributed consensus algorithm, not all mode nodes participate in the consensus process, but consensus is reached through a committee composed of some nodes. As compared with the conventional consensus process, such a consensus process provides a consensus time within several seconds and performance of thousands of TPS. In addition, the BADA consensus distribution algorithm can make the election of a committee fair and safe using a nonce chain. As a result, the BADA distributed consensus algorithm provides excellent performance in decentralization and security.
A. Competitive distributed consensus algorithm
In general, blockchain is divided into a competitive consensus algorithm and a non-competitive consensus algorithm, depending on how a chain is maintained. A competition consensus scheme accepts only one consensus, satisfying specific conditions first, because it does not guarantee finality and reach different consensus values at the same time. Such a scheme has the advantage of solving the problem such as malicious nonparticipation or opposition because everyone does not have to participate in proof. However, there is a possibility of double payment because a fork occurs. In addition, in the case of an auxiliary chain that was not selected in the fork, all resources used in mining during that time may be invalidated. PoW/PoS (Proof-of-Stakes) consensus algorithms are appropriate for such a competitive consensus scheme.
PoW proves that all nodes, participating in a block generation process, performed repetitive hashing operations, and performed corresponding tasks. A specific operation is performed using computing power possessed by each node, and a node calculating a target value the fastest generates a block. PoW requires block determination time to solve a fork caused by multiple nodes that simultaneously and successfully generate blocks. Therefore, it takes a lengthy time for the transaction information to be confirmed. In addition, since all nodes perform the same hash calculation task, computing resources are wasted and excessive energy is consumed. In addition, there is a risk of centralization caused by collusion of a single subject or multiple subjects having high computational performance. PoS is a proposed method to compensate for the disadvantages of PoW. In PoS block generation is determined depending on a stake of each node. All nodes can generate blocks, but the nodes having a larger share succeed in block generation by generating blocks depending on a stake of each node. PoS does not waste computing resources, as compared with PoW. However, a monopoly may occur due to nodes that have more stakes. Also, similarly to PoW, there is a problem that block scalability cannot be provided because a fork may occur. It takes several minutes for actual transaction data to be reflected. Due to the performance of tens of TPS levels, there is a limitation in practical service application.
As described above, the competitive distributed consensus algorithm does not guarantee block scalability because all nodes simultaneously generate several blocks. For this reason, an additional determination time is required, which causes a decrease in efficiency. Recently, most blockchain platforms are trending to use non-competitive consensus algorithms providing block scalability and excellent performance.
B. Non-Competitive distributed consensus algorithm
The non-competitive consensus scheme guarantees finality, reaches only one consensus at a time, and is performed by many people with voting, or the like, to maintain the unity of the blockchain. Resources are not wated because only one chain operates. However, in a method that more than two-thirds should reach consensus, a system may be damaged if one-third do not vote or wickedly interrupt the voting. Since voting is conducted under the control of a master node or a leader node, there is a disadvantage of centralization. A typical non-competitive consensus scheme algorithm is a Practical Byzantine Fault Tolerance (PBFT) algorithm. The PBFT algorithm can reach consensus even in the presence of malicious nodes called byzantine nodes. When the number of Byzantine nodes is f, consensus is reached by fixed 3f + 1 consensus nodes. The consensus is reached when 2f + 1 or more nodes (2/3 of the consensus nodes) reach consensus through a four-step consensus process [14]. The PBFT algorithm provides block scalability and excellent performance, as compared with the competitive consensus scheme. However, since all nodes participating in the consensus at each consensus step transmit consensus messages through broadcasting, the complexity of the messages increases to 0(n2). Therefore, the consensus time increases as the number of participating nodes increases. In addition, it may be difficult to use the PBFT algorithm in a public blockchain because the leader node, which plays an important role in block generation, should be predefined.
Algorand algorithm was proposed to provide block scalability while ensuring decentralization for use in public blockchains. Algorand algorithm uses a verifiable random function (VRF) to select a node to participate in consensus, among all nodes participating in the blockchain, and allows block consensus to reached by the elected nodes. The block consensus process is largely divided into two steps. In first step, nodes qualified for block generation by VRF generate candidate blocks and then propagate the candidate blocks to all nodes participating in the blockchain through broadcasting. Similarly, a single block to reach consensus, among the candidate blocks, is selected by nodes that have qualification by VRF. In second step, the block selected in first step is similarly voted by the verification nodes selected by VRF, and the corresponding block is finally confirmed. In this case, when one block verification is not completed during the verification process, eleven consensus step steps may be performed in the worst case due to a process of creating an empty block to reach consensus again. At each step, when a proportion of byzantine nodes is 20%, 2,000 nodes should participate in consensus. In the final step, 10,000 nodes should participate. Similarly to the PBFT algorithm, the Algorand algorithm transmits a consensus message by broadcasting at each consensus step to increase the complexity of the message, so that it takes 22 seconds to reach consensus.
C. BADA distributed consensus algorithm
The BADA distributed consensus algorithm, proposed to overcome the limitations of the existing distributed consensus algorithm, is generally divided into a step of electing a congress to reach a distributed consensus for each block and a step of reaching consensus of blocks by the elected congress. In the step of electing a congress, respectively participating nodes in the network disclose nonce chain information to ensure decentralization and security, and the disclosed information is used to obtain congress qualifications for each block. In addition, a protocol to mutually verify the obtained congress qualifications is proposed. In the block consensus step, the consensus is reached through a four-step consensus process. In this case, scalability is guaranteed by proposing a consensus protocol that provides message complexity for the exchange of consensus messages between distributed congress nodes. Accordingly, the BADA distributed consensus algorithm provides consensus time within several seconds and performance of thousands of TPS [13].
In the block consensus process, a certain number of congresses to reach consensus of blocks are elected to ensure security. Referring to Fig. 1, The block consensus process is performed through four steps: Delegate Request, Preparation, Commitment, and Committed. All congress nodes transmit the transactions, stored in their Mempool, to a chairman node in the Delegate Request step. The chairman node selects nodes that have transmitted the Delegate Request, including the chairman node, as a committee, and creates a candidate block consisting of a transaction commonly submitted by f + 1 or more nodes and a congress for the next block consensus. In the Preparation step, the chairman node transmits a preparation message to committee nodes, and the committee nodes verify the received candidate blocks. When the block verification is complete, each of the committee nodes generates multiple signature fragments and transmits multiple signature fragments to the chairman node. In the Commitment step, the chairman node integrates the multiple signature fragments, received from the committee node, to write a signature to a candidate block, and creates a final block. Finally, in the Committed step, the chairman node propagates the final block to all nodes connected to the blockchain, and the nodes receiving the block execute the transactions stored in the block, reflect the result on a ledger, and start the next block consensus.
The BADA distributed consensus algorithm generally includes a step of electing a congress to conduct distributed consensus for each block and a step of reaching consensus of a block by the elected congress. In the step of electing the congress, each node participating in the network discloses nonce chain information to ensure decentralization and security [14], and the disclosed information is used to obtain congress qualification for each block. In addition, a protocol may mutually verify the obtained congress qualifications. In the block consensus step, the consensus is reached through a four-step consensus process on consensus blocks. In this case, scalability is guaranteed by presenting a consensus protocol that provides message complexity O(n) for the exchange of consensus messages between distributed congress nodes. Accordingly, the BADA distributed consensus algorithm provides a consensus time within several seconds and performance of thousands of TPS.
Each node is designed to perform the same congress election and consensus process for simulating the block consensus process similar to the actual BADA distributed consensus algorithm. Congress manager manages the list of BADA nodes registered in the network for congress election and qualification verification. In particular, the congress manager generates and transmits a consensus participation request message after checking whether the node is qualified for the next block congress every block. In addition, in the case of the chairman node, the consensus participation qualification of the requested node is verified. Crypto serves to verify the signature of consensus messages exchanged between nodes through the ECSchnorr multi-signature used in the BADA distributed consensus algorithm, and serves to generate and verify the multi-signature in the block consensus process. A transaction processor receives and inspects the transaction propagated from a transaction generator, and stores the verified transaction in the Mempool. In addition, the transaction processor serves to execute the transaction stored in consensus-reached block and to reflect the executed transaction on a distributed ledger.