Consensus from signatures of work

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, all attempts to formalize a building block that is sufficient for designing consensus protocols in this setting, rely on a very strong independence assumption about adversarial accesses to the underlying computational resource. In this work, we relax this assumption by putting forth a primitive, which we call 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; moderate unforgeability—producing a sequence of SoWs, for chosen messages, does not provide an advantage to an adversary in terms of running time; and honest 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 in a sense 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 known provably secure consensus protocols in this setting, which rely on the strong independence property mentioned above in a fundamental way.