Paper 2023/063
Threshold Signatures in the Multiverse
Abstract
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 coexist. A universe can be (adaptively) created via a noninteractive asynchronous setup. Crucially, each party in the multiverse holds constantsized 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 opensource implementation and a detailed evaluation.
Metadata
 Available format(s)
 Category
 Applications
 Publication info
 Published elsewhere. IEEE S&P 2023
 Keywords
 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  History
 20230120: approved
 20230120: received
 See all versions
 Short URL
 https://ia.cr/2023/063
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/063, 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}, url = {https://eprint.iacr.org/2023/063} }