International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Bootstrapping the Blockchain, with Applications to Consensus and Fast PKI Setup

Juan A. Garay
Aggelos Kiayias
Nikos Leonardos
Giorgos Panagiotakos
DOI: 10.1007/978-3-319-76581-5_16
Search ePrint
Search Google
Conference: PKC 2018
Abstract: The Bitcoin backbone protocol (Eurocrypt 2015) extracts basic properties of Bitcoin’s underlying blockchain data structure, such as “common prefix” and “chain quality,” and shows how fundamental applications including consensus and a robust public transaction ledger can be built on top of them. The underlying assumptions are “proofs of work” (POWs), adversarial hashing power strictly less than 1/2 and no adversarial pre-computation—or, alternatively, the existence of an unpredictable “genesis” block.In this paper we first show how to remove the latter assumption, presenting a “bootstrapped” Bitcoin-like blockchain protocol relying on POWs that builds genesis blocks “from scratch” in the presence of adversarial pre-computation. Importantly, the round complexity of the genesis block generation process is independent of the number of participants.Next, we consider applications of our construction, including a PKI generation protocol and a consensus protocol without trusted setup assuming an honest majority (in terms of computational power). Previous results in the same setting (unauthenticated parties, no trusted setup, POWs) required a round complexity linear in the number of participants.
  title={Bootstrapping the Blockchain, with Applications to Consensus and Fast PKI Setup},
  booktitle={Public-Key Cryptography – PKC 2018},
  series={Public-Key Cryptography – PKC 2018},
  author={Juan A. Garay and Aggelos Kiayias and Nikos Leonardos and Giorgos Panagiotakos},