Paper 2019/315

Blockchains from Non-Idealized Hash Functions

Juan A. Garay, Aggelos Kiayias, and Giorgos Panagiotakos


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: {\em collision resistance}, {\em computational randomness extraction} and {\em 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 {\em iterated search problems} (ISP). ISPs enable the concise and modular specification of blockchain protocols, and may be of independent interest.

Note: Rewritten focusing on non-idealized hash functions.

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2020
blockchain protocolsproof-of-workfalsifiable assumptionsnon-idealized hash functions
Contact author(s)
pagio91i @ gmail com
akiayias @ inf ed ac uk
garay @ cse tamu edu
2020-11-13: last of 10 revisions
2019-03-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Juan A.  Garay and Aggelos Kiayias and Giorgos Panagiotakos},
      title = {Blockchains from Non-Idealized Hash Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2019/315},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.