diff options
Diffstat (limited to 'bip-0340.mediawiki')
| -rw-r--r-- | bip-0340.mediawiki | 12 |
1 files changed, 6 insertions, 6 deletions
diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index 58a4e50..afd71b0 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -111,8 +111,8 @@ The following conventions are used, with constants as defined for [https://www.s ** The function ''bytes(P)'', where ''P'' is a point, returns ''bytes(x(P))''. ** The function ''int(x)'', where ''x'' is a 32-byte array, returns the 256-bit unsigned integer whose most significant byte first encoding is ''x''. ** The function ''has_even_y(P)'', where ''P'' is a point, returns ''y(P) mod 2 = 0''. -** The function ''lift_x_even_y(x)'', where ''x'' is an integer in range ''0..p-1'', returns the point ''P'' for which ''x(P) = x''<ref> - Given a candidate X coordinate ''x'' in the range ''0..p-1'', there exist either exactly two or exactly zero valid Y coordinates. If no valid Y coordinate exists, then ''x'' is not a valid X coordinate either, i.e., no point ''P'' exists for which ''x(P) = x''. The valid Y coordinates for a given candidate ''x'' are the square roots of ''c = x<sup>3</sup> + 7 mod p'' and they can be computed as ''y = ±c<sup>(p+1)/4</sup> mod p'' (see [https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus Quadratic residue]) if they exist, which can be checked by squaring and comparing with ''c''.</ref> and ''has_even_y(P)'', or fails if no such point exists. The function ''lift_x_even_y(x)'' is equivalent to the following pseudocode: +** The function ''lift_x(x)'', where ''x'' is an integer in range ''0..p-1'', returns the point ''P'' for which ''x(P) = x''<ref> + Given a candidate X coordinate ''x'' in the range ''0..p-1'', there exist either exactly two or exactly zero valid Y coordinates. If no valid Y coordinate exists, then ''x'' is not a valid X coordinate either, i.e., no point ''P'' exists for which ''x(P) = x''. The valid Y coordinates for a given candidate ''x'' are the square roots of ''c = x<sup>3</sup> + 7 mod p'' and they can be computed as ''y = ±c<sup>(p+1)/4</sup> mod p'' (see [https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus Quadratic residue]) if they exist, which can be checked by squaring and comparing with ''c''.</ref> and ''has_even_y(P)'', or fails if no such point exists. The function ''lift_x(x)'' is equivalent to the following pseudocode: *** Let ''c = x<sup>3</sup> + 7 mod p''. *** Let ''y = c<sup>(p+1)/4</sup> mod p''. *** Fail if ''c ≠ y<sup>2</sup> mod p''. @@ -179,7 +179,7 @@ Input: * A signature ''sig'': a 64-byte array The algorithm ''Verify(pk, m, sig)'' is defined as: -* Let ''P = lift_x_even_y(int(pk))''; fail if that fails. +* Let ''P = lift_x(int(pk))''; fail if that fails. * Let ''r = int(sig[0:32])''; fail if ''r ≥ p''. * Let ''s = int(sig[32:64])''; fail if ''s ≥ n''. * Let ''e = int(hash<sub>BIP0340/challenge</sub>(bytes(r) || bytes(P) || m)) mod n''. @@ -189,7 +189,7 @@ The algorithm ''Verify(pk, m, sig)'' is defined as: For every valid secret key ''sk'' and message ''m'', ''Verify(PubKey(sk),m,Sign(sk,m))'' will succeed. -Note that the correctness of verification relies on the fact that ''lift_x_even_y'' always returns a point with an even Y coordinate. A hypothetical verification algorithm that treats points as public keys, and takes the point ''P'' directly as input would fail any time a point with odd Y is used. While it is possible to correct for this by negating points with odd Y coordinate before further processing, this would result in a scheme where every (message, signature) pair is valid for two public keys (a type of malleability that exists for ECDSA as well, but we don't wish to retain). We avoid these problems by treating just the X coordinate as public key. +Note that the correctness of verification relies on the fact that ''lift_x'' always returns a point with an even Y coordinate. A hypothetical verification algorithm that treats points as public keys, and takes the point ''P'' directly as input would fail any time a point with odd Y is used. While it is possible to correct for this by negating points with odd Y coordinate before further processing, this would result in a scheme where every (message, signature) pair is valid for two public keys (a type of malleability that exists for ECDSA as well, but we don't wish to retain). We avoid these problems by treating just the X coordinate as public key. ==== Batch Verification ==== @@ -202,11 +202,11 @@ Input: The algorithm ''BatchVerify(pk<sub>1..u</sub>, m<sub>1..u</sub>, sig<sub>1..u</sub>)'' is defined as: * Generate ''u-1'' random integers ''a<sub>2...u</sub>'' in the range ''1...n-1''. They are generated deterministically using a [https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator CSPRNG] seeded by a cryptographic hash of all inputs of the algorithm, i.e. ''seed = seed_hash(pk<sub>1</sub>..pk<sub>u</sub> || m<sub>1</sub>..m<sub>u</sub> || sig<sub>1</sub>..sig<sub>u</sub> )''. A safe choice is to instantiate ''seed_hash'' with SHA256 and use [https://tools.ietf.org/html/rfc8439 ChaCha20] with key ''seed'' as a CSPRNG to generate 256-bit integers, skipping integers not in the range ''1...n-1''. * For ''i = 1 .. u'': -** Let ''P<sub>i</sub> = lift_x_even_y(int(pk<sub>i</sub>))''; fail if it fails. +** Let ''P<sub>i</sub> = lift_x(int(pk<sub>i</sub>))''; fail if it fails. ** Let ''r<sub>i</sub> = int(sig<sub>i</sub>[0:32])''; fail if ''r<sub>i</sub> ≥ p''. ** Let ''s<sub>i</sub> = int(sig<sub>i</sub>[32:64])''; fail if ''s<sub>i</sub> ≥ n''. ** Let ''e<sub>i</sub> = int(hash<sub>BIP0340/challenge</sub>(bytes(r<sub>i</sub>) || bytes(P<sub>i</sub>) || m<sub>i</sub>)) mod n''. -** Let ''R<sub>i</sub> = lift_x_even_y(r<sub>i</sub>)''; fail if ''lift_x_even_y(r<sub>i</sub>)'' fails. +** Let ''R<sub>i</sub> = lift_x(r<sub>i</sub>)''; fail if ''lift_x(r<sub>i</sub>)'' fails. * Fail if ''(s<sub>1</sub> + a<sub>2</sub>s<sub>2</sub> + ... + a<sub>u</sub>s<sub>u</sub>)⋅G ≠ 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. |