Paper 2017/775 Original: eprint.iacr.org/2017/775 ↗

Consensus from Signatures of Work

Abstract

Assuming the existence of a public-key infrastructure (PKI), digital signatures are a fundamental building block in the design of secure consensus protocols with optimal resilience. More recently, with the advent of blockchain protocols like Bitcoin, consensus has been considered in the ``permissionless'' setting where no authentication or even point-to-point communication is available. Yet, despite some positive preliminary results, there has been no attempt to formalize a building block that is sufficient for designing consensus protocols in this setting. In this work we fill this void by putting forth a formalization of such a primitive, which we call {\em signatures of work} (SoW). Distinctive features of our new notion are a lower bound on the number of steps required to produce a signature; fast verification; {\em moderate unforgeability}---producing a sequence of SoWs, for chosen messages, does not provide an advantage to an adversary in terms of running time; and signing time independence---most relevant in concurrent multi-party applications, as we show. Armed with SoW, we then present a new permissionless consensus protocol which is secure assuming an honest majority of computational power, thus providing a blockchain counterpart to the classical Dolev-Strong consensus protocol. The protocol is built on top of a SoW-based blockchain and standard properties of the underlying hash function, thus improving on the only known provably secure consensus protocol in this setting, which relies on the random-oracle model in a fundamental way.