<p>These <code>bip340_test_vectors</code> are used in two places: the unit tests (<a href="https://github.com/sipa/bitcoin/blob/taproot/src/test/key_tests.cpp" rel="nofollow noreferrer">src/test/key_tests.cpp</a>) and the functional tests (<a href="https://github.com/sipa/bitcoin/blob/taproot/test/functional/test_framework/key.py" rel="nofollow noreferrer">test/functional/test_framework/key.py</a>).</p>
<p>The Python code for testing the <code>bip340_test_vectors</code> is <a href="https://github.com/bitcoin/bips/blob/master/bip-0340/test-vectors.py" rel="nofollow noreferrer">here</a>.</p>
<p>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.</p>
<p>The public key <code>DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659</code> is reused 9 times for example but the distinct signatures are generated using different messages, auxiliary randomness etc.</p>
<p>The first five test cases have valid signatures (a verification result of TRUE) although the fourth test case (index = 3) has a comment of <code>test fails if msg is reduced modulo p or n</code> (I'm not sure what this means)</p>
<p>That leaves the remaining test cases that fail the signature verification:<a href="https://i.sstatic.net/KqAAZ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/KqAAZ.png" alt="bip340_test_vectors" /></a>
<strong>The elliptic curve that BIP 340 signatures are defined upon is secp256k1 (the same curve that we use for ECDSA) which is:</strong></p>
<p>y<sup>2</sup> = x<sup>3</sup> + 7 (mod p)</p>
<p><strong>where the field size</strong> p = 2<sup>256</sup> - 2<sup>32</sup> - 977 <strong>or</strong></p>
<p><code>p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F</code> <strong>in hex and is prime.</strong></p>
<p><strong>The generator point G (on the curve) that we use is (G<sub>x</sub>, G<sub>y</sub>) where</strong></p>
<p>G<sub>x</sub>=<code>0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798</code></p>
<p>G<sub>y</sub>=<code>0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8</code></p>
<p><strong>The curve order of secp256k1 is:</strong></p>
<p><code>n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141</code></p>
<p>(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 <a href="https://bitcoin.stackexchange.com/questions/95209/elliptic-curve-point-at-infinity">here</a>. It is not on the curve and is defined by (x,y) + (x,-y) = infinity.)</p>
<p>The public key P (point) associated with a secret (private) key is calculated using:</p>
<p>P = d (mod n).G</p>
<p>where d is the private key (scalar) and G is the generator point (point).</p>
<p><strong>A BIP 340 Schnorr signature is a 64 byte array (R<sub>x</sub> , s).</strong></p>
<p><strong>The first 32 bytes is the X coordinate of R</strong>.</p>
<p><strong>R = k'⋅G</strong></p>
<p>R is a point (R<sub>x</sub>, R<sub>y</sub>)</p>
<p>k' is randomness (mod n) as specified by <a href="https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#default-signing" rel="nofollow noreferrer">BIP 340</a></p>
<p>G is the generator point defined earlier</p>
<p><strong>The second 32 bytes is the s that satisfies:</strong></p>
<p><strong>s⋅G = R + H(r | pk | m)⋅P (mod n)</strong></p>
<p>This can be written as s.G = R + e.P where e = H(r | pk | m)</p>
<p>Or alternatively s = k' + e.d where d is the private key (scalar).</p>
<p>G is the generator point defined earlier (point)</p>
<p>R is calculated earlier (point)</p>
<p>H is the hash function (function)</p>
<p>r is the the X coordinate of R, R<sub>x</sub>  (scalar)</p>
<p>pk is the X coordinate of the public key P, P<sub>x</sub> (scalar)</p>
<p>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>
<p>P is the public key (point)</p>
<p><strong>Index 5</strong> 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.</p>
<p><strong>Index 6</strong> is referring to the <a href="https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#default-signing" rel="nofollow noreferrer">BIP 340</a> design choice to implicitly choose the Y coordinate that is even (each valid X coordinate has two possible Y coordinates, <a href="https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#cite_note-5" rel="nofollow noreferrer">one that is odd and one that is even</a>). If the Y coordinate is odd then it is not following the BIP 340 specification and the signature verification should fail.</p>
<p><strong>Index 7</strong> 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.</p>
<p><code>-m = n-m (mod n)</code></p>
<p>Obviously there are no actual &quot;negative&quot; numbers in the ring of integers (mod n).</p>
<p><strong>Index 8</strong> 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.</p>
<p><strong>Index 9</strong> states <code>R = sG - eP</code> is infinite and that the test fails if <code>has_even_y(inf)</code> is TRUE and <code>x(inf)=0</code>. 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 <code>has_even_y</code> returns TRUE (which it shouldn't) and <code>x(inf)</code> returns 0.</p>
<p><strong>Index 10</strong> states <code>R = sG - eP</code> is infinite.</p>
<p><strong>Index 11</strong> states <code>sig[0:32]</code> 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.</p>
<p><strong>Index 12</strong> 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.</p>
<p><strong>Index 13</strong> 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.</p>
<p><strong>Index 14</strong> 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.</p>
<p>(Jimmy Song's <a href="https://github.com/jimmysong/programmingbitcoin/blob/master/ch03.asciidoc" rel="nofollow noreferrer">Chapter 3</a> 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 <a href="https://diyhpl.us/wiki/transcripts/chaincode-labs/2019-08-16-elichai-turkel-schnorr-signatures/" rel="nofollow noreferrer">presentation</a> at Chaincode Labs or this London BitDevs <a href="https://diyhpl.us/wiki/transcripts/london-bitcoin-devs/2020-06-16-socratic-seminar-bip-schnorr/" rel="nofollow noreferrer">Socratic Seminar</a> on BIP 340)</p>
<p>Thanks to Pieter Wuille and Jonas Nick for suggested edits on the initial post.</p>

CC BY-SA 4.0
2020-10-08T17:26:31.393Z
"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.
Pieter Wuille
CC BY-SA 4.0
2020-10-08T17:36:02.717Z
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?
Michael Folkson
CC BY-SA 4.0
2020-10-08T17:44:29.323Z
Indeed. It's just trying to predict things an implementation may do accidentally wrong.
Pieter Wuille
CC BY-SA 4.0
2020-10-06T19:24:53.543Z
2020-10-09T22:12:48.300Z
2020-10-09T22:12:48.300Z
Michael Folkson
<p>I'm digging <a href="https://bitcoin.stackexchange.com/questions/99306/i-would-like-to-dig-into-the-open-taproot-pr-to-understand-it-test-it-and-possi">further</a> into the open Taproot PR. I found these <a href="https://github.com/sipa/bitcoin/blob/taproot/test/functional/test_framework/bip340_test_vectors.csv" rel="nofollow noreferrer">BIP340 test vectors</a>.</p>
<p>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?</p>

<bitcoin-core-development><schnorr-signatures><taproot><bitcoincore-review><functional-test>
I'm digging further into the open Taproot PR. Can you explain the BIP340 test vectors?
Michael Folkson
# I'm digging further into the open Taproot PR. Can you explain the BIP340 test vectors?

(Asked by: username_0 on 2020-10-06)

I'm digging [further](https://bitcoin.stackexchange.com/questions/99306/i-would-like-to-dig-into-the-open-taproot-pr-to-understand-it-test-it-and-possi) into the open Taproot PR. I found these [BIP340 test vectors](https://github.com/sipa/bitcoin/blob/taproot/test/functional/test_framework/bip340_test_vectors.csv).

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?

**Tags:** bitcoin-core-development, schnorr-signatures, taproot, bitcoincore-review, functional-test


---

## 1 answers

### Answer by username_0 on 2020-10-06. Score: 2 | Accepted answer

These `bip340_test_vectors` are used in two places: the unit tests ([src/test/key\_tests.cpp](https://github.com/sipa/bitcoin/blob/taproot/src/test/key_tests.cpp)) and the functional tests ([test/functional/test\_framework/key.py](https://github.com/sipa/bitcoin/blob/taproot/test/functional/test_framework/key.py)).

The Python code for testing the `bip340_test_vectors` is [here](https://github.com/bitcoin/bips/blob/master/bip-0340/test-vectors.py).

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:[![bip340_test_vectors](https://i.sstatic.net/KqAAZ.png)](https://i.sstatic.net/KqAAZ.png)
**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](https://bitcoin.stackexchange.com/questions/95209/elliptic-curve-point-at-infinity). 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](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#default-signing)

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](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#default-signing) 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](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#cite_note-5)). 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](https://github.com/jimmysong/programmingbitcoin/blob/master/ch03.asciidoc) 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](https://diyhpl.us/wiki/transcripts/chaincode-labs/2019-08-16-elichai-turkel-schnorr-signatures/) at Chaincode Labs or this London BitDevs [Socratic Seminar](https://diyhpl.us/wiki/transcripts/london-bitcoin-devs/2020-06-16-socratic-seminar-bip-schnorr/) on BIP 340)

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

> **Comments:**
> **username_1**: "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.  
> **username_0**: 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?  
> **username_1**: Indeed. It's just trying to predict things an implementation may do accidentally wrong.  

---

