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.
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
Its purpose is to introduce randomness into each signature.
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.
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.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
Alice sends both the message
(R, s)
.Alice sends both the message
m
and the signature (R, s)
to Bob.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.
- G: A constant that is well-known within the Bitcoin protocol.
- h: Bob computes
h = H(R || P || m)
. Since he hasR
,P
, andm
, he can calculateh
. - 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.
Try it out: Want to practice coding Schnorr signatures yourself? Visit bitcoindevs.xyz/decoding/schnorr-signature for a hands-on experience!