Paper 2016/991

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

Juan A. Garay, Aggelos Kiayias, Nikos Leonardos, and Giorgos Panagiotakos

Abstract

The Bitcoin backbone protocol [Eurocrypt 2015] extracts basic properties of Bitcoin's underlying {\em 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$ {\em 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 \emph{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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2018
Keywords
Bitcoinbootstrappingunlinkability
Contact author(s)
pagio91i @ gmail com
History
2018-03-23: last of 3 revisions
2016-10-17: received
See all versions
Short URL
https://ia.cr/2016/991
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/991,
      author = {Juan A.  Garay and Aggelos Kiayias and Nikos Leonardos and Giorgos Panagiotakos},
      title = {Bootstrapping the Blockchain, with Applications to Consensus and Fast {PKI} Setup},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/991},
      year = {2016},
      url = {https://eprint.iacr.org/2016/991}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.