Introduction
We design & implement BLS threshold signatures that scale to millions of signers and a scalable distributed key generation protocol for bootstrapping.
Abstract
The resurging interest in Byzantine fault tolerant
systems will demand more scalable threshold cryptosystems.
Unfortunately, current systems scale poorly, requiring time
quadratic in the number of participants. In this paper, we present
techniques that help scale threshold signature schemes (TSS),
verifiable secret sharing (VSS) and distributed key generation
(DKG) protocols to hundreds of thousands of participants and
beyond. First, we use efficient algorithms for evaluating polynomials at multiple points to speed up computing Lagrange
coefficients when aggregating threshold signatures. As a result, we
can aggregate a 130,000 out of 260,000 BLS threshold signature
in just 6 seconds (down from 30 minutes). Second, we show
how “authenticating” such multipoint evaluations can speed up
proving polynomial evaluations, a key step in communication-efficient VSS and DKG protocols. As a result, we reduce the
asymptotic (and concrete) computational complexity of VSS and
DKG protocols from quadratic time to quasilinear time, at
a small increase in communication complexity. For example,
using our DKG protocol, we can securely generate a key for
the BLS scheme above in 2.3 hours (down from 8 days). Our
techniques improve performance for thresholds as small as 255
and generalize to any Lagrange-based threshold scheme, not
just threshold signatures. Our work has certain limitations: we
require a trusted setup, we focus on synchronous VSS and
DKG protocols and we do not address the worst-case complaint
overhead in DKGs. Nonetheless, we hope it will spark new
interest in designing large-scale distributed systems.