Schnorr signatures

tl;dr: Signs $m$ as $\sigma = (R, s)$, where $s = r - H(R, m) \cdot \sk$, $R = g^r$ and $r\randget \Zp$. Verifies this signature against $\pk = g^\sk$ as $R \equals g^s \cdot \pk^{H(R, m)}$.

A bit of history

The Schnorr signature scheme was originally introduced by Claus-Peter Schnorr, a German mathematician, in a CRYPTO’89 paper1. In the paper, Schnorr first proposes an identification scheme which he then turns into a signature scheme using the well-known Fiat-Shamir transform2. The original paper describes the signature scheme assuming a specific choice of Abelian group: a prime-order $q$ subgroup of $\Zps$, where $p$ is a prime. Later work naturally observed that any prime-order group suffices (e.g., elliptic curve groups)3.

Schnorr patented his scheme in 1990. This was likely the biggest reason why Bitcoin, and the rest of the cryptocurrency space, (unfortunately?) chose ECDSA as its signature scheme, instead of Schnorr, which is simpler, more efficient and easier to thresholdize into a $t$-out-of-$n$ scheme. In 2010, once the patent expired, Schnorr became more popular.

One advantage of ECDSA over Schnorr I can think of is its public key recovery feature, which Bitcoin leverages in P2PKH mode4 to keep TXN signatures smaller. In fact, Bitcoin leveraged P2PKH since the beginning it seems5.

The Schnorr signature scheme

Preliminaries:

• We assume a group $\Gr$ of prime order $p$ and a finite field $\Zp$
• Let $g$ denote the generator of $\Gr$
• We assume a collision-resistant hash function $H : \Gr \times \{0,1\}^* \rightarrow \Zp$.

$\mathsf{Schnorr}$.$\mathsf{KeyGen}(1^\lambda) \rightarrow (\sk, \pk)$:

• $\sk\randget\Zp$
• $\pk \gets g^\sk$

$\mathsf{Schnorr}$.$\mathsf{Sign}(m, \sk) \rightarrow \sigma$:

• $r\randget\Zp$
• $R \gets g^r$
• $s \gets (r - H(R, m) \cdot \sk) \bmod p$
• $\sigma\gets (R, s)$

Note: It is also possible to use a $+$ instead of a $-$ when computing $s$. The verification equation can be adjusted to account for it (e.g., see EdDSA below).

$\mathsf{Schnorr}$.$\mathsf{Verify}(m, \pk, \sigma) \rightarrow \{0,1\}$:

• $(R, s) \gets \sigma$
• assert $R \equals g^s \cdot \pk^{H(R, m)}$

Correctness

The scheme is correct if signatures created via $\mathsf{Schnorr.Sign}$ verify correctly via $\mathsf{Schnorr.Verify}$.

Let’s see why this holds: \begin{align} R &\equals g^s \cdot \pk^{H(R, m)}\\
g^r &\equals g^{r-H(R, m)\cdot \sk} \cdot (g^\sk)^{H(R, m)}\\
g^r &\equals g^{r-H(R, m)\cdot \sk} \cdot g^{H(R, m) \cdot \sk}\\
g^r &\equals g^r \end{align}

Batch verification

Schnorr signature verification is significantly faster when done in batch. Specifically, given $(\sigma_i, m_i, \pk_i)_{i\in [n]}$, one can ensure all signatures verify (i.e., that $\mathsf{Schnorr.Verify}(m_i, \pk_i, \sigma_i) = 1,\forall i\in [n]$) by taking a random linear combination of the verification equations and combining them into one.

Assume $\sigma_i = (R_i, s_i)$. Then, pick $z_i \randget \{0,1\}^\lambda,\forall i\in[n]$ and check: \begin{align} \prod_{i \in [n]} R_i^{-z_i} g^{s_i \cdot z_i} \pk_i^{H(R_i, m_i)\cdot z_i} \equals 1 \end{align} This will be much faster when using multi-exponentiation algorithms such as Bos-Coster or BDL+126.

Even better, when the public keys are the same (i.e., $\pk_i = \pk, \forall i\in[n]$), then the size of the multi-exponentiation can be reduced: \begin{align} \left(\prod_{i \in [n]} R_i^{-z_i} g^{s_i \cdot z_i}\right) \pk^{\sum_{i\in[n]} H(R_i, m_i)\cdot z_i} \equals 1 \end{align}

Alternative $(e, s)$ formulation

In this formulation, the signature includes the hash $e = H(R, m)$ instead of $R$. This may have advantages if the hash can be made smaller. The original Schnorr paper1 claims $\lambda$-bit hashes (as opposed to $2\lambda$) are sufficient for $\lambda$-bit security, but not sure if that has changed.

$\mathsf{Schnorr}’$.$\mathsf{Sign}(m, \sk) \rightarrow \sigma$:

• $r\randget\Zp$
• $R \gets g^r$
• $e \gets H(R, m)$
• $s \gets (r + e \cdot \sk)\bmod p$
• $\sigma\gets (e, s)$

$\mathsf{Schnorr}’$.$\mathsf{Verify}(m, \pk, \sigma) \rightarrow \{0,1\}$:

• $(e, s) \gets \sigma$
• assert $e \equals H(g^s \cdot \pk^e, m)$

EdDSA and Ed25519 formulation

EdDSA

EdDSA is a Schnorr-based signature scheme designed for groups $\Gr$ of non-prime order $p = h\cdot q$, where $q\approx 2^{2\lambda}$ and $h=8$ (but can be generalized to $h=2^c$, for any $c$7). EdDSA has a few modifications for security. In particular, (1) the nonce $r$ is generated pseudo-randomly from the SK and the message $m$ and (2) the signing additionally hashes over the public key.

EdDSA uses multiple hash functions:

• $H_1 : \{0,1\}^{2\lambda} \rightarrow \{0,1\}^{4\lambda}$,
• $H_2 : \{0,1\}^{2\lambda} \times \{0,1\}^* \rightarrow \{0,1\}^{4\lambda}$
• $H_3 : \Gr \times \Gr \times \{0,1\}^* \rightarrow \{0,1\}^{4\lambda}$

These are typically instantiated from a single hash function $H : \{0,1\}^* \rightarrow \{0,1\}^{4\lambda}$ via proper domain separation.

$\mathsf{EdDSA}$.$\mathsf{KeyGen}(1^\lambda) \rightarrow (\sk, \pk)$:

• $b \gets 2\lambda$
• $\vec{k} \randget \{0,1\}^{b}$
• $\vec{h} \gets H_1(\vec{k}) \in \{0,1\}^{2b}$
• $a \gets 2^{b-2} + \sum_{3 \le i \le b - 3} 2^i h_i$
• $\sk \gets (a, (h_b, \ldots h_{2b-1}))$
• $\pk \gets g^{a}$

What is up with this weird generation of the secret key $a$? tl;dr is that it allows for “the same [Ed25519] secrets [to] also be used safely with X25519 if you also need to do a key-exchange.”8

$\mathsf{EdDSA}$.$\mathsf{Sign}(m, \sk) \rightarrow \sigma$:

• Parse $(a, (h_b, \ldots h_{2b-1})) \gets \sk$
• $r \gets H_2(h_b,\ldots, h_{2b-1}, m) \in \{0,1\}^{2b}$
• $R \gets g^r$
• $s \gets (r + H_3(R, \pk, m) \cdot a)\bmod q$
• $\sigma\gets (R, s)$

As per [BDL+12]6 the inclusion of $\pk$ in $H_3$ is “an inexpensive way to alleviate concerns that several public keys could be attacked simultaneously”. Another yet-to-be explored advantage is that it prevents an adversary who is given a target signature $\sigma$ from finding a message $m$ and a public key $\pk$ for which it verifies. For example, this is possible in plain Schnorr where, given any $\sigma$, the adversary can pick any message $m$ it wants and compute the PK as $\pk = (g^s / R)^{1/H(R, m)}$.

$\mathsf{EdDSA}$.$\mathsf{Verify}(m, \pk, \sigma) \rightarrow \{0,1\}$:

• $(R, s) \gets \sigma$
• assert $g^s \equals R \cdot \pk^{H(R, \pk, m)}$

An alternative version of the verification function multiplies by the cofactor $h$ in the exponent: $g^{h\cdot s} \equals R^h \cdot \pk^{h\cdot H(R, \pk, m)}$. The subtleties of this are discussed by Henry de Valence[^devalance].

Ed25519

Ed25519 is just EdDSA over the Edwards 25519 curve with $\lambda=128$ and an appropriate choice of hash function. This is stated in the EdDSA paper6:

Our recommended curve for EdDSA is a twisted Edwards curve birationally equivalent to the curve Curve25519 […] We use the name Ed25519 for EdDSA with this particular choice of curve.

Typically, the most common flavor of Ed25519 is Ed25519-SHA-512 which uses SHA2-512 as its hash function.

(Mis)implementing Schnorr

Surprisingly, implementing Schnorr signatures can be quite tricky. Previous work explores the many subtleties in depth9$^,$10$^,$7. Instead of rehashing their explanations, I will summarize three main pitfalls to watch out for. (Unfortunately, Ed25519 only handles the first one.)

Pitfall #1: Securely generating the nonce $r$

This is the most important pitfall to avoid in Schnorr signatures:

Pitfall: If an implementation produces two signatures that reuse the same $r$, then the secret key can be extracted. Therefore, it is crucial for security that $r$ be sampled randomly.

Recommendation: As we discuss later, picking $r$ pseudorandomly based on the message and the secret key obviates this problem.

We showcase the attack below. Suppose an implementation produces two signatures $\sigma_1 = (R, s_1)$ and $\sigma_2 = (R, s_2)$ on messages $m_1 \ne m_2$, respectively, that reuse the same $r$. Specifically: \begin{align} R &= g^r\\
s_1 &= r + H(R, m_1) \cdot \sk\\
s_2 &= r + H(R, m_2) \cdot \sk \end{align} Then, an attacker can extract $\sk$ as follows: \begin{align} \frac{s_1 - s_2}{H(R, m_1) - H(R, m_2)} &= \frac{H(R, m_1)\sk - H(R, m_2)\sk}{H(R, m_1) - H(R, m_2)}\\
&= \frac{\sk(H(R, m_1) - H(R, m_2))}{H(R, m_1) - H(R, m_2)}\\
&= \sk \end{align}

For this attack to work, the denominator above must be not zero, which happens with overwhelming probability when $m_1\ne m_2$ and $H$ is collision-resistant. This attack works even when using the alternative $(e, s)$ formulation of Schnorr singatures, described later.

Pitfall #2: Non-canonical serialization

Pitfall: The description above and, in fact, most academic descriptions, do not distinguish between a group (or field) element and its serialization into bytes. Yet developers who implement Schnorr must come up with a serialization format for these elements before they can, say, be sent over the network or fed into a hash function. Ambiguities in this format can create signature malleability issues.

For example, consider the code that deserializes the $s\in \Zp$ component of the Schnor signature. Typically, naively-written code will not check that the positive integer encoded in the bytes is $< p$. As a result, such code will accept two different byte representations of the same $s$. This could allow for one valid Schnorr signature $\sigma$ on $m$ to be mauled by an attacker into another different-but-still-valid signature $\sigma’$ on $m$.

Such malleability attacks might not seem like a big deal: after all, there was already a valid $\sigma$ on $m$, what do we care if someone can create a new $\sigma’$ that’s also valid? Fair enough, but many applications often (incorrectly) assume that a message only has one, unique, valid signature. In the past, such attacks may have been used to drain money from (poorly-implemented) cryptocurrency exchanges11.

Recommendation: Developers need to ensure that each group (or field) element has a single / unique / canonical serialized representation into bytes and that deserialization only accepts this canonical representation. Recently, Ristretto25512 is a popular elliptic curve group that offers canonical (de)serialization.

Pitfall #3: Using non-prime order groups

Pitfall: The description above and, in fact, most academic descriptions, make a crucial assumption: that $\Gr$ is a prime-order group.

Yet, Ed25519, which is the most popular implementation of Schnorr, does not use prime-order groups. Instead, it uses composite order groups where the order is $h\cdot q$ where $q$ is prime and $h = 8$ is the so-called cofactor. This actually creates subtle issues when batch-verifying Schnorr signatures, for example, where signatures that verify individually will not verify as part of a batch9.

Recommendation: If you have the freedom in your application, you should avoid implementing Schnorr over non-prime order groups (i.e., avoid Ed25519) and adopt Schnorr variants like Schnorrkel13 which use prime-order groups.

Conclusion

By now, you should be pretty well-versed in Schnorr signatures and a few of their properties: nonce reuse attacks, batch verification, alternative forms, etc. There is so much more to say about them. Perhaps this article will grow over time.

1. Efficient Identification and Signatures for Smart Cards, by Schnorr, C. P., in Advances in Cryptology — CRYPTO’ 89 Proceedings, 1990  2

2. How To Prove Yourself: Practical Solutions to Identification and Signature Problems, by Fiat, Amos and Shamir, Adi, in Advances in Cryptology — CRYPTO’ 86, 1987

3. Not sure what the earliest work is that uses Schnorr signatures over, say, elliptic curves.

4. High-speed high-security signatures, by Bernstein, Daniel J. and Duif, Niels and Lange, Tanja and Schwabe, Peter and Yang, Bo-Yin, in Journal of Cryptographic Engineering, 2012, [URL]  2 3

5. The Provable Security of Ed25519: Theory and Practice, by Jacqueline Brendel and Cas Cremers and Dennis Jackson and Mang Zhao, in Cryptology ePrint Archive, Report 2020/823, 2020, [URL]  2

6. An Explainer On Ed25519 Clamping, Jake Craige

7. It’s 255:19AM. Do you know what your validation criteria are?, Henry de Valence  2

8. Taming the many EdDSAs, by Konstantinos Chalkias and François Garillot and Valeria Nikolaenko, in Cryptology ePrint Archive, Report 2020/1244, 2020, [URL]

9. Bitcoin Transaction Malleability and MtGox, by Decker, Christian and Wattenhofer, Roger, in Computer Security - ESORICS 2014, 2014