International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Juan A. Garay
Aggelos Kiayias
Nikos Leonardos
Giorgos Panagiotakos
Download:
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.
BibTeX
@inproceedings{pkc-2018-28898,
  title={Bootstrapping the Blockchain, with Applications to Consensus and Fast PKI Setup},
  booktitle={Public-Key Cryptography – PKC 2018},
  series={Public-Key Cryptography – PKC 2018},
  publisher={Springer},
  volume={10770},
  pages={465-495},
  doi={10.1007/978-3-319-76581-5_16},
  author={Juan A. Garay and Aggelos Kiayias and Nikos Leonardos and Giorgos Panagiotakos},
  year=2018
}