Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing

By Eleftherios Kokoris-Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi, Linus Gasser, Bryan Ford. USENIX Security Symposium, 2016

778 citations recorded by the source corpus.

While showing great promise, Bitcoin requires users to wait tens of minutes for transactions to commit, and even then, offering only probabilistic guarantees. This paper introduces ByzCoin, a novel Byzantine consensus protocol that leverages scalable collective signing to commit Bitcoin transactions irreversibly within seconds. ByzCoin achieves Byzantine consensus while preserving Bitcoin's open membership by dynamically forming hash power-proportionate consensus groups that represent recently-successful block miners. ByzCoin employs communication trees to optimize transaction commitment and verification under normal operation while guaranteeing safety and liveness under Byzantine faults, up to a near-optimal tolerance of f faulty group members among 3f + 2 total. ByzCoin mitigates double spending and selfish mining attacks by producing collectively signed transaction blocks within one minute of transaction submission. Tree-structured communication further reduces this latency to less than 30 seconds. Due to these optimizations, ByzCoin achieves a throughput higher than PayPal currently handles, with a confirmation latency of 15-20 seconds.

Subfields: Artificial Intelligence, Computer Networks and Communications, Information Systems

View Paper: https://www.semanticscholar.org/paper/efd99fe3b5b620d89aa03201199c45988c688670

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Information Systems

Citations in the corpus

The Honey Badger of BFT Protocols (2016, neutral): “assumptions involving the underlying currency itself [32, 32, 35, 37] to bootstrap faster BFT protocols, by selecting a random committee to perform BFT in every different epoch.”
Monoxide: Scale out Blockchains with Asynchronous Consensus Zones (2019, background): “ByzCoin [24] leverages the collective signing and optimizes the transaction commitment of the BFT-based blockchain.”
Scalable Bias-Resistant Distributed Randomness (2017, methodology): “challenge, we use BFT-CoSi from ByzCoin [39], a Byzantine consensus protocol that uses scalable collective signing, to agree on successfully delivering the commitment V̂ .”
SBFT: A Scalable and Decentralized Trust Infrastructure (2018, background): “Several recent proposals [4], [38], [45], [62], [66] explore the idea of building distributed ledgers that elect a committee (potentially of a few hundreds of nodes) from a large pool of nodes (potentially thousands or more) and have this smaller committee run a Byzantine fault tolerant replication ”
OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding (2018, methodology): “RSCoin [16] In Permissioned Partial No 30 N/A 1 sec Elastico [34] In PoW No No 1600 1 hour 800 sec ByzCoin [32] No N/A No 1008 19 years 40 sec Bitcoin-NG [21] No N/A No 1000 N/A 600 sec PBFT [9], [11] No N/A No 16 N/A 1 sec Nakamoto [36] No N/A No 4000 N/A 600 sec OmniLedger Yes Yes Yes 2400 68.”
Algorand: Scaling Byzantine Agreements for Cryptocurrencies (2017, methodology): “, Bitcoin); for example, ByzCoin [32] 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.”
A Survey on Consensus Mechanisms and Mining Strategy Management in Blockchain Networks (2018, methodology): “rk, but also avoids excessive message overhead and latency due to complete shard reconstruction (cf. Elastico). In the shard level, a committee can employ any leader-based BFT protocol (e.g., ByzCoin [162]) to provide intra-shard consensus. In [180], another epoch-based, two-level-BFT protocol for f”
HotStuff: BFT Consensus with Linearity and Responsiveness (2019, background): “As described above, recent blockchain solutions hybridize Proof-of-Work solutions with classical BFT solutions in various ways [7, 17, 26, 29, 31, 33, 42].”
Performance Analysis of Hyperledger Fabric Platforms (2018, background): “[42] introduced a scalable consensus protocol for public blockchain platforms called ByzCoin.”
Towards Scaling Blockchain Systems via Sharding (2018, methodology): “ize. As a consequence, scaling proposals for PBFT focus either on reducing the number of nodes required to tolerate fByzantine failures [18, 39, 11], or improving on the quadratic communication bound [32]. 3.1.1 AHL - Reducing the number of nodes The complexity of PBFT, which is its need for three d”
Chainspace: A Sharded Smart Contracts Platform (2017, methodology): “ByzCoin [15] extends Bitcoin-NG for high transaction throughput.”
Hijacking Bitcoin: Routing Attacks on Cryptocurrencies (2016, background): “In addition to the propagation of blocks, nodes also propagate transactions between them that await inclusion in the chain by whichever node creates the next block.”
KEVM: A Complete Formal Semantics of the Ethereum Virtual Machine (2018, background): “These blockchains and the blockchain-based systems they create tackle a wide range of disparate problems, including currency [2] [3], [4], distributed storage [5], academic research on consensus protocols [6], and more [7].”
Narwhal and Tusk: a DAG-based mempool and efficient BFT consensus (2021, background): “Specifically, to improve on Bitcoin’s [33] throughput of only 4 tx/sec early works [29] suggested committee based consensus protocols.”