Paper 2023/063

Threshold Signatures in the Multiverse

Leemon Baird, Swirlds Labs
Sanjam Garg, University of California, Berkeley, NTT Research
Abhishek Jain, Johns Hopkins University
Pratyay Mukherjee, SupraOracles
Rohit Sinha, Meta
Mingyuan Wang, University of California, Berkeley
Yinuo Zhang, University of California, Berkeley

We introduce a new notion of {\em multiverse threshold signatures} (MTS). In an MTS scheme, multiple universes -- each defined by a set of (possibly overlapping) signers, their weights, and a specific security threshold -- can co-exist. A universe can be (adaptively) created via a non-interactive asynchronous setup. Crucially, each party in the multiverse holds constant-sized keys and releases compact signatures with size and computation time both independent of the number of universes. Given sufficient partial signatures over a message from the members of a specific universe, an aggregator can produce a short aggregate signature relative to that universe. We construct an MTS scheme building on BLS signatures. Our scheme is practical, and can be used to reduce bandwidth complexity and computational costs in decentralized oracle networks. As an example data point, consider a multiverse containing 2000 nodes and 100 universes (parameters inspired by Chainlink's use in the wild) each of which contains arbitrarily large subsets of nodes and arbitrary thresholds. Each node computes and outputs 1 group element as its partial signature; the aggregator performs under 0.7 seconds of work for each aggregate signature, and the final signature of size 192 bytes takes 6.4 ms (or 198K EVM gas units) to verify. For this setting, prior approaches when used to construct MTS, yield schemes that have one of the following drawbacks: (i) partial signatures that are 97$\times$ larger, (ii) have aggregation times 311$\times$ worse, or (iii) have signature size 39$\times$ and verification gas costs 3.38$\times$ larger. We also provide an open-source implementation and a detailed evaluation.

Available format(s)
Publication info
Published elsewhere. IEEE S&P 2023
Threshold SignatureBLSMultiverse Signature
Contact author(s)
leemon @ swirldslabs com
sanjamg @ berkeley edu
abhishek @ cs jhu edu
pratyay85 @ gmail com
sinharo @ gmail com
mingyuan @ berkeley edu
yinuo yz @ gmail com
2023-01-20: approved
2023-01-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Leemon Baird and Sanjam Garg and Abhishek Jain and Pratyay Mukherjee and Rohit Sinha and Mingyuan Wang and Yinuo Zhang},
      title = {Threshold Signatures in the Multiverse},
      howpublished = {Cryptology ePrint Archive, Paper 2023/063},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.