Paper Review of ByzCoin.
This post is a summary of the paper called ByzCoin. The video presentation is available online.
The paper proposes a combination of PoW and BFT protocols to realize highly-performant open consensus protocol. ByzCoin addresses four key challenges of bringing PBFT’s to cryptocurrencies: (1) open membership, (2) scalability, (3) POW block conflicts, and (4) transaction commitment rate.
The expirements show that ByzCoin can reach consensus in less than 20 seconds, on a 1MB block. A larger consensus group can reached consensus on an 8MB block in 90 seconds, showing that the systems scales both with the number of participants and with the block size. These experiments suggest that ByzCoin can handle loads higher than PayPal and comparable with Visa.
Before I start explaining how the paper had addressed the four challenges, I would give a high level illustration of ByzCoin’s design.
The upper part of the above graph shows the window size of involved minners on the main blockchain and lower part shows the consensus group that will sign and witness for new blocks to be added.
First key design is that ByzCoin uses Bitcoin’s proof-of-work mechanism to determine consensus groups dynamically while preserving Bitcoin’s defense against Sybil attacks. When a miner finds a solution to the puzzle, it becomes a member of the committee and receives a share in the current consensus window which moves one step forward (ejecting the oldest miner).
Second key design is that PBFT is not scalable, but with collective signing, PBFT is scalable. Collective signing reduces both the costs of PBFT rounds and the costs for light clients to verify transaction commitment. Collective Signing(CoSi) does not directly implement BFT, but it offers a primitive that the leader in a BFT protocol can use to collect and aggregate prepare and commit messages during PBFT rounds.
CoSi involves four rounds of communication at the end of which a collective signature is generated and verified by all members of the group. The signature is structured as a tree of Schnorr signatures O(logn). It significantly reduces the size of messages broadcast in the network during the prepare and commit phase of PBFT, because each node no longer needs individual signatures from all the other for verification. CoSi reduces the typical signature verification complexity from O(n) to O(1) using aggregation.
In more detials of ByzCoin algorithm, the first CoSi’s round (phase 1) implements the pre-prepare phase in the standard PBFT protocol. The collective signature resulting from this first CoSi round implements the PBFT protocol’s prepare phase, in which the leader obtains attestations from a two-thirds super-majority quorum of consensus group members that the leader’s proposal is safe and consistent with all previously committed history.
The second CoSi round is to implement the PBFT protocol’s commit phase, in which the leader obtains attestations from a two-thirds super-majority that all the signing members witnessed the successful result of the prepare phase and made a positive commitment to remember the decision.
Byzcoin replaces MAC-authenticated direct communication with digital signatures to make authentication transferable and thereby enabling sparser communication patterns that can reduce the normal case communication latency from O(n²) to O(n).
Bitcoin-NG and Byzcoin separate leader election from transaction validation in PoW, thus increase the overall performance. ByzCoin configures that the sliding-share-window mechanism replaces one member of the consensus group at a new keyblock. A consensus group is organized into a communication tree where the most recent miner (the leader) is at the root. The leader runs an O(n) variant of PBFT (using CoSI) to get all members to agree on the next microblock. This yields a slightly tighter fault-tolerance threshold than that of classical BFT consensus: N ≥ 3 f + 2 is needed anytime, where N is the consensus group size and f the Byzantine population. The outcome is a collective signature that proves that at least two-thirds of the consensus group members witnessed and attested the microblock. A node in the network can verify in O(1) that a microblock has been validated by the consensus group. ByzCoin uses the same incentive model as Bitcoin, but the remuneration is shared between members of the leader group in proportion to their shares.
ByzCoin’s PoW-based keyblock chain is still susceptible to forks. A fork can split the consensus group and potentially make the PBFT consensus stall, which can further aggravated by the presence of selfish miners. In response, ByzCoin relies on a deterministic prioritization function tweaked with high output entropy to resolve forks timely and reduce the impact of selfish miners.
ByzCoin’s ledger consists of two parallel blockchains: a keyblock chain and a microblock chain. Keyblocks are mined via PoW as in Nakamoto consensus and used for maintaining a consensus group from recent keyblock miners according to a sliding-share-window mechanism. Specifically, when a miner finds a new keyblock, it is credited one share in the consensus group and the share window moves one share forward. Only miners with shares in the window can participate in the subsequent consensus. Old shares expire once being left out of the window and so does the share owner’s eligibility of consensus participation. The window length is subject to designer’s choice on the consensus group size as well as the overall consensus participation fairness.
Every time a keyblock is signed, ByzCoin forces a mandatory PBFT view-change to the keyblock’s miner. This way the power of verifying transactions in blocks is assigned to the rightful miner, who has an era of microblock creation from the moment his keyblock is signed until the next keyblock is signed.
ByzCoin is vulnerable to slow down or temporary DoS attack and 51% attack. ByzCoin provides a latency of about 35 seconds and a throughput of 230 KBytes/sec of data appended to the ledger with an 8 MByte block size and 1000 participants in the Byzantine agreement.
Below Figures are illustration of experiment evaluations of ByzCoin.The experiment has consensus group sizes between 144 and 1008 nodes, which corresponds to a window of successful keyblock miners ranging from the last day’s up to the last week’s. The graph below shows ByzCoin’s throughput in comparison to other systems.
