Verify Schnorr

[LSantos06]

[1] https://en.bitcoin.it/wiki/Schnorr

To check the validity of a signature (R, s) against a public key P, do the following:

Note that sG = (k- f(h . R . P))G = kG - f(h . R . P)xG = R - f(h . R . P)P. So we simply compare sG + f(h . R . P)P to R to check the signature.

An advantage of this method is that, if parties cooperate, we can generate a single signature that validates two or more separate transactions.

Choose h1, h2, x1, x2, G, P1=Gx1, P2=Gx2. Each party chooses a nonce yielding k1 and k2, and publicly shares R1=Gk1, R2=Gk2.

Let R = R1+R2. Each signer generates an s, s1 = k1 - f(h . R . P)x1, s2 = k2 - f(h . R . P)x2. The signature (R, s) where s = s1 + s2 proves both transactions are signed.

Note that sG = (s1 + s2)G = s1G + s2G = (k1 - f(h . R . P)x1)G + (k2 - f(h . R . P)x2)G = k1G - f(h . R . P)x1G + k2G - f(h . R . P)x2G = R1 + R2 - f(h . R . P)(P1 + P2) = R - f(h . R . P)(P1 + P2)

To verify, check that sG +f(h . R . P)(P1+P2) is R.

This can be easily generalized from 2 to N.

[2] https://github.com/bitcoin-core/secp256k1/blob/04c8ef36ad35e846ac27157021a78f79465f2a22/src/modules/schnorr/schnorr_impl.h

Verification:
Inputs: 32-byte message m, public key point Q, signature: (32-byte r, scalar s)

Signature is invalid if s >= order.
Signature is invalid if r >= p.
Compute scalar h = Hash(r || m). Signature is invalid if h == 0 or h >= order.
Decompress x coordinate r into point R, with odd y coordinate. Fail if R is not on the curve.
Signature is valid if R + h * Q + s * G == 0.

[3] https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

Input:

- The public key pk: a 33-byte array
- The message m: a 32-byte array
- A signature sig: a 64-byte array

The signature is valid if and only if the algorithm below does not fail.
- Let P = point(pk); fail if point(pk) fails.
- Let r = int(sig[0:32]); fail if r ≥ p.
- Let s = int(sig[32:64]); fail if s ≥ n.
- Let e = int(hash(bytes(r) || bytes(P) || m)) mod n.
- Let R = sG - eP.
- Fail if infinite(R) or jacobi(y(R)) ≠ 1 or x(R) ≠ r.

[LSantos06]

[1] https://github.com/bitcoin-core/secp256k1/blob/e96901a4b951dfb6336114d223151dd0f5ffb89b/include/secp256k1.h#L307
[2] https://github.com/bitcoin-core/secp256k1/blob/870a977644de7f7d7c47c6928d0dac3381fa8b70/src/eckey_impl.h#L17
[4] https://bitcointalk.org/index.php?topic=1875417.0
[5] https://www.tutorialspoint.com/c_standard_library/c_function_memcmp.htm
[6] https://github.com/bitcoin-core/secp256k1/blob/14196379ec8ec6343b2fbafd67669d3d694d08dd/src/ecmult.h#L23
[7] https://github.com/bitcoin-core/secp256k1/blob/14196379ec8ec6343b2fbafd67669d3d694d08dd/src/ecmult.h#L30