Schnorr

Schnorr signatures are a proposed future extension that give a new way to generate signatures r, s on a hash h.

Given a hash value h, hash function f(), private key x, group generator G, and public key P=xG, we can generate a Schnorr signature on h as follows:

Choose a random nonce k. Let R=Gk, and let s = k - f(h . R . P)x. The Schnorr signature is the pair (R, s). Note that R is a public key, so would require 33 bytes to represent (32 bytes + 1 bit indicating "even" vs "odd").

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.