Schnorr signatures: everything you wanted to know, but were afraid to ask!

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 paper¹. In the paper, Schnorr first proposes an identification scheme which he then turns into a signature scheme using the well-known Fiat-Shamir transform². 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)³.

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 mode⁴ to keep TXN signatures smaller. In fact, Bitcoin leveraged P2PKH since the beginning it seems⁵.

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, rather than individually via $\mathsf{Schnorr.Verify}$.

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.

More formally, the batch verification algorithm looks like this:

$\mathsf{Schnorr.BatchVerify}((m_i, \pk_i, \sigma_i)_{i\in[n]}) \rightarrow \{0,1\}$:

• $z_i \randget \{0,1\}^\lambda,\forall i\in[n]$
• $(R_i, s_i) \gets \sigma_i,\forall i\in[n]$
• assert $\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$

The speed-up comes from using multi-exponentiation algorithms such as Bos-Coster or BDL+12⁶ in the last check.

Note: 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, which further speeds up the verification: \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}

Implementing batch verification so that it returns the same results as individual verification may be trickier than it appears over non-prime order groups like Edwards 25519⁷$^,$⁸.

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 paper¹ claims $\lambda$-bit hashes (as opposed to $2\lambda$) are sufficient for $\lambda$-bit security, but not sure if that has changed.

On the other hand, a disadvantage is that this formulation does not allow for more efficient batch verification.

$\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$⁹). 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 and (3) EdDSA has been designed so that the SK can be safely reused in Diffie-Hellman (DH) key exchange protocols like X25519.

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.”¹⁰

$\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]⁶ 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)}$. (In the future, I hope to expand on why such a security notion may be useful.)

$\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⁷.

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 paper⁶:

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 depth⁷$^,$⁸$^,$⁹. 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 element and its serialization into bytes. (Same applies to field elements.) Yet developers who implement Schnorr must understand the caveats of (de)serializing these elements to (1) avoid issues such as signature malleability and (2) maintain compatibility with other libraries.

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 exchanges¹¹.

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. Ristretto255¹² is a recently-proposed 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 batch⁷.

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 Schnorrkel¹³ 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.

Questions for the reader

1. What other aspects of Schnorr signatures should this blog post address?
2. The original Schnorr paper¹ claims $\lambda$-bit hashes (as opposed to $2\lambda$) are sufficient for $\lambda$-bit security. I believe this analysis remains true?
3. What is a good academic reference for the cleanest EUF-CMA security proof for (single-signer) Schnorr?
4. What is the the earliest work that defines Schnorr signatures over elliptic curves?

---