Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / Consensus

Date: received 25 Nov 2020, last revised 29 Nov 2020

Contact author: matthieu rambaud at telecom-paris fr

Available format(s): PDF | BibTeX Citation

Version: 20201129:224740 (All versions of this report)

Short URL: ia.cr/2020/1480