###### tags: `hydra`

# 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](#Appendix-A) and [Appendix B](#Appendix-B) respectively.

## Diferent constructions
In the Hydra paper, there are a few referenced works. In particular, those cited references are:
* [[BN06]](https://cseweb.ucsd.edu/~mihir/papers/multisignatures-ccs.pdf) Multi-signatures in the plain public-key model and a general forking lemma.
* [[Bol03]](https://www.cc.gatech.edu/~aboldyre/papers/bold.pdf) Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme (used in simulations).
* [[BDN18]](https://eprint.iacr.org/2018/483.pdf) Compact multi-signatures for smaller blockchains.
* [[MOR01]](https://www.cs.bu.edu/~reyzin/multisig.html) 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]](https://eprint.iacr.org/2018/483.pdf), and in the following constructions:
* [[DGNW19]](https://eprint.iacr.org/2019/514.pdf) Pixel: Multi-signatures for Consensus.
* [[MPSW19]](https://eprint.iacr.org/2018/068.pdf) Simple Schnorr Multi-Signatures with Applications to Bitcoin (aka MuSig).
* [[NRS20]](https://eprint.iacr.org/2020/1261.pdf) 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]](https://eprint.iacr.org/2018/483.pdf) (pairing)| N/A | 1 exp | 2 pair | 1 | 1 | $O(1)$ | no | non-interactive | no | RO and coDH |
|[Pixel](https://eprint.iacr.org/2019/514.pdf)| 2 exp | 4 exp | 3 pair + 1 exp | 2 | 1 | $O((\log T)^2)$ | yes | non-interactive | no | RO and wBDHI |
|[Mu](https://eprint.iacr.org/2018/483.pdf)[Sig](https://eprint.iacr.org/2018/068.pdf)| N/A | $1$ exp | $2$ exp | $1$ | $1$ | $1$ | no | $3$ | yes| RO and DL |
|[MuSig2](https://eprint.iacr.org/2020/1261.pdf)| 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. 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](#MuSig2) 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](#MuSig)). MuSig2, in contrast, is a newer construction and has less adoption.

Finally, in case we are willing to switch to [pairing based signatures](https://en.wikipedia.org/wiki/BLS_digital_signature), 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 currently does not support pairing friendly curves.

We now expose details of the constructions in two groups: the [`Schnorr-compatible`](#Schnorr-compatible-schemes) and the [`Schnorr-incompatible`](#Schnorr-incompatible-schemes) constructions. The former are the multi-signature constructions that allow the verification procedure to be as with Schnorr signatures. 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]](https://eprint.iacr.org/2018/483.pdf) (in _Compact multi-signatures for smaller blockchains_) and by Maxwell _et al._ [[MPSW19]](https://eprint.iacr.org/2018/068.pdf) (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
* [here](https://github.com/gcash/bchd/blob/master/bchec/musig.go)

**Notes**: proposed adoption in [BIP-0340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki), and available since soft fork [Taproot](https://bitcoinops.org/en/topics/taproot/).

Other important names that have implemented this are
* [Web 3 Foundation](https://github.com/w3f/schnorrkel), implemented in Rust, over Ristretto group in Curve25519 (using curve25519-dalek). And the announcement [here](https://github.com/w3f/schnorrkel/blob/master/annoucement.md).
* [Elements Project](https://github.com/ElementsProject/secp256k1-zkp/blob/f6e4f869e03e1b4e0628e173745764038a2715f7/src/modules/thresholdsig/design.md), implemented in C, over curve secp256k1. This by far seems the most mature implementation. Also, interesting read for MuSigs: [**MuSig: A new multisignature standard**](https://blockstream.com/2019/02/18/en-musig-a-new-multisignature-standard/).
* [ZenGoX](https://github.com/ZenGo-X/multi-party-eddsa/wiki/Aggregated-9-Signatures), implemented in Rust, with an API over several curves.

#### 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](#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:
* In the [multy-party Schnorr](https://github.com/ZenGo-X/multi-party-schnorr) repo, by ZenGo-X ().

#### 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]](https://eprint.iacr.org/2018/483.pdf) and [[DGNW19]](https://eprint.iacr.org/2019/514.pdf) which are not compatible with Schnorr signatures.
### Compact multi-signatures for smaller blockchains (pairing based) <a name="blsbased"></a>

This paper also presents a DL-based solution (not pairing based), which is the same as the one presented in [[MPSW19]](https://eprint.iacr.org/2018/068.pdf). In this section we only study the pairing based solution, and describe the DL solution in [this section](#MuSig).

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:
* In the [Signature schemes](https://github.com/lovesh/signature-schemes), by lovesh.
* In the [multy-party Schnorr](https://github.com/ZenGo-X/multi-party-schnorr) repo, by ZenGo-X ().

#### 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:
* [Pixel](https://github.com/lovesh/pixel-signature), by lovesh.
* [Pixel](https://github.com/algorand/pixel), by algorand team.

#### 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} $$