Paper 2023/498

Subset-optimized BLS Multi-signature with Key Aggregation

Foteini Baldimtsi, Mysten Labs, George Mason University
Konstantinos Kryptos Chalkias, Mysten Labs
Francois Garillot, Lurk Labs
Jonas Lindstrom, Mysten Labs
Ben Riva, Mysten Labs
Arnab Roy, Mysten Labs
Alberto Sonnino, Mysten Labs, University College London
Pun Waiwitlikhit, Stanford University, Mysten Labs
Joy Wang, Mysten Labs

We propose a variant of the original Boneh, Drijvers, and Neven (Asiacrypt '18) BLS multi-signature aggregation scheme best suited to applications where the full set of potential signers is fixed and known and any subset $I$ of this group can create a multi-signature over a message $m$. This setup is very common in proof-of-stake blockchains where a $2f+1$ majority of $3f$ validators sign transactions and/or blocks and is secure against $\textit{rogue-key}$ attacks without requiring a proof of key possession mechanism. In our scheme, instead of randomizing the aggregated signatures, we have a one-time randomization phase of the public keys: each public key is replaced by a sticky randomized version (for which each participant can still compute the derived private key). The main benefit compared to the original Boneh at al. approach is that since our randomization process happens only once and not per signature we can have significant savings during aggregation and verification. Specifically, for a subset $I$ of $t$ signers, we save $t$ exponentiations in $\mathbb{G}_2$ at aggregation and $t$ exponentiations in $\mathbb{G}_1$ at verification or vice versa, depending on which BLS mode we prefer: $\textit{minPK}$ (public keys in $\mathbb{G}_1$) or $\textit{minSig}$ (signatures in $\mathbb{G}_1$). Interestingly, our security proof requires a significant departure from the co-CDH based proof of Boneh at al. When $n$ (size of the universal set of signers) is small, we prove our protocol secure in the Algebraic Group and Random Oracle models based on the hardness of the Discrete Log problem. For larger $n$, our proof also requires the Random Modular Subset Sum (RMSS) problem.

Available format(s)
Public-key cryptography
Publication info
BLSmulti-signaturessignature aggregationblockchain
Contact author(s)
foteini @ mystenlabs com
chalkiaskostas @ gmail com
arnabr @ gmail com
2023-04-20: last of 2 revisions
2023-04-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Foteini Baldimtsi and Konstantinos Kryptos Chalkias and Francois Garillot and Jonas Lindstrom and Ben Riva and Arnab Roy and Alberto Sonnino and Pun Waiwitlikhit and Joy Wang},
      title = {Subset-optimized BLS Multi-signature with Key Aggregation},
      howpublished = {Cryptology ePrint Archive, Paper 2023/498},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.