You are looking at a specific version 20201129:224740 of this paper. See the latest version.

Paper 2020/1480

Malicious Security Comes for Free in Consensus with Leaders

Matthieu Rambaud

Abstract

We remove the so far quadratic bit communication cost of three desirable properties of consensus protocols with leaders: { Responsiveness with Optimal latency }, { Optimistic Fast Track } and { Strong Unanimity }. No existing consensus protocol with leaders with subquadratic bit complexity has any of those properties so far. [Hotstuff, Podc'19] has suboptimal latency of two more messages delays, whereas Hotstuffv1 is not responsive. [SBFT, Dsn'19] has quadratic complexity every time a new leader appears. Strong Unanimity has equally quadratic complexity so far [Chan et al Podc'19] in this setting. We reduce the communication costs of each of these properties down to $O(n\log n)$. In addition, we achieve them { simultaneously }, with optimal corruption threshold. To achieve these specifications we use the structure of the consensus of Castro-Liskov / [SBFT, Dsn'19], in which we drop-in succinct (range-) proofs of knowledge as a replacement for the forwarding of many messages. We use the same kind of strategy to enable a Fast Track and Strong Unanimity. Namely, we incorporate the additional structure of [SBFT, Dsn'19] and of [Chan et al Podc'19] in the previous protocol. Which we instantiate with proofs of knowledge of: a set of signed messages, from a threshold number of issuers, in which no value appears in majority. The required proofs of knowledge can be obtained from any succinct proof system. Of independent interest, we also introduce alternative elementary proofs, solely based on a black box Threshold Signature Scheme (TSS). { Applied } to the state of the art leader-less fully asynchronous consensus protocol [Podc'19], which uses the [Hotstuff, Podc'19] consensus as baseline, this reduces its latency by $25\%$. This speedup directly carries over the state machine replication system [Hotstuff, Podc'19], and thus to Libra. Of independent interest we maintain linear complexity when requiring both External Validity and Halting in finite time, in the Amortized regime over long values. Instantiated with the recent unpublished logarithmic Transparent TSS of Attema et al, none of our protocols requires a trusted setup or a distributed key generation.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Consensus
Contact author(s)
matthieu rambaud @ telecom-paris fr
History
2023-05-17: last of 4 revisions
2020-11-29: received
See all versions
Short URL
https://ia.cr/2020/1480
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.