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 $k$ ($=\,\! 2t{\,+\,}1$) of such reports, calling $v_\mathrm{max}$ the highest reported value, the leader can efficiently build a short proof that a threshold number of $k-t$ honest players have their inputs lower than this $v_\mathrm{max}$. As highlighted in the state of the art BFT [Abraham et al. Podc'23], any of our lightweight implementations of PnS can be plugged in their BFT, or the one of [Gelashvili et al FC'22], to bring down their complexities from quadratic to linear. Previous BFTs implicitely implemented PnS by either (i) having the leader multicasting the $k$ signed reports, so this had quadratic communication complexity, or (ii) multicasting an aggregate signature on the reports, with verification complexity of $k+1$ pairings, so this had a total quadratic computation complexity. To match our linear complexity claim, we introduce a very simple constant-sized and constant-verification implementation of PnS, built from any threshold (or multi-) signature scheme. We then bring further optimizations by introducing the following tools of possible independent interest: (1) a simple and general optimization to BFTs, which applies to any view without a hidden lock. It removes the need for sending and verifying a PnS. Previous optimizations applied to a narrower set of views, essentially, those for which the leader of the previous one was honest and enjoyed synchrony; (2) a simple compiler from any multisignature scheme, into an aggregate signature scheme of a special-purpose type. It operates over tagged messages, each key can sign at most one message with a given tag.

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.