Schnorr Signature

Notice: If you'd like to practice and write code for the Schnorr signatures explained in this post, head over to https://bitcoindevs.xyz/decoding/schnorr-signature. Some of the code here uses classes and methods from Bitcoin Core's functional test framework.

We have two main characters to help us understand how Schnorr signatures work:

Alice (The signer): wants to sign a message using Schnorr and send it to Bob.
Bob (The verifier): wants to verify that the message is truly signed and comes from Alice.

The interaction between Alice and Bob involves two key steps: Signature Generation and Signature Verification.

Signature Generation (Alice)

Step 1: Generate Key Pair (d, P)

Alice generates a private key d, then calculates her public key P by multiplying her private key with the generator point:

Step 2: Generate Nonce and Nonce Commitment (k, R)

The nonce, referred to as k, is a random value that Alice generates during the signature process.
Its purpose is to introduce randomness into each signature.

Why do we need a nonce?
Answer: The nonce ensures that even if Alice signs the same message multiple times, each signature will be unique. This added randomness prevents attackers from analyzing repeated patterns and attempting to reverse-engineer Alice’s private key.

Alice generates the nonce k and computes the Nonce Commitment:

Warning: Reusing a nonce (k) when creating Schnorr signatures is extremely dangerous!

Note: In the Taproot context, BIP340 requires that the y-coordinate of the point R (computed from k) is even.

BIP340 defines a new way of encoding elliptic curve points. To make the encoding of a point as compact as possible, only the x-coordinate of the point is used (i.e., 32 bytes).

For a given x-coordinate on the secp256k1 curve, there are two possible curve points:

$\mathbf{y^2 = x^3 + 7}$ (Two y-coordinate values for a given x-coordinate)

For x, both (x, y) and (x, -y) are valid curve points.

One of the y-coordinates is even, and the other is odd. BIP340 constrains private key points k such that the y-value of R is even.

If the equation is valid, Bob can be confident that the signature was indeed created by Alice.

All the information needed for verification is already known to Bob:

s: Sent by Alice as part of the signature.
G: A constant that is well-known within the Bitcoin protocol.
h: Bob computes h = H(R || P || m). Since he has R, P, and m, he can calculate h.
P: This is Alice's public key, which Bob knows in advance.

Once Bob has confirmed that the equation holds, he can be fully assured that the message is authentic, has not been tampered with, and truly originated from Alice.