Include reference implementation for X + Parity Keys

[JeremyRubin]

According to BIP-340, XOnly keys have 32 bytes and signatures have 64 bytes.

If X + Parity is used, signatures would be 65 bytes and Keys 33 bytes. Really, they just require one bit, but the minimum encoding unit is 8 bits, so there is 7 bits waste.

It would be useful to include a reference implementation here of X + Parity Schnorr signatures. A future upgrade to Bitcoin might choose this encoding. I'm not super familiar with this codebase, but perhaps if it is conceptually ACKd to include this in secp256k1, myself or others might do the work (v.s. if it's guaranteed to be rejected).

[jonasnick]

The scope of the library is defined in CONTRIBUTING.md. In particular, we recommend a specification and providing arguments for relevance in the Bitcoin space. I think a vague potential future upgrade to Bitcoin does not give sufficient evidence for relevance alone and would in practice put an eventual PR near the bottom of the priority list. If a future upgrade was concrete and with community support, of course this changes considerations.

I generally agree that a BIP 340-variant with 32-byte public keys + parity bit can be useful in some situations to avoid the need for parity bit tracking in more complex protocols such as MuSig2. But as long as Bitcoin consensus uses BIP 340, I don't see a particularly high demand for such a scheme right now.

[JeremyRubin]

A number of developers are proposing and working on upgrades which would include a parity bit, it was a large topic of conversation at the recent Austin Forum. I didn't attend but @reardencode did. out of that, @rustyrussell is working on a "script restoration" which features 33 byte taproot outs with bits reserved (it seems) for parity info.

I also proposed using those bits for parity and some other use cases, independently.

The reason to include the functions here is that lack of exposed functions for this makes it substantially more difficult to develop and test prototypes for upgrades including x + parity keys. In other words, secp256k1 is the horse, and the BIPs in progress the cart. Right now the cart is before the horse, and adding symbols for x+parity would rectify that situation.

[real-or-random]

A number of developers are proposing and working on upgrades which would include a parity bit,

Can you point to any specifications or documents?

[JeremyRubin]

I don't think there's a detailed spec out there yet, but here's some references. The point of adding some functionality in libsecp would be to aid in the people prototyping process.

https://twitter.com/reardencode/status/1788994390817648749

https://twitter.com/rusty_twit/status/1787198698851877011

https://github.com/rustyrussell/bitcoin/tree/guilt/op-cat

https://github.com/rustyrussell/bips/tree/guilt/varops

https://twitter.com/JeremyRubin/status/1782220444185116883

https://twitter.com/JeremyRubin/status/1782544875264549074