Enhancing Bitcoin Security and Performance withStrong Consistency via Collective Signing
Eleftherios Kokoris-Kogias, Philipp Jovanovic, Nicolas Gailly,Ismail Khoffi, Linus Gasser, and Bryan FordEPFL
1.

INTRODUCTION

While showing great promise, Bitcoin [13] faces some fundamental security and performance hurdles that prevent its large-scale
adoption: In comparison to classic payment providers, such as VISA
or PayPal, which are able to perform hundreds to thousands oftransactions (tx) per second1 with very low transaction confirmation latencies, Bitcoin’s current transaction throughput is limited toabout 7 tx/sec and its consensus mechanism requires users to waittens of minutes for transactions commitment, even then, providing
only probabilistic consistency gurantees. This means that inconsistencies (forks) might occur when different miners find new blocks
independently and at about the same time which then splits thepeers’ views on the blockchain. Fork-resolution regularly destroys
large numbers of transactions, sometimes even hours after their initial submission, thereby wasting all the computational power spenton the orphaned branch. As a consequence, Bitcoin’s peer-to-peer
network establishes a consistent view on the distributed ledger only
eventually. The probabilistic consistency of Bitcoin’s consensus
mechanism is also one of the reasons that the cryptocurrency issusceptible to all kinds of attacks [1, 6–8, 10, 14]. One solution
to mitigate many of those problems, is to eliminate Bitcoin’s lazy
fork-resolution mechanism and adopt strong consistency [3, 4], amore proactive approach that offers the following important benefits:
1. All miners agree on the validity of the blocks right away, without
wasting computational power to resolve forks.
2. Clients need not wait extended periods to be certain that a submitted transaction is committed; as soon as it appears in theblockchain, the transaction can be considered confirmed.
3. Once a block has been appended to the blockchain, it stays there,
forever (as long as there is an honest majority of miners). This
property is also often referred to as forward security.
In this work we show how to implement strong consistency in Bitcoin by introducing ByzCoin [9, 11], a novel Byzantine consensus
protocol. We moreover present results from our experimental evaluation which indicate that ByzCoin-improved Bitcoin can increase
its throughput by two orders of magnitude, and finally also discuss
some of the basic deployment challenges that need to be solved.

2.

BYZCOIN

ByzCoin is a novel scalable Byzantine fault-tolerant (BFT) consensus protocol that provides strong consistency, while scaling toprocessing throughputs of hundreds of transactions per second, among
hundreds to thousands of decentralized miners. ByzCoin utilizes anadaptation of the well-studied Practical Byzantine Fault Tolerance(PBFT) [2] and introduces four key improvements over Bitcoin:
1. ByzCoin’s improved PBFT-like consensus mechanism commits
Bitcoin transactions irreversibly within seconds.
2. ByzCoin preserves Bitcoin’s open-membership property by dynamically forming hash power-proportionate consensus groups
that represent recently-successful block miners.
1

https://en.bitcoin.it/wiki/Scalability#Scalability_targets

3. ByzCoin uses communication trees to further optimize transaction commitments and verification under normal operation while
guaranteeing safety and liveness under Byzantine faults.
4. ByzCoin decouples the election of a new leader from transaction verification, an approach inspired by Bitcoin-NG [5], thatenables ByzCoin’s transaction throughput to further increase.
Together, all these optimizations enable ByzCoin to achieve throughputs higher than PayPal currently handles, and to provide low confirmation latencies. Another benefit of ByzCoin’s fast transaction
commitment, ranging from a few seconds up to at most one or two
minutes after submission, is the mitigation of double-spending andselfish mining attacks.

2.1

DesignAn overview on ByzCoin’s design is depicted in Fig. 1.
share window of size w

keyblock (co-signed)Lmicroblock (co-signed)
shareminer (co-signer)L

leaderFigure 1: ByzCoin design

The lower part of Fig. 1 shows ByzCoin’s consensus group thatis comprised of recently-successful block miners and uses a PBFTlike mechanism to reach consensus. Instead of PBFT’s MAC-based
authentication, which has quadratic communication and computation complexity, ByzCoin uses CoSi [15], a distributed protocol thatutilizes aggregated Schnorr signatures and tree-based communication to make large-scale, decentralized, collective signing practical.
Overall, CoSi reduces communication complexity from quadratic
to logarithmic, enables third-party verifiability, and signature verification in constant-time complexity. For more details on how exactly ByzCoin’s consensus group mechanism works we refer to theresearch paper [11]. Another feature that ByzCoin adopts fromPBFT is the role of the consensus group leader whose task is tobundle transactions into blocks and initiate new signing rounds. Allactions, however, taken by the leader have to be approved by a twothirds supermajority of the consensus group members, which effectively leads to strong consistency and all of its benefits discussed
earlier. In case the leader misbehaves, the miners in ByzCoin’s
consensus group can start a voting round and dismiss the Byzantine node but only if, again, a two-thirds supermajority approves.
The requirement of the two-thirds supermajority for decision making comes from Byzantine agreement theory [12] that permits atmost f malicious/faulty nodes among a total of 3f + 1 nodes. Another important part is the leader election mechanism, which brings
us to the next component of ByzCoin’s design.

2.2

Experimental Results

To evaluate the design of ByzCoin, we wrote a prototype, available on GitHub as part of the cothority project2 , and conductedthorough experiments, measuring transaction confirmation-latency
and throughput. We experimented with 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 lastweek’s. Fig. 2 shows ByzCoin’s throughput in comparison to othersystems. The data for our simulations is based on actual transactions from a portion of the Bitcoin blockchain.
The average latency we measured, for example for 32 MB blocks(≈ 66000 tx) and a consensus group size of 144 members, wasaround 90 seconds. For this particular configuration, ByzCoin’s
throughput (≈ 700 tx/sec) outperforms PayPal’s as shown in Fig. 2.
For a more elaborate discussion of ByzCoin’s performance evaluation we refer again to the research paper [11].

2.3

Deployment Challenges

Developing a reasonable deployment strategy for ByzCoin on
top of Bitcoin involves solving at least the following three challenges:
2

https://github.com/dedis/cothority

BitcoinFlat/CoSi 144 miners
Tree/CoSi 144 miners (ByzCoin)
Tree/CoSi 1008 miners (ByzCoin)

10 5Transactions per Second

The upper part of Fig. 1 shows ByzCoin’s blockchain which is
divided into two interdependent sub-chains: one for keyblocks andone for microblocks.
Keyblocks are used to manage ByzCoin’s consensus group membership. These blocks are generated by the miners through proofof-work roughly every 10 minutes, as in Bitcoin, and are collectively signed by ByzCoin’s consensus group. Keyblocks form aregular blockchain. A miner who successfully mines a new keyblock is rewarded with a consensus group share, a so-called proofof-membership, thereby gains entry into the consensus group, if heis not already a member, and becomes the next group leader. A
fixed-size sliding window mechanism constitutes the total numberof available shares: Any share beyond the current window expires
and miners who no longer hold any valid shares drop out of theconsensus group. The number of valid shares in the possession ofa miner reflects his voting power within the consensus group, whencommitting transactions. Moreover, this number determines theportion of coins a miner receives as a reward, when a new keyblock is found. In other words, ByzCoin rewards not only thenode that mines a new keyblock but instead splits, proportionate
to the valid shares each miner holds, the produced coins among
all miners of the consensus group. ByzCoin also uses this technique to split transaction costs as a reward, once no more coins canbe mined. The proof-of-membership approach ensures liveness,as dormant miners are removed from the consensus group and theshare-proportionate rewards further incite all miners to remain active and contribute to the progress of the system.
Microblocks, on the contrary, contain transactions, are proposedby the current leader, and, as they do not require proof-of-work, arecommitted much more frequently by the consensus group. Eachmicroblock contains, in addition to the list of transactions, a hashof the last microblock to ensure total ordering, as well as a hashof the leader’s keyblock to identify the era the microblock belongs
to. Even though microblocks are created by the consensus groupleader, ByzCoin’s witness-mechanism deters leaders from misbehaving (such as mounting double-spend attacks), because any misconduct would be immediately detected by the other group members, which in turn can trigger a view change thereby removing themalicious node.
For more details on ByzCoin’s design we refer to the research
paper [11].

10 4
VISA (~2000 tx/sec)

10 3 PayPal (~500 tx/sec)
10 2
10 1
10 0

0.5

1.0

2.0

4.0

8.0

Block Size (MB)

16.0

32.0

Figure 2: Throughput

1. Roll out code that is backward-compatible with the current Bitcoin system until a critical mass of miners supports the new ByzCoin consensus.
2. Build the initial consensus group which then switches to the newconsensus mechanism once the above critical mass appears.
3. Handle (hopefully rare) PBFT deadlock events, e.g., because
too many miners disappear in too short a time and no two-thirds
supermajority is or will ever again be available in the current
consensus group.
To address the first two challenges, we can utilize the already running Nakamoto consensus as a bootstrapping mechanism. Froman outside point of view, Bitcoin would basically operate as usual,
so long as the bootstrapping is not finished. A few things change
from the perspective of the miners though: each miner puts his public key and contact information (IP address/port number), respectively, into every block he creates. Including the public key enablesa miner to claim the block as a share once he finds the necessary
proof-of-work; the contact information is required so that consensus group members are able to find each other and create the communication tree. As soon as the number of distributed shares hits
the maximum share-window size, all miners in the consensus group
switch to ByzCoin, the last miner to join the group becomes theleader, and the group co-signs the leader’s keyblock. Afterwards,
the leader creates the new microblock-subchain from his keyblockand starts creating and submitting microblocks to the co-signingconsensus procedure. To handle the third challenge, we can use theNakamoto consensus as a fall-back option: If miners notice a lackof progress from the PBFT consensus group for too long (perhaps
after several view-changes), they return to committing transactions
as part of their keyblocks, just as in vanilla Bitcoin, thus effectively
reverting the system to its pre-ByzCoin agreement mechanism. As
soon as a certain threshold of shares is again distributed, miners
can re-start ByzCoin’s consensus. Another option would be to use
Bitcoin-NG as a fall-back mechanism, which has the advantage ofproviding similarly good performance as ByzCoin but guarantees
not all of ByzCoin’s security features.

3.

CONCLUSION

ByzCoin is a scalable Byzantine fault tolerant consensus algorithm for open decentralized blockchain systems such as Bitcoin.
ByzCoin’s strong consistency increases Bitcoin’s core security guarantees—shielding against attacks on the consensus and mining
system such as N-confirmation double-spending, intentional blockchain forks, and selfish mining—and also enables high scalability
and low transaction latency. We developed a wide-scale prototype
implementation of ByzCoin, validated its efficiency with measurements and experiments, and have shown that Bitcoin can increase
the capacity of transactions it handles by more than two orders ofmagnitude.

4.

REFERENCES[1] M. Apostolaki, et al. Hijacking Bitcoin: Large-scale Network Attacks on
Cryptocurrencies. arXiv preprint arXiv:1605.07524, 2016.
[2] M. Castro et al. Practical Byzantine Fault Tolerance. In 3rd OSDI, Feb. 1999.
[3] K. Croman, et al. On Scaling Decentralized Blockchains (A Position Paper). In
3rd Workshop on Bitcoin and Blockchain Research, 2016.
[4] C. Decker, et al. Bitcoin Meets Strong Consistency. In 17th International
Conference on Distributed Computing and Networking (ICDCN), Singapore,January 2016.
[5] I. Eyal, et al. Bitcoin-NG: A Scalable Blockchain Protocol. In 13th USENIX
Symposium on Networked Systems Design and Implementation (NSDI 16),
Santa Clara, CA, Mar. 2016. USENIX Association.
[6] I. Eyal et al. Majority is not enough: Bitcoin mining is vulnerable. In Financial
Cryptography and Data Security, pages 436–454. Springer, 2014.
[7] A. Gervais, et al. Tampering with the Delivery of Blocks and Transactions inBitcoin. In 22nd ACM SIGSAC Conference on Computer and Communications
Security, pages 692–705. ACM, 2015.
[8] E. Heilman, et al. Eclipse Attacks on Bitcoin’s Peer-to-Peer Network. In 24th
USENIX Security Symposium, pages 129–144, 2015.
[9] P. Jovanovic. ByzCoin: Securely Scaling Blockchains. Hacking, Distributed,August 2016.
[10] G. O. Karame, et al. Double-spending fast payments in Bitcoin. In 19th ACM
Conference on Computer and communications security, pages 906–917. ACM,
2012.
[11] E. Kokoris-Kogias, et al. Enhancing Bitcoin Security and Performance withStrong Consistency via Collective Signing. In Proceedings of the 25th USENIX
Conference on Security Symposium, 2016.
[12] L. Lamport, et al. The Byzantine Generals Problem. TOPLAS, 4(3):382–401,
1982.
[13] S. Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System, 2008.
[14] K. Nayak, et al. Stubborn Mining: Generalizing Selfish Mining and Combining
with an Eclipse Attack. In 1st IEEE European Symposium on Security andPrivacy, Mar. 2015.
[15] E. Syta, et al. Keeping Authorities “Honest or Bust” with Decentralized Witness
Cosigning. In 37th IEEE Symposium on Security and Privacy, May 2016.