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

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 proceeding › Conference 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 language	English
Title of host publication	Public-Key Cryptography -- PKC 2018
Editors	Michel Abdalla, Ricardo Dahab
Place of Publication	Rio de Janeiro, Brazil
Publisher	Springer International Publishing AG
Pages	465-495
Number of pages	31
ISBN (Electronic)	978-3-319-76581-5
ISBN (Print)	978-3-319-76580-8
DOIs	https://doi.org/10.1007/978-3-319-76581-5_16
Publication status	Published - 1 Mar 2018
Event	21st edition of the International Conference on Practice and Theory of Public Key Cryptography - Rio De Janeiro, Brazil Duration: 25 Mar 2018 → 29 Mar 2018 https://pkc.iacr.org/2018/index.html

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer, Cham
Volume	10770
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st edition of the International Conference on Practice and Theory of Public Key Cryptography
Abbreviated title	PKC 2018
Country/Territory	Brazil
City	Rio De Janeiro
Period	25/03/18 → 29/03/18
Internet address	https://pkc.iacr.org/2018/index.html

Access to Document

10.1007/978-3-319-76581-5_16

BtcPrecompAccepted author manuscript, 638 KB

https://link.springer.com/chapter/10.1007/978-3-319-76581-5_16

Panoramix:Privacy and Accountability in Networks via Optimized Randomized Mix-nets
Kiayias, A.
EU government bodies
1/09/15 → 31/01/19
Project: Research

Cite this

@inproceedings{05be1652ba204655a7801378ce216314,

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

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.",

author = "Garay, {Juan A.} and Aggelos Kiayias and Nikos Leonardos and Giorgos Panagiotakos",

year = "2018",

month = mar,

day = "1",

doi = "10.1007/978-3-319-76581-5_16",

language = "English",

isbn = "978-3-319-76580-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer International Publishing AG",

pages = "465--495",

editor = "Michel Abdalla and Ricardo Dahab",

booktitle = "Public-Key Cryptography -- PKC 2018",

address = "Switzerland",

note = "21st edition of the International Conference on Practice and Theory of Public Key Cryptography, PKC 2018 ; Conference date: 25-03-2018 Through 29-03-2018",

url = "https://pkc.iacr.org/2018/index.html",

}

Garay, JA, Kiayias, A, Leonardos, N & Panagiotakos, G 2018, Bootstrapping the Blockchain, with Applications to Consensus and Fast PKI Setup. in M Abdalla & R Dahab (eds), Public-Key Cryptography -- PKC 2018. Lecture Notes in Computer Science, vol. 10770, Springer International Publishing AG, Rio de Janeiro, Brazil, pp. 465-495, 21st edition of the International Conference on Practice and Theory of Public Key Cryptography, Rio De Janeiro, Brazil, 25/03/18. https://doi.org/10.1007/978-3-319-76581-5_16

Bootstrapping the Blockchain, with Applications to Consensus and Fast PKI Setup. / Garay, Juan A.; Kiayias, Aggelos; Leonardos, Nikos et al.

Public-Key Cryptography -- PKC 2018. ed. / Michel Abdalla; Ricardo Dahab. Rio de Janeiro, Brazil : Springer International Publishing AG, 2018. p. 465-495 (Lecture Notes in Computer Science; Vol. 10770).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Garay, Juan A.

AU - Kiayias, Aggelos

AU - Leonardos, Nikos

AU - Panagiotakos, Giorgos

PY - 2018/3/1

Y1 - 2018/3/1

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-76581-5_16

DO - 10.1007/978-3-319-76581-5_16

M3 - Conference contribution

SN - 978-3-319-76580-8

T3 - Lecture Notes in Computer Science

SP - 465

EP - 495

BT - Public-Key Cryptography -- PKC 2018

A2 - Abdalla, Michel

A2 - Dahab, Ricardo

PB - Springer International Publishing AG

CY - Rio de Janeiro, Brazil

T2 - 21st edition of the International Conference on Practice and Theory of Public Key Cryptography

Y2 - 25 March 2018 through 29 March 2018

ER -

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

Abstract

Publication series

Conference

Access to Document

Fingerprint

Projects

Panoramix:Privacy and Accountability in Networks via Optimized Randomized Mix-nets

Cite this