Blockchains from non-idealized hash functions

Juan A. Garay; Aggelos Kiayias; Giorgos Panagiotakos

doi:10.1007/978-3-030-64375-1_11

Blockchains from non-idealized hash functions

Juan A. Garay, Aggelos Kiayias^*, Giorgos Panagiotakos

^*Corresponding author for this work

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

Abstract / Description of output

The formalization of concrete, non-idealized hash function properties sufficient to prove the security of Bitcoin and related protocols has been elusive, as all previous security analyses of blockchain protocols have been performed in the random oracle model. In this paper we identify three such properties, and then construct a blockchain protocol whose security can be reduced to them in the standard model assuming a common reference string (CRS). The three properties are: collision resistance, computational randomness extraction and iterated hardness. While the first two properties have been extensively studied, iterated hardness has been empirically stress-tested since the rise of Bitcoin; in fact, as we demonstrate in this paper, any attack against it (assuming the other two properties hold) results in an attack against Bitcoin. In addition, iterated hardness puts forth a new class of search problems which we term iterated search problems (ISP). ISPs enable the concise and modular specification of blockchain protocols, and may be of independent interest.

Original language	English
Title of host publication	Theory of Cryptography
Subtitle of host publication	18th International Conference
Editors	Rafael Pass, Krzysztof Pietrzak
Publisher	Springer
Pages	291-321
Number of pages	31
Volume	12550
ISBN (Print)	9783030643744
DOIs	https://doi.org/10.1007/978-3-030-64375-1_11
Publication status	Published - 9 Dec 2020
Event	18th International Conference on Theory of Cryptography - Durham, United States Duration: 16 Nov 2020 → 19 Nov 2020

Publication series

Name	Lecture Notes in Computer Science
Volume	12550
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	18th International Conference on Theory of Cryptography
Abbreviated title	TCCC 2020
Country/Territory	United States
City	Durham
Period	16/11/20 → 19/11/20

Keywords / Materials (for Non-textual outputs)

blockchain protocols
proof-of-work
falsifiable assumptions
non-idealized hash functions

Access to Document

10.1007/978-3-030-64375-1_11

GarayEtalTCCC2020BlockchainsFromNon-idealizedHashFunctionsSubmitted manuscript, 588 KBLicence: Creative Commons: Attribution (CC-BY)

https://ia.cr/2019/315Licence: Creative Commons: Attribution (CC-BY)

Cite this

@inproceedings{5b4de53d12964375bbe80910917ee729,

title = "Blockchains from non-idealized hash functions",

abstract = "The formalization of concrete, non-idealized hash function properties sufficient to prove the security of Bitcoin and related protocols has been elusive, as all previous security analyses of blockchain protocols have been performed in the random oracle model. In this paper we identify three such properties, and then construct a blockchain protocol whose security can be reduced to them in the standard model assuming a common reference string (CRS). The three properties are: collision resistance, computational randomness extraction and iterated hardness. While the first two properties have been extensively studied, iterated hardness has been empirically stress-tested since the rise of Bitcoin; in fact, as we demonstrate in this paper, any attack against it (assuming the other two properties hold) results in an attack against Bitcoin. In addition, iterated hardness puts forth a new class of search problems which we term iterated search problems (ISP). ISPs enable the concise and modular specification of blockchain protocols, and may be of independent interest.",

keywords = "blockchain protocols, proof-of-work, falsifiable assumptions, non-idealized hash functions",

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

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2020.; 18th International Conference on Theory of Cryptography , TCCC 2020 ; Conference date: 16-11-2020 Through 19-11-2020",

year = "2020",

month = dec,

day = "9",

doi = "10.1007/978-3-030-64375-1_11",

language = "English",

isbn = "9783030643744",

volume = "12550",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "291--321",

editor = "Rafael Pass and Krzysztof Pietrzak",

booktitle = "Theory of Cryptography",

}

Garay, JA, Kiayias, A & Panagiotakos, G 2020, Blockchains from non-idealized hash functions. in R Pass & K Pietrzak (eds), Theory of Cryptography: 18th International Conference. vol. 12550, Lecture Notes in Computer Science, vol. 12550, Springer, pp. 291-321, 18th International Conference on Theory of Cryptography , Durham, United States, 16/11/20. https://doi.org/10.1007/978-3-030-64375-1_11

Blockchains from non-idealized hash functions. / Garay, Juan A.; Kiayias, Aggelos; Panagiotakos, Giorgos.
Theory of Cryptography: 18th International Conference. ed. / Rafael Pass; Krzysztof Pietrzak. Vol. 12550 Springer, 2020. p. 291-321 (Lecture Notes in Computer Science; Vol. 12550).

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

TY - GEN

T1 - Blockchains from non-idealized hash functions

AU - Garay, Juan A.

AU - Kiayias, Aggelos

AU - Panagiotakos, Giorgos

N1 - Publisher Copyright: © International Association for Cryptologic Research 2020.

PY - 2020/12/9

Y1 - 2020/12/9

N2 - The formalization of concrete, non-idealized hash function properties sufficient to prove the security of Bitcoin and related protocols has been elusive, as all previous security analyses of blockchain protocols have been performed in the random oracle model. In this paper we identify three such properties, and then construct a blockchain protocol whose security can be reduced to them in the standard model assuming a common reference string (CRS). The three properties are: collision resistance, computational randomness extraction and iterated hardness. While the first two properties have been extensively studied, iterated hardness has been empirically stress-tested since the rise of Bitcoin; in fact, as we demonstrate in this paper, any attack against it (assuming the other two properties hold) results in an attack against Bitcoin. In addition, iterated hardness puts forth a new class of search problems which we term iterated search problems (ISP). ISPs enable the concise and modular specification of blockchain protocols, and may be of independent interest.

AB - The formalization of concrete, non-idealized hash function properties sufficient to prove the security of Bitcoin and related protocols has been elusive, as all previous security analyses of blockchain protocols have been performed in the random oracle model. In this paper we identify three such properties, and then construct a blockchain protocol whose security can be reduced to them in the standard model assuming a common reference string (CRS). The three properties are: collision resistance, computational randomness extraction and iterated hardness. While the first two properties have been extensively studied, iterated hardness has been empirically stress-tested since the rise of Bitcoin; in fact, as we demonstrate in this paper, any attack against it (assuming the other two properties hold) results in an attack against Bitcoin. In addition, iterated hardness puts forth a new class of search problems which we term iterated search problems (ISP). ISPs enable the concise and modular specification of blockchain protocols, and may be of independent interest.

KW - blockchain protocols

KW - proof-of-work

KW - falsifiable assumptions

KW - non-idealized hash functions

UR - http://www.scopus.com/inward/record.url?scp=85098240935&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-64375-1_11

DO - 10.1007/978-3-030-64375-1_11

M3 - Conference contribution

AN - SCOPUS:85098240935

SN - 9783030643744

VL - 12550

T3 - Lecture Notes in Computer Science

SP - 291

EP - 321

BT - Theory of Cryptography

A2 - Pass, Rafael

A2 - Pietrzak, Krzysztof

PB - Springer

T2 - 18th International Conference on Theory of Cryptography

Y2 - 16 November 2020 through 19 November 2020

ER -

Blockchains from non-idealized hash functions

Abstract / Description of output

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Other files and links

Fingerprint

PRIViLEDGE: Privacy in Distributed Ledgers

Cite this

Blockchains from non-idealized hash functions

Abstract / Description of output

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Other files and links

Fingerprint

Projects

PRIViLEDGE: Privacy in Distributed Ledgers

Cite this