Schnorr

Schnorr, together with ECDSA, were two new signature algorithms introduced in Plutus during Cardano's Valentine upgrade. MuSig2 is a two-round multi-signature scheme will be integrated to Hydra.

Generalised specification

This section presents the generalized signature system ECDSA and MuSig2. In the [parameter] (#parameters-of-instantiation) section, we present the specific parameters used in Cardano and MuSig2 C implementation.

A Schnorr signature consists of the following three algorithms:

• $\text{KeyGen}(1^{\lambda })$ takes as input the security parameter $\lambda$ and returns a key-pair $(x,vk)$. First, it chooses $x\leftarrow Z_q$. Finally, compute $vk\leftarrow x\cdot G$, and return $(x,vk)$.
• $\text{Sign}(x,vk,m)$ takes as input a keypair $(x,vk)$ and a message $m$, and returns a signature $\sigma$. Let $r\leftarrow Z_q$. Compute $R=r\cdot G$, then compute $c\leftarrow \text{H}(R,vk,m)$, and finally compute $s=r+c\cdot x$. The signature is $\sigma \leftarrow (R,s)$.
• $\text{Verify}(m,vk,\sigma )$ takes as input a message $m$, a verification key $vk$ and a signature $\sigma$, and returns $\text{result}\in \{\text{true},\text{false}\}$ depending on whether the signature is valid or not. The algorithm returns $\text{true}$ if $s\cdot G=R+c\cdot vk$

Let $N$ be the number of signers and $V$ be the number of nonces. A two-round multi-signature scheme MuSig2 that outputs an ordinary Schnorr signature includes the following steps:

• $\text{KeyGen}(1^{\lambda })$ takes as input the security parameter $\lambda$ and returns a key-pair $(x,vk)$. First, it chooses $x\leftarrow Z_q$. Finally, compute $vk\leftarrow x\cdot G$, and return $(x,vk)$.

• $\text{BatchComm}(1^{\lambda })$ takes as input the security parameter $\lambda$ and returns $V$ key-pairs $\{(r_1,R_1),\dots ,(r_V,R_V)\}$. First, it chooses the nonces $r_j\leftarrow Z_q$. Finally, computes the commitments $R_j\leftarrow r_j\cdot G$, and returns the list including $V$ tuples of nonces and commitments.

• $\text{AggrPubKey}(\{v{k}_1,\dots ,v{k}_N\},{vk}_s)$ takes the list of public keys and the signer's public key, returns the aggregate public key $X$ and $a_s$. First creates $L=({vk}_1||{vk}_2||\dots ||{vk}_N)$. Computes $a_i=H_{agg}(L||{vk}_i)$ for $i=1\dots N$. Finally, generates the aggregate public key by $X={\Sigma }_{i=1}^N(a_i\cdot {vk}_i)$ and the signer keeps her own $a_s$.

• $\text{AggrComm}(\{R_{11},R_{12},\dots ,R_{1V},\dots ,R_{N1},\dots ,R_{NV}\})$ takes the list of all signers' commitment lists, returns the list of aggregate commitments. $\{R_j={\Sigma }_{i=1}^N(R_{ij}){\}}_{j=\mathrm{1..}V}$.

• $\text{Sign}(x_s,{vk}_s,m,X,(R_1,\dots ,R_V),(r_{s1},\dots ,r_{sV}))$ takes as input the keypair of the signer, a message $m$, aggregate public key, the list of commitments and the list of nonces of the signer. Returns a signature $\sigma$. First, creates $b=H_{non}(X||(R_1,\dots ,R_V)||m)\in Z_q$. Computes $R={\Sigma }_{j=1}^V(R_j^{r^{j-1}})$ and $c=H_{sig}(X||R||m)$. The single signature is calculated as ${\sigma }_s=c{a}_s{x}_s+{\Sigma }_{i=1}^V(r_{sj}{b}^{j-1})$.

• $\text{AggrSig}(\{{\sigma }_1,\dots ,{\sigma }_N\},R)$ takes the list of all signers' single signatures and aggregate commitment, returns the aggregate signature $(R,\sigma )$ where $\sigma ={\Sigma }_{i=1}^N({\sigma }_i)$.

• $\text{Verify}(m,X,\sigma ,R)$ takes as input a message, aggregate verification key, aggregate signature, and aggregate commitment. Computes $c=H_{sig}(X||R||m)$ and accepts the signature if $\sigma \cdot G=R+c\cdot X$.

Parameters of instantiation

The above is the standard definition, and in cardano we instantiate it over curve SECP256k1. Moreover, we follow BIP-0340. The following are the two specifications of the above algorithm required for compatibility. Citing literally BIP-0340:

• We use implicit Y coordinates. We encode an elliptic curve point with 32 bytes, and we implicitly choose the Y coordinate that is even[6].
• We use tagged hashed of SHA256 for the challenge computation. More precisely, in order to compute H(R, vk, m), one computes SHA256(SHA256("BIP0340/challenge")||SHA256("BIP0340/challenge") || R || vk || m).

More precisely, the following is what is the specification used in the plutus built-in functions:

• The verification key must correspond to the (x, y) coordinates of a point on the SECP256k1 curve, where x, y are unsigned integers in big-endian form.
• The verification key must correspond to a result produced by secp256k1_xonly_pubkey_serialize. This implies all of the following:
  • The verification key is 32 bytes long.
  • The bytes of the signature correspond to the x coordinate.
• The input to verify is the message to be checked; this can be of any length, and can contain any bytes in any position.
• The signature must correspond to a point R on the SECP256k1 curve, and an unsigned integer s in big-endian form.
• The signature must follow the BIP-340 standard for encoding. This implies all the following:
  • The signature is 64 bytes long.
  • The first 32 bytes are the bytes of the x coordinate of R, as a big-endian unsigned integer.
  • The last 32 bytes are the bytes of s.

      ┏━━━━━━━━━━━━━━┯━━━━━━━━━━━━━━━┓
      ┃ R <32 bytes> │ s <32 bytes>  ┃
      ┗━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━┛
      <--------- signature ---------->