Schnorr
Bitcoin currently uses the ECDSA algorithm to generate cryptographic signatures for a given message and secp256k1 keypair. Schnorr is an alternative algorithm with several advantages. The main reason that Bitcoin did not originally use Schnorr signatures is that Schnorr was not standardized, and was not available in common crypto libraries.
Technical details
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)x)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.