Aggregate, Threshold, Multisig and Multisignatures

A brief survey and comparison

Introduction

Digital signatures play a central role in Blockchain technology since every single transaction needs to be signed to be valid. To be precise, digital signatures have a threefold objective in blockchain protocols:

1. They prove ownership and provide authorization to spend the funds.
2. They prove non-repudiation, meaning that the proof of authorization is undeniable.
3. They prove that a transaction has not and cannot be modified.

Current signing schemes, where a single user issues signatures for messages, may suffer from a potential threat since it represents a single point of failure that can ruin the scheme if a malicious user gets control of the secret key.

The above problem can be avoided by introducing either multisignature schemes or threshold signatures. Both schemes are quite similar in the sense that they are multiparty protocols and require a minimum of m out of n users to sign a file to prove authenticity. Nevertheless, there are a few, but important, differences between them, and it is the objective of this report to compare, from a high perspective, both signature schemes.

Since the field is getting active with several proposals, such as MuSig2 or FROST, it is a good moment for an introduction and a comparison of three techniques that share some similarities and differences and tend to be confused in the blockchain environment. The goal is to present multisignature, threshold signatures and aggregate signatures, avoiding as much as possible any technical terms while providing an elementary introduction to MuSig2 and FROST.

Digital signature schemes

The following section may be polemical as one of the objectives is to remove the confusion around concepts such as multisignatures, threshold and aggregate signatures, which are concepts that merge and combine in many situations within the blockchain.

Multisignatures

In a naive approach to multisignatures, each of n users has a public/private pair of keys. A valid signature in this situation is a collection of signatures of n users. Verification of the signatures requires using the public key of each signer to verify the final signature.

Allowing each participant to have its key pair makes multisignature-based authentication take up a lot more space. A configuration requiring a quorum of n signatures must include not only all n signatures but also n public keys. ​​This makes multi-signature transactions more costly, with space and processing costs scaling linearly in n.

On the other hand, users with personal key pairs have the opportunity to participate in several signature processes in parallel, contrary to what happens in threshold signatures, where each player has a shared secret key that issues a portion of the signature. These shares must be combined to generate a valid final signature. Observe that these shares may not be used in another signing process by themselves.

Keys involved in a multisignature scheme are stored on-chain, whereas in threshold schemes computations and secret sharing are performed off-chain, and only one public key is stored on-chain. This makes threshold schemes much cheaper than multisignature proposals in terms of space and computation required for verification.

Naive multisignatures may not be the best solution for Blockchain due to its inefficiency. To overcome this issue, some solutions allow all participants involved in the process to sign the message with their secret key; then the outputs are combined into a single message that is verified using a combined public key. This is the mechanism that uses MuSig2, for instance, as it will be described below.

Aggregate signatures

Aggregate signatures are used, among other applications, to the reduction of the sizes in certificate chains or to reduce messages sizes in routing protocols.

Aggregate signatures are the non-trivial generalization of multi-signatures (where all users sign the same message). An aggregate signature allows creating a single compact signature from m signatures on m distinct messages from m distinct signers. This provides faster verification as well as a reduction in storage and bandwidth.

There are two primary mechanisms of signature aggregation: general and sequential aggregation. To describe these mechanisms, assume a set of m users having each a public/private pair of keys and user i wants to sign message Mi.

1. In a general signature aggregation scheme, each user i (from the group of m users) creates signature i on his/her message Mi. To generate an aggregate signature, anyone can run the public aggregation algorithm to take all m signatures (σ1, σ2, …, σk) and compress them into a single signature σ.
2. In a sequential signature aggregation scheme, user 1 signs M1 to obtain σ1; user 2 then combines σ1 and M2 to obtain σ2; and so on. The final signature σ is generated by user k which binds Mk and the signature σk-1. Sequential signature aggregation can only take place during the signing process.

Techniques for aggregating signatures are known for a variety of signature schemes such as Schnorr, lattice-based and pairing-based. Concerning pairing-based aggregate signatures, it is important to highlight the BLS scheme (Boneh et al.), which is being used by blockchain proposals such as Dfinity and Algorand. Nevertheless, these proposals sign the same message, so one should consider these solutions an example of multisignature, rather than a proper aggregate signature scheme.

Last but not least, most of the proposals require a specific order when signing a message, but there are schemes where this requirement is no longer needed (Lu et al.)

Aggregate signature schemes should restrict any adversary from creating a valid aggregate signature on his/her own.

Threshold signatures

A (m, n)-threshold signature scheme is a digital signature scheme where any m or more signers from a group of n signers can produce signatures on behalf of the group. This signature can be later verified with a public group key, which is generated after combining the public keys of the participants. In general, a threshold signature does not reveal the actual group members that have cooperated to produce it.

The goal of a threshold signature scheme is to enforce control over the signing capability (for m > 1), to eliminate single points of failure (for n > 1), or both.

Each group of signers can be managed by a trusted group authority, which oversees joining and leaving the group. Many groups can choose to be managed by the same trusted group authority, or a group can choose to fully distribute the group management among its members such that every member is involved in all management operations.

Any subset of (more than) m-out-of-n members of a group G can produce a signature. To do so, each member contributes a partial signature to a designated combiner, and the combiner derives the intended threshold signature from the partial signatures.

Everyone who has access to the public group key of group G can verify the threshold signature. The designated combiner can be a real entity such as the trusted group authority, or it can be a virtual entity whose operations are computed in a distributed fashion among all group members. A threshold signature scheme is robust if the designated combiner can verify the validity of each partial signature before accepting it as an input to a threshold signature.

A comparison

For the moment we have described four techniques that are very similar between them. Below follows a comparison of the several methods surveyed:

(*) In this case, messages can be distinct, up to n.

(**) Assumed to be a (m, n)-threshold scheme.

Introducing MuSig2 and FROST

Amongst the proposals that are being considered to introduce multisignatures or threshold signatures in blockchain platforms, one finds MuSig2 and FROST. The following sections are intended as a brief, non-technical introduction to both schemes. Those interested in the details and the mathematical backbone will enjoy reading (Nick et al.) and (Komlo and Goldberg).

A brief introduction to MuSig2

The proposal MuSig2 (Nick et al.) cannot be considered a naive multisignature scheme as it shares some similarities with aggregate signature proposals.

Amongst the highlights of the scheme, one finds:

• It's secure under parallel signing sessions.
• The possibility of key aggregation.
• It outputs ordinary Schnorr signatures.
• Reduces the communication rounds to two, in contrast to the earlier proposal MuSig, which requires three rounds.
• Has signer complexity similar to ordinary Schnorr signatures.

In MuSig2 each participant has a pair of keys, one private and one public key. They are generated by taking x ∈ ℤ at random and computing X = g^x for g a generator of a cyclic group G.

The scheme uses two signing rounds to produce m intermediate signatures for the m users, and a final combination of these signatures creates a single final signature.

This signature is verified with a public key generated by the combination of the public keys of the users.

When this scheme is used to authenticate a blockchain transaction, the only data published on-chain is one public key and one signature, which is indistinguishable from a usual Schnorr signature, therefore the costs are much lower than a multisignature and equal to those generated by a threshold mechanism. Furthermore, the key generation in MuSig2 is simpler than the key generation in threshold schemes. The main drawback of MuSig2, when compared to any threshold signature scheme, is the fact that it requires the m signers to participate (m = n), which makes MuSig2 a rigid solution.

Turning multisignatures into threshold schemes

To make a multisignature more flexible, a possible solution could be the modification of the algorithm to turn it into a threshold scheme. This option requires the definition of a Merkle tree including the keys of all admissible signers. This Merkle tree would allow checking if a group of prospective signers is valid or not by traversing it.

Let n be the number of participants and m the threshold. The number of elements contained in the above Merkle tree is the combinatorial number C(n,m). The space complexity of this tree, O(n^(n-m)), is exponential on the threshold.

Searching, traversing, inserting or deleting an element in a Merkle tree has time complexity O(log(C(n, m)))<O(log(n^m))=O(m · log(n))

The idea of including a Merkle tree with the groups of admissible signers can be used with MuSig2, BLS, or any other multisignature scheme. This feature is included in Taproot under the hood of merkelized abstract syntax trees (MAST), which are a method of using Merkle trees to store the various user-selected conditions that must be fulfilled for the encumbered bitcoins to be spent.

A brief introduction to FROST

The threshold proposal FROST (Komlo and Goldberg) uses a semi-trusted signature aggregator (SA) whose role allows signers to reduce the network overhead. The aggregator is used for coordination and it doesn’t have access to privileged information. The SA role can be played either by a participant in the protocol or by an external 3rd party. The SA is trusted to identify misbehaving participants and also is responsible for publishing the group’s signature at the end of the protocol. In case of a misbehaving SA, the protocol remains secure against adaptive CCA. A malicious SA has the power to perform DDoS attacks, or falsely report malicious participants, but cannot learn the private key or cause improper messages to be signed.

Key generation in FROST is done in 2 rounds and relies on Pedersen’s distributed key generation algorithm, whereas the singing algorithm builds upon additive secret sharing.

Furthermore, signing operations make use of binding techniques to avoid forgery attacks. The signing process consists of two parts: a pre-processing stage and a single round signing phase, but one may combine them to get a single-round signing phase.

Final remarks

The different techniques studied so far have all advantages and disadvantages. Naive multisignatures could be considered inefficient due to the requirement of validating different signatures. Nevertheless, it is the simplest solution and depending on the number of participants, it can be an interesting option.

Multisignatures schemes with aggregation properties, such as MuSig2 or BLS, overcome the efficiency concerns highlighted above, so they can be considered as a plausible solution when the number of participants grows. Nevertheless, and being strict, multisignatures (either naive or non-naive) are still a bit rigid since it is required for all participants involved in an operation to be present.

A more flexible solution is to consider threshold schemes, either implementing a scheme based on distributed key generation such as FROST or the proposal made by Stinson and Strobl (Stinson and Strobl) or combining a Merkle tree containing the admissible signers with any multisignature proposal such as MuSig2 or BLS.

References

1. Boneh, Dan, et al. “Aggregate and Verifiably Encrypted Signatures from Bilinear Maps.” Lecture Notes in Computer Science, vol. 2656, Springer, 2003, pp. 416–432. SpringerLink, https://link.springer.com/chapter/10.1007/3-540-39200-9_26.
2. Komlo, Chelsea, and Ian Goldberg. “FROST: Flexible Round-Optimized Schnorr Threshold Signatures.” Lecture Notes in Computer Science, vol. 12804, Springer, 2021, pp. 34–65. SpringerLink, https://link.springer.com/chapter/10.1007/978-3-030-81652-0_2.
3. Lu, Xiuhua, et al. “A Lattice-Based Unordered Aggregate Signature Scheme Based on the Intersection Method.” IEEE Access, vol. 6, 2018, pp. 33986–33994. IEEE Xplore, https://ieeexplore.ieee.org/document/8386429.
4. Nick, Jonas, et al. “MuSig2: Simple Two-Round Schnorr Multi-signatures.” Lecture Notes in Computer Science, vol. 12825, Springer, 2021, pp. 189–221. SpringerLink, https://link.springer.com/chapter/10.1007/978-3-030-84242-0_8.
5. Stinson, Douglas R., and Reto Strobl. “Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates.” Lecture Notes in Computer Science, vol. 2119, Springer, 2001, pp. 417–434. SpringerLink, https://link.springer.com/chapter/10.1007/3-540-47719-5_33.