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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationPublic-Key Cryptography -- PKC 2018
EditorsMichel Abdalla, Ricardo Dahab
Place of PublicationRio de Janeiro, Brazil
PublisherSpringer International Publishing AG
Pages465-495
Number of pages31
ISBN (Electronic)978-3-319-76581-5
ISBN (Print)978-3-319-76580-8
DOIs
Publication statusPublished - 1 Mar 2018
Event21st edition of the International Conference on Practice and Theory of Public Key Cryptography - Rio De Janeiro, Brazil
Duration: 25 Mar 201829 Mar 2018
https://pkc.iacr.org/2018/index.html

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Cham
Volume10770
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference21st edition of the International Conference on Practice and Theory of Public Key Cryptography
Abbreviated titlePKC 2018
CountryBrazil
CityRio De Janeiro
Period25/03/1829/03/18
Internet address

Fingerprint

Dive into the research topics of 'Bootstrapping the Blockchain, with Applications to Consensus and Fast PKI Setup'. Together they form a unique fingerprint.

Cite this