Paper 2017/775

Blockchain and Consensus from Proofs of Work without Random Oracles

Juan A. Garay and Aggelos Kiayias and Giorgos Panagiotakos

Abstract

One of the most impactful applications of ``proofs of work'' (POW) currently is in the design of blockchain protocols such as Bitcoin. Yet, despite the wide recognition of POWs as the fundamental cryptographic tool in this context, there is no known cryptographic formulation that implies the security of the Bitcoin blockchain protocol. Indeed, all previous works formally arguing the security of the Bitcoin protocol relied on direct proofs in the random oracle model, thus circumventing the difficulty of isolating the required properties of the core POW primitive. In this work we fill this gap by providing a formulation of the POW primitive that implies the security of the Bitcoin blockchain protocol in the standard model. Our primitive entails a number of properties that parallel an efficient non-interactive proof system: completeness and fast verification, security against malicious provers (termed ``hardness against tampering and chosen message attacks'') and efficiency and security for honest provers (the latter captured as almost $k$-wise independence of the proving algorithm running time). Interestingly, our formulation is incomparable with previous formulations of POWs that applied the primitive to contexts other than the blockchain and highlights the importance of {\em run-time independence} as a property for POWs suitable for blockchain protocols. Using our primitive and standard properties of the underlying hash function, we establish the security of the Bitcoin backbone protocol [Eurocrypt 2015] without relying on random oracles. We then tackle the question of constructing a consensus protocol based on POW. We illustrate that previously known solutions essentially relied on the random oracle and propose a new blockchain-based consensus protocol provably secure under the same assumptions as above. This yields the first consensus protocol for honest majority reducible to a POW primitive without random oracles.