I'm digging further into the open Taproot PR. Can you explain the BIP340 test vectors?

Question

I'm digging further into the open Taproot PR. I found these BIP340 test vectors.

They have secret keys, public keys, aux_rand (auxiliary randomness), message, signature and whether the signature verifies or not. Can you explain why the signatures that fail are failing?

Answer 1

These bip340_test_vectors are used in two places: the unit tests (src/test/key_tests.cpp) and the functional tests (test/functional/test_framework/key.py).

The Python code for testing the bip340_test_vectors is here.

There are 15 test cases in all but only 4 distinct secret keys, 7 distinct public keys (3 of them don't have secret keys) and 15 distinct signatures.

The public key DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659 is reused 9 times for example but the distinct signatures are generated using different messages, auxiliary randomness etc.

The first five test cases have valid signatures (a verification result of TRUE) although the fourth test case (index = 3) has a comment of test fails if msg is reduced modulo p or n (I'm not sure what this means)

That leaves the remaining test cases that fail the signature verification: The elliptic curve that BIP 340 signatures are defined upon is secp256k1 (the same curve that we use for ECDSA) which is:

y² = x³ + 7 (mod p)

where the field size p = 2²⁵⁶ - 2³² - 977 or

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F in hex and is prime.

The generator point G (on the curve) that we use is (G_x, G_y) where

G_x=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

G_y=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

The curve order of secp256k1 is:

n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

(The curve order n is such that nG = point at infinity. Every n times we cycle back to the point at infinity. The point at infinity is defined here. It is not on the curve and is defined by (x,y) + (x,-y) = infinity.)

The public key P (point) associated with a secret (private) key is calculated using:

P = d (mod n).G

where d is the private key (scalar) and G is the generator point (point).

A BIP 340 Schnorr signature is a 64 byte array (R_x , s).

The first 32 bytes is the X coordinate of R.

R = k'⋅G

R is a point (R_x, R_y)

k' is randomness (mod n) as specified by BIP 340

G is the generator point defined earlier

The second 32 bytes is the s that satisfies:

s⋅G = R + H(r | pk | m)⋅P (mod n)

This can be written as s.G = R + e.P where e = H(r | pk | m)

Or alternatively s = k' + e.d where d is the private key (scalar).

G is the generator point defined earlier (point)

R is calculated earlier (point)

H is the hash function (function)

r is the the X coordinate of R, R_x (scalar)

pk is the X coordinate of the public key P, P_x (scalar)

m is the message (scalar). The message in Bitcoin's case is the part of the Bitcoin transaction that needs to be signed according to the SIGHASH flag.

P is the public key (point)

Index 5 has a public key that is not on the secp256k1 curve that Bitcoin uses. The public key is calculated by multiplying the private key (scalar) by the generator point and so it must be on the elliptic curve. If it isn't it is not possible to generate a valid signature. Indeed the secret key is not provided for this public key as there is no secret key that can multiply with the generator point to get the public key.

Index 6 is referring to the BIP 340 design choice to implicitly choose the Y coordinate that is even (each valid X coordinate has two possible Y coordinates, one that is odd and one that is even). If the Y coordinate is odd then it is not following the BIP 340 specification and the signature verification should fail.

Index 7 uses a negated message to verify a signature of an original message. Negated means taking the complement with the group order n. The signature won't be valid if you verify it using the negated message rather than the actual message used in the signature.

-m = n-m (mod n)

Obviously there are no actual "negative" numbers in the ring of integers (mod n).

Index 8 has a negated s value. See Index 7 for the definition of negated. If you validate with a negated s rather than the initial s the signature validation will fail.

Index 9 states R = sG - eP is infinite and that the test fails if has_even_y(inf) is TRUE and x(inf)=0. The point at infinity is not on the curve, has no coordinates at all but implementations need a representation of it. If an implementation uses (0,0) as the point at infinity then this test will fail if has_even_y returns TRUE (which it shouldn't) and x(inf) returns 0.

Index 10 states R = sG - eP is infinite.

Index 11 states sig[0:32] is not an X coordinate on the curve. If the first 32 bytes of the BIP 340 Schnorr signature is not an X coordinate on the elliptic curve then this is not a valid signature.

Index 12 also refers to first 32 bytes of the signature. But this time the 32 bytes are equal to the field size of the curve p. This is not possible under mod p (all values must be between 0 and p-1) so no valid signature is possible here.

Index 13 refers to the second 32 bytes of the 64 byte signature. s can't be equal to the curve order n because it is defined mod n which means it can only take a value between 0 and n-1.

Index 14 has a public key with a X coordinate that exceeds the field size (p = 2^256 - 2^32 - 977). This is not possible under mod p (all values must be between 0 and p-1) so no valid signature is possible here.

(Jimmy Song's Chapter 3 on Elliptic Curve Cryptography of his book Programming Bitcoin is helpful for explaining the secp256k1 curve. It was published before BIP 340 was finalized and so only covers ECDSA signatures, not Schnorr signatures. For an introduction to Schnorr signatures see Elichai Turkel's presentation at Chaincode Labs or this London BitDevs Socratic Seminar on BIP 340)

Thanks to Pieter Wuille and Jonas Nick for suggested edits on the initial post.