schnorr: implement publicKeyTweakTest()

This method is analogous to secp256k1_xonly_pubkey_tweak_test() in the branch of libsecp256k1 used in the bip-taproot working branch:

https://github.com/sipa/bitcoin/blob/e97f84c8044b4f095e16956266da9c3416dd639d/src/secp256k1/src/secp256k1.c#L839

Unlike publicKeyTweakAdd() this method preserves the Y coordinate of the tweaked key, and negates it based on a provided boolean argument. The tweaked-and-possibly-negated key is then tested for equality against a second public key.

This algorithm is defined in bip-taproot as a witness commitment check during script-path spending:

Let t = hashTapTweak(p || km).

If t ≥ 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141 (order of secp256k1), fail.

Let Q = point(q) if (c[0] & 1) = 1 and -point(q) otherwise. Fail if this point is not on the curve.

If Q ≠ P + int(t)G, fail.

The use of the Y-coordinate in an otherwise X-only bip-schnorr context is explained in a footnote in bip-taproot:

Why is it necessary to reveal a bit to indicate if the point represented by the output public key is negated in a script path spend? The point function (defined in bip-schnorr) always constructs a point with a square Y coordinate, but because Q is constructed by adding the taproot tweak to the internal public key P, it cannot easily be guaranteed that Q in fact has such a Y coordinate. Therefore, before verifying the taproot tweak the original point is restored by negating if necessary. We can not ignore the Y coordinate because it would prevent batch verification. Trying out multiple internal keys until there's such a Q is possible but undesirable and unnecessary since this information about the Y coordinate only consumes an unused bit.

Testing

Official test vectors for bip-taproot have not been published yet, but I have generated a set of valid (and invalid) taproot transactions by modifying the feature_taproot.py test in sipa's taproot working branch.

I have my own in-progress Taproot branch of bcoin, and this new method for bcrypto/schnorr is called in this commit, which tests against the generated Taproot vectors:

https://github.com/pinheadmz/bcoin/commit/b4eb1f5ac3e67f759109d8bb7856c34cbf9f913b

I can explicitly add some of these test vectors to bcrypto if this PR is concept/approach ACK.

bcoin-org / bcrypto

schnorr: implement publicKeyTweakTest() #37

Testing