Bootstrapping the Blockchain, with Applications to Consensus and Fast PKI Setup Conference Paper uri icon


  • 2018, International Association for Cryptologic Research. The Bitcoin backbone protocol (Eurocrypt 2015) extracts basic properties of Bitcoins 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-computationor, 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.

published proceedings


author list (cited authors)

  • Garay, J. A., Kiayias, A., Leonardos, N., & Panagiotakos, G.

citation count

  • 11

complete list of authors

  • Garay, Juan A||Kiayias, Aggelos||Leonardos, Nikos||Panagiotakos, Giorgos

publication date

  • March 2018