Add notes for precomputing the pubkey when signing

[ajtowns]

Fixes: #190

[gmaxwell]

extbytes(P) is 32 bytes long, right? it needs to be to allow the precomp. Or padding is required to pad up to a 64 byte boundary.

[sipa]

The negate-at-keygen-time idea looks great on paper, but I'm not sure it's very realistic to expect that's how things will be implemented in practice.

For example, BIP32 internally will inevitably keep working with 33-byte public keys, and output those. Its master fingerprints that are used for lookup, are based on hashes that involve the 33-byte serialization. Those can be shielded off, by transforming the BIP32 output into the spec's format. However it doesn't stop there. Signing implementations need to be able to look up derivation paths for public keys encountered, using infrastructure that likely indexes by 33-byte public keys. PSBT extensions for Taproot will need a way to refer to the (pre-tweaked) public keys so that the signer can find the correct tweaked private key. Unless we expect to effectively replace that infrastructure, those references to public keys will have to be in the existing 33-byte form, even if the signature scheme works with reduced 32-byte ones.

I think negating-at-keygen will either gratuitously break a lot of stuff, or end up being bypassed (by effectively doing all operations in the old style, and then converting at the last second before signing to the spec's format). At that point, we'd be better off specifying that conversion at signing routine itself, so that it can be compared with test vectors.

[jonasnick]

So if I understand correctly, you're saying that there is some map on a hardware wallet from 33 byte public keys to secret keys. And that this PR would prevent filling that map.

As an alternative to not negating the secret key during key gen we could bring back the is_negated flag which is an additional output of KeyGen and define a CompressedPubKey function that takes the keypair and the is_negated flag and outputs a compressed pubkey.

[ajtowns]

I think it makes sense that signers will frequently/usually have a secret key that might generate a non-even public key P, so it makes more sense to treat that as the fundamental type, rather than a sk that's already been negated if necessary.

I think this means Sign_Tweak(sk, topbranch, m) would look like:

Let d' = int(sk)
Fail if d' = 0 or d' >= n
Let P = d*G
Let d = d' if has_even_y(P), otherwise d = n - d'
Let t = int(hash_TapTweak( bytes(P) || topbranch ))
Fail if t >= n
Let skt = bytes( d + t mod n )
Return Sign(skt, m)

which leaves Q to be calculated within Sign which is fine. (EDIT: Well, unless you want to check that it matches the sPK, in which case you calculate Q first, check it, then pass it on)

So I think that means it makes sense to treat secret keys as 32-bytes representing ints in (0,n), and as an optimisation having P=d*G as well so that you can easily get the 32-byte pubkey we care about bytes(P), and whether you need to negate the secret key (has_even_y(P)), because you'll have to work out both things almost any time you use the secret key, but that's fine to leave as a note.

I've added a section for the bip32-style conversion; if we expect that to be the main use, seems worth calling it out more strongly. Didn't add an algorithm though, because they're both trivial.

[sipa]

ACK

[elichai]

I'd prefer if we try to distance 32 byte pubkeys away as much as possible from the current ecdsa keys, because I think this is how people will fail, by using the same keys for both without any regard to the implications. But I understand if you say that changing BIP32 a bit for schnorr is too much and people will inevitably keep using that. (especially when some really persistent users can use the same seckey anyway here).

[sipa]

@jonasnick I think that makes sense as an implementation. I'm not sure we need it immediately - a minimal Schnorr implementation can probably keep using the existing pubkey type + a serialize_xonly mechanism?

[jonasnick]

@sipa Just brought this up because 1) we don't have a sign_tweaked function right now and 2) I was asked to allow signing with precomputed pubkeys, but I wouldn't do that without a keypair type. I'll first try to keep the diff in libsecp PR as small as possible while also removing most of the xonly_pubkey cruft.