Distributed Cryptography Based on the Proofs of Work.
Marcin Andrychowicz, Stefan Dziembowski · 2014
Abstract. Motivated by the recent success of Bitcoin we study the question of constructing distributed crypto-graphic protocols in a fully peer-to-peer scenario (without any trusted setup) under the assumption that the adver-sary 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 imple-mentations (probably after some optimizations and simplifications). We discuss some possible applications of our protocols at the end of the paper. We stress however that the goal of this paper is not to propose new cryptocurrencies or to analyze the existing ones. 1