Byzcoin vs Bitcoin
Bitcoin has many limitations. The major problems are that transaction confirmation is probabilistic (not deterministic) and it takes 1 block, around 10 minutes to commit. Altogether it seems to be a bad deal. Hence enters ByzCoin which claims that it solves both problems. It uses PBFT to make a transaction deterministic. But, there rise additional problems when implementing PBFT. PBFT does not support open/permission less environment and is a very expensive algorithm with communication complexity O(n^2).
The paper started with a strawman solution of using PBFT in bitcoin. The problems with the solution highlighted are closed distributed system and scalability. The closed distributed system means PBFT works only when the consensus group is fixed and well defined. In terms of scalability, PBFT is inefficient as it uses Message Authentication Code for authenticating trustees. Hence, each trustee should interact with each other trustee in every round yielding O(n^2) complexity for the communication. This complexity is dreadful for a system having thousands of nodes.
Firstly, to make PBFT work in open environment, the paper suggested forming a smaller consensus group. To become a member of the consensus group, a node should be a miner and within the window size. Explaining it further, it means, a node must solve a cryptographic puzzle to become a member of the consensus group. This concept is termed as “proof-of membership”. Coming to window size, to choose which miners are the part of the consensus group, a number w (known as window size) is defined. w is the latest blocks in the blockchain. All the miners of the latest w blocks are members of the consensus group. In order to motivate the miners to be part of the consensus group, incentives similar to bitcoin( like mining rewards and transaction fees) are implemented.
Secondly, to make PBFT scalable, the paper suggests many successive techniques as follows:
• Using Digital Signature instead of MAC: The Digital Signature fulfils Non-repudiation i.e. the authentication of the origin of the message is confirmed. This will reduce the communication complexity to O(n) from O(n2) as the leader can collect and distribute the digital signatures to other participants.
• Implementation of CoSi : Although till now the complexity is reduced to O(n) yet it seems to be heavy algorithm when we scale to hundreds of thousands of nodes. To reduce the communication expenses further, they are using CoSi which combines both the concepts of communication trees and Schnorr Signature. The idea is to have a single signature to verify for a whole consensus group.
Thirdly, they propose a solution for increasing the transaction throughput. They inherited the solution from Bitcoin-NG, which relies on the observation that mining in Bitcoin involves two functionalities, firstly the leader election with the proof of work and secondly, the verification of the transaction. Bitcoin-NG proposed to decouple these two functionalities by having two types of blocks: microblock which contains all the transaction and keyblock which is mined and represent leader election. Unlike Bitcoin-NG, in which a malicious leader could rewrite history or double-spend within this period until the next keyblock, ByzCoin ensures that each microblock is irreversibly committed regardless of the current leader’s behavior. Also unlike Bitcoin-NG, they propose to maintain two different blockchains for microblock and keyblock to combat race conditions between miners.
They performed extensive experiments on DeterLab network. They answered two major questions i.e. the size of the consensus group ByzCoin can scale to and the transaction throughput it can provide. They set 4 different systems for performance evaluations. Those included a basic PBFT(one proposed as strawman solution), CoSi without using tree communication, tree Communication without using CoSi and lastly, ByzCoin(tree communication with CoSi).In case of scalability, the results showed PBFT scales the worst. The one without tree communications scales up to 100 miners only. Whereas the other two models have comparable results, with ByzCoin performing better around 1000 miners.
In case of throughput, the one without tree communication itself performs much better than PBFT. Coming to ByzCoin, it has throughput increased by two orders of magnitude. The results aligns with the hypothesis of improvement in throughput with implementation of decoupling.In case of limitations of the system proposed, the biggest is that it can tolerate only 1/3 of malicious behaviour (unlike 1/2 in bitcoin). Also, it proposed the solution with scaling up and not scaling out.Concluding, they propose and combine some novel ideas to make PBFT possible (in terms of scalability) in Bitcoin. They use digital signatures and CoSi to make PBFT scalable. Also, they propose to use PoW to create permissionless open PBFT. Lastly, they deployed the idea of decoupling the leader election and transaction verification for improving throughput.
I am reviewing and summarizing the following research paper:
“https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/kogias”
