Welcome to the resource topic for 2020/1480
Title:
Malicious Security Comes for Free in Consensus with Leaders
Authors: Mark Abspoel, Thomas Attema, Matthieu Rambaud
Abstract:We consider Byzantine Agreement in the fully asynchronous network model with t < n/3 corruptions out of n players. An important challenge in this field is to develop efficient protocols, measured in the total number of bits communicated. We present the first consensus protocol with quasilinear complexity that achieves the following three desirable properties: responsiveness with optimal latency, optimistic fast track, and strong unanimity. To date, {none of these} three properties has been achieved with subquadratic complexity. Our protocol uses the leader-based framework, which proceeds in phases in which a single player is designated as the leader for that phase. Our key insight is that previous constructions that achieve some of the three properties implicitly require the leader to prove knowledge of certain signed messages from sufficiently many (2t+1) distinct players. We observe that, up to now, proving this knowledge was done by naively forwarding these messages to all players, resulting in quadratic communication. We formalize these proofs for the first time, with two novel abstractions that we refer to as proof of recency'' (PoR) and proof of exclusivity’’ (PoE). We are able to use recent results on communication-efficient zero-knowledge protocols to {directly} instantiate these proofs with constant size, and as a result, obtain a consensus protocol with quasilinear complexity. Due to the generality of our techniques, we are able to directly improve existing constructions. In particular, we can improve the latency of HotStuff (PODC’19), which is implemented in Facebook’s Libra, from 7 to 5 messages before output, and even to 3 in optimistic executions, while preserving a worst-case quasilinear complexity. Our protocol uses standard cryptographic assumptions and only requires a public-key infrastructure, in contrast to the trusted setup required in HotStuff. Of independent interest, we show that both the PoR and PoE functionalities can also be obtained by interactive protocols, using any threshold signature scheme in a black box manner, while keeping optimal latency and the complexity {linear} in n, at the cost of one of several possible tradeoffs regarding complexity and responsiveness. Finally we provide {halting in finite time} with both external validity and linear complexity, in the amortized regime over long input values.
ePrint: https://eprint.iacr.org/2020/1480
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .