Consensus from Signatures of Work

Juan A.  Garay; Aggelos Kiayias; Giorgos Panagiotakos

Paper 2017/775

Consensus from Signatures of Work

Juan A. Garay, Aggelos Kiayias, and Giorgos Panagiotakos

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.

Note: The most important difference of this version of the paper with respect to previous versions is the introduction of the notion of SoW, replacing the Proof of Work (PoW) notion. Moreover, many proofs have been rewritten in a clearer fashion, and the properties required from the underlying computational primitive have been simplified. Finally, additional related work regarding consensus protocols has been added.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Minor revision. Cryptographers’ Track at the RSA Conference
DOI: 10.1007/978-3-030-40186-3_14
Keywords: Bitcoin proof of work consensus
Contact author(s): pagio91i @ gmail com
History: 2020-04-13: last of 6 revisions; 2017-08-16: received; See all versions
Short URL: https://ia.cr/2017/775
License: CC BY

BibTeX

@misc{cryptoeprint:2017/775,
      author = {Juan A.  Garay and Aggelos Kiayias and Giorgos Panagiotakos},
      title = {Consensus from Signatures of Work},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/775},
      year = {2017},
      doi = {10.1007/978-3-030-40186-3_14},
      url = {https://eprint.iacr.org/2017/775}
}