bip-0327: add more test vectors #2351

Add Sign test vectors for a secnonce with k2' = 0 and for a secnonce
generated for a different public key. No previous test vector detected
an implementation that checks only k1', or one that omits the public
key check added in 1.0.0-rc.2.

Add test vectors for a single signer, a 4-byte extra_in, and plain and
x-only tweaks in DeterministicSign. They detect implementations that
reject a single signer, encode the length of extra_in as 32 whenever
extra_in is present, or treat every tweak in DeterministicSign as
x-only.

State in the BIP that all inputs in the test vectors have the lengths
that the algorithms require.

Add a README to the vectors directory that states when to add a test
vector: only if it detects a plausible implementation mistake that the
other test vectors do not detect. Name that mistake in the comment of
each added test vector.

Co-authored-by: Ferdinando Ametrano <ferdinando@ametrano.net>

Add Sign test vectors with k2' = n and k2' = n + 1. Together they
detect implementations that check the secret nonce values only for
zero, that check k2' <= n instead of k2' < n, or that reduce k2' mod n
before checking it for zero. No single value detects the last two:
among values of at least n, checking k2' <= n accepts only n, while
reducing first rejects only n. For k2' = n, the optional correctness
check at the end of Sign also fails, because k2'*G is infinity, so this
vector detects the k2' <= n mistake only in implementations that omit
that check.

Add NonceGen and DeterministicSign test vectors with a 256-byte
message. They detect implementations that encode only the low byte of
len(m); the longest message in the previous test vectors has 38 bytes.
DeterministicSign needs its own vector because it encodes len(m)
separately.

A public key and its negation have the same X coordinate, and their
compressed encodings differ only in the first byte. Add a Sign test
vector with a secnonce generated for the negation of the signer's public
key, and a KeyAgg test vector with a public key and its negation. They
detect implementations that compare public keys only by their X
coordinates, in the public key check of Sign, in GetSecondKey, or in
KeyAggCoeffInternal. Distinct public keys in the previous test vectors
also have distinct X coordinates.

The public key check in Sign ensures that the secret key provided to
Sign is determined when NonceGen is invoked. Comparing only X
coordinates determines the secret key only up to negation.

In the previous NonceGen test vectors, every rand_ consists of the byte
0F repeated 32 times, every present sk of the byte 02 repeated 32 times,
and every pk has an even Y coordinate. Add a test vector whose rand_ and
sk are not a repeated byte and whose pk has an odd Y coordinate. It
detects implementations that reverse the byte order of rand_ or sk, that
replace the first byte of pk with 02, or that use only the first byte of
rand_.

With the last mistake, two NonceGen invocations with the same other
arguments return the same secnonce with probability 1/256, although the
BIP requires that Sign is never executed twice with the same secnonce.

The PartialSigVerify test vector with the partial signature n fails the
verification equation even without the range check. So it does not
detect implementations that omit the range check or that check s > n
instead of s >= n. Change the pubnonces of the test vector such that the
partial signature 0 is valid, keeping the aggregate nonce. Since
n*G = 0*G, the partial signature n then satisfies the verification
equation, and only the range check rejects it. The previous version of
the test vector detects no mistake that the new version does not detect,
so it is replaced rather than kept.

gen_vectors_helper.py computes the new pubnonces.

ApplyTweak multiplies gacc by g, which is -1 if an x-only tweak negates
the aggregate public key. In every previous tweak sequence, the product
of all values of g equals the last one. Add a test vector with two
x-only tweaks, of which only the first negates the aggregate public key.
It detects implementations that set gacc to g instead of multiplying it
by g.

PartialSigAgg adds e*g*tacc, where g is -1 if the aggregate public key Q
has an odd Y coordinate. In the previous PartialSigAgg test vectors,
tacc is 0 whenever Q has an odd Y coordinate. Add a test vector with a
plain tweak and an odd Q, generated by gen_vectors_helper.py. It detects
implementations that omit g.

Add a changelog entry for the changes to the test vectors.