Parity of the group commitment for BIP-340

[pdyraga]

In BIP-340 there are two places in the signing protocol where we need to invert a scalar if the elliptic curve point for that scalar has an even Y coordinate. The first place is when d is calculated, and the second place is where k is calculated:

Let d' = int(sk)
Fail if d' = 0 or d' ≥ n
Let P = d'⋅G
Let d = d' if has_even_y(P), otherwise let d = n - d' .

Let k' = int(rand) mod n[13].
Fail if k' = 0.
Let R = k'⋅G.
Let k = k' if has_even_y(R), otherwise let k = n - k' .

https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#default-signing

For d calculation, we will have to take it into account for the key generation protocol. In unit tests, we simply do the inversion for the secret key, as proposed in #11.

For k the situation is more complicated because it is calculated according to the FROST protocol. In unit tests, we retry signing as in #11. In the production code, we most probably have to retry in ROAST with the same signer set, as proposed in @eth-r's prototype. This situation shouldn't be considered an error. I believe we have the following two options:

• do not execute round 2 if the group commitment has unexpected parity,
• let the entire protocol finish and retry for a failed signature but without identifying malicious parties.

[eth-r]

Not executing round 2 in the case of bad parity breaks the normal operation of ROAST in annoying ways. With large groups, it is exceedingly likely that the coordinator would be able to cope by trying different samples from the commits it has received, but this is completely different logic from what ROAST normally uses and would require special casing.

In fact, with a 51/100 group, if the coordinator receives just 52 commits there is a less than a 1/4,000,000,000,000,000 chance that the coordinator could not select a group capable of producing a valid signature. Effectively, this is the equivalent of 52 repeated signing attempts.

Thus it may be worth it to write the logic for processing such special cases, although it does make the code less elegant in general. ROAST protocols that do not rely on this sort of parity would just skip the special case logic altogether.