Paper 2021/916

Mithril: Stake-based Threshold Multisignatures

Pyrros Chaidos and Aggelos Kiayias

Abstract

Stake-based multiparty cryptographic primitives operate in a setting where participants are associated with their stake, security is argued against an adversary that is bounded by the total stake it possesses —as opposed to number of parties— and we are interested in scalability, i.e., the complexity of critical operations depends only logarithmically in the number of participants (who are assumed to be numerous). In this work we put forth a new stake-based primitive, stake-based threshold multisignatures (STM, or “Mithril” signatures), which allows the aggregation of individual signatures into a compact multisignature provided the stake that supports a given message exceeds a stake threshold. This is achieved by having for each message a pseudorandomly sampled subset of participants eligible to issue an individual signature; this ensures the scalability of signing, aggregation and verification. We formalize the primitive in the universal composition setting and propose efficient constructions for STMs. We also showcase that STMs are eminently useful in the cryptocurrency setting by providing two applications: (i) stakeholder decision-making for Proof of Work (PoW) blockchains, specifically, Bitcoin, and (ii) fast bootstrapping for Proof of Stake (PoS) blockchains.

Note: Updated comparison table.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
digital signatureszero knowledgeblockchains
Contact author(s)
pchaidos @ di uoa gr
akiayias @ inf ed ac uk
History
2022-01-19: last of 4 revisions
2021-07-08: received
See all versions
Short URL
https://ia.cr/2021/916
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/916,
      author = {Pyrros Chaidos and Aggelos Kiayias},
      title = {Mithril: Stake-based Threshold Multisignatures},
      howpublished = {Cryptology ePrint Archive, Paper 2021/916},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/916}},
      url = {https://eprint.iacr.org/2021/916}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.