###### tags: `hydra`
# MuSig2 verification over a non prime order group

As discussed in the [document](https://hackmd.io/@_XlWbpTTRNaI4BeB7d8qig/BkCL6LFPO) presenting MuSig2's library API, the incompatibility between Ed25519 verification and MuSig2 verification is that the group over which [MuSig2 is proved secure](https://eprint.iacr.org/2020/1261.pdf) is not the same as the group over which [Ed25519 signatures](https://ed25519.cr.yp.to/ed25519-20110926.pdf) are computed. Both schemes are Schnorr variants with quasi-equal verification procedures, and therefore leave the possibility of using an Ed25519 verifier to verify MuSig2 signatures. To this end, similar transforms used in Ed25519 are required to make MuSig2 non-prime order compatible.

We begin discussing Ristretto255, a technique for co-factor ellimination, which defines a prime order group over Curve25519 with non-malleable encodings, and explain how this may solve our problem. Then we proceed defining the original MuSig2 and Ed25519 protocols. Finally, we give details of what would be the required changes to make MuSig2's protocol compatible with Ed25519 verification equation following two strategies: a hybrid between Ristretto and normal verification, and one without requiring the use of the Ristretto technique. To keep consistency in the group operations notation, we use additive notation (contrarily to what is used in MuSig2's paper), and use $[a]A$ to define the scalar multiplication between scalar $a$ and elliptic curve point $A$.

### Ristretto255
The [Ristretto prime order group](https://ristretto.group/ristretto.html) allows constructing prime order groups over elliptic curves that define cofactor-8 groups, with non-malleable encodings. It extends [Mike Hamburg's Decaf](https://www.shiftleft.org/papers/decaf/decaf.pdf) approach to cofactor elimination to support curves such as (the twisted edwards form of) Curve25519. In particular, this allows an existing Curve25519 library to implement a prime-order group with only a thin abstraction layer, and without changing the cryptographic assumptions. Fortunatelly, [libsodium offers such a functionality](https://libsodium.gitbook.io/doc/advanced/point-arithmetic/ristretto).

A point in the ristretto prime order group is represented by an Edwards point. Different Edwards points can represent the same ristretto point. Group operations are as in the original curve, meaning that no overhead is added to operations (which is ideal for fast curves, such as edwards curves). The equality function is changed, so that the different points that are in the same equivalence class are considered equal. Similarly, the encoding (from an edwards curve) is made such that points in the same equivalence class receive the same bitwise-representation. The decoding only accepts valid encodings.

In a nutshell, the Edwards point that represents a Ristretto point has _a_ canonical encoding, but not _the_ canonical encoding that we expect: i.e. it is not necessarily part of the prime order subgroup (even if it is considered equivalent to its torsion-free component). The canonical representation is achieved by means of isogenies between different curves, and canonical representations of cosets of points in these curves. Therefore, if we generate a MuSig2 signature using the ristretto prime order group, and then directly translate those points back to their Edwards form to perform the verification, it does not always validate (as validation compares a point received by the signer, and a point computed by the verifier). To ensure that a verifier always accepts a valid signature, we need to get the torsion-free component of the Ristretto point. We can achieve that by multiplying by the torsion-safe scalar of the group defined over Curve25519 (or rather its edwards form). Paraphrasing, we want to map the canonical encoding that Ristretto uses, to its torsion-free element.

The torsion-safe scalar, $k$, cancels out the torsion point of any group element. In particular, let $l$ be the prime order, then $k$ needs to have the following properties: $k = 1 \mod l$ and $k = 0 \mod 8$. Given that $l = 5 \mod 8$ we get that $k = 3l + 1$. Therefore, if we multiply any point by $k$, we are guaranteed to get the result in the prime order subgroup, which is the canonical representation that will allow us to map the signature generated using the Ristretto technique, to the standard verification of Ed25519 signatures. We define the required change to exploit this technique in the section [below](#MuSig-with-Ristretto).

### MuSig2
We assume the number of nonces to be two, i.e. $v=2$. Similarly, let $m$ be the number of signers.

* [$\texttt{Setup}$:] On input a security parameter $\lambda$, the setup algorithm $\texttt{Setup}$ runs $(\mathbb{G}, p, G)\leftarrow\texttt{GrGen}(1^{\lambda})$, to get a group $\mathbb{G}$ of prime order $p$ with generator $G$. Then, it selects three hash functions $H_a, H_n, H_s: \{0,1\}^*\rightarrow\mathbb{Z}_p$.
* [$\texttt{KeyGen}$:] Each signer generates a random private key $x\leftarrow_{R}\mathbb{Z}_p$, and computes the corresponding public key $X = [x]G$.
* [$\texttt{Sign}_1$:] Let $X_i$ and $x_i$ be the public and private keys of signer $i$. For $j\in\{1, ..., v\}$, signer $i$ performs the following:
* Chooses at random a nonce, $r_{i,j}\leftarrow_R\mathbb{Z}_p$
* Commits to it, $R_{i,j} = [r_{i,j}]G$
* Broadcast the commitment to all other signers
* [$\texttt{Sign}_2$:] Let $M$ be the message to sign. Let $L=\{X_i\}_{i=1}^{m}$ be the multiset of all public keys involved in the signing process. For $i\in\{1,...,m\}$, the signer computes $a_i=H_a(L || X_i)$, and then the aggregate key $\tilde{X}=\sum_{i=1}^m [a_i]X_i$. Upon reception of all nonces $R_{i,j}$ for $i\in\{1,...,m\}$ and $j\in\{1,...,v\}$, the signer $i$ computes the following steps:
* $R_j=\sum_{i=1}^m R_{i,j}$ for each $j\in\{1,...,v\}$
* Computes $b_1=1$ and $(b_2,...,b_v)=H_n(j, \tilde{X},(R_1,...,R_v), M)$ for $j\in\{1,...,v\}$
* $R = \sum_{j=1}^v [b_j]R_j$
* $c = H_s(\tilde{X}, R, M)$
* $s_i = c\cdot a_i\cdot x_i + \sum_{j=1}^v r_{1,j}b_j \mod p$
These values are sent to the aggregator
* [$\texttt{AggrSig}$:] Finally, an aggregator (which can be any party) computes $s=\sum_{i=1}^n s_i \mod p$, and returns the signature $(R, s)$.
* [$\texttt{Verification}$:] Given a public key $\tilde{X}$ and a signature $(R, s)$, the verifier accepts if $[s]G = R + [H_s(\tilde{X}, R, M)]\tilde{X}$.

### Ed25519
EdDSA generates the private key in a particular manner to ensure that the public key is not a low order point, and to achieve constant time operations (key bitwise manipulation).

Unfortunately, Ed25519 was defined in a way quite open to interpretation of what is to be considered a good signature, resulting in several implementations having different verification procedures. We stick to the verification equation of `libsodium`, which is what our nodes (will eventually) run.

* [$\texttt{Setup}$:] The setup algorithm $\texttt{Setup}$ runs $(E, p = 8\cdot l, G)\leftarrow\texttt{GrGen}(1^{256})$, to get the group defined over (a birationally equivalent curve wrt $\text{Curve25519}$) $E$, which has order $p = 8\cdot l$ with $l$ being a large prime, and generator $G$. Furthermore, the setup returns SHA-512 (which we refer to as $H(\cdot)$).
* [$\texttt{KeyGen}$:] A signer generates a random private key $k\leftarrow_{R}\{0, 1\}^{256}$. Then it computes its hash $H(k) = (h_0,\ldots,h_{511})$, and uses the bits to determine an integer. Precisely
\\[x\leftarrow 2^{b−2} + \sum_{3≤i≤b−3} 2^ih_i,\\]
and computes the corresponding public key $X = [x]G$.
* [$\texttt{Sign}$] The signer sets $r = H(h_0,\ldots,h_{511}, M)$. Then it defines $R = [r]G$. Finally, it computes $s = (r + H(R, X, M)x) \mod l$ and sends the pair $(R, s)$.
* [$\texttt{Verification}$:] Given a public key $X$ and a signature $(R, s)$, the verifier checks that $R, X\in E$, none have small order, $X$ is canonical and that $s\in\{0,\ldots,l-1\}$, and accepts if $[s]G = R + [H_s(X, R, M)]X$.

### Differences
First thing that catches our eyes is the verification equation. It is exactly the same for both algorithms, except for some additional checks that Ed25519 verifier performs to handle the non-prime order group (note also the difference of checking $s\in\{0,\ldots,l-1\}$ rather than $\mod p$). This would make us think that an Ed25519 verifier could verify MuSig2 signatures without even knowing that it is verifying a multisignature. However, there are subtle differences that we need to handle with care, to ensure that the properties of MuSig2 are kept.

* The groups over which both signatures are defined do not have the same properties. In particular, MuSig2 is defined over a prime order group, while Ed25519 is defined over a non-prime order group. Non-prime order groups contain additional subgroups, whose elements do not lie in the intended prime order group. Operations with such elements can leak private information or give unexpected results.
* Ed25519 makes some bitwise maniputalion to the secret key (it does not take it uniformly at random from $\mathbb{Z}_l$). This is motivated by security goals: (i) it ensures that the highest bit is set, ensuring that bad implementations (that have variable time depending on the highest bit) are constant time; (ii) it ensures that the secret key is a multiple of 8 (the cofactor), and therefore any element multiplied by the secret key falls in the prime order subgroup (it eliminates the torsion components).
* Ed25519 uses deterministic nonce generation, while MuSig2 relies on random nonce generation. Moreover, in MuSig2 they point out that a deterministic nonce generation would make the scheme insecure. This, however, makes no difference to the security analysis, as hash functions (used for deterministic nonce generation) are treated as a random oracle.

We have a clear path to follow of where we need to handle the cofactor in order for the signature to keep its properties---we need to follow the steps of Ed25519. However, we need to understand how that affects the security proof.

#### MuSig with Ristretto
As introduced above, the ristretto technique allows us to work over a prime order group using Curve25519. However, if the signature is sent _as is_ to the Ed25519 verifier, it will not necessarily validate. The points that represent a Ristretto point are not necessarily in the prime order subgroup, which is a sufficient condition for the verification to fail. In order to ensure that the Ed25519 verifier always validates the signature, we need to map the aggregated public key, $\tilde{X}$, and the announcement of the signature, $R$, to their torsion-free representation. In particular, let $(R, s)$ be a valid signature for public key $\tilde{X}$ using the ristretto prime order group. Before sending the signature to the Ed25519 verifier, the following step is required:
* [$\texttt{TorsionFree}$:] The signer (or aggregator) sets $R' = [k]R$ and $\tilde{X}' = [k]\tilde{X}$, where $k$ is the torsion-safe scalar. Then, it returns $(\tilde{X}', (R', s))$.

Using this output, the Ed25519 verifier will validate the signature.

#### Musig2 over Curve25519
The other technique is to run MuSig2 over Curve25519, and perform the necessary checks throughout the protocol to ensure that none of the points exchanged are not in the prime order subgroup. We present the protocol of MuSig2 instantiated in a group of non-prime order, precisely in a group of order $8 * l$ for $l$ a large prime. We write in bold the changes made to the original protocol.
* [$\texttt{Setup}$:] On input a security parameter $\lambda$, the setup algorithm $\texttt{Setup}$ runs $(\mathbf{E}, \mathbf{p = 8\cdot l}, G)\leftarrow\texttt{GrGen}(1^{256})$, **to get the group defined over (a birationally equivalent curve wrt $\text{Curve25519}$) $E$, which has order $p = 8\cdot l$ with $l$ being a large prime, and generator $G$**. Then, it selects three hash functions $H_a, H_n, H_s: \{0,1\}^*\rightarrow\mathbb{Z}_{\mathbf{l}}$, **and SHA-512 (which we refer to as $H(\cdot)$). The first three hash functions can be constructed from SHA-512 using domain separation.**
* [$\texttt{KeyGen}$:] **A signer generates a random private key $k\leftarrow_{R}\{0, 1\}^{256}$. Then it computes its hash $H(k) = (h_0,\ldots,h_{511})$, and uses the bits to determine an integer. Precisely
\\[x\leftarrow 2^{b−2} + \sum_{3≤i≤b−3} 2^ih_i,\\]**
and computes the corresponding public key $X = [x]G$.

* [$\texttt{Sign}_1$:] Let $X_i$ and $x_i$ be the public and private keys of signer $i$. For $j\in\{1, ..., v\}$, signer $i$ performs the following:
* Chooses at random a nonce, $r_{i,j}\leftarrow_R\mathbb{Z}_{\mathbf{l}}$
* Commits to it, $R_{i,j} = [r_{i,j}]G$
* Broadcast the commitment to all other signers
* [$\texttt{Sign}_2$:] Let $M$ be the message to sign. Let $L=\{X_i\}_{i=1}^{m}$ be the multiset of all public keys involved in the signing process. For $i\in\{1,...,m\}$, the signer **checks that $X_i$ is in $E$, does not have low order and is in canonical representation**, computes $a_i=H_a(L || X_i)$, and then the aggregate key $\tilde{X}=\sum_{i=1}^m [a_i]X_i$. Upon reception of all nonces $R_{i,j}$ for $i\in\{1,...,m\}$ and $j\in\{1,...,v\}$, the signer $i$ computes the following steps:
* **Check that $R_{i,j}$ is in $E$ and does not have low order**
* $R_j=\sum_{i=1}^m R_{i,j}$ for each $j\in\{1,...,v\}$
* Computes $b_1=1$ and $(b_2,...,b_v)=H_n(j, \tilde{X},(R_1,...,R_v), M)$ for $j\in\{1,...,v\}$
* $R = \sum_{j=1}^v [b_j]R_j$
* $c = H_s(\tilde{X}, R, M)$
* $s_i = c\cdot a_i\cdot x_i + \sum_{j=1}^v r_{1,j}b_j \mod \mathbf{l}$
These values are sent to the aggregator
* [$\texttt{AggrSig}$:] Finally, an aggregator (which can be any party) computes $s=\sum_{i=1}^n s_i \mod \mathbf{l}$, and returns the signature $(R, s)$.
* [$\texttt{Verification}$:] Given a public key $\tilde{X}$ and a signature $(R, s)$, the verifier **checks that $R, \tilde{X}\in E$, none have small order, $\tilde{X}$ is canonical, and that $s\in\{0,\ldots,l-1\}$, and** accepts if $[s]G = R + [H_s(\tilde{X}, R, M)]\tilde{X}$.

The question now is whether we can still apply the security proof to the modified scheme. We set to analyse how these changes affect the security proof of MuSig2.

### Conclusion
Both techniques seem valid for our goal---we can generate a MuSig2 signature and verify it using the standard Ed25519 verification equation. However, we need to understand if these changes affect the security proof. Using the ristretto group seems a more elegant solution, as most of the algorithm remains unchanged, and we only require a few scalar multiplications before sending the signature to the verifier. Nonetheless, a formal verification and analysis that indeed such a technique is possible is required.

## Can it be safely instantiated with ATMs?
We would require to share the different $a_i$s of the non-signers with the verifier, rather than have the latter compute it. Does this keep safety? Let's understand what the exponents are used for.

These exponents are used to prevent rogue-key attacks, meaning that the value that will be used in the homomorphic addition of the keys, is not the public key of each participant, but the public key to the power of an exponent that is only known once all the set of keys is determined.