Paper 2014/796

Distributed Cryptography Based on the Proofs of Work

Marcin Andrychowicz and Stefan Dziembowski


Motivated by the recent success of Bitcoin we study the question of constructing distributed cryptographic protocols in a fully peer-to-peer scenario (without any trusted setup) under the assumption that the adversary has limited computing power. We propose a formal model for this scenario and then we construct the following protocols working in it: (i) a broadcast protocol secure under the assumption that the honest parties have computing power that is some non-negligible fraction of computing power of the adversary (this fraction can be small, in particular it can be much less than 1/2), (ii) a protocol for identifying a set of parties such that the majority of them is honest, and every honest party belongs to this set (this protocol works under the assumption that the majority of computing power is controlled by the honest parties). Our broadcast protocol can be used to generate an unpredictable beacon (that can later serve, e.g., as a genesis block for a new cryptocurrency). The protocol from Point (ii) can be used to construct arbitrary multiparty computation protocols. Our main tool for checking the computing power of the parties are the Proofs of Work (Dwork and Naor, CRYPTO 92). Our broadcast protocol is built on top of the classical protocol of Dolev and Strong (SIAM J. on Comp. 1983). Although our motivation is mostly theoretic, we believe that our ideas can lead to practical implementations (probably after some optimizations and simplifications). We discuss some possible applications of our protocols at the end of the paper.

Note: Reorganized introduction.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Proofs of WorkBitcoinBroadcastMultipaty Computation Protocols
Contact author(s)
std @ mimuw edu pl
2014-12-17: last of 5 revisions
2014-10-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marcin Andrychowicz and Stefan Dziembowski},
      title = {Distributed Cryptography Based on the Proofs of Work},
      howpublished = {Cryptology ePrint Archive, Paper 2014/796},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.