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

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?

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:

y2 = x3 + 7 (mod p)

where the field size p = 2256 - 232 - 977 or

`p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F` in hex and is prime.

The generator point G (on the curve) that we use is (Gx, Gy) where

Gx=`0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798`

Gy=`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 (Rx , s).

The first 32 bytes is the X coordinate of R.

R = k'⋅G

R is a point (Rx, Ry)

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, Rx (scalar)

pk is the X coordinate of the public key P, Px (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.

• "Negating" means taking the complement with the group order n, because "-v = n-v mod n". There are no actual "negative" numbers in the ring of integers mod n. Commented Oct 8, 2020 at 17:26
• For index=7 it says "negated message". Why does one of the test cases have the complement of the message? Just to show that the signature won't be correct if the complement of the message is used rather than the actual message? Commented Oct 8, 2020 at 17:36
• Indeed. It's just trying to predict things an implementation may do accidentally wrong. Commented Oct 8, 2020 at 17:44