bitcoin-dev

Schnorr signatures BIP

Schnorr signatures BIP

Original Postby Russell O'Connor

Posted on: August 4, 2018 12:22 UTC

The proposed change is to the verification equation of a quadratic residue, which currently reads "Let R = sG - eP" and would be changed to "Let R = sG + eP".

The proposed change would result in faster verification as it avoids negating a point or a coefficient. In the current method, reconstructing R from r requires verifying "sG - eP = R", which effectively verifies "0 = sG - eP - R" or "0 = R - sG + eP", requiring at least one point or coefficient to be negated due to opposite signs between sG and eP. However, under the revised verification scheme, verification would instead require "0 = sG + eP + (-R)", which does not require negating R. (-R) can be constructed directly from r by finding a y coordinate that is not a quadratic residue, which is the same amount of work required to construct R from r. This change would remove one negation operation from the cost of doing verification in either verification procedure.