### Efficient Algorithms for Broadcast and Consensus Based on Proofs of Work

##### 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. Note: This article contains incorrect claims. Some of its contributions were subsumed by eprint article 2022/823

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Broadcast Byzantine Agreement Proof of Works Time Locked Encryption
Contact author(s)
lisa eckey @ crisp-da de
lossjulian @ gmail com
History
2022-06-27: last of 2 revisions
See all versions
Short URL
https://ia.cr/2017/915

CC BY

BibTeX

@misc{cryptoeprint:2017/915,
author = {Lisa Eckey and Sebastian Faust and Julian Loss},
title = {Efficient Algorithms for Broadcast and Consensus Based on Proofs of Work},
howpublished = {Cryptology ePrint Archive, Paper 2017/915},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/915}},
url = {https://eprint.iacr.org/2017/915}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.