Skip to content

Multi signatures

Jump to bottom
iquerejeta edited this page Apr 29, 2021 · 6 revisions

ℹ️ Original author: Iñigo Querejeta Azurmendi in HackMD. Math rendering not great in Github wikis---visit the HackMD link to view a nicely rendered text.

Multisignatures

In this document we present a list of different multisignature constructions in order to compare them, and further select which construction fits best the protocol requirements. We study different constructions which might be contestants for such functionality, and determine whether there exists implementations. For self-containedness we include the formal definitions and security properties of multisignature schemes in Appendix A and Appendix B respectively.

Diferent constructions

In the Hydra paper, there are a few referenced works. In particular, those cited references are:

  • [BN06] Multi-signatures in the plain public-key model and a general forking lemma.
  • [Bol03] Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme (used in simulations).
  • [BDN18] Compact multi-signatures for smaller blockchains.
  • [MOR01] Accountable-subgroup multisignatures.

However, there has been some recent constructions which are better suited for our needs. We base the analysis in this document in the constructions presented in [BDN18], and in the following constructions:

  • [DGNW19] Pixel: Multi-signatures for Consensus.
  • [MPSW19] Simple Schnorr Multi-Signatures with Applications to Bitcoin (aka MuSig).
  • [NRS20] MuSig2: Simple Two-Round Schnorr Multi-Signatures.
Scheme Key update Sign Verify $\mid\sigma\mid$ $\mid\mathsf{vk}\mid$ $\mid\mathsf{sk}\mid$ Forward security Rounds EdComp Assumptions
[BDN18] (pairing) N/A 1 exp 2 pair 1 1 $O(1)$ no non-interactive no RO and coDH
Pixel 2 exp 4 exp 3 pair + 1 exp 2 1 $O((\log T)^2)$ yes non-interactive no RO and wBDHI
MuSig N/A $1$ exp $2$ exp $1$ $1$ $1$ no $3$ yes RO and DL
MuSig2 N/A $2\cdot v$ exp $2$ exp $2$ $1$ $1$ no $2$ (can be made non-interactive) yes RO and OMDL

My preliminary selection is MuSig2. It is Schnorr compatible, making it easy to transition to. Users can keep using Ed25519 keys, and the verification algorithm stay as is. Moreover, it can be made non-interactive---the first round can be pre-computed before knowing the message. MuSig is also an interesting contestant, as it is also Schnorr compatible. The main difference between the two is in a trade-off between the number of rounds and the protocol complexity. The former requires only two rounds, and can be made non-interactive. This is clearly an interesting property for our use case. However, it requires a higher communication complexity, as commitments to $v$ nonces need to be shared (see below for what $v$ is expected to be). In contrast, MuSig requires to send a single commitment, and an additional hashed value. Another importanrt difference between the two constructions is that MuSig has several implementations, and has generated interest in several important projects (see below). MuSig2, in contrast, is a newer construction and has less adoption.

Finally, in case we are willing to switch to pairing based signatures, Boneh et al.'s construction seems to be the best suited, as we do not require forward secrecy for the multi sig, and therefore Pixel is an overkill. Boneh et al.'s construction is simple to prove, to audit and has minimal overhead.

In general, I have found no implementation over Libsodium, but implementing MuSig or MuSig2 on top of it should not be too much effort. However, if we decide to go for a pairing-based solution, Libsodium is certainly not the library we will use (see this issue).

We now expose details of the constructions in two groups: the Schnorr-compatible and the Schnorr-incompatible constructions. The former are the multi-signature constructions that allow the verification procedure to be as with Schnorr signatures. This extends to Ed25519 signatures---an Ed25519 verifier could verify these multisignatures in the exact same way as it verifies Ed25519 signatures; it does not even need to know it is a multisignature. In contrast, the Schnorr-incompatible constructions have a signature verification different to those of Schnorr. Positive point of the Schnorr-compatible signatures, is that the key material is exactly the same as the Schnorr signature scheme key material. We begin our analysis with Schnorr-compatible schemes, and proceed with Schnorr-incompatible schemes.

Schnorr-compatible schemes

In this section wqe present MuSig and MuSig2. Two schemes that present a construction which is compatible with Schnorr verification procedure.

MuSig

This scheme was independently presented and proven secure by Boneh et al. [BDN18] (in Compact multi-signatures for smaller blockchains) and by Maxwell et al. [MPSW19] (in Simple Schnorr Multi-Signatures with Applications to Bitcoin).

This scheme achieves Schnorr compatibility in exchange of interaction among the signees. Each signer first sends a hash of the commitment of the randomness. Then it waits for all users to send their hashes. Once all are received, it sends the commitments themselves. Waits untill all send it back. Finally, each signer individually signs the message and sends it back to the other signers (this step may be performed directly by the verifier). Any third party can act as a verifier by taking all corresponding signatures and public keys, appending them, and perform a signature verification.

The complexity of this scheme is the following:

  • Signature: 1 exponantiation
  • Verification: 2 exponantiations
  • Size signature: 1 group element
  • Size of verification key: 1 group element
  • Size of signing key: $O(1)$
  • Forward security: no
  • Rounds: 3

Apparently a musig implementation for Bitcoin

Notes: proposed adoption in BIP-0340, and available since soft fork Taproot.

Other important names that have implemented this are

Cryptographic assumption

System is proven secure in the Random Oracle model under Discrete Log problem.

MuSig2

Simple Two-Round Schnorr Multi-Signatures

There are two proofs. One that depends solely in the one-more discrete logarithm (OMDL) assumption in the Random Oracle Model (ROM), and another which is a combination of the ROM and the Algebraic Group Model (AGM).

This scheme is the first two round scheme which is secure in the concurrent setting, where users are allowed to sign several messages concurrently.

This scheme achieves the same as MuSig describe above, but requires 2 rounds by the signees in exchange of some performance. In particular, the participants share $v$ nonces (per message to be signed), and the authors prove that by doing that, they can reduce the number of interactions to two. If we accept the AGM, $v=2$, otherwise it must be greater than 4. The very interesting part of this scheme, is that no interaction is necessary (if we precompute the first round). In particular, the procedure is as follows:

  • All signers generate $v$ random nonces per message to be signed, and commit to them. They then broadcast these commitments to all other signees. This phase can be precomputed before knowing the message.
  • Then, each signer computes the shared public key, and the randomness used in the signing procedure. This randomness is computed out of the nonce commitments shared in the first round, and some additional randomness computed with a hash function. It is very important that the same nonce is not used for different signatures.
  • Finally, all signatures can be appended. This could be by a central party (aggregator), or directly by the chain or verification script.

It is crucial to never reuse the nonces in other signature procedures. They should be safely deleted. Otherwise, if the signer reuses the nonce, an adversary can trivially extract the secret key.

The complexity of this scheme is the following:

  • Signature: $2\cdot v$ exponantiation
  • Verification: 2 exponantiations
  • Size signature: 2 group elements
  • Size of verification key: 1 group element
  • Size of signing key: $O(1)$
  • Forward security: no
  • Rounds: 2

Implementation:

Cryptographic assumption

System is proven secure in the Random Oracle model under the One More Discrete Logarithm (OMDL) problem. In a nutshell: Input: \[A_1=g^{\alpha_1}, A_2 = g^{(\alpha_2)},\ldots, A_l=g^{(\alpha_l)},\] \[\alpha_1, \alpha_2, \alpha_{l-1},\]

for $(\alpha_i)_{i\in[1,l]}\in_R\mathbb{Z}_q$.

Compute: \[\alpha_1, \alpha_2, \alpha_{l-1},\alpha_l.\]

This proof works for $v\geq 4$. However, the authors prove that if we further assume that AGM on top of the above assumptions, the system is proved secure with $v = 2$.

Schnorr-incompatible schemes

In this section we study the schemes presented in [BDN18] and [DGNW19] which are not compatible with Schnorr signatures.

Compact multi-signatures for smaller blockchains (pairing based)

This paper also presents a DL-based solution (not pairing based), which is the same as the one presented in [MPSW19]. In this section we only study the pairing based solution, and describe the DL solution in this section.

The scheme is simple--- no need of interaction between the different signees, at the cost of using pairings. A multi-signature run consists on each of the signees performing a signature locally, with no need of communicating with the other signees, and publishing their corresponding signature. Any third party can act as a verifier by aggregating the distinct signatures, and performing a single verification check. The complexity of this scheme is the following:

  • Signature: 1 exponantiation
  • Verification: 2 pairings
  • Size signature: 1 group element
  • Size of verification key: 1 group element
  • Size of signing key: O(1)
  • Rounds: Non-interactive

This scheme might be of interest in the medium term, as we will need to add support to pairing friendly curves for the ongoing projects of Midnight.

Existing imlementations:

Cryptographic assumption

System is proven secure in the Random Oracle model under the co-Diffie-Hellman (coDH) problem. In a nutshell: Input: \[A_1=g_1^{\alpha}, A_2 = g_1^{\beta},A_3=g_2^{\beta},\] for $(\alpha,\beta)\in_R\mathbb{Z}_q^2$.

Compute: \[y=g_1^{\alpha\cdot\beta}.\]

Pixel

This scheme is similar to the scheme above, where the signing procedure is non-interactive, and the scheme is pairing-based. It has worst performance numbers with the benefit that it is forward secure. This means that the scheme considers a key update after each signature. As far as I understood the usage of multisignatures in the context of Hydra, we do not require forward secrecy. In Cardano, the forward secrecy property is only required for Key Evolving Signatures (KES), which are used by the stake pool owner to sign blocks.

The complexity of this scheme is the following:

  • Key update: 2 exponantiations
  • Signature: 4 exponantiation
  • Verification: 3 pairings + 1 exponantiation
  • Size signature: 2 group elements
  • Size of verification key: 1 group element
  • Size of signing key: $O((\log T)^2)$
  • Forward security: Yes
  • Rounds: Non-interactive

Existing implementations:

Cryptographic assumption

System is proven secure in the Random Oracle Model under the Weak bilinear Diffie-Hellman (wBDHI) inversion problem over type-3 pairings (a variant of the Diffie-Hellman inversion problem over bilinear groups). In a nutshell: Input: \[A_1=g_1^{\alpha}, A_2 = g_1^{(\alpha^2)},\ldots, A_l=g_1^{(\alpha^l)},\] \[B_1=g_2^{\alpha}, B_2 = g_2^{(\alpha^2)},\ldots, B_l=g_2^{(\alpha^l)},\] \[C_1=g_1^\gamma, C_2=g_2^\gamma\] for $\alpha,\gamma\in_R\mathbb{Z}_q$.

Compute: \[e(g_1,g_2)^{(\gamma\cdot\alpha^{l + 1})}.\]

Appendix A

A multisignature scheme is defined as a tuple of algorithms $\textsf{MS} = (\textsf{MS-Setup, MS-KG, MS-AVK, MS-Sign, MS-ASign, MS-Verify)}$ such that $\Pi\leftarrow\textsf{MS-Setup}(1^k)$ generates public parameters---where $k$ is the security parameter. Then, given the public parameters, one can generate a verification-signing key pair calling, $(\mathsf{vk,sk})\leftarrow\textsf{MS-KG}(\Pi)$. Then, the multisig scheme should provide a signing and an aggregate functionality. Mainly

  • $\sigma\leftarrow\textsf{MS-Sign}(\Pi, \mathsf{sk}, m)$, which signs a message $m$ using signing key $\mathsf{sk}$, and
  • $\tilde{\sigma}\leftarrow\textsf{MS-ASig}(\Pi, m, \mathcal{V, S)}$, which given a message $m$, a set of signatures, $\mathcal{S}$, over the message $m$, and the corresponding set of verification keys, $\mathcal{V}$, aggregates all signatures into a single, aggregate signature $\tilde{\sigma}$.

To generate an aggregate verification key, one calls the function $\mathsf{avk}\leftarrow\textsf{MS-AVK}(\Pi, \mathcal{V})$, which given input a set of verification keys, $\mathcal{V}$, returns an aggregate verification key that can be used for verification: $\textsf{MS-Verify}(\Pi, \mathsf{avk}, m, \tilde{\sigma})\in{\textsf{true},\textsf{false}}$. We will make the public parameters input implicit throughout the whole document..

Paraphrasing the above, a multisignature scheme is expected to be a protocol where distinct parties may generate signatures, such that any party with access to the message signed, the signatures, and the verification keys may aggregate them (signatures and verification keys) into a single signature verification.

Appendix B

A secure multisignature scheme needs to satisfy two properties: completeness and unforgeability.

Completeness. For any $n,\Pi\leftarrow\textsf{MS-Setup}(1^k)$ and $(\mathsf{vk}_i, \mathsf{sk}_i)\leftarrow\textsf{MS-KG}(\Pi)$ for $i\in[1,n]$, for any message $m$ if we have $\sigma_i\leftarrow\textsf{MS-Sign}(\Pi, \mathsf{sk}i,m)$, $\tilde{\sigma}\leftarrow\textsf{MS-ASig}(\Pi, m, {\mathsf{vk}i}{i=1}^n, {\sigma_i}{i=1}^n)$, and $\mathsf{avk}\leftarrow\textsf{MS-AVK}(\Pi,{\mathsf{vk}i}{i=1}^n)$, then $\textsf{MS-Verify}(\Pi, \tilde{\sigma}, m,\mathsf{avk})=\textsf{true}$.

Paraphrasing, if the signers follow the protocol, then the verifier must accept.

Unforgeability. This property is defined by a three-stage game:

  1. Setup. The challenger runs $\Pi\leftarrow\textsf{MS-Setup}(1^k)$, generates the challenge key pair $(\mathsf{vk}^, \mathsf{sk}^)\leftarrow\textsf{MS-KG}(\Pi)$ and runs the adversary $\mathcal{A}(\Pi,\mathsf{vk}^*)$.
  2. Signing queries. \mathcal{A} is allowed to make signing queries on any message $m$, i.e., $\mathcal{A}$ has access to the signing oracle $\textsf{MS-Sign}(\Pi, \mathsf{sk}^*, \cdot)$.
  3. Output. Finally, \mathcal{A} outputs a multisignature forgery $\tilde{\sigma}^$, a message $m^$, and a set of verification keys $\mathcal{V}^$. $\mathcal{A}$ wins if $\mathsf{vk}^\in\mathcal{V}^$, $\mathcal{A}$ made no signing queries on $m^$, and $$\textsf{MS-Verify}(\Pi, \textsf{MS-AVK}(\Pi, \mathcal{V}^), m^, \tilde{\sigma}^*)=\textsf{true} $$
Clone this wiki locally