# Brief Announcement

Brief Announcement: Malicious Security Comes for Free in Consensus with Leaders

We consider consensus protocols in the model that is most commonly considered for use in state machine replication, as initiated by Dwork-Lynch-Stockmeyer, then by Castro-Liskov in 1999 with “PBFT”. Such protocols guarantee, assuming n players out of which t < n/3 are maliciously corrupted, that the honest players output the same valid value within a finite number of messages, after the (unknown) point in time where both: the network becomes synchronous, and a designated player (the leader) is honest. The state of the art (Hotstuff, PODC’19), achieves linear communication complexity, but at the cost of additional latency, due to one more round-trip with the leader. Furthermore, it relies on constant-size threshold signatures schemes (TSS), for which all prior-known constructions require a costly interactive (or trusted) setup. We remove all of these limitations. The communication bottleneck of PBFT lies in the subprotocol, denoted as “view change”, in which the leader forwards 2t + 1 signed messages to each player. Then, each player checks that these 2t + 1 messages satisfy some predicate, which we denote “non-supermajority”. We replace this with a responsive subprotocol, with linear communication complexity, that enables players to check this predicate. Its construction is elementary, since it requires only black box use of any TSS. In the full version of our paper [5] we achieve three things. Firstly, we further optimize this subprotocol from succinct arguments of many signed messages, which we instantiate from Attema-Cramer Rambaud [8, 2021-3-9 version]. As an introduction to these methods, we discuss here the simplest case, which is the construction in [8] of the first logarithmic-sized TSS with transparent setup. Second, we also address another complexity challenge pointed in Hotstuff, namely, that protocols with fast termination in favorable runs, have so far quadratic complexity, due to an even more complex view change. Third, we enable halting in finite time with (amortized) linear complexity, which was an unsolved question so far when external validity is required.

Subjectbft

consensus

state machine replication

succinct proofs

Computational complexity

Network security

Communication complexity

Consensus protocols

External validities

Linear complexity

Quadratic complexity

State machine replication

State of the art

Threshold signature

Complex networks

http://resolver.tudelft.nl/uuid:94deaefc-7bd5-47ed-8280-ba739e6a32ab

TNO identifier967809

9781450385480

Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 40th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2021, 26 July 2021 through 30 July 2021, 195-198

Bibliographical noteSponsor: ACM SIGACT;ACM SIGOPS

conference paper

To receive the publication files, please send an e-mail request to TNO Library. |