Cryptology ePrint Archive: Report 2019/315

Iterated Search Problems and Blockchain Security under Falsifiable Assumptions

Juan A. Garay and Aggelos Kiayias and Giorgos Panagiotakos

Abstract: We put forth a new class of search problems, {\em iterated search problems} (ISP), and study their relation to the design of secure blockchain protocols. We prove that (i) the Bitcoin blockchain protocol implies a hard ISP problem, but ISP hardness is not by itself sufficient to prove its security, and (ii) a suitably enhanced class of ISPs is sufficient to imply, via construction, a secure blockchain protocol in the common reference string (CRS) model. We then put forth a specific proposal for an enhanced ISP based on an underlying cryptographic hash function. The resulting blockchain protocol's security reduces to the ISP hardness of the hash-based scheme and to a computational randomness extraction property of the hash function. As a corollary, we obtain a blockchain protocol secure in the standard model under falsifiable assumptions; in contrast, all previous blockchain protocols were shown secure in the random oracle model.

Category / Keywords: foundations / blockchain protocols, proof-of-work, falsifiable assumptions

Date: received 21 Mar 2019, last revised 25 Jun 2019

Contact author: pagio91i at gmail com,akiayias@inf ed ac uk,garay@cse tamu edu

Available format(s): PDF | BibTeX Citation

Note: Improved the ISR attack.

Version: 20190625:170859 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]