Paper 2017/775

Proofs of Work for Blockchain Protocols

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 security for honest provers (termed ``uniquely successful under chosen key and message attacks''). Interestingly, our formulation is incomparable with previous formulations of POWs that applied the primitive to contexts other than the blockchain. Our result paves the way for proving the security of blockchain protocols in the standard model assuming our primitive can be realized from computational assumptions.