Paper 2020/1480
Proofs of non-Supermajority: the missing link for two-phase BFT with responsive view-change and linear complexity
Abstract
We consider leader-based Byzantine state machine replication, a.k.a. "BFT", under partial synchrony. We provide a generic solution enabling to match simultaneously, for the first time, three arguably gold standards of BFT: in two phases, with a responsive view change and a linear complexity per view.
It is based on a new threshold primitive, which we call Proofs of non-Supermajority (or PnS for short). A PnS system enables players, each with an input number, to report their input to a leader, with extra hints enabling their efficient aggregation. Out of a threshold number
Note: Forks on the v1 (November 2020), of which the TSS-based PnS briefly announced to Podc'21. New results of independent interest are the (1) (2) and (3) (cf abstract and introduction). Some previous material of the April 2021 version is now forked in [Abspoel, Rambaud, Tonkikh, Consensus Days'22] (fast tracks) and, in a preliminary form, in section 7 of eprint 2020/1447.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- ConsensusByzantine fault toleranceblockchainsmultisignaturesproofs of possessionaggregate signatures
- Contact author(s)
-
christophe levrat @ telecom-paris fr
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
-
CC BY
BibTeX
@misc{cryptoeprint:2020/1480, author = {Christophe Levrat and Matthieu Rambaud}, title = {Proofs of non-Supermajority: the missing link for two-phase {BFT} with responsive view-change and linear complexity}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/1480}, year = {2020}, url = {https://eprint.iacr.org/2020/1480} }