The Bitcoin Backbone Protocol with Chains of Variable Difficulty

Juan A. Garay, Aggelos Kiayias, Nikos Leonardos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

Bitcoin’s innovative and distributedly maintained blockchain data structure hinges on the adequate degree of difficulty of so-called “proofs of work,” which miners have to produce in order for transactions to be inserted. Importantly, these proofs of work have to be hard enough so that miners have an opportunity to unify their views in the presence of an adversary who interferes but has bounded computational power, but easy enough to be solvable regularly and enable the miners to make progress. As such, as the miners’ population evolves over time, so should the difficulty of these proofs. Bitcoin provides this adjustment mechanism, with empirical evidence of a constant block generation rate against such population changes.

In this paper we provide the first (to our knowledge) formal analysis of Bitcoin’s target (re)calculation function in the cryptographic setting, i.e., against all possible adversaries aiming to subvert the protocol’s properties. We extend the q-bounded synchronous model of the Bitcoin backbone protocol [Eurocrypt 2015], which posed the basic properties of Bitcoin’s underlying blockchain data structure and shows how a robust public transaction ledger can be built on top of them, to environments that may introduce or suspend parties in each round.

We provide a set of necessary conditions with respect to the way the population evolves under which the “Bitcoin backbone with chains of variable difficulty” provides a robust transaction ledger in the presence of an actively malicious adversary controlling a fraction of the miners strictly below 50% in each instant of the execution. Our work introduces new analysis techniques and tools to the area of blockchain systems that may prove useful in analyzing other blockchain protocols.
Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2017. CRYPTO 2017
EditorsJ Katz, Shacham H
PublisherSpringer, Cham
Number of pages33
ISBN (Electronic)978-3-319-63688-7
ISBN (Print)978-3-319-63687-0
Publication statusPublished - 29 Jul 2017
EventCRYPTO 2017: 37th Annual International Cryptology Conference - University of California, Santa Barbara, Santa Barbara, United States
Duration: 20 Aug 201624 Aug 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Cham
ISSN (Print)0302-9743


ConferenceCRYPTO 2017
Abbreviated titleCRYPTO 2017
Country/TerritoryUnited States
CitySanta Barbara
Internet address


Dive into the research topics of 'The Bitcoin Backbone Protocol with Chains of Variable Difficulty'. Together they form a unique fingerprint.

Cite this