Subset-optimized BLS Multi-signature with Key Aggregation

Mysten Labs designed a new signature aggregation protocol, optimized for Proof-of-Stake blockchains, like Sui. You can view the paper on the IACR site.

Validator Signatures in Proof of Stake Blockchains

Proof-of-Stake (PoS) blockchains, like Sui, rely on a sufficient number of validators agreeing on which transactions to add to the blockchain. The way this agreement is communicated is by the validators individually signing the same message encoding a proposed transaction. Once there are enough signatures, the proposer can offer these as proof that enough validators agreed to add the transaction. However, the cumulative size of all of these signatures can run into megabytes. Is it possible to have a short signature on a message that attests to the fact that multiple signers signed it? Ideally, we want a signature that’s comparable in size to a single signer signature, can be created efficiently given the individual signatures, and can be verified almost as fast as one.

Through the years, cryptographers have invented many flavors of such a compression scheme:

1. Threshold signatures: In this mode of compressing signatures, there are a total of n parties and there is a threshold t. A valid aggregate signature can be constructed once we have any subset of signers of size more than t sign the message. The final signature does not depend upon which subset of signers signed it. The final signature is typically the same size as any individual one, and can be verified as fast. However, a major drawback of these systems is that the signers need to engage in a distributed key generation protocol to set up their individual keys, before starting to sign any message.
   
   

2. SNARKs: Essentially once an aggregator has a set of signatures, they construct a short proof that they know such a set. This allows for short aggregate signatures, and pretty fast verification. However, producing this proof is still pretty inefficient, which is a bottleneck on fast finality consensus systems.
   
   

3. Proofs of possession: In these schemes, the signers provide a proof of possession of their individual signing keys at the setup phase. Once these proofs are available, the schemes enable remarkably fast aggregation and verification algorithms. However, obtaining and checking the proofs of possession introduce extra system complexity and induce additional burden on verifiers.

Beyond these broad categories, there are protocols that require more rounds of interaction, or perform a generic slow preprocessing step followed by fast aggregation at the time of actual signing, or employ heavy randomized aggregation and verification steps.

When the set of validators start scaling up, all of these mechanisms start exhibiting some deficiencies. Ideally, in a blockchain with thousands of validators, we want to have a signature aggregation system that can work with a dynamic set of signers, work without any setup phase, work with the native public key of the signers, and enable fast aggregation and verification algorithms.

We talk about our proposal to address all these challenges, which stands on the shoulder of a couple decades of research in this space. In particular we build upon BLS signatures, and its extensions.

BLS Signatures

Boneh, Lynn and Shacham invented a remarkable signature scheme in 2001 [BLS01], which has enjoyed significant exploration due to its simple algebraic structure. In particular, the scheme has enabled advanced distributed protocols for achieving threshold signing, complex policy-based signing, blind signatures, efficient distributed key generation, and so on. Aggregating signatures on a single message is an important blockchain application, as Proof-of-Stake (PoS) blockchains require multiple signatures on the same transaction. The set of signers may be quite dynamic, as the validator sets change over time. The construction of Boneh, Drijvers, and Neven [BDN18] built on top of BLS and obtained non-interactive aggregation of signatures which enjoyed a strong definition of security, which in particular ruled out rogue-key attacks.

Rogue-key attacks are launched by adversaries which can craft public keys which are algebraically related to honest public keys that they want to attack. If we aggregate BLS signatures in naive ways, the attacker can choose keys that cancel out the honest public keys. This way they can pretend to claim that many honest signers signed a message, by including rogue signing keys. [BDN18] prevented this attack by making these algebraic manipulations almost impossible to achieve. In particular, the scheme makes the adversary commit to the full set of public keys they want to attack and these commitments are bound to the aggregation.

Our Proposal

Although their scheme is remarkably efficient, we observed that in important blockchain settings there is room for significant improvement. In some PoS blockchains like Sui, the full set of validators is already known at the start of every epoch. In such a setting we can have the random commitments just depend on the full set of validators. Although, for any specific transaction, the particular subset of signers may be different, the randomizations now depend on the full set. This simple observation now enables some remarkable optimizations:

1. The signers can pre-randomize their keys when the epoch starts, based on their knowledge of the full set of signers.
   
   

2. As a result, the individual signatures also get pre-randomized automatically.
   
   

3. Aggregation of signatures is just adding elliptic curve points, corresponding to the pre-randomized signatures, which is a super fast operation.
   
   

4. The aggregated verification key is also just adding elliptic curve points, corresponding to the pre-randomized verification keys.

You can find the technical paper with a formal description of the protocol and its security proof on the IACR site. We also performed several experiments to compare our protocol with the [BDN18] protocol and demonstrated significant practical efficiency gains.