The Bitcoin Backbone Protocol: Analysis and Applications

By Juan A. Garay, Aggelos Kiayias, Nikos Leonardos. International Conference on the Theory and Application of Cryptographic Techniques, 2015

1,615 citations recorded by the source corpus.

Bitcoin is the first and most popular decentralized cryptocurrency to date. In this work, we extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone, and prove three of its fundamental properties which we call Common Prefix, Chain Quality, and Chain Growth in the static setting where the number of players remains fixed. Our proofs hinge on appropriate and novel assumptions on the “hashing power” of the protocol participants and their interplay with the protocol parameters and the time needed for reliable message passing between honest parties in terms of computational steps. A takeaway from our analysis is that, all else being equal, the protocol’s provable tolerance in terms of the number of adversarial parties (or, equivalently, their “hashing power” in our model) decreases as the duration of a message passing round increases. Next, we propose and analyze applications that can be built “on top” of the backbone protocol, specifically focusing on Byzantine agreement (BA) and on the notion of a public transaction ledger. Regarding BA, we observe that a proposal due to Nakamoto falls short of solving it, and present a simple alternative which works assuming that the adversary’s hashing power is bounded by 1/3. The public transaction ledger captures the essence of Bitcoin’s operation as a cryptocurrency, in the sense that it guarantees the liveness and persistence of committed transactions. Based on this notion, we describe and analyze the Bitcoin system as well as a more elaborate BA protocol and we prove them secure assuming the adversary’s hashing power is strictly less than 1/2. Instrumental to this latter result is a technique we call 2-for-1 proof-of-work (PoW) that has proven to be useful in the design of other PoW-based protocols.

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

View Paper: https://www.semanticscholar.org/paper/9b5618e4d3295ac642e03681e3b9c7bf6db265e3

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

Tesseract: Real-Time Cryptocurrency Exchange using Trusted Hardware (2017, background): “Bitcoin [63, 35, 67] and similar cryptocurrencies derive their security from two assumptions:”
CrowdBC: A Blockchain-Based Decentralized Framework for Crowdsourcing (2019, background): “Since t0 t ðd=8Þt, according to Chernoff bounds [56], we have:”
Demystifying Incentives in the Consensus Computer (2015, methodology): “In fact, the parameter f in [42] typically depends on the parameter ε in our paper.”
Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol (2017, methodology): “The core of the idea is to provide a PoS analogue of “endorsing” inputs in a fair proportion using the same logic as the PoW-based byzantine agreement protocol for honest majority from [12].”
Bitcoin-NG: A Scalable Blockchain Protocol (2015, background): “The exact assumptions and guarantees are explored in diﬀerent works [10, 34, 22].”
Cryptocurrencies Without Proof of Work (2014, background): “The decentralized nature of Bitcoin [12,19] means that anyone can become a “miner” at any point in time, and thus participate in the security maintenance of the Bitcoin system and be compensated for this work.”
RapidChain: Scaling Blockchain via Full Sharding (2018, background): “In contrast, RapidChain is a BFT-based consensus protocol, where the blockchain maintained by each committee grows based on member votes rather than the longest chain principle [31].”
Ouroboros Genesis: Composable Proof-of-Stake Blockchains with Dynamic Availability (2018, methodology): “As shown in [4], assuming the honest parties are strongly connected, this setup can realize the multicast network with eventual delivery [18, 25, 33].”
Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts (2016, background): “On one hand, researchers have identified attacks on various aspects of the system [29], [34]; on the other, efforts to formally understand the security of blockchain consensus have begun [32], [45].”
The Quest for Scalable Blockchain Fabric: Proof-of-Work vs. BFT Replication (2015, neutral): “Although the Bitcoin protocol does not actually implement consensus in the traditional distributed computing sense, it comes very close to consensus with probabilistic agreement [26].”
Centrally Banked Cryptocurrencies (2015, methodology): “As demonstrated by Eyal and Sirer [7] and Garay et al. [8], an attacker can temporarily withhold blocks and ultimately undermine fairness.”
Redactable Blockchain – or – Rewriting History in Bitcoin and Friends (2017, methodology): “We start with a brief description of a blockchain abstraction, due to Garay, Kiayias and Leonardos [27], in Section 3.”
Sustainability of bitcoin and blockchains (2017, background): “Some provide gentle, general introductions to the technology applied in bitcoin (e.g. [5]), while others provide more detailed overviews of the technical operation of bitcoin (e.g. [6 ,7 ,8]) as well as economical and ﬁnancial aspects (e.g. [9 ]).”
Architecture of the Hyperledger Blockchain Fabric (2016, background): “Consensus protocols for blockchain are currently being debated very actively, in research [6, 10] but also by fintech startup companies (e.”