How Do Robust Subgroup Multisignatures Work?

TL;DR

Robust subgroup multisignatures let any threshold-sized subset of eligible signers jointly approve one message while producing a compact signature and identifying the actual participants. The construction uses BLS signature aggregation, but it must prevent malicious public-key manipulation through defenses such as proof of possession, while remaining fault-tolerant when some signers are unavailable or disruptive.

Transcript

This work is entitled Robust Subgroup Multisignatures for Consensus, and this is a joint work with, uh, Jia Liu, who is affiliated with HEI in the UK. My name is David Galindo. I'm affiliated with the University of Birmingham in UK and VALLI in Switzerland. A reminder of the, uh, primitive of multisignatures. We have a set of N signers who want to ... Read More

Key Insights

• Multisignatures bind a group of signers to one common message by combining their contributions into a final signature that represents collective approval.
• Non-interactive multisignatures let each participant independently produce a message for a coordinator or combiner, which uses public information to calculate the final signature and requires no special trusted status.
• The simplest multisignature construction combines signatures from any secure signature scheme, but its final size and verification time grow linearly with the number of participating signers.
• Compact multisignatures reduce storage overhead by compressing multiple individual signatures into one signature, ideally with a size independent of the number of signers, although the technique does not apply to every secure signature scheme.
• T-out-of-N subgroup multisignatures allow a qualifying subset of the eligible group to sign successfully, so the protocol can continue even when some parties are absent, unavailable, or unwilling to participate.
• Robustness requires disruptive signers to be unable to poison or interrupt the signing process, while traceability identifies the actual participants and prevents an honest non-signer from later being represented as a signer.
• BLS aggregation works by multiplying signatures on the same message and multiplying the corresponding public keys, producing a single signature and an aggregated public key that can be checked with a pairing equation.
• Naive BLS aggregation is vulnerable to malicious public-key manipulation, but proof of possession can augment each public key with evidence that its registrant knows the corresponding secret key.

Questions & Answers

Q: What is a non-interactive multisignature?

A non-interactive multisignature is a protocol in which multiple parties, each holding an individual public and secret signing-key pair, independently produce contributions for the same message. They send those contributions to a coordinator or combiner, which calculates the final signature using public information. The combiner needs no special authority and can be one of the signing parties.

Q: Why are basic multisignature constructions inefficient?

A basic construction has every party sign the common message with an ordinary secure signature scheme, then combines all individual signatures into the final result. Although this method is simple and works with any secure signature scheme, the final signature requires storage proportional to the number of signers, and verification time also grows linearly with that number.

Q: What makes a multisignature compact?

A multisignature is compact when its final representation uses less storage than the combined size of all individual signatures. The ideal described in the presentation is a final signature whose size is independent of the number of signers. This reduces storage overhead and can improve verification time, but compact aggregation generally cannot be applied to every secure signature scheme.

Q: What is a T-out-of-N subgroup multisignature?

A T-out-of-N subgroup multisignature allows a subgroup drawn from a global set of N eligible signers to jointly sign a message, provided the required threshold T is met. Unlike an N-out-of-N design, it does not require every eligible party to be present. This allows signing to proceed when some participants are unavailable or choose not to participate.

Q: What does robustness mean for subgroup multisignatures?

Robustness means that individual signers should not be able to interrupt or poison the collective signing process. The construction should remain fault-tolerant when some eligible parties are unavailable or disruptive. It should also trace which members actually signed, ensuring that an honest participant who did not sign is not falsely represented as having approved the message.

Q: How can subgroup multisignatures support proof-of-stake consensus?

A proof-of-stake consensus protocol can begin block creation with a known set of validators and require a minimum number of them to approve the block contents. A subgroup multisignature lets the qualifying validators combine their approvals into one compact signature. Because every validator is not required, the chain can continue progressing despite unavailable or disruptive members.

Q: How does BLS signature aggregation create a compact signature?

BLS signatures place each signature in a group where signatures on the same message can be multiplied together. The corresponding public keys can also be multiplied into one aggregated public key. Pairing-based verification then checks the combined signature against that key. The result compresses multiple signatures and public keys into single group elements rather than storing each signature separately.

Q: Why is naive BLS multisignature aggregation vulnerable?

Naive BLS aggregation permits an adversary to construct a malicious public key using the inverse of an existing aggregated public key and a chosen group exponent. Adding that key makes the new aggregate equal to a value controlled by the adversary. The attacker can then create a signature on a chosen message that verifies under the manipulated aggregated public key.

Q: How does proof of possession defend BLS aggregation?

Proof of possession augments a BLS public key with an additional element demonstrating possession of its corresponding secret key. The presentation describes constructing this evidence by hashing a user's public key and raising the result to that user's secret key. Requiring such evidence addresses attacks in which an adversary registers a specially manipulated public key without knowing its matching secret key.

Summary & Key Takeaways

• Multisignatures bind multiple parties to one common message. A basic non-interactive construction collects every individual signature and combines them, but its storage and verification costs grow linearly with the number of signers. Compact designs instead seek a final signature whose size is ideally independent of the group size.

• The proposed primitive extends N-out-of-N multisignatures to T-out-of-N subgroup signing. It is designed to identify the parties who actually signed, tolerate unavailable participants, and prevent disruptive signers from poisoning the process. Its primary intended application is validator approval in proof-of-stake consensus, with multisignature wallets as another example.

• BLS signatures support compact aggregation because signatures on the same message and their corresponding public keys can be multiplied into single group elements. A naive construction is vulnerable to a malicious public-key attack that enables forgery under a manipulated aggregate key. Proof of possession is presented as a recognized defense against this attack.