What does a signature verifier actually check?

Evidence

Each numbered marker in the text points here, and the ↩ links lead back to every place that cites an entry. Quotes are verbatim from the BIP files at commit 3a10b5b, including their wiki markup; links open the exact lines; the quoted text sits under each entry. Labels say what kind of statement each is: a rule, the author’s rationale, history, a test vector, or our own inference.

1. ↩ a b c Rule Verify takes a 32-byte public key, a message of any length (a byte array), and a 64-byte signature.

   BIP 340 L177–179

   Quoted source text (1)

   * The public key ''pk'': a 32-byte array * The message ''m'': a byte array * A signature ''sig'': a 64-byte array

2. ↩ a b c d e f g Rule Verify lifts pk to a point P, checks r < p and s < n, computes the challenge e, computes R = s⋅G − e⋅P, and fails if R is infinite, has odd y, or has an x coordinate different from r; it succeeds only if no step failed.

   BIP 340 L182–190

   Quoted source text (1)

   * Let ''P = lift_x(int(pk))''; fail if that fails. * Let ''r = int(sig[0:32])''; fail if ''r &ge; p''. * Let ''s = int(sig[32:64])''; fail if ''s &ge; n''. * Let ''e = int(hash_{BIP0340/challenge}(bytes(r) || bytes(P) || m)) mod n''. * Let ''R = s⋅G - e⋅P''. * Fail if ''is_infinite(R)''. * Fail if ''not has_even_y(R)''. * Fail if ''x(R) &ne; r''. * Return success iff no failure occurred before reaching this point.

3. ↩ History BIP 340 was assigned in 2020; its preamble records the status Deployed and the type Specification.

   BIP 340 L11 BIP 340 L9 BIP 340 L10

   Quoted source text (3)

   Assigned: 2020-01-19

   Status: Deployed

   Type: Specification

4. ↩ Rule BIP 340 proposes a standard for 64-byte Schnorr signatures over the curve secp256k1. It reuses the curve and hash function Bitcoin already uses for ECDSA.

   BIP 340 L21 BIP 340 L48

   Quoted source text (2)

   This document proposes a standard for 64-byte Schnorr signatures over the elliptic curve ''secp256k1''.

   By reusing the same curve and hash function as Bitcoin uses for ECDSA

5. ↩ a b Rule The BIP's Python reference implementation is naive, non-constant-time and for demonstration only; the vectors are published as a CSV file.

   BIP 340 L289 BIP 340 L292 BIP 340 L288

   Quoted source text (3)

   a naive, highly inefficient, and non-constant time [[bip-0340/reference.py|pure Python 3.7 reference implementation of the signing and verification algorithm]]

   The reference implementation is for demonstration purposes only and not to be used in production environments.

   we provide a [[bip-0340/test-vectors.csv|collection of test vectors in CSV format]]

6. ↩ a b c d Rule The public key pk is the x coordinate of a point P with even y; a signature is (r, s) where r is the x coordinate of a point R with even y, and s⋅G = R + tagged_hash(r || pk || m)⋅P.

   BIP 340 L92

   Quoted source text (1)

   our final scheme ends up using public key ''pk'' which is the X coordinate of a point ''P'' on the curve whose Y coordinate is even and signatures ''(r,s)'' where ''r'' is the X coordinate of a point ''R'' whose Y coordinate is even. The signature satisfies ''s⋅G = R + tagged_hash(r || pk || m)⋅P''.

7. ↩ a b Rule Every valid x coordinate has two possible y coordinates, one even and one odd; BIP 340 implicitly takes the even one for both P and R, so an x-only key is equivalent to a compressed key with the prefix byte 0x02.

   BIP 340 L82 BIP 340 L77 BIP 340 L79

   Quoted source text (3)

   we pick that option for ''P'', and thus our X-only public keys become equivalent to a compressed public key that is the X-only key prefixed by the byte 0x02. For consistency, the same is done for ''R''

   (every valid X coordinate has two possible Y coordinates)

   This means that for a valid X coordinate, one of the corresponding Y coordinates will be even, and the other will be odd.

8. ↩ a b c History BIP 340 accepts messages of arbitrary size; earlier revisions required exactly 32 bytes, and the changelog records the change in 2023-04. Pre-hashing is still recommended for performance with large messages. Implementations may reject messages too large for their environment.

   BIP 340 L221 BIP 340 L225 BIP 340 L299 BIP 340 L234 BIP 340 L222

   Quoted source text (5)

   The signature scheme specified in this BIP accepts byte strings of arbitrary size as input messages.

   Earlier revisions of this BIP required messages to be exactly 32 bytes.

   2023-04: Allow messages of arbitrary size

   We note that pre-hashing is recommended for performance reasons in applications that deal with large messages.

   It is understood that implementations may reject messages which are too large in their environment or application context,

9. ↩ a b c Test vector The published vectors include valid signatures on messages of 0, 1, 17, 32 and 100 bytes; for each, the challenge hash input is 64 tag bytes, 32 bytes of r, 32 bytes of P and the whole message.

   BIP 340 (test-vectors.csv) L17 BIP 340 (test-vectors.csv) L18 BIP 340 (test-vectors.csv) L19 BIP 340 (test-vectors.csv) L20

   Quoted source text (4)

   message of size 0 (added 2022-12)

   message of size 1 (added 2022-12)

   message of size 17 (added 2022-12)

   message of size 100 (added 2022-12)

10. ↩ Author’s rationale BIP 340 uses a fixed 64-byte signature instead of DER encoding (variable size, up to 72 bytes) and 32-byte public keys instead of 33-byte compressed points.

    BIP 340 L43 BIP 340 L44

    Quoted source text (2)

    -encoding for signatures (which are variable size, and up to 72 bytes), we can use a simple fixed 64-byte format.

    public keys in this proposal are encoded as 32 bytes.

11. ↩ Author’s rationale The authors require the verification algorithm to be completely specified at the byte level, so that nobody can make a signature valid to some verifiers but not others; they cite DER parsing problems with ECDSA.

    BIP 340 L46 BIP 340 L46 BIP 340 L46

    Quoted source text (3)

    To be safe for usage in consensus systems, the verification algorithm must be completely specified at the byte level. This guarantees that nobody can construct a signature that is valid to some verifiers but not all.

    the lack of exact specification for the DER parsing of ECDSA signatures has caused problems for Bitcoin

    This is traditionally not a requirement for digital signature schemes

12. ↩ a b Rule lift_x(x) returns the point with that x coordinate and even y, or fails if x is greater than p − 1 or no such point exists.

    BIP 340 L113–114 BIP 340 L114

    Quoted source text (2)

    returns the point ''P'' for which ''x(P) = x''

    and ''has_even_y(P)'', or fails if ''x'' is greater than ''p-1'' or no such point exists.

13. ↩ a b c d Test vector All 19 published vectors (9 valid, 10 invalid) give the published result when run through this site's step-by-step verifier, which uses @noble/curves arithmetic and is cross-checked against noble's own verifier; the eight vectors with secret keys also reproduce their signatures.

    BIP 340 (test-vectors.csv) L1

    Quoted source text (1)

    index,secret key,public key,aux_rand,message,signature,verification result,comment

14. ↩ a b Test vector Checking each valid hero vector's key and signature against another fixture's message fails, in every such pairing, at the even-y or x(R) step, because the message changes e and therefore R.

    BIP 340 L185–186

    Quoted source text (1)

    * Let ''e = int(hash_{BIP0340/challenge}(bytes(r) || bytes(P) || m)) mod n''. * Let ''R = s⋅G - e⋅P''.

15. ↩ a b Test vector The CSV comment says how an invalid vector was made, not necessarily which check rejects it: vector 7 ('negated message') is rejected because the recomputed R has odd y, before any x comparison; vectors 8 and 11 fail at the x(R) comparison.

    BIP 340 (test-vectors.csv) L9 BIP 340 L188 BIP 340 (test-vectors.csv) L10

    Quoted source text (3)

    FALSE,negated message

    * Fail if ''not has_even_y(R)''.

    FALSE,negated s value

16. ↩ a b Rule Points are on the curve y² = x³ + 7 over the integers modulo p; p is the field size and n the curve order, both given as exact constants.

    BIP 340 L100 BIP 340 L98–99

    Quoted source text (2)

    Uppercase variables refer to points on the curve with equation ''y² = x³ + 7'' over the integers modulo ''p''.

    The constant ''p'' refers to the field size, ''0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F''. ** The constant ''n'' refers to the curve order, ''0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141''.

17. ↩ a b Rule hash_name(x) is SHA256(SHA256(tag) || SHA256(tag) || x), where tag is the UTF-8 encoding of name.

    BIP 340 L120

    Quoted source text (1)

    returns the 32-byte hash ''SHA256(SHA256(tag) || SHA256(tag) || x)'', where ''tag'' is the UTF-8 encoding of ''name''.

18. ↩ Author’s rationale Tags keep a hash computed for one purpose from being reinterpreted in another context.

    BIP 340 L86

    Quoted source text (1)

    To make sure hashes used in one context can't be reinterpreted in another one, hash functions can be tweaked with a context-dependent tag name, in such a way that collisions across contexts can be assumed to be infeasible.

19. ↩ Author’s rationale Without the public key in the challenge, a third party could turn a signature for P into one for P + a⋅G for any additive tweak a, which the authors say would make signatures insecure with BIP 32 unhardened derivation and with tweaks such as Taproot's; so the public key is prefixed to the message in the challenge.

    BIP 340 L64 BIP 340 L64 BIP 340 L66

    Quoted source text (3)

    a third party can convert a signature ''(R, s)'' for public key ''P'' into a signature ''(R, s + a⋅hash(R || m))'' for public key ''P + a⋅G'' and the same message ''m'', for any given additive tweak ''a'' to the signing key.

    and other methods that rely on additive tweaks to existing keys such as Taproot.

    which means that the public key is prefixed to the message in the challenge hash input.

20. ↩ Rule BIP 340 gives BIP 341 as an example of pre-hashing to a 32-byte digest; BIP 341's key-path rule verifies a signature over hash_TapSighash(0x00 || SigMsg(...)), a 32-byte tagged hash.

    BIP 340 L227–229 BIP 341 L142

    Quoted source text (2)

    to create a 32-byte digest which can be passed to signing or verification (as for example done in [[bip-0341.mediawiki|BIP341]].)

    return ''Verify(q, hash_TapSighash(0x00 || SigMsg(0x00, 0)), sig)''

21. ↩ Author’s rationale BIP 340 signatures reveal R (as r) rather than e; the authors chose this because it supports batch verification, as no elliptic-curve operations sit inside the hashes.

    BIP 340 L60 BIP 340 L62

    Quoted source text (2)

    This supports batch verification, as there are no elliptic curve operations inside the hashes.

    We choose the ''R''-option, which supports batch verification.

22. ↩ Rule BIP 340 also specifies batch verification: if every signature is valid it succeeds; if any is invalid it succeeds only with negligible probability.

    BIP 340 L215

    Quoted source text (1)

    If all individual signatures are valid (i.e., ''Verify'' would return success for them), ''BatchVerify'' will always return success. If at least one signature is invalid, ''BatchVerify'' will return success with at most a negligible probability.

23. ↩ Author’s rationale The authors argue that implicit y coordinates are not a reduction in security, although they halve the set of valid public keys: breaking an x-only key can be at most a small constant term faster than breaking a full one.

    BIP 340 L84 BIP 340 L84

    Quoted source text (2)

    Despite halving the size of the set of valid public keys, implicit Y coordinates are not a reduction in security.

    This shows that breaking an X-only public key can be at most a small constant term faster than breaking a full one.

24. ↩ Rule Every BIP 340 public key has two corresponding secret keys, sk and n − sk.

    BIP 340 L132

    Quoted source text (1)

    A side effect is that ''PubKey(sk) = PubKey(bytes(n - int(sk))'', so every public key has two corresponding secret keys.

25. ↩ Rule lift_x fails if x ≥ p, computes c = x³ + 7 mod p and y = c^((p+1)/4) mod p, fails if y² ≠ c, and returns the point with the even one of y and p − y.

    BIP 340 L115–119

    Quoted source text (1)

    *** Fail if ''x &ge; p''. *** Let ''c = x³ + 7 mod p''. *** Let ''y = c^(p+1)/4 mod p''. *** Fail if ''c &ne; y² mod p''. *** Return the unique point ''P'' such that ''x(P) = x'' and ''y(P) = y'' if ''y mod 2 = 0'' or ''y(P) = p-y'' otherwise.

26. ↩ Rule BIP 340 says applications should make sure a message signed for one context is never accepted in another, and recommends a tagged pre-hash or a 33-byte context prefix.

    BIP 340 L249 BIP 340 L255

    Quoted source text (2)

    applications should ensure that a signed application message intended for one context is never deemed valid in a different context

    we recommend applications to use exactly one of the following methods to pre-process application messages before passing it to the signature scheme:

27. ↩ Author’s rationale The authors state that the SUF-CMA security of Schnorr signatures implies they are non-malleable, whereas ECDSA signatures are inherently malleable.

    BIP 340 L35

    Quoted source text (1)

    The SUF-CMA security of Schnorr signatures implies that they are non-malleable. On the other hand, ECDSA signatures are inherently malleable

28. ↩ Rule Multiparty signing is left to interactive schemes such as MuSig2 (BIP 327); BIP 340 warns that multisignature schemes are generally insecure with the rand generation of its default signing algorithm or any other deterministic method.

    BIP 340 L268 BIP 340 L170

    Quoted source text (2)

    By means of an interactive scheme such as [https://eprint.iacr.org/2020/1261.pdf MuSig2] ([[bip-0327.mediawiki|BIP327]]), participants can aggregate their public keys into a single public key which they can jointly sign for.

    It is important to note that multisignature signing schemes in general are insecure with the ''rand'' generation from the default signing algorithm above (or any other deterministic method).

29. ↩ Author’s rationale From a verifier's perspective, an n-of-n MuSig2 signature is no different from an ordinary signature.

    BIP 340 L268

    Quoted source text (1)

    This allows ''n''-of-''n'' multisignatures which, from a verifier's perspective, are no different from ordinary signatures

30. ↩ Rule Signing is not unique: other ways of generating the rand value produce different but equally valid signatures; however rand is generated, it must be a fresh uniformly random 32-byte string not even partially predictable to an attacker.

    BIP 340 L165 BIP 340 L165

    Quoted source text (2)

    producing a different but still valid signature (in other words, this is not a ''unique'' signature scheme)

    the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.

31. ↩ Rule For every valid secret key and message, verifying the default signer's signature with the matching public key succeeds.

    BIP 340 L192

    Quoted source text (1)

    For every valid secret key ''sk'' and message ''m'', ''Verify(PubKey(sk),m,Sign(sk,m))'' will succeed.