Schnorr: Difference between revisions
Add summary |
m Fix a broken link to BIP340. |
||
| (3 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
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. | 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== | ==Technical details== | ||
Schnorr signatures are a proposed future extension that give a new way to generate signatures | 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: | 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: | ||
| Line 11: | Line 13: | ||
To check the validity of a signature (R, s) against a public key P, do the following: | 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. | 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. | An advantage of this method is that, if parties cooperate, we can generate a single signature that validates two or more separate transactions. | ||
| Line 26: | Line 28: | ||
==See also== | ==See also== | ||
[https://github.com/ | [https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki Draft Schnorr specification for future use in Bitcoin] | ||
[[Category:Technical]] | [[Category:Technical]] | ||
Latest revision as of 09:52, 15 September 2021
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.