Cryptology ePrint Archive: Report 2017/915

Efficient Algorithms for Broadcast and Consensus Based on Proofs of Work

Lisa Eckey and Sebastian Faust and Julian Loss

Abstract: Inspired by the astonishing success of cryptocurrencies, most notably the Bitcoin system, several recent works have focused on the design of robust blockchain-style protocols that work in a peer-to-peer setting such as the Internet. In contrast to the setting traditionally considered in multiparty computation (MPC), in these systems, honesty is measured by computing power instead of requiring that only a certain fraction of parties is controlled by the adversary. This provides a potential countermeasure against the so-called Sybil attack, where an adversary creates fake identities, thereby easily taking over the majority of parties in the system. In this work we design protocols for Broadcast and Byzantine agreement that are secure under the assumption that the majority of computing power is controlled by the honest parties and for the first time have expected constant round complexity. This is in contrast to earlier works (Crypto'15, ePrint'14) which have round complexities that scale linearly with the number n of parties; an undesirable feature in a P2P environment with potentially thousands of users. In addition, our main protocol which runs in quasi-constant rounds, introduces novel ideas that significantly decrease communication complexity. Concretely, this is achieved by using an appropriate time-locked encryption scheme and by structuring the parties into a network of so-called cliques.

Category / Keywords: cryptographic protocols / Broadcast, Byzantine Agreement, Proof of Works, Time Locked Encryption

Date: received 20 Sep 2017, last revised 26 Sep 2017

Contact author: julian loss at rub de

Available format(s): PDF | BibTeX Citation

Version: 20170926:065523 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]