Pairing-based Aggregate Multi-Signatures

Problems with scaling

As the number of validators grows, the total size of all validator signatures also grows and impacts the block size. For a new block to be confirmed, it needs to be verified and signed off by more than ⅔ validators in the current committee. These signatures must be stored as part of the block data. Assuming the committee size is 300, and each signature size is 32 bytes, the total size of more than ⅔ validator signatures (201 signatures) is at least 201 * 32 bytes = 6,432 bytes. This makes scaling the number of validators much more difficult.

Cryptographic solution

To solve this problem, we implement the BLS-based aggregate multi-signature scheme AMSP [BDN18], which combines all validator signatures into one single signature. The size of the aggregate signature is the same as a single validator signature. Regardless of the number of validators, the size of the aggregate signature is only 32 bytes, even though it is combined from multiple signatures.
The ASMP scheme does not require too much information exchange between validators. The Vote Phase (Algorithm 1) has a Signature Signing Step, in which validators verify the proposed block and sign off on it. The Signature Signing Step is completed in just one round. The Commit Phase has a Signature Verification Step for verifying validator signatures and a Signature Aggregation Step for combining them into a single short aggregate signature without any additional interaction.
Not only is its size short, but the aggregate signature also ensures security and requires little interaction among validators.

References

[BDN18] Dan Boneh, Manu Drijvers, and Gregory Neven. Compact multi-signatures for smaller blockchains. In Thomas Peyrin and Steven Galbraith, editors, ASIACRYPT 2018, Part II, volume 11273 of LNCS, pages 435–464. Springer, Heidelberg, December 2018.

8 Likes