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.

Now, let’s follow Alice as she creates a Schnorr signature.

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:

To see this in action, run the following code to generate Alice's key pair and display the private and public keys.

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 introduces 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

k is a scalar, R is a point on the elliptic curve.

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

BitcoinOptech provides a more detailed explanation of this requirement:

Let’s generate a random nonce k and calculate its associated point R.

This example shows how to check if R's y-coordinate (and its negative, -y) is even or odd, which is crucial for Taproot’s nonce requirements.

Step 3: Challenge Computation (h)

Alice computes the challenge hash h using the following formula:

The challenge hash is created by concatenating R, P, and the message m.

Step 4: Challenge Response (s)

Using the challenge hash, Alice calculates the challenge response s:

Step 5: Create the Signature

The final signature for the message is the pair (R, s).
Alice sends both the message m and the signature (R, s) to Bob.

Hands-On: Complete the Code to Generate a Schnorr Signature

Below is a code snippet that generates a Schnorr signature, but some key parts are missing. Follow the instructions in the code to complete it so that it runs successfully and displays a "Success!" message at the end.

Note: You'll see a method called tagged_hash in the code. If you're unfamiliar with tagged hashes and their purpose, refer to our previous topic on Tagged Hashes for a quick refresher.

Nonce Generation for Schnorr Signatures

In the previous example, we used a random nonce for Schnorr signatures, which depends on a secure random generator. However, if this generator is compromised, it can expose the private key.

Why is Nonce Generation Important?

If the randomness in nonce generation is compromised, it can reveal the private key used in signing. To avoid this risk, BIP340 suggests a deterministic method for generating nonces.

Steps to Generate a Nonce

1. Compute t: XOR the bytes of the private key (d) with a tagged hash of auxiliary random data (a).

2. Generate rand: Hash the tagged data with t, the public key (P), and the message (m).

3. Calculate k (Nonce): Set k = int(rand) mod n, where n is the order of the curve. This ensures a unique, unpredictable nonce for each signature.

Coding Exercise: Nonce Generation

To better understand how nonce generation works, try creating a Schnorr signature using BIP340’s nonce scheme. Follow the instructions in the code snippet below to implement the nonce generation steps yourself.

Verification Process (Bob)

Bob wants to ensure that the message hasn’t been compromised during transmission and that it’s genuinely signed by Alice.

To verify this, Bob checks if the following verification equation holds:

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, so Bob has this value.
• 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.