A Composability Treatment of Bitcoin's Transaction Ledger with Variable Difficulty

Juan Garay; Yun Lu; Julien Prat; Brady Testa; Vassilis Zikas

Paper 2024/1823

A Composability Treatment of Bitcoin's Transaction Ledger with Variable Difficulty

Juan Garay, Texas A&M University

Yun Lu, University of Victoria

Julien Prat, École Polytechnique

Brady Testa, Texas A&M University

Vassilis Zikas, Georgia Institute of Technology

Abstract

As the first proof-of-work (PoW) permissionless blockchain, Bitcoin aims at maintaining a decentralized yet consistent transaction ledger as protocol participants (“miners”) join and leave as they please. This is achieved by means of a subtle PoW difficulty adjustment mechanism that adapts to the perceived block generation rate, and important steps have been taken in previous work to provide a rigorous analysis of the conditions (such as bounds on dynamic participation) that are sufficient for Bitcoin’s security properties to be ascertained. Such existing analysis, however, is property-based, and as such only guarantees security when the protocol is run . In this paper we present the first (to our knowledge) simulation-based analysis of the Bitcoin ledger in the dynamic setting where it operates, and show that the protocol abstraction known as the Bitcoin backbone protocol emulates, under certain participation restrictions, Bitcoin’s intended specification. Our formulation and analysis extend the existing Universally Composable treatment for the fixed-difficulty setting, and develop techniques that might be of broader applicability, in particular to other composable formulations of blockchain protocols that rely on difficulty adjustment.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: Bitcoin Dynamic Participation Universal Composability
Contact author(s): garay @ tamu edu
yunlu @ uvic ca
Julien Prat @ ensae fr
btesta @ tamu edu
vzikas @ gatech edu
History: 2024-11-08: approved; 2024-11-07: received; See all versions
Short URL: https://ia.cr/2024/1823
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1823,
      author = {Juan Garay and Yun Lu and Julien Prat and Brady Testa and Vassilis Zikas},
      title = {A Composability Treatment of Bitcoin's Transaction Ledger with Variable Difficulty},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1823},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1823}
}