summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPieter Wuille <pieter.wuille@gmail.com>2019-10-15 12:11:17 -0700
committerPieter Wuille <pieter.wuille@gmail.com>2020-01-19 14:47:33 -0800
commit0d4191bae5facdb7b4ae20ab5f7afc98f7e84877 (patch)
tree1071d696e7893e765120c4b2c6b1574a5f8704da
parent7f5926703a162b8dd18e1d4e024be0c73eeebef2 (diff)
Formulate claims about BatchVerify more accurately
-rw-r--r--bip-schnorr.mediawiki2
1 files changed, 1 insertions, 1 deletions
diff --git a/bip-schnorr.mediawiki b/bip-schnorr.mediawiki
index af279c7..b7bd541 100644
--- a/bip-schnorr.mediawiki
+++ b/bip-schnorr.mediawiki
@@ -192,7 +192,7 @@ The algorithm ''BatchVerify(pk<sub>1..u</sub>,m<sub>1..u</sub>,sig<sub>1..u</sub
* Fail if ''(s<sub>1</sub> + a<sub>2</sub>s<sub>2</sub> + ... + a<sub>u</sub>s<sub>u</sub>)⋅G &ne; R<sub>1</sub> + a<sub>2</sub>⋅R<sub>2</sub> + ... + a<sub>u</sub>⋅R<sub>u</sub> + e<sub>1</sub>⋅P<sub>1</sub> + (a<sub>2</sub>e<sub>2</sub>)⋅P<sub>2</sub> + ... + (a<sub>u</sub>e<sub>u</sub>)⋅P<sub>u</sub>''.
* Return success iff no failure occurred before reaching this point.
-With overwhelming probability, ''BatchVerify(pk<sub>1..u</sub>,m<sub>1..u</sub>,sig<sub>1..u</sub>) = Verify(pk<sub>1</sub>,m<sub>1</sub>,sig<sub>1</sub>) and Verify(pk<sub>2</sub>,m<sub>2</sub>,sig<sub>2</sub>) and ... and Verify(pk<sub>u</sub>,m<sub>u</sub>,sig<sub>u</sub>)''. If all signatures are valid it will always succeed. If one or more signatures are invalid, it will succeed with probability ''2<sup>-n</sup>''.
+If all individual signatures are valid (i.e., ''Verify'' would return success for them), ''BatchVerify'' will always return success. If at least one signature is invalid, ''BatchVerify'' will return success with at most a negligable probability.
=== Optimizations ===