The Schnorr Signature equation as simple as possible
History
The Schnorr signature scheme was introduced by Claus-Peter Schnorr, a German mathematician, in 1989 and patented in 1990. Due to the patent, the scheme was not widely adopted in public cryptography. Schnorr held the patent until 2008, the same year Satoshi Nakamoto introduced Bitcoin. The Digital Signature Algorithm (DSA) was published by The National Institute of Standards and Technology (NIST) in 1991. Curiously, DSA algorithm was developed as a workaround to Schnorr’s patent restrictions. While the Schnorr scheme utilizes a straightforward linear equation, DSA involves a more complex equation with division, limiting certain optimizations and applications available in the Schnorr scheme.
Elliptic Curve Math
Without going into deep mathematical details, the Schnorr signature equation for an elliptic curve over an integer field modulo prime (m) involves two types of elements:
Integer values on a field with a prime modulo (denoted here by lowercase Latin letters, such as r or x)Points on the elliptic curve defined over the same prime modulo field (denoted here by uppercase Latin letters, such as P or R). An elliptic curve over an integer field has a special point denoted as the generator point (G). This is a specific point on the curve such that any other point can be derived by multiplying the generator point by an integer.
Several basic operations are defined for elliptic curve points:
Point Addition: A + B = CPoint Multiplication by an integer: k ∙ A = kA = DPoint Negation: -A = E (where A + (-B) = C implies A — B = C)
These operations are similar to standard algebra, with one significant exception: division is not defined in elliptic curve cryptography. The lack of a division operation for the points on an elliptic curve is a fundamental aspect of its security, closely tied to the discrete logarithm problem.
The Schnorr Signature
The following outlines the Bitcoin implementation of the Schnorr signature scheme, which differs slightly from the original.
Let:
x — the secret key (a random integer less m),P = xG — the public key (a point on the elliptic curve),r — an ephemeral secret (another random integer less m),R = rG — the ephemeral public key (a point on the curve).h(message) — a hash function applied to some message, producing an integer. Bitcoin uses double sha256 and some additional arguments transformations (see BIP340)
The Schnorr signature is generated as follows:
s = r + h(R,P,m)⋅x (1)
Here, {R, s} is the signature, and only someone with knowledge of both x and r can compute s.
The signature is valid if the following equation is satisfied:
sG = R + h(R,P,d)⋅P (2)
Equation (2) is derived by multiplying equation (1) by G. In this equation, P is the public key, R is part of the signature, and d is the data being signed.
More Context
The use of the integer field with a prime modulo is central to this type of cryptography. Although the specifics go beyond the scope of this article, it is important to note that the prime modulo is slightly smaller than the formal integer boundary used in computer calculations. For example, the formal integer boundary for Bitcoin’s secp256k1 curve is the maximum 256-bit integer (32 bytes):
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,
and the prime modulo is:
0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F.
At least but not last, it means that the private key, which is greater than m, is invalid.
Each point on an elliptic curve is defined by two coordinates: x and y. The elliptic curve equation allows the y-coordinate to be computed from the x-coordinate, but this produces two possible solutions — one even and one odd. As a result, each private key in elliptic curve cryptography (ECC) corresponds to two potential public keys. In Bitcoin, this is addressed by discarding point with an odd y-coordinate, retaining only the even solution. This approach ensures that public keys have a consistent 256-bit length, matching the 256-bit private keys.
Future articles will discuss several interesting and practical operations that stem from this scheme.
The Bitcoin Schnorr Signature in a Nutshell was originally published in Coinmonks on Medium, where people are continuing the conversation by highlighting and responding to this story.