Sunday, March 18, 2018

Paper review. Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing.

This paper appeared in USENIX Security in 2016, and is by Eleftherios Kokoris Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi, Linus Gasser, and Bryan Ford at EPFL.

The link includes the conference presentation video which is useful. Kudos to USENIX for providing this. Other organizations should take a hint. It is 2018-- how hard is it to make the conference videos and presentation material available online?

The problem

Bitcoin does not provide instant irreversibility. Bitcoin protocol needs 6 consecutive blocks to be appended to conclude the irreversibility of a block with very high probability. A useful analogy here is to imagine the 6 additional blocks trapping the original block in amber layers. After that the adversaries don't have the computing power to go back 6 blocks to rewrite history and catch up and beat the current longest chain.

Instant irreversibility would be helpful, because it would save you from having to wait 6 more blocks to be added (which amounts to 1 hour in Bitcoin's block mining rate) to finalize a transaction.

The key idea

To provide instant irreversibility in a PoW-based blockchain, the paper proposes the Byzcoin protocol which employs practical byzantine consensus protocol (PBFT) over a special committee/council of nodes.

Byzcoin assembles the special council group by populating it with the PoW winners in the last 24 hours, and updates this council in a sliding window fashion. In contrast to Bitcoin which employs PoW for electing a leader that has the ultimate say on the next block, in Byzcoin PoW is used for electing members to the council which collectively endorses the next block. For consensus the council runs PBFT and signs the block with their blessing. This makes the block instantly irreversible. The instant irreversibility works provided that the council has less than 1/3 byzantine nodes.

The 24 hour window-frame for assembling council members from is chosen because for a mining rate of 10 minutes per PoW, a 24 hour period corresponds to 144 PoW winners. A smaller number of nodes in the council would be problematic, because there would still be a non-insignificant probability that more than the 1/3 of selected members to the group is Byzantine, even though in the larger population byzantine nodes are less than 1/3. The rewarding for mining a PoW puzzle is done slowly over the window frame, and not immediately when miner mines a keyblock. This way the miner is incentivized to stay and serve as part of the council to collect the entire reward.

To enhance throughput, Byzcoin adopts Bitcoin-NG's microblocks idea.

To improve efficiency of collective endorsement of blocks, Byzcoin employs using Shnorr signatures for scalable collective signing and public validation of blocks. Collective signing reduces both the costs of PBFT rounds and the costs for light clients to verify transaction commitment.

ByzCoin implements Byzantine consensus using collective signing rounds to make PBFT's prepare and commit phases scalable. Once a miner creates a new keyblock, it forms a CoSi communication tree for collective signing with itself as the leader.  Collective signing enables the leader to request publicly validated statement through Schnorr multi signatures with communication trees that are used in multicast protocols for scalability purposes.

In the original PBFT protocol, the trustees authenticate each other via non-transferable symmetric-key MACs: each trustee must communicate directly with most other trustees in every round, thus yielding O($n^2$) communication complexity.
By replacing MAC-authenticated communication with digital signatures, and employing scalable collective signing over multicast communication trees, Byzcoin reduces per-round communication complexity further to O(log n) and reduces signature verification complexity from O(n) to O(1).

Increased attack surface?

I think Byzcoin creates a problem by increasing the attack surface. It gives a period of 24 hours (or due to the sliding window, most likely less than that) for the attackers to conspire and buy council members.

As recent studies show Bitcoin is not very decentralized. There are heavy players mining good fraction of the blocks. Within a frame of many hours, it may be possible for the known members of the council to conspire to commit a heist.

Of course you cannot invent transactions on behalf of others because you don't have their private keys, but when council members conspire such that the number of Byzantine nodes increase of 1/3rd of the council, they may rewrite history and pull off some double-spending transactions. Or, maybe they are motivated not by profit but by another motive such as making the system nonoperational for some duration.

MAD questions

1. What is the maximum damage a Byzantine council can do? I am not savvy about the type of exchanges and smartcontracts deployed in blockchains in practice. Especially, since I haven't read much about smartcontracts yet, I am still unclear about what could be the worst heist a Byzantine council can pull.

2. How does Elastico compare with Byzcoin? Elastico paper and Byzcoin papers came out around the same time, so they do not cite each other. Elastico also used councils and run PBFT in the councils as part of the sharding protocol it implemented. Elastico did not claim instant-irreversibility. While it probably comes close to achieving it, there is still a short probabilistic reversibility window remaining in Elastico. Byzcoin provides instant-irreversibility thanks to the council running PBFT to endorse blocks to be added to the chain.

No comments:

Two-phase commit and beyond

In this post, we model and explore the two-phase commit protocol using TLA+. The two-phase commit protocol is practical and is used in man...