PDBFT 2.0 Consensus Algorithm

PDBFT2.0 is a Byzantine Fault Tolerance (BFT) protocol deployed in Plian, a multi-blockchain platform that is capable of processing over 100k smart contract transactions per second in a production environment.

PDBFT2.0 is based on the classic PBFT protocol, with 3 major improvements:

• Linear Communication: PDBFT2.0 achieves linear worst-case communication volume, in contract to PBFT’s O(n4)

• Random Leader Selection: The leader of each round in PDBFT2.0 is selected by a verifiable random function (VRF), which prevents the leader from being predictably attacked

• Low Overhead: PDBFT2.0 involves only a single round of voting instead of two in PBFT, which reduces both communication overhead and confirmation time.

PBFT is a protocol with three phases: pre-prepare, prepare and commit. In phase prepare and commit, each validator has to broadcast its vote for the proposed block. Upon receiving 2f+1 commit votes, each validator finalizes the block. Due to the broadcasting of votes, the complexity of communication grows as the square of the number of nodes, O(n^2). To reduce this, PDBFT2.0 establishes a leader for each voting round to collect votes from all validators. In addition, PDBFT2.0 adopts BLS threshold signatures to achieve linear communication. An (n,t)-threshold signature on a message m is a single, constant-sized aggregate signature that passes verification if and only if at least t out of the n participants sign m. Note that the verifier does not need to know the identities of the t signers. Each collector derives an (n,2f+1)-threshold signature after collecting 2f+1 votes. The threshold signature can be seen as a single signature with constant size. After that, the collector broadcasts the threshold signature and each validator can confirm that more than 2f+1 validators have voted for the proposed block via verify threshold signature.

In classic PBFT, two rounds of voting are deployed to guarantee the safety and liveness of protocol. However, in PDBFT2.0, a single round of voting achieves this without losing safety or liveness. And as each vote for the current block specifies the hash of the previous block, each vote is the confirmation for the previous block as well. Hence, the vote for the current block is the prepare-vote and commit-vote for the current block and the previous block at the same time. If more than 2f+1 votes for the current block are collected by a validator, the previous block is finalized at once. Therefore, each block is finalized after just two rounds of voting which ensures the safety of the network.

Similar to PBFT, the view change subprotocol of PDBFT2.0 is triggered when the validators cannot reach consensus in a single round. This can be due to an asynchronous network (e.g., when more than 1/3n nodes are offline), or the presence of malicious collectors/leaders. PDBFT2.0 handles a view change with the Linear View Change (LVC) algorithm. The essence of LVC is that the leader of the next round sends its highest commit certificate instead of all commit certificates, which reduces transmission volume during a view change by a factor of O(n). In PBFT or tendermint, each leader is decided in a round-robin scheduling which can be predicted by the adversary. PDBFT2.0 avoids this situation by selecting collectors (leaders) randomly, using a VRF. A VRF is a pseudo-random generator whose output is verifiable (i.e., on whether a given number is indeed the output of the VRF), random, uniformly distributed, and unpredictable beforehand. With random leaders, the leader of the next round is unpredictable and the adversary can not attack the leader in advance.