The Bitcoin Backbone Protocol: Analysis and Applications

Nytro · September 30, 2014

Juan A. Garay

Yahoo Labs

Aggelos Kiayias

University of Athens

Nikos Leonardos

University of Athens

September 30, 2014

Abstract

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 two of its fundamental properties which we call common prefix and chain quality. Our

proofs hinge on appropriate and novel assumptions on the “hashing power” of the adversary

relative to network synchronicity; our results are shown to be tight under high synchronization.

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 Nakamoto’s suggestion 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, proving them secure assuming high network synchronicity and

that the adversary’s hashing power is strictly less than 1=2, while the adversarial bound needed

for security decreases as the network desynchronizes.

Recommended Posts