maaku
commented
5 years ago I took a stab at implementing this using the latest secp256k1 library, and came away with an understanding that this is probably not something we want to implement, as specified. The choice of R.y vs s as the tie-breaking determinant is not a free choice. Requiring los-S has implementation advantages within the libsecp256k1 implementation, and is very efficient to check in the network serialization layer. And while it was conveyed to me that these options are mutually exclusive, that doesn't appear to be the case: the signing code can grind nonce values to find signatures that are both low-S and have a quadratic residue for 'R.y'. This is not unlike recent Bitcoin Core code which grinds nonce values to produce a short r value, reducing the size of the signature by one byte.
In light of this, I am changing the title of this issue and removing it from the rebase-0.10 project. In the future it would be nice to grind nonce values to produce quadratic R.y signatures, but this is now a 'nice to have' and no longer a release blocker.
Note: Original title was "Switch signature tie breaker to be quadratic residue instead of low-S in verification." See this comment for an explanation of the change. The below text no longer applies.
In the rebase to 0.9 we changed the signing code to only produce signatures for which the R.y value is a quadratic residue, as opposed to bitcoin's tie breaking condition of low-S. Should this become mandatory and consensus-enforced, the change would enable batch validation of ECDSA signatures. In 0.10 the "LOW_S" verification condition is added which enforces this. We should change this verification code to enforce R.y quadratic residue instead.