diff options
author | Luke Dashjr <luke_github1@dashjr.org> | 2021-05-17 23:34:19 +0000 |
---|---|---|
committer | GitHub <noreply@github.com> | 2021-05-17 23:34:19 +0000 |
commit | 40b68284ebc0f06084ccfe064eac99e79f51ec4b (patch) | |
tree | 124a2cbfc87cdb55e40c0a216357f2bb1b38396f /bip-0340.mediawiki | |
parent | a099f43ce2013e5dc17e9ad4aa92b5c53fd69da7 (diff) | |
parent | 255b5b67c09879eb9d3e731ce45493ded9be87c9 (diff) | |
download | bips-40b68284ebc0f06084ccfe064eac99e79f51ec4b.tar.xz |
Merge pull request #1122 from jonasnick/bip340-remove-graph
BIP340: remove batch speedup graph and link to it instead
Diffstat (limited to 'bip-0340.mediawiki')
-rw-r--r-- | bip-0340.mediawiki | 4 |
1 files changed, 1 insertions, 3 deletions
diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index 1de7faa..b5a47d3 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -56,9 +56,7 @@ encodings and operations. '''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 the base point ''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 pairs ''(e, s)'' that satisfy ''e = hash(s⋅G - e⋅P || m)''. This variant avoids minor complexity introduced by the encoding of the point ''R'' in the signature (see paragraphs "Encoding R and public key point P" and "Implicit Y coordinates" further below in this subsection). Moreover, revealing ''e'' instead of ''R'' allows for potentially shorter signatures: Whereas an encoding of ''R'' inherently needs about 32 bytes, the hash ''e'' can be tuned to be shorter than 32 bytes, and [http://www.neven.org/papers/schnorr.pdf a short hash of only 16 bytes suffices to provide SUF-CMA security at the target security level of 128 bits]. However, a major drawback of this optimization is that finding collisions in a short hash function is easy. This complicates the implementation of secure signing protocols in scenarios in which a group of mutually distrusting signers work together to produce a single joint signature (see Applications below). In these scenarios, which are not captured by the SUF-CMA model due its assumption of a single honest signer, a promising attack strategy for malicious co-signers is to find a collision in the hash function in order to obtain a valid signature on a message that an honest co-signer did not intend to sign. -# Signatures are pairs ''(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-0340/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)''.]] +# Signatures are pairs ''(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.<ref>The speedup that results from batch verification can be demonstrated with the cryptography library [https://github.com/jonasnick/secp256k1/blob/schnorrsig-batch-verify/doc/speedup-batch.md libsecp256k1].</ref> Since we would like to avoid the fragility that comes with short hashes, the ''e'' variant does not provide significant advantages. We choose the ''R''-option, which supports batch verification. |