summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPieter Wuille <pieter.wuille@gmail.com>2019-10-15 17:28:52 -0700
committerPieter Wuille <pieter.wuille@gmail.com>2020-01-19 14:47:33 -0800
commit20f9901809de4850da8d25f0913c65e77b7fd754 (patch)
tree0c6e2b783d7e5e539f99c01bb3c9050fc1573b80
parentaef148ffc622330ea1308c53b154aeeadd22ef10 (diff)
Update bip-schnorr.mediawiki
Co-Authored-By: Tim Ruffing <tim@timruffing.de>
-rw-r--r--bip-schnorr.mediawiki6
1 files changed, 3 insertions, 3 deletions
diff --git a/bip-schnorr.mediawiki b/bip-schnorr.mediawiki
index 4fede9d..12a7379 100644
--- a/bip-schnorr.mediawiki
+++ b/bip-schnorr.mediawiki
@@ -49,14 +49,14 @@ encodings and operations.
=== Design ===
'''Schnorr signature variant''' Elliptic Curve Schnorr signatures for message ''m'' and public key ''P'' generally involve a point ''R'', integers ''e'' and ''s'' picked by the signer, and generator ''G'' which satisfy ''e = hash(R || m)'' and ''s⋅G = R + e⋅P''. Two formulations exist, depending on whether the signer reveals ''e'' or ''R'':
-# Signatures are ''(e,s)'' that satisfy ''e = hash(s⋅G - e⋅P || m)''. This supports more compact signatures, since [http://www.neven.org/papers/schnorr.pdf the hash ''e'' can be made as small as 16 bytes without sacrificing security], whereas an encoding of ''R'' inherently needs about 32 bytes. Moreover, this variant avoids minor complexity introduced by the encoding of the point ''R'' in the signature (see paragraphs "Encoding the sign of R" and "Implicit Y coordinate" further below in this subsection).
-# Signatures are ''(R,s)'' that satisfy ''s⋅G = R + hash(R || m)⋅P''. This supports batch verification, as there are no elliptic curve operations inside the hashes. Batch verification enables significant speedups.
+# Signatures are ''(e, s)'' that satisfy ''e = hash(s⋅G - e⋅P || m)''. This supports more compact signatures, since [http://www.neven.org/papers/schnorr.pdf the hash ''e'' can be made as small as 16 bytes without sacrificing security], whereas an encoding of ''R'' inherently needs about 32 bytes. Moreover, this variant avoids minor complexity introduced by the encoding of the point ''R'' in the signature (see paragraphs "Encoding the sign of R" and "Implicit Y coordinate" further below in this subsection).
+# Signatures are ''(R, s)'' that satisfy ''s⋅G = R + hash(R || m)⋅P''. This supports batch verification, as there are no elliptic curve operations inside the hashes. Batch verification enables significant speedups.
[[File:bip-schnorr/speedup-batch.png|center|frame|This graph shows the ratio between the time it takes to verify ''n'' signatures individually and to verify a batch of ''n'' signatures. This ratio goes up logarithmically with the number of signatures, or in other words: the total time to verify ''n'' signatures grows with ''O(n / log n)''.]]
We choose the ''R''-option to support batch verification.
-'''Key prefixing''' When using the verification rule above directly, it is possible for a third party to convert a signature ''(R, s)'' for key ''P'' into a signature ''(R, s + a⋅hash(R || m))'' for key ''P + a⋅G'' and the same message, for any integer ''a''. To combat this, we choose ''key prefixed''<ref>A limitation of committing to the public key (rather than to a short hash of it, or not at all) is that it removes the ability for public key recovery or verifying signatures against a short public key hash. These constructions are generally incompatible with batch verification.</ref> Schnorr signatures; changing the equation to ''s⋅G = R + hash(R || P || m)⋅P''. Key prefixing also seems to be a requirement for the security proof of the MuSig multisignature scheme (see below, under applications). It is not strictly necessary to do this explicitly for Bitcoin currently, as all signature hashes indirectly commit to the public keys already. However, this may change with proposals such as SIGHASH_NOINPUT ([https://github.com/bitcoin/bips/blob/master/bip-0118.mediawiki BIP 118]), or when the signature scheme is used for other purposes&mdash;especially in combination with schemes like [https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki BIP32]'s unhardened derivation.
+'''Key prefixing''' When using the verification rule above directly, it is possible for a third party to convert a signature ''(R, s)'' for key ''P'' into a signature ''(R, s + a⋅hash(R || m))'' for key ''P + a⋅G'' and the same message, for any integer ''a''. To combat this, we choose ''key prefixed''<ref>A limitation of committing to the public key (rather than to a short hash of it, or not at all) is that it removes the ability for public key recovery or verifying signatures against a short public key hash. These constructions are generally incompatible with batch verification.</ref> Schnorr signatures; changing the equation to ''s⋅G = R + hash(R || P || m)⋅P''. Key prefixing also seems to be a requirement for the security proof of the MuSig multisignature scheme (see Applications below). It is not strictly necessary to do this explicitly for Bitcoin currently, as all signature hashes indirectly commit to the public keys already. However, this may change with proposals such as SIGHASH_NOINPUT ([https://github.com/bitcoin/bips/blob/master/bip-0118.mediawiki BIP 118]), or when the signature scheme is used for other purposes&mdash;especially in combination with schemes like [https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki BIP32]'s unhardened derivation.
'''Encoding R and public key point P''' There exist several possibilities for encoding elliptic curve points:
# Encoding the full X and Y coordinates of ''P'' and ''R'', resulting in a 64-byte public key and a 96-byte signature.