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. One key advantage is that when multiple keys are used to sign the same message with Schnorr, the resulting signatures can be combined into a single signature. This can be used to significantly reduce the size of multisig payments and other multisig related transactions, for example lightning channel transactions.
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.