(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.Category / Keywords: cryptographic protocols / Proofs of Work, Bitcoin, Broadcast, Multipaty Computation Protocols Date: received 5 Oct 2014, last revised 17 Dec 2014 Contact author: std at mimuw edu pl Available format(s): PDF | BibTeX Citation Note: Reorganized introduction. Version: 20141217:202421 (All versions of this report) Short URL: ia.cr/2014/796 Discussion forum: Show discussion | Start new discussion