From 2a122f20c521ad8f678477ebfc251d163685e09c Mon Sep 17 00:00:00 2001 From: Anthony Towns Date: Tue, 21 Jan 2020 08:46:19 +1000 Subject: missing space --- bip-0341.mediawiki | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/bip-0341.mediawiki b/bip-0341.mediawiki index ec11f6a..fb8b82a 100644 --- a/bip-0341.mediawiki +++ b/bip-0341.mediawiki @@ -95,7 +95,7 @@ The parameter ''hash_type'' is an 8-bit unsigned value. The SIGHASH The parameter ''ext_flag'' is an integer in range 0-127, and is used for indicating (in the message) that extensions are added at the end of the message'''What extensions use the ''ext_flag'' mechanism?''' [[bip-0342.mediawiki|BIP342]] reuses the same common signature message algorithm, but adds BIP342-specific data at the end, which is indicated using ''ext_flag = 1''.. -If the parameters take acceptable values, the message is the concatenation of the following data, in order(with byte size of each item listed in parentheses). Numerical values in 2, 4, or 8-byte are encoded in little-endian. +If the parameters take acceptable values, the message is the concatenation of the following data, in order (with byte size of each item listed in parentheses). Numerical values in 2, 4, or 8-byte are encoded in little-endian. * Control: ** ''hash_type'' (1). -- cgit v1.2.3 From 8b4f79b6f66afc7e3ddcca2bc4804f9145878fc9 Mon Sep 17 00:00:00 2001 From: Jonas Nick Date: Wed, 29 Jan 2020 15:44:45 +0000 Subject: BIP-340: Stress that secret key should be fresh and if not then RFC6979 shouldn't be used --- bip-0340.mediawiki | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index d2f92db..2fe3481 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -132,7 +132,7 @@ The following conventions are used, with constants as defined for [https://www.s ==== Public Key Generation ==== Input: -* The secret key ''sk'': a 32-byte array, generated uniformly at random +* The secret key ''sk'': a 32-byte array, freshly generated uniformly at random The algorithm ''PubKey(sk)'' is defined as: * Let ''d = int(sk)''. @@ -164,7 +164,7 @@ The algorithm ''Sign(sk, m)'' is defined as: ==== Alternative Signing ==== -It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The algorithm in the previous section is deterministic, i.e., it will always produce the same signature for a given message and secret key. This method does not need a random number generator (RNG) at signing time and is thus trivially robust against failures of RNGs. Alternatively the 32-byte ''rand'' value may be generated in other ways, producing a different but still valid signature (in other words, this is not a ''unique'' signature scheme). '''No matter which method is used to generate the ''rand'' value, the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.''' +It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The algorithm in the previous section is deterministic, i.e., it will always produce the same signature for a given message and secret key. This method does not need a random number generator (RNG) at signing time and is thus trivially robust against failures of RNGs. Alternatively the 32-byte ''rand'' value may be generated in other ways, producing a different but still valid signature (in other words, this is not a ''unique'' signature scheme). '''No matter which method is used to generate the ''rand'' value, the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.''' Freshness implies that reusing a secret key in different signature schemes is discouraged. For example, if the ''rand'' value was computed as per RFC6979 and the same secret key is used in deterministic ECDSA with RFC6979, the signatures can leak the secret key through nonce reuse. '''Synthetic nonces''' For instance when a RNG is available, 32 bytes of RNG output can be appended to the input to ''hashBIPSchnorrDerive''. This will change the corresponding line in the signing algorithm to ''rand = hashBIPSchnorrDerive(bytes(d) || m || get_32_bytes_from_rng())'', where ''get_32_bytes_from_rng()'' is the call to the RNG. It is safe to add the output of a low-entropy RNG. Adding high-entropy RNG output may improve protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks and side-channel attacks]. Therefore, '''synthetic nonces are recommended in settings where these attacks are a concern''' - in particular on offline signing devices. -- cgit v1.2.3 From ddc31eb6f6a288f92f91198bae5d0359ac54cef9 Mon Sep 17 00:00:00 2001 From: Jonas Nick Date: Thu, 30 Jan 2020 12:04:38 +0000 Subject: BIP-340: Improve wording of recommendation for fresh secret keys --- bip-0340.mediawiki | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index 2fe3481..c3f5291 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -164,7 +164,7 @@ The algorithm ''Sign(sk, m)'' is defined as: ==== Alternative Signing ==== -It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The algorithm in the previous section is deterministic, i.e., it will always produce the same signature for a given message and secret key. This method does not need a random number generator (RNG) at signing time and is thus trivially robust against failures of RNGs. Alternatively the 32-byte ''rand'' value may be generated in other ways, producing a different but still valid signature (in other words, this is not a ''unique'' signature scheme). '''No matter which method is used to generate the ''rand'' value, the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.''' Freshness implies that reusing a secret key in different signature schemes is discouraged. For example, if the ''rand'' value was computed as per RFC6979 and the same secret key is used in deterministic ECDSA with RFC6979, the signatures can leak the secret key through nonce reuse. +It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The algorithm in the previous section is deterministic, i.e., it will always produce the same signature for a given message and secret key. This method does not need a random number generator (RNG) at signing time and is thus trivially robust against failures of RNGs. Alternatively the 32-byte ''rand'' value may be generated in other ways, producing a different but still valid signature (in other words, this is not a ''unique'' signature scheme). '''No matter which method is used to generate the ''rand'' value, the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.''' Nonce freshness with a derandomize nonce function implies that the same inputs must not be presented in another context. This can be most reliably accomplished by not reusing the same private key across different signing schemes. For example, if the ''rand'' value was computed as per RFC6979 and the same secret key is used in deterministic ECDSA with RFC6979, the signatures can leak the secret key through nonce reuse. '''Synthetic nonces''' For instance when a RNG is available, 32 bytes of RNG output can be appended to the input to ''hashBIPSchnorrDerive''. This will change the corresponding line in the signing algorithm to ''rand = hashBIPSchnorrDerive(bytes(d) || m || get_32_bytes_from_rng())'', where ''get_32_bytes_from_rng()'' is the call to the RNG. It is safe to add the output of a low-entropy RNG. Adding high-entropy RNG output may improve protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks and side-channel attacks]. Therefore, '''synthetic nonces are recommended in settings where these attacks are a concern''' - in particular on offline signing devices. -- cgit v1.2.3 From 6581a87ff25cce0e10a20d40e85442ac5fbd17a4 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 28 Jan 2020 23:19:01 -0800 Subject: Switch to even-y tiebreaker for pubkeys --- bip-0340.mediawiki | 25 +++++++++++++------------ bip-0341.mediawiki | 14 +++++++------- 2 files changed, 20 insertions(+), 19 deletions(-) diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index c3f5291..c3ce7f6 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -85,9 +85,9 @@ In the case of ''R'' the third option is slower at signing time but a bit faster for elliptic curve operations). The two other options require a possibly expensive conversion to affine coordinates first. This would even be the case if the sign or oddness were explicitly coded (option 2 in the list above). We therefore choose option 3. -For ''P'' the speed of signing and verification does not significantly differ between any of the three options because affine coordinates of the point have to be computed anyway. For consistency reasons we choose the same option as for ''R''. The signing algorithm ensures that the signature is valid under the correct public key by negating the secret key if necessary. +For ''P'', using the third option comes at the cost of computing a Jacobi symbol (test for squaredness) at key generation or signing time, without avoiding a conversion to affine coordinates (as public keys will use affine coordinates anyway). We choose the second option, making public keys implicitly have an even Y coordinate, to maximize compatibility with existing key generation algorithms and infrastructure. -Implicit Y coordinates are not a reduction in security when expressed as the number of elliptic curve operations an attacker is expected to perform to compute the secret key. An attacker can normalize any given public key to a point whose Y coordinate is a square by negating the point if necessary. This is just a subtraction of field elements and not an elliptic curve operationThis can be formalized by a simple reduction that reduces an attack on Schnorr signatures with implicit Y coordinates to an attack to Schnorr signatures with explicit Y coordinates. The reduction works by reencoding public keys and negating the result of the hash function, which is modeled as random oracle, whenever the challenge public key has an explicit Y coordinate that is not a square. A proof sketch can be found [https://medium.com/blockstream/reducing-bitcoin-transaction-sizes-with-x-only-pubkeys-f86476af05d7 here].. +Implicit Y coordinates are not a reduction in security when expressed as the number of elliptic curve operations an attacker is expected to perform to compute the secret key. An attacker can normalize any given public key to a point whose Y coordinate is even by negating the point if necessary. This is just a subtraction of field elements and not an elliptic curve operationThis can be formalized by a simple reduction that reduces an attack on Schnorr signatures with implicit Y coordinates to an attack to Schnorr signatures with explicit Y coordinates. The reduction works by reencoding public keys and negating the result of the hash function, which is modeled as random oracle, whenever the challenge public key has an explicit Y coordinate that is odd. A proof sketch can be found [https://medium.com/blockstream/reducing-bitcoin-transaction-sizes-with-x-only-pubkeys-f86476af05d7 here].. '''Tagged Hashes''' Cryptographic hash functions are used for multiple purposes in the specification below and in Bitcoin in general. To make sure hashes used in one context can't be reinterpreted in another one, hash functions can be tweaked with a context-dependent tag name, in such a way that collisions across contexts can be assumed to be infeasible. Such collisions obviously can not be ruled out completely, but only for schemes using tagging with a unique name. As for other schemes collisions are at least less likely with tagging than without. @@ -95,7 +95,7 @@ For example, without tagged hashing a BIP340 signature could also be valid for a This proposal suggests to include the tag by prefixing the hashed data with ''SHA256(tag) || SHA256(tag)''. Because this is a 64-byte long context-specific constant and the ''SHA256'' block size is also 64 bytes, optimized implementations are possible (identical to SHA256 itself, but with a modified initial state). Using SHA256 of the tag name itself is reasonably simple and efficient for implementations that don't choose to use the optimization. -'''Final scheme''' As a result, our final scheme ends up using public key ''pk'' which is the X coordinate of a point ''P'' on the curve whose Y coordinate is a square and signatures ''(r,s)'' where ''r'' is the X coordinate of a point ''R'' whose Y coordinate is a square. The signature satisfies ''s⋅G = R + tagged_hash(r || pk || m)⋅P''. +'''Final scheme''' As a result, our final scheme ends up using public key ''pk'' which is the X coordinate of a point ''P'' on the curve whose Y coordinate is even and signatures ''(r,s)'' where ''r'' is the X coordinate of a point ''R'' whose Y coordinate is a square. The signature satisfies ''s⋅G = R + tagged_hash(r || pk || m)⋅P''. === Specification === @@ -117,16 +117,17 @@ The following conventions are used, with constants as defined for [https://www.s ** 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 ''is_square(x)'', where ''x'' is an integer, returns whether or not ''x'' is a quadratic residue modulo ''p''. Since ''p'' is prime, it is equivalent to the [https://en.wikipedia.org/wiki/Legendre_symbol Legendre symbol] ''(x / p) = x(p-1)/2 mod p'' being equal to ''1''For points ''P'' on the secp256k1 curve it holds that ''y(P)(p-1)/2 ≠ 0 mod p''.. ** The function ''has_square_y(P)'', where ''P'' is a point, is defined as ''not is_infinite(P) and is_square(y(P))''For points ''P'' on the secp256k1 curve it holds that ''has_square_y(P) = not has_square_y(-P)''.. -** The function ''lift_x(x)'', where ''x'' is an integer in range ''0..p-1'', returns the point ''P'' for which ''x(P) = x'' +** The function ''has_even_y(x)'', where ''P'' is a point, returns ''y(P) mod 2 = 0''. +** The function ''lift_x_square_y(x)'', where ''x'' is an integer in range ''0..p-1'', returns the point ''P'' for which ''x(P) = x'' 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 = x3 + 7 mod p'' and they can be computed as ''y = ±c(p+1)/4 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''. and ''has_square_y(P)'' - If ''P := lift_x(x)'' does not fail, then ''y := y(P) = c(p+1)/4 mod p'' is square. Proof: If ''lift_x'' does not fail, ''y'' is a square root of ''c'' and therefore the [https://en.wikipedia.org/wiki/Legendre_symbol Legendre symbol] ''(c / p)'' is ''c(p-1)/2 = 1 mod p''. Because the Legendre symbol ''(y / p)'' is ''y(p-1)/2 mod p = c((p+1)/4)((p-1)/2) mod p = 1((p+1)/4) mod p = 1 mod p'', ''y'' is square. -, or fails if no such point exists. The function ''lift_x(x)'' is equivalent to the following pseudocode: + If ''P := lift_x_square_y(x)'' does not fail, then ''y := y(P) = c(p+1)/4 mod p'' is square. Proof: If ''lift_x_square_y'' does not fail, ''y'' is a square root of ''c'' and therefore the [https://en.wikipedia.org/wiki/Legendre_symbol Legendre symbol] ''(c / p)'' is ''c(p-1)/2 = 1 mod p''. Because the Legendre symbol ''(y / p)'' is ''y(p-1)/2 mod p = c((p+1)/4)((p-1)/2) mod p = 1((p+1)/4) mod p = 1 mod p'', ''y'' is square. +, or fails if no such point exists. The function ''lift_x_square_y(x)'' is equivalent to the following pseudocode: *** Let ''c = x3 + 7 mod p''. *** Let ''y = c(p+1)/4 mod p''. *** Fail if ''c ≠ y2 mod p''. *** Return the unique point ''P'' such that ''x(P) = x'' and ''y(P) = y'', or fail if no such point exists. -** The function ''point(x)'', where ''x'' is a 32-byte array, returns the point ''P = lift_x(int(x))''. +** 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'' and ''has_even_y(P)'', or fails if no such point exists. If such a point does exist, it is always equal to either ''lift_x_square_y(x)'' or ''-lift_x_square_y(x)'', which suggests implementing it in terms of ''lift_x_square_y'', and optionally negating the result. ** The function ''hashtag(x)'' where ''tag'' is a UTF-8 encoded tag name and ''x'' is a byte array returns the 32-byte hash ''SHA256(SHA256(tag) || SHA256(tag) || x)''. ==== Public Key Generation ==== @@ -153,7 +154,7 @@ The algorithm ''Sign(sk, m)'' is defined as: * Let ''d' = int(sk)'' * Fail if ''d' = 0'' or ''d' ≥ n'' * Let ''P = d'⋅G'' -* Let ''d = d' '' if ''has_square_y(P)'', otherwise let ''d = n - d' ''. +* Let ''d = d' '' if ''has_even_y(P)'', otherwise let ''d = n - d' ''. * Let ''rand = hashBIPSchnorrDerive(bytes(d) || m)''. * Let ''k' = int(rand) mod n''Note that in general, taking a uniformly random 256-bit integer modulo the curve order will produce an unacceptably biased result. However, for the secp256k1 curve, the order is sufficiently close to ''2256'' that this bias is not observable (''1 - n / 2256'' is around ''1.27 * 2-128'').. * Fail if ''k' = 0''. @@ -183,7 +184,7 @@ Input: * A signature ''sig'': a 64-byte array The algorithm ''Verify(pk, m, sig)'' is defined as: -* Let ''P = point(pk)''; fail if ''point(pk)'' fails. +* Let ''P = lift_x_even_y(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(hashBIPSchnorr(bytes(r) || bytes(P) || m)) mod n''. @@ -193,7 +194,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 ''point(pk)'' always returns a point with a square 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 non-square Y is used. While it is possible to correct for this by negating points with non-square 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_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. ==== Batch Verification ==== @@ -206,11 +207,11 @@ Input: The algorithm ''BatchVerify(pk1..u, m1..u, sig1..u)'' is defined as: * Generate ''u-1'' random integers ''a2...u'' 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(pk1..pku || m1..mu || sig1..sigu )''. 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 ''Pi = point(pki)''; fail if ''point(pki)'' fails. +** Let ''Pi = lift_x_even_y(int(pki))''; fail if it fails. ** Let ''ri = int(sigi[0:32])''; fail if ''ri ≥ p''. ** Let ''si = int(sigi[32:64])''; fail if ''si ≥ n''. ** Let ''ei = int(hashBIPSchnorr(bytes(ri) || bytes(Pi) || mi)) mod n''. -** Let ''Ri = lift_x(ri)''; fail if ''lift_x(ri)'' fails. +** Let ''Ri = lift_x_square_y(ri)''; fail if ''lift_x_square_y(ri)'' fails. * Fail if ''(s1 + a2s2 + ... + ausu)⋅G ≠ R1 + a2⋅R2 + ... + au⋅Ru + e1⋅P1 + (a2e2)⋅P2 + ... + (aueu)⋅Pu''. * Return success iff no failure occurred before reaching this point. diff --git a/bip-0341.mediawiki b/bip-0341.mediawiki index fb8b82a..c6efaab 100644 --- a/bip-0341.mediawiki +++ b/bip-0341.mediawiki @@ -59,13 +59,13 @@ The following rules only apply when such an output is being spent. Any other out * Let ''q'' be the 32-byte array containing the witness program (the second push in the scriptPubKey) which represents a public key according to [[bip-0340.mediawiki#design|BIP340]]. * Fail if the witness stack has 0 elements. -* If there are at least two witness elements, and the first byte of the last element is 0x50'''Why is the first byte of the annex 0x50?''' The 0x50 is chosen as it could not be confused with a valid P2WPKH or P2WSH spending. As the control block's initial byte's lowest bit is used to indicate the public key's Y squareness, each leaf version needs an even byte value and the immediately following odd byte value that are both not yet used in P2WPKH or P2WSH spending. To indicate the annex, only an "unpaired" available byte is necessary like 0x50. This choice maximizes the available options for future script versions., this last element is called ''annex'' ''a'''''What is the purpose of the annex?''' The annex is a reserved space for future extensions, such as indicating the validation costs of computationally expensive new opcodes in a way that is recognizable without knowing the scriptPubKey of the output being spent. Until the meaning of this field is defined by another softfork, users SHOULD NOT include annex in transactions, or it may lead to PERMANENT FUND LOSS. and is removed from the witness stack. The annex (or the lack of thereof) is always covered by the signature and contributes to transaction weight, but is otherwise ignored during taproot validation. +* If there are at least two witness elements, and the first byte of the last element is 0x50'''Why is the first byte of the annex 0x50?''' The 0x50 is chosen as it could not be confused with a valid P2WPKH or P2WSH spending. As the control block's initial byte's lowest bit is used to indicate the public key's Y oddness, each leaf version needs an even byte value and the immediately following odd byte value that are both not yet used in P2WPKH or P2WSH spending. To indicate the annex, only an "unpaired" available byte is necessary like 0x50. This choice maximizes the available options for future script versions., this last element is called ''annex'' ''a'''''What is the purpose of the annex?''' The annex is a reserved space for future extensions, such as indicating the validation costs of computationally expensive new opcodes in a way that is recognizable without knowing the scriptPubKey of the output being spent. Until the meaning of this field is defined by another softfork, users SHOULD NOT include annex in transactions, or it may lead to PERMANENT FUND LOSS. and is removed from the witness stack. The annex (or the lack of thereof) is always covered by the signature and contributes to transaction weight, but is otherwise ignored during taproot validation. * If there is exactly one element left in the witness stack, key path spending is used: ** The single witness stack element is interpreted as the signature and must be valid (see the next section) for the public key ''q'' (see the next subsection). * If there are at least two witness elements left, script path spending is used: ** Call the second-to-last stack element ''s'', the script. ** The last stack element is called the control block ''c'', and must have length ''33 + 32m'', for a value of ''m'' that is an integer between 0 and 128'''Why is the Merkle path length limited to 128?''' The optimally space-efficient Merkle tree can be constructed based on the probabilities of the scripts in the leaves, using the Huffman algorithm. This algorithm will construct branches with lengths approximately equal to ''log2(1/probability)'', but to have branches longer than 128 you would need to have scripts with an execution chance below 1 in ''2128''. As that is our security bound, scripts that truly have such a low chance can probably be removed entirely., inclusive. Fail if it does not have such a length. -** Let ''p = c[1:33]'' and let ''P = point(p)'' where ''point'' and ''[:]'' are defined as in [[bip-0340.mediawiki#design|BIP340]]. Fail if this point is not on the curve. +** Let ''p = c[1:33]'' and let ''P = lift_x_even_y(int(p))'' where ''lift_x_even_y'' and ''[:]'' are defined as in [[bip-0340.mediawiki#design|BIP340]]. Fail if this point is not on the curve. ** Let ''v = c[0] & 0xfe'' and call it the ''leaf version'''''What constraints are there on the leaf version?''' First, the leaf version cannot be odd as ''c[0] & 0xfe'' will always be even, and cannot be ''0x50'' as that would result in ambiguity with the annex. In addition, in order to support some forms of static analysis that rely on being able to identify script spends without access to the output being spent, it is recommended to avoid using any leaf versions that would conflict with a valid first byte of either a valid P2WPKH pubkey or a valid P2WSH script (that is, both ''v'' and ''v | 1'' should be an undefined, invalid or disabled opcode or an opcode that is not valid as the first opcode). The values that comply to this rule are the 32 even values between ''0xc0'' and ''0xfe'' and also ''0x66'', ''0x7e'', ''0x80'', ''0x84'', ''0x96'', ''0x98'', ''0xba'', ''0xbc'', ''0xbe''. Note also that this constraint implies that leaf versions should be shared amongst different witness versions, as knowing the witness version requires access to the output being spent.. ** Let ''k0 = hashTapLeaf(v || compact_size(size of s) || s)''; also call it the ''tapleaf hash''. ** For ''j'' in ''[0,1,...,m-1]'': @@ -75,7 +75,7 @@ The following rules only apply when such an output is being spent. Any other out **** If ''kj ≥ ej'': ''kj+1 = hashTapBranch(ej || kj)''. ** Let ''t = hashTapTweak(p || km)''. ** If ''t ≥ 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141'' (order of secp256k1), fail. -** Let ''Q = point(q) if (c[0] & 1) = 1 and -point(q) otherwise'''''Why is it necessary to reveal a bit to indicate if the point represented by the output public key is negated in a script path spend?''' The ''point'' function (defined in [[bip-0340.mediawiki#design|BIP340]]) always constructs a point with a square Y coordinate, but because ''Q'' is constructed by adding the taproot tweak to the internal public key ''P'', it cannot easily be guaranteed that ''Q'' in fact has such a Y coordinate. Therefore, before verifying the taproot tweak the original point is restored by negating if necessary. We can not ignore the Y coordinate because it would prevent batch verification. Trying out multiple internal keys until there's such a ''Q'' is possible but undesirable and unnecessary since this information about the Y coordinate only consumes an unused bit.. Fail if this point is not on the curve. +** Let ''Q = lift_x_even_y(int(q)) if (c[0] & 1) = 0 and -lift_x_even_y(int(q)) otherwise'''''Why is it necessary to reveal a bit to indicate if the point represented by the output public key is negated in a script path spend?''' The ''lift_x_even_y'' function (defined in [[bip-0340.mediawiki#design|BIP340]]) always constructs a point with an even Y coordinate, but because ''Q'' is constructed by adding the taproot tweak to the internal public key ''P'', it cannot easily be guaranteed that ''Q'' in fact has such a Y coordinate. Therefore, before verifying the taproot tweak the original point is restored by negating if necessary. We can not ignore the Y coordinate because it would prevent batch verification. Trying out multiple internal keys until there's such a ''Q'' is possible but undesirable and unnecessary since this information about the Y coordinate only consumes an unused bit.. Fail if this point is not on the curve. ** If ''Q ≠ P + int(t)G'', fail. ** Execute the script, according to the applicable script rules'''What are the applicable script rules in script path spends?''' [[bip-0342.mediawiki|BIP342]] specifies validity rules that apply for leaf version 0xc0, but future proposals can introduce rules for other leaf versions., using the witness stack elements excluding the script ''s'', the control block ''c'', and the annex ''a'' if present, as initial stack. @@ -150,7 +150,7 @@ Satisfying any of these conditions is sufficient to spend the output. '''Initial steps''' The first step is determining what the internal key and the organization of the rest of the scripts should be. The specifics are likely application dependent, but here are some general guidelines: * When deciding between scripts with conditionals (OP_IF etc.) and splitting them up into multiple scripts (each corresponding to one execution path through the original script), it is generally preferable to pick the latter. * When a single condition requires signatures with multiple keys, key aggregation techniques like MuSig can be used to combine them into a single key. The details are out of scope for this document, but note that this may complicate the signing procedure. -* If one or more of the spending conditions consist of just a single key (after aggregation), the most likely one should be made the internal key. If no such condition exists, it may be worthwhile adding one that consists of an aggregation of all keys participating in all scripts combined; effectively adding an "everyone agrees" branch. If that is inacceptable, pick as internal key a point with unknown discrete logarithm. One example of such a point is ''H = point(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0)'' which is [https://github.com/ElementsProject/secp256k1-zkp/blob/11af7015de624b010424273be3d91f117f172c82/src/modules/rangeproof/main_impl.h#L16 constructed] by taking the hash of the standard uncompressed encoding of the [https://www.secg.org/sec2-v2.pdf secp256k1] base point ''G'' as X coordinate. In order to avoid leaking the information that key path spending is not possible it is recommended to pick a fresh integer ''r'' in the range ''0...n-1'' uniformly at random and use ''H + rG'' as internal key. It is possible to prove that this internal key does not have a known discrete logarithm with respect to ''G'' by revealing ''r'' to a verifier who can then reconstruct how the internal key was created. +* If one or more of the spending conditions consist of just a single key (after aggregation), the most likely one should be made the internal key. If no such condition exists, it may be worthwhile adding one that consists of an aggregation of all keys participating in all scripts combined; effectively adding an "everyone agrees" branch. If that is inacceptable, pick as internal key a point with unknown discrete logarithm. One example of such a point is ''H = lift_x_even_y(0x0250929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0)'' which is [https://github.com/ElementsProject/secp256k1-zkp/blob/11af7015de624b010424273be3d91f117f172c82/src/modules/rangeproof/main_impl.h#L16 constructed] by taking the hash of the standard uncompressed encoding of the [https://www.secg.org/sec2-v2.pdf secp256k1] base point ''G'' as X coordinate. In order to avoid leaking the information that key path spending is not possible it is recommended to pick a fresh integer ''r'' in the range ''0...n-1'' uniformly at random and use ''H + rG'' as internal key. It is possible to prove that this internal key does not have a known discrete logarithm with respect to ''G'' by revealing ''r'' to a verifier who can then reconstruct how the internal key was created. * If the spending conditions do not require a script path, the output key should commit to an unspendable script path instead of having no script path. This can be achieved by computing the output key point as ''Q = P + int(hashTapTweak(bytes(P)))G''. '''Why should the output key always have a taproot commitment, even if there is no script path?''' If the taproot output key is an aggregate of keys, there is the possibility for a malicious party to add a script path without being noticed by the other parties. This allows to bypass the multiparty policy and to steal the coin. @@ -178,13 +178,13 @@ def taproot_tweak_pubkey(pubkey, h): t = int_from_bytes(tagged_hash("TapTweak", pubkey + h)) if t >= SECP256K1_ORDER: raise ValueError - Q = point_add(point(pubkey), point_mul(G, t)) - is_negated = not has_square_y(Q) + Q = point_add(lift_x_even_y(int_from_bytes(pubkey)), point_mul(G, t)) + is_negated = not has_even_y(Q) return bytes_from_int(x(Q)), is_negated def taproot_tweak_seckey(seckey0, h): P = point_mul(G, int_from_bytes(seckey0)) - seckey = SECP256K1_ORDER - seckey0 if not has_square_y(P) else seckey + seckey = seckey0 if has_even_y(P) else SECP256K1_ORDER - seckey0 t = int_from_bytes(tagged_hash("TapTweak", bytes_from_int(x(P)) + h)) if t >= SECP256K1_ORDER: raise ValueError -- cgit v1.2.3 From d11cf65b6c439e6a330d24bc2864e712a6cc499b Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 28 Jan 2020 23:35:43 -0800 Subject: Change tags to prevent inconsistent breakage with earlier draft --- bip-0340.mediawiki | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index c3ce7f6..70fcfc6 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -155,19 +155,19 @@ The algorithm ''Sign(sk, m)'' is defined as: * Fail if ''d' = 0'' or ''d' ≥ n'' * Let ''P = d'⋅G'' * Let ''d = d' '' if ''has_even_y(P)'', otherwise let ''d = n - d' ''. -* Let ''rand = hashBIPSchnorrDerive(bytes(d) || m)''. +* Let ''rand = hashBIP340/nonce(bytes(d) || m)''. * Let ''k' = int(rand) mod n''Note that in general, taking a uniformly random 256-bit integer modulo the curve order will produce an unacceptably biased result. However, for the secp256k1 curve, the order is sufficiently close to ''2256'' that this bias is not observable (''1 - n / 2256'' is around ''1.27 * 2-128'').. * Fail if ''k' = 0''. * Let ''R = k'⋅G''. * Let ''k = k' '' if ''has_square_y(R)'', otherwise let ''k = n - k' ''. -* Let ''e = int(hashBIPSchnorr(bytes(R) || bytes(P) || m)) mod n''. +* Let ''e = int(hashBIP340/challenge(bytes(R) || bytes(P) || m)) mod n''. * Return the signature ''bytes(R) || bytes((k + ed) mod n)''. ==== Alternative Signing ==== It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The algorithm in the previous section is deterministic, i.e., it will always produce the same signature for a given message and secret key. This method does not need a random number generator (RNG) at signing time and is thus trivially robust against failures of RNGs. Alternatively the 32-byte ''rand'' value may be generated in other ways, producing a different but still valid signature (in other words, this is not a ''unique'' signature scheme). '''No matter which method is used to generate the ''rand'' value, the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.''' Nonce freshness with a derandomize nonce function implies that the same inputs must not be presented in another context. This can be most reliably accomplished by not reusing the same private key across different signing schemes. For example, if the ''rand'' value was computed as per RFC6979 and the same secret key is used in deterministic ECDSA with RFC6979, the signatures can leak the secret key through nonce reuse. -'''Synthetic nonces''' For instance when a RNG is available, 32 bytes of RNG output can be appended to the input to ''hashBIPSchnorrDerive''. This will change the corresponding line in the signing algorithm to ''rand = hashBIPSchnorrDerive(bytes(d) || m || get_32_bytes_from_rng())'', where ''get_32_bytes_from_rng()'' is the call to the RNG. It is safe to add the output of a low-entropy RNG. Adding high-entropy RNG output may improve protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks and side-channel attacks]. Therefore, '''synthetic nonces are recommended in settings where these attacks are a concern''' - in particular on offline signing devices. +'''Synthetic nonces''' For instance when a RNG is available, 32 bytes of RNG output can be appended to the input to ''hashBIP340/nonce''. This will change the corresponding line in the signing algorithm to ''rand = hashBIPSchnorrDerive(bytes(d) || m || get_32_bytes_from_rng())'', where ''get_32_bytes_from_rng()'' is the call to the RNG. It is safe to add the output of a low-entropy RNG. Adding high-entropy RNG output may improve protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks and side-channel attacks]. Therefore, '''synthetic nonces are recommended in settings where these attacks are a concern''' - in particular on offline signing devices. '''Verifying the signing output''' To prevent random or attacker provoked computation errors, the signature can be verified with the verification algorithm defined below before leaving the signer. This prevents publishing invalid signatures which may leak information about the secret key. '''If the additional computational cost is not a concern, it is recommended to verify newly created signatures and reject them in case of failure.''' @@ -187,7 +187,7 @@ The algorithm ''Verify(pk, m, sig)'' is defined as: * Let ''P = lift_x_even_y(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(hashBIPSchnorr(bytes(r) || bytes(P) || m)) mod n''. +* Let ''e = int(hashBIP340/challenge(bytes(r) || bytes(P) || m)) mod n''. * Let ''R = s⋅G - e⋅P''. * Fail if ''not has_square_y(R)'' or ''x(R) ≠ r''. * Return success iff no failure occurred before reaching this point. @@ -210,7 +210,7 @@ The algorithm ''BatchVerify(pk1..u, m1..u, sig1..ui = lift_x_even_y(int(pki))''; fail if it fails. ** Let ''ri = int(sigi[0:32])''; fail if ''ri ≥ p''. ** Let ''si = int(sigi[32:64])''; fail if ''si ≥ n''. -** Let ''ei = int(hashBIPSchnorr(bytes(ri) || bytes(Pi) || mi)) mod n''. +** Let ''ei = int(hashBIP340/challenge(bytes(ri) || bytes(Pi) || mi)) mod n''. ** Let ''Ri = lift_x_square_y(ri)''; fail if ''lift_x_square_y(ri)'' fails. * Fail if ''(s1 + a2s2 + ... + ausu)⋅G ≠ R1 + a2⋅R2 + ... + au⋅Ru + e1⋅P1 + (a2e2)⋅P2 + ... + (aueu)⋅Pu''. * Return success iff no failure occurred before reaching this point. -- cgit v1.2.3 From 8a009b90d8ccb200f3f31ae58d1615368c528cc6 Mon Sep 17 00:00:00 2001 From: Anthony Towns Date: Wed, 29 Jan 2020 18:32:30 +1000 Subject: notes about precomputed pubkey data --- bip-0340.mediawiki | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index 70fcfc6..3d7e635 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -128,6 +128,7 @@ The following conventions are used, with constants as defined for [https://www.s *** Fail if ''c ≠ y2 mod p''. *** Return the unique point ''P'' such that ''x(P) = x'' and ''y(P) = y'', or fail if no such point exists. ** 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'' and ''has_even_y(P)'', or fails if no such point exists. If such a point does exist, it is always equal to either ''lift_x_square_y(x)'' or ''-lift_x_square_y(x)'', which suggests implementing it in terms of ''lift_x_square_y'', and optionally negating the result. +** The function ''extbytes(P)'', where ''P'' is a point, returns the compressed 33-byte encoding of P, that is ''0x02 || bytes(x(P))'' if ''has_even_y(P)'' or ''0x03 || bytes(x(P))'' otherwise. ** The function ''hashtag(x)'' where ''tag'' is a UTF-8 encoded tag name and ''x'' is a byte array returns the 32-byte hash ''SHA256(SHA256(tag) || SHA256(tag) || x)''. ==== Public Key Generation ==== @@ -154,8 +155,8 @@ The algorithm ''Sign(sk, m)'' is defined as: * Let ''d' = int(sk)'' * Fail if ''d' = 0'' or ''d' ≥ n'' * Let ''P = d'⋅G'' +* Let ''rand = hashBIP340/nonce(bytes(d') || extbytes(P) || m)''Including the [https://moderncrypto.org/mail-archive/curves/2020/001012.html public key as input to the nonce hash] helps ensure the robustness of the signing algorithm, preventing leakage of the secret key if the calculation of the public key ''P'' is performed incorrectly or maliciously, for example due to being left to the caller for performance reasons.. * Let ''d = d' '' if ''has_even_y(P)'', otherwise let ''d = n - d' ''. -* Let ''rand = hashBIP340/nonce(bytes(d) || m)''. * Let ''k' = int(rand) mod n''Note that in general, taking a uniformly random 256-bit integer modulo the curve order will produce an unacceptably biased result. However, for the secp256k1 curve, the order is sufficiently close to ''2256'' that this bias is not observable (''1 - n / 2256'' is around ''1.27 * 2-128'').. * Fail if ''k' = 0''. * Let ''R = k'⋅G''. @@ -167,7 +168,7 @@ The algorithm ''Sign(sk, m)'' is defined as: It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The algorithm in the previous section is deterministic, i.e., it will always produce the same signature for a given message and secret key. This method does not need a random number generator (RNG) at signing time and is thus trivially robust against failures of RNGs. Alternatively the 32-byte ''rand'' value may be generated in other ways, producing a different but still valid signature (in other words, this is not a ''unique'' signature scheme). '''No matter which method is used to generate the ''rand'' value, the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.''' Nonce freshness with a derandomize nonce function implies that the same inputs must not be presented in another context. This can be most reliably accomplished by not reusing the same private key across different signing schemes. For example, if the ''rand'' value was computed as per RFC6979 and the same secret key is used in deterministic ECDSA with RFC6979, the signatures can leak the secret key through nonce reuse. -'''Synthetic nonces''' For instance when a RNG is available, 32 bytes of RNG output can be appended to the input to ''hashBIP340/nonce''. This will change the corresponding line in the signing algorithm to ''rand = hashBIPSchnorrDerive(bytes(d) || m || get_32_bytes_from_rng())'', where ''get_32_bytes_from_rng()'' is the call to the RNG. It is safe to add the output of a low-entropy RNG. Adding high-entropy RNG output may improve protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks and side-channel attacks]. Therefore, '''synthetic nonces are recommended in settings where these attacks are a concern''' - in particular on offline signing devices. +'''Synthetic nonces''' For instance when a RNG is available, RNG output can be appended to the input to ''hashBIP340/nonce''. This will change the corresponding line in the signing algorithm to ''rand = hashBIP340/nonce(bytes(d') || extbytes(P) || m || get_bytes_from_rng())'', where ''get_bytes_from_rng()'' is the call to the RNG. It is safe to add the output of a low-entropy RNG. Adding high-entropy RNG output may improve protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks and side-channel attacks]. Therefore, '''synthetic nonces are recommended in settings where these attacks are a concern''' - in particular on offline signing devices. Note that adding up to 23 bytes comes with no performance penalty, while adding over 32 bytes serves no security purpose. '''Verifying the signing output''' To prevent random or attacker provoked computation errors, the signature can be verified with the verification algorithm defined below before leaving the signer. This prevents publishing invalid signatures which may leak information about the secret key. '''If the additional computational cost is not a concern, it is recommended to verify newly created signatures and reject them in case of failure.''' @@ -176,6 +177,8 @@ It should be noted that various alternative signing algorithms can be used to pr '''Multisignatures''' This signature scheme is compatible with various types of multisignature and threshold schemes such as [https://eprint.iacr.org/2018/068 MuSig], where a single public key requires holders of multiple secret keys to participate in signing (see Applications below). '''It is important to note that multisignature signing schemes in general are insecure with the ''rand'' generation from the default signing algorithm above (or any other deterministic method).''' +'''Precomputed public key data''' For many uses the compressed 33-byte encoding of the public key may already be known, making it easy to evaluate ''extbytes(P)'', ''has_even_y(P)'' and ''bytes(P)''. As such, having signers supply this directly may be more efficient than calculating them from the secret key. However, if this optimization is used, signers must ensure the public key is correctly calculated and not taken from untrusted sources. + ==== Verification ==== Input: -- cgit v1.2.3 From 455504b3af46bb39894a11b54fb10edb11528186 Mon Sep 17 00:00:00 2001 From: Anthony Towns Date: Sat, 1 Feb 2020 01:39:56 +1000 Subject: Include d in nonce rather than d' --- bip-0340.mediawiki | 5 ++--- 1 file changed, 2 insertions(+), 3 deletions(-) diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index 3d7e635..3aa6e05 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -128,7 +128,6 @@ The following conventions are used, with constants as defined for [https://www.s *** Fail if ''c ≠ y2 mod p''. *** Return the unique point ''P'' such that ''x(P) = x'' and ''y(P) = y'', or fail if no such point exists. ** 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'' and ''has_even_y(P)'', or fails if no such point exists. If such a point does exist, it is always equal to either ''lift_x_square_y(x)'' or ''-lift_x_square_y(x)'', which suggests implementing it in terms of ''lift_x_square_y'', and optionally negating the result. -** The function ''extbytes(P)'', where ''P'' is a point, returns the compressed 33-byte encoding of P, that is ''0x02 || bytes(x(P))'' if ''has_even_y(P)'' or ''0x03 || bytes(x(P))'' otherwise. ** The function ''hashtag(x)'' where ''tag'' is a UTF-8 encoded tag name and ''x'' is a byte array returns the 32-byte hash ''SHA256(SHA256(tag) || SHA256(tag) || x)''. ==== Public Key Generation ==== @@ -155,8 +154,8 @@ The algorithm ''Sign(sk, m)'' is defined as: * Let ''d' = int(sk)'' * Fail if ''d' = 0'' or ''d' ≥ n'' * Let ''P = d'⋅G'' -* Let ''rand = hashBIP340/nonce(bytes(d') || extbytes(P) || m)''Including the [https://moderncrypto.org/mail-archive/curves/2020/001012.html public key as input to the nonce hash] helps ensure the robustness of the signing algorithm, preventing leakage of the secret key if the calculation of the public key ''P'' is performed incorrectly or maliciously, for example due to being left to the caller for performance reasons.. * Let ''d = d' '' if ''has_even_y(P)'', otherwise let ''d = n - d' ''. +* Let ''rand = hashBIP340/nonce(bytes(d) || bytes(P) || m)''Including the [https://moderncrypto.org/mail-archive/curves/2020/001012.html public key as input to the nonce hash] helps ensure the robustness of the signing algorithm by preventing leakage of the secret key if the calculation of the public key ''P'' is performed incorrectly or maliciously, for example if it is left to the caller for performance reasons.. * Let ''k' = int(rand) mod n''Note that in general, taking a uniformly random 256-bit integer modulo the curve order will produce an unacceptably biased result. However, for the secp256k1 curve, the order is sufficiently close to ''2256'' that this bias is not observable (''1 - n / 2256'' is around ''1.27 * 2-128'').. * Fail if ''k' = 0''. * Let ''R = k'⋅G''. @@ -177,7 +176,7 @@ It should be noted that various alternative signing algorithms can be used to pr '''Multisignatures''' This signature scheme is compatible with various types of multisignature and threshold schemes such as [https://eprint.iacr.org/2018/068 MuSig], where a single public key requires holders of multiple secret keys to participate in signing (see Applications below). '''It is important to note that multisignature signing schemes in general are insecure with the ''rand'' generation from the default signing algorithm above (or any other deterministic method).''' -'''Precomputed public key data''' For many uses the compressed 33-byte encoding of the public key may already be known, making it easy to evaluate ''extbytes(P)'', ''has_even_y(P)'' and ''bytes(P)''. As such, having signers supply this directly may be more efficient than calculating them from the secret key. However, if this optimization is used, signers must ensure the public key is correctly calculated and not taken from untrusted sources. +'''Precomputed public key data''' For many uses the compressed 33-byte encoding of the public key corresponding to the secret key may already be known, making it easy to evaluate ''has_even_y(P)'' and ''bytes(P)''. As such, having signers supply this directly may be more efficient than recalculating the public key from the secret key. However, if this optimization is used, signers must ensure the public key is correctly calculated and not taken from untrusted sources. ==== Verification ==== -- cgit v1.2.3 From 453947f43ab1d67df777ce6a26c8904a80afe20f Mon Sep 17 00:00:00 2001 From: Anthony Towns Date: Sat, 1 Feb 2020 16:53:02 +1000 Subject: give bip32 conversion its own section --- bip-0340.mediawiki | 2 ++ 1 file changed, 2 insertions(+) diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index 3aa6e05..bd04d69 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -142,6 +142,8 @@ The algorithm ''PubKey(sk)'' is defined as: Note that we use a very different public key format (32 bytes) than the ones used by existing systems (which typically use elliptic curve points as public keys, or 33-byte or 65-byte encodings of them). A side effect is that ''PubKey(sk) = PubKey(bytes(n - int(sk))'', so every public key has two corresponding secret keys. +==== Public Key Conversion ==== + As an alternative to generating keys randomly, it is also possible and safe to repurpose existing key generation algorithms for ECDSA in a compatible way. The secret keys constructed by such an algorithm can be used as ''sk'' directly. The public keys constructed by such an algorithm (assuming they use the 33-byte compressed encoding) need to be converted by dropping the first byte. Specifically, [[bip-0032.mediawiki|BIP32]] and schemes built on top of it remain usable. ==== Default Signing ==== -- cgit v1.2.3 From 806b46fde106dfa0a2c29127283d20b2bcc8e888 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Tue, 18 Feb 2020 23:42:42 -0800 Subject: Switch to new synth nonce scheme and make it default --- bip-0340.mediawiki | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index bd04d69..1b7f8d7 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -151,13 +151,14 @@ As an alternative to generating keys randomly, it is also possible and safe to r Input: * The secret key ''sk'': a 32-byte array * The message ''m'': a 32-byte array +* Auxiliary data ''a'': a byte array of length 0 or more The algorithm ''Sign(sk, m)'' is defined as: * Let ''d' = int(sk)'' * Fail if ''d' = 0'' or ''d' ≥ n'' * Let ''P = d'⋅G'' * Let ''d = d' '' if ''has_even_y(P)'', otherwise let ''d = n - d' ''. -* Let ''rand = hashBIP340/nonce(bytes(d) || bytes(P) || m)''Including the [https://moderncrypto.org/mail-archive/curves/2020/001012.html public key as input to the nonce hash] helps ensure the robustness of the signing algorithm by preventing leakage of the secret key if the calculation of the public key ''P'' is performed incorrectly or maliciously, for example if it is left to the caller for performance reasons.. +* Let ''rand = hashBIP340/nonce(xor(bytes(d), HBIP340/aux(a)) || bytes(P) || m)''Including the [https://moderncrypto.org/mail-archive/curves/2020/001012.html public key as input to the nonce hash] helps ensure the robustness of the signing algorithm by preventing leakage of the secret key if the calculation of the public key ''P'' is performed incorrectly or maliciously, for example if it is left to the caller for performance reasons., where ''xor(a,b)'' represents the byte-wise xor of ''a'' and ''b''. * Let ''k' = int(rand) mod n''Note that in general, taking a uniformly random 256-bit integer modulo the curve order will produce an unacceptably biased result. However, for the secp256k1 curve, the order is sufficiently close to ''2256'' that this bias is not observable (''1 - n / 2256'' is around ''1.27 * 2-128'').. * Fail if ''k' = 0''. * Let ''R = k'⋅G''. @@ -165,11 +166,11 @@ The algorithm ''Sign(sk, m)'' is defined as: * Let ''e = int(hashBIP340/challenge(bytes(R) || bytes(P) || m)) mod n''. * Return the signature ''bytes(R) || bytes((k + ed) mod n)''. -==== Alternative Signing ==== +When an RNG is available at signing time, up to 32 bytes of its output should be included in ''a''. The result is then called a ''synthetic nonce''. Doing so may improve protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks and side-channel attacks]. Therefore, '''synthetic nonces are recommended in settings where these attacks are a concern''' - in particular on offline signing devices. Adding more than 32 bytes serves no security purpose. Note that while this means the resulting nonce is not deterministic, its normal security properties do not depend on the quality of the RNG, and in fact using a completely broken RNG is still secure. -It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The algorithm in the previous section is deterministic, i.e., it will always produce the same signature for a given message and secret key. This method does not need a random number generator (RNG) at signing time and is thus trivially robust against failures of RNGs. Alternatively the 32-byte ''rand'' value may be generated in other ways, producing a different but still valid signature (in other words, this is not a ''unique'' signature scheme). '''No matter which method is used to generate the ''rand'' value, the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.''' Nonce freshness with a derandomize nonce function implies that the same inputs must not be presented in another context. This can be most reliably accomplished by not reusing the same private key across different signing schemes. For example, if the ''rand'' value was computed as per RFC6979 and the same secret key is used in deterministic ECDSA with RFC6979, the signatures can leak the secret key through nonce reuse. +==== Alternative Signing ==== -'''Synthetic nonces''' For instance when a RNG is available, RNG output can be appended to the input to ''hashBIP340/nonce''. This will change the corresponding line in the signing algorithm to ''rand = hashBIP340/nonce(bytes(d') || extbytes(P) || m || get_bytes_from_rng())'', where ''get_bytes_from_rng()'' is the call to the RNG. It is safe to add the output of a low-entropy RNG. Adding high-entropy RNG output may improve protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks and side-channel attacks]. Therefore, '''synthetic nonces are recommended in settings where these attacks are a concern''' - in particular on offline signing devices. Note that adding up to 23 bytes comes with no performance penalty, while adding over 32 bytes serves no security purpose. +It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The 32-byte ''rand'' value may be generated in other ways, producing a different but still valid signature (in other words, this is not a ''unique'' signature scheme). '''No matter which method is used to generate the ''rand'' value, the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.''' Nonce freshness with a derandomized nonce function implies that the same inputs must not be presented in another context. This can be most reliably accomplished by not reusing the same private key across different signing schemes. For example, if the ''rand'' value was computed as per RFC6979 and the same secret key is used in deterministic ECDSA with RFC6979, the signatures can leak the secret key through nonce reuse. '''Verifying the signing output''' To prevent random or attacker provoked computation errors, the signature can be verified with the verification algorithm defined below before leaving the signer. This prevents publishing invalid signatures which may leak information about the secret key. '''If the additional computational cost is not a concern, it is recommended to verify newly created signatures and reject them in case of failure.''' -- cgit v1.2.3 From 88d30c704fbb88bfa00b00b26d2eb1cde3b5925a Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Fri, 21 Feb 2020 16:39:19 -0800 Subject: Address comments --- bip-0340.mediawiki | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-) diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index 1b7f8d7..73edd96 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -151,28 +151,29 @@ As an alternative to generating keys randomly, it is also possible and safe to r Input: * The secret key ''sk'': a 32-byte array * The message ''m'': a 32-byte array -* Auxiliary data ''a'': a byte array of length 0 or more +* Auxiliary random data ''a'': a byte array of length 0 to 32 (inclusive) The algorithm ''Sign(sk, m)'' is defined as: * Let ''d' = int(sk)'' * Fail if ''d' = 0'' or ''d' ≥ n'' * Let ''P = d'⋅G'' * Let ''d = d' '' if ''has_even_y(P)'', otherwise let ''d = n - d' ''. -* Let ''rand = hashBIP340/nonce(xor(bytes(d), HBIP340/aux(a)) || bytes(P) || m)''Including the [https://moderncrypto.org/mail-archive/curves/2020/001012.html public key as input to the nonce hash] helps ensure the robustness of the signing algorithm by preventing leakage of the secret key if the calculation of the public key ''P'' is performed incorrectly or maliciously, for example if it is left to the caller for performance reasons., where ''xor(a,b)'' represents the byte-wise xor of ''a'' and ''b''. +* Let ''t'' be the byte-wise xor of ''bytes(d)'' and ''HBIP340/aux(a)''The auxiliary random data is hashed (with a unique tag) as a precaution against situations where the randomness may be correlated with the private key itself. It is xored with the private key (rather than combined with it in a hash) to reduce the number of operations exposed to the actual secret key.. +* Let ''rand = hashBIP340/nonce(t || bytes(P) || m)''Including the [https://moderncrypto.org/mail-archive/curves/2020/001012.html public key as input to the nonce hash] helps ensure the robustness of the signing algorithm by preventing leakage of the secret key if the calculation of the public key ''P'' is performed incorrectly or maliciously, for example if it is left to the caller for performance reasons.. * Let ''k' = int(rand) mod n''Note that in general, taking a uniformly random 256-bit integer modulo the curve order will produce an unacceptably biased result. However, for the secp256k1 curve, the order is sufficiently close to ''2256'' that this bias is not observable (''1 - n / 2256'' is around ''1.27 * 2-128'').. * Fail if ''k' = 0''. * Let ''R = k'⋅G''. * Let ''k = k' '' if ''has_square_y(R)'', otherwise let ''k = n - k' ''. * Let ''e = int(hashBIP340/challenge(bytes(R) || bytes(P) || m)) mod n''. -* Return the signature ''bytes(R) || bytes((k + ed) mod n)''. +* Let ''sig = bytes(R) || bytes((k + ed) mod n)''. +* If ''Verify(bytes(P), m, sig)'' (see below) returns failure, abortVerifying the signature before leaving the signer prevents random or attacker provoked computation errors. This prevents publishing invalid signatures which may leak information about the secret key. It is recommended, but can be omitted if the computation cost is prohibitive.. +* Return the signature ''sig''. -When an RNG is available at signing time, up to 32 bytes of its output should be included in ''a''. The result is then called a ''synthetic nonce''. Doing so may improve protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks and side-channel attacks]. Therefore, '''synthetic nonces are recommended in settings where these attacks are a concern''' - in particular on offline signing devices. Adding more than 32 bytes serves no security purpose. Note that while this means the resulting nonce is not deterministic, its normal security properties do not depend on the quality of the RNG, and in fact using a completely broken RNG is still secure. +The auxiliary random data should be set to fresh randomness generated at signing time, resulting in what is called a ''synthetic nonce''. If no randomness is available, a simple counter can be used as well, or even nothing at all. Using any non-repeating value increases protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks]. Using unpredictable randomness additionally increases protection against other side-channel attacks, and is '''recommended whenever available'''. Note that while this means the resulting nonce is not deterministic, the randomness is only supplemental to security. The normal security properties (excluding side-channel attacks) do not depend on the quality of the signing-time RNG. ==== Alternative Signing ==== -It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The 32-byte ''rand'' value may be generated in other ways, producing a different but still valid signature (in other words, this is not a ''unique'' signature scheme). '''No matter which method is used to generate the ''rand'' value, the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.''' Nonce freshness with a derandomized nonce function implies that the same inputs must not be presented in another context. This can be most reliably accomplished by not reusing the same private key across different signing schemes. For example, if the ''rand'' value was computed as per RFC6979 and the same secret key is used in deterministic ECDSA with RFC6979, the signatures can leak the secret key through nonce reuse. - -'''Verifying the signing output''' To prevent random or attacker provoked computation errors, the signature can be verified with the verification algorithm defined below before leaving the signer. This prevents publishing invalid signatures which may leak information about the secret key. '''If the additional computational cost is not a concern, it is recommended to verify newly created signatures and reject them in case of failure.''' +It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The 32-byte ''rand'' value may be generated in other ways, producing a different but still valid signature (in other words, this is not a ''unique'' signature scheme). '''No matter which method is used to generate the ''rand'' value, the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.''' For nonces without randomness this implies that the same inputs must not be presented in another context. This can be most reliably accomplished by not reusing the same private key across different signing schemes. For example, if the ''rand'' value was computed as per RFC6979 and the same secret key is used in deterministic ECDSA with RFC6979, the signatures can leak the secret key through nonce reuse. '''Nonce exfiltration protection''' It is possible to strengthen the nonce generation algorithm using a second device. In this case, the second device contributes randomness which the actual signer provably incorporates into its nonce. This prevents certain attacks where the signer device is compromised and intentionally tries to leak the secret key through its nonce selection. -- cgit v1.2.3 From 4f482a6748a97887d54c9c70682085aad7febefd Mon Sep 17 00:00:00 2001 From: Tim Ruffing Date: Mon, 24 Feb 2020 21:59:13 +0100 Subject: Fix a few minor issues * Recommend a byte length for aux random data * Clarify that with signature verification by default at the end of the signing algorithm, using public keys from untrusted sources is not an issue. * A few editorial nits --- bip-0340.mediawiki | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index 73edd96..917ca24 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -2,7 +2,7 @@ BIP: 340 Title: Schnorr Signatures for secp256k1 Author: Pieter Wuille - Jonas Nick + Jonas Nick Tim Ruffing Comments-Summary: No comments yet. Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0340 @@ -40,7 +40,7 @@ propose a new standard, a number of improvements not specific to Schnorr signatu made: * '''Signature encoding''': Instead of using [https://en.wikipedia.org/wiki/X.690#DER_encoding DER]-encoding for signatures (which are variable size, and up to 72 bytes), we can use a simple fixed 64-byte format. -* '''Public key encoding''': Instead of using ''compressed'' 33-byte encodings of elliptic curve points which are common in Bitcoin today, public keys in this proposal are encoded as 32 bytes. +* '''Public key encoding''': Instead of using [https://www.secg.org/sec1-v2.pdf ''compressed''] 33-byte encodings of elliptic curve points which are common in Bitcoin today, public keys in this proposal are encoded as 32 bytes. * '''Batch verification''': The specific formulation of ECDSA signatures that is standardized cannot be verified more efficiently in batch compared to individually, unless additional witness data is added. Changing the signature scheme offers an opportunity to address this. * '''Completely specified''': To be safe for usage in consensus systems, the verification algorithm must be completely specified at the byte level. This guarantees that nobody can construct a signature that is valid to some verifiers but not all. This is traditionally not a requirement for digital signature schemes, and the lack of exact specification for the DER parsing of ECDSA signatures has caused problems for Bitcoin [https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-July/009697.html in the past], needing [[bip-0066.mediawiki|BIP66]] to address it. In this document we aim to meet this property by design. For batch verification, which is inherently non-deterministic as the verifier can choose their batches, this property implies that the outcome of verification may only differ from individual verifications with negligible probability, even to an attacker who intentionally tries to make batch- and non-batch verification differ. @@ -169,7 +169,7 @@ The algorithm ''Sign(sk, m)'' is defined as: * If ''Verify(bytes(P), m, sig)'' (see below) returns failure, abortVerifying the signature before leaving the signer prevents random or attacker provoked computation errors. This prevents publishing invalid signatures which may leak information about the secret key. It is recommended, but can be omitted if the computation cost is prohibitive.. * Return the signature ''sig''. -The auxiliary random data should be set to fresh randomness generated at signing time, resulting in what is called a ''synthetic nonce''. If no randomness is available, a simple counter can be used as well, or even nothing at all. Using any non-repeating value increases protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks]. Using unpredictable randomness additionally increases protection against other side-channel attacks, and is '''recommended whenever available'''. Note that while this means the resulting nonce is not deterministic, the randomness is only supplemental to security. The normal security properties (excluding side-channel attacks) do not depend on the quality of the signing-time RNG. +The auxiliary random data should be set to fresh randomness generated at signing time, resulting in what is called a ''synthetic nonce''. Using 32 bytes of randomness is optimal but if obtaining randomness is expensive, fewer random bytes can be used. If randomness is not available, a simple counter can be used as well (optimally at least 64 bits wide), or even an empty byte array of length 0. Using any non-repeating value increases protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks]. Using unpredictable randomness additionally increases protection against other side-channel attacks, and is '''recommended whenever available'''. Note that while this means the resulting nonce is not deterministic, the randomness is only supplemental to security. The normal security properties (excluding side-channel attacks) do not depend on the quality of the signing-time RNG. ==== Alternative Signing ==== @@ -180,7 +180,7 @@ It should be noted that various alternative signing algorithms can be used to pr '''Multisignatures''' This signature scheme is compatible with various types of multisignature and threshold schemes such as [https://eprint.iacr.org/2018/068 MuSig], where a single public key requires holders of multiple secret keys to participate in signing (see Applications below). '''It is important to note that multisignature signing schemes in general are insecure with the ''rand'' generation from the default signing algorithm above (or any other deterministic method).''' -'''Precomputed public key data''' For many uses the compressed 33-byte encoding of the public key corresponding to the secret key may already be known, making it easy to evaluate ''has_even_y(P)'' and ''bytes(P)''. As such, having signers supply this directly may be more efficient than recalculating the public key from the secret key. However, if this optimization is used, signers must ensure the public key is correctly calculated and not taken from untrusted sources. +'''Precomputed public key data''' For many uses the compressed 33-byte encoding of the public key corresponding to the secret key may already be known, making it easy to evaluate ''has_even_y(P)'' and ''bytes(P)''. As such, having signers supply this directly may be more efficient than recalculating the public key from the secret key. However, if this optimization is used and additionally the signature verification at the end of the signing algorithm is dropped for increased efficiency, signers must ensure the public key is correctly calculated and not taken from untrusted sources. ==== Verification ==== -- cgit v1.2.3 From cd19095fb039ee74dbb33225af21e83846e5a083 Mon Sep 17 00:00:00 2001 From: Tim Ruffing Date: Fri, 28 Feb 2020 18:25:31 +0100 Subject: Switch to only 32 bytes aux --- bip-0340.mediawiki | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index 917ca24..883ef3a 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -151,7 +151,7 @@ As an alternative to generating keys randomly, it is also possible and safe to r Input: * The secret key ''sk'': a 32-byte array * The message ''m'': a 32-byte array -* Auxiliary random data ''a'': a byte array of length 0 to 32 (inclusive) +* Auxiliary random data ''a'': a 32-byte array The algorithm ''Sign(sk, m)'' is defined as: * Let ''d' = int(sk)'' @@ -169,7 +169,7 @@ The algorithm ''Sign(sk, m)'' is defined as: * If ''Verify(bytes(P), m, sig)'' (see below) returns failure, abortVerifying the signature before leaving the signer prevents random or attacker provoked computation errors. This prevents publishing invalid signatures which may leak information about the secret key. It is recommended, but can be omitted if the computation cost is prohibitive.. * Return the signature ''sig''. -The auxiliary random data should be set to fresh randomness generated at signing time, resulting in what is called a ''synthetic nonce''. Using 32 bytes of randomness is optimal but if obtaining randomness is expensive, fewer random bytes can be used. If randomness is not available, a simple counter can be used as well (optimally at least 64 bits wide), or even an empty byte array of length 0. Using any non-repeating value increases protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks]. Using unpredictable randomness additionally increases protection against other side-channel attacks, and is '''recommended whenever available'''. Note that while this means the resulting nonce is not deterministic, the randomness is only supplemental to security. The normal security properties (excluding side-channel attacks) do not depend on the quality of the signing-time RNG. +The auxiliary random data should be set to fresh randomness generated at signing time, resulting in what is called a ''synthetic nonce''. Using 32 bytes of randomness is optimal. If obtaining randomness is expensive, 16 random bytes can be padded with 16 null bytes to obtain a 32-byte array. If randomness is not available at all at signing time, a simple counter wide enough to not repeat in practice (e.g., 64 bits or wider) and padded with null bytes to a 32 byte-array can be used, or even the constant array with 32 null bytes. Using any non-repeating value increases protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks]. Using unpredictable randomness additionally increases protection against other side-channel attacks, and is '''recommended whenever available'''. Note that while this means the resulting nonce is not deterministic, the randomness is only supplemental to security. The normal security properties (excluding side-channel attacks) do not depend on the quality of the signing-time RNG. ==== Alternative Signing ==== -- cgit v1.2.3 From d41e778ca12408de476f4c75d79d6480728fbb8d Mon Sep 17 00:00:00 2001 From: Jonas Nick Date: Sun, 2 Feb 2020 16:14:30 +0000 Subject: BIP 340: Update reference code and test vectors as follows: - use evenness as tiebreaker - using different tags for nonce- and challenge hashing - add pubkey to nonce function. --- bip-0340/reference.py | 22 +++++++++++++------ bip-0340/test-vectors.csv | 30 +++++++++++++------------- bip-0340/test-vectors.py | 55 ++++++++++++++++++++++++++++++----------------- 3 files changed, 66 insertions(+), 41 deletions(-) diff --git a/bip-0340/reference.py b/bip-0340/reference.py index f2a944f..9b5592e 100644 --- a/bip-0340/reference.py +++ b/bip-0340/reference.py @@ -51,7 +51,7 @@ def bytes_from_int(x): def bytes_from_point(P): return bytes_from_int(x(P)) -def point_from_bytes(b): +def lift_x_square_y(b): x = int_from_bytes(b) if x >= p: return None @@ -61,6 +61,13 @@ def point_from_bytes(b): return None return [x, y] +def lift_x_even_y(b): + P = lift_x_square_y(b) + if P is None: + return None + else: + return [x(P), y(P) if y(P) % 2 == 0 else p - y(P)] + def int_from_bytes(b): return int.from_bytes(b, byteorder="big") @@ -73,6 +80,9 @@ def is_square(x): def has_square_y(P): return not is_infinity(P) and is_square(y(P)) +def has_even_y(P): + return y(P) % 2 == 0 + def pubkey_gen(seckey): x = int_from_bytes(seckey) if not (1 <= x <= n - 1): @@ -87,13 +97,13 @@ def schnorr_sign(msg, seckey0): if not (1 <= seckey0 <= n - 1): raise ValueError('The secret key must be an integer in the range 1..n-1.') P = point_mul(G, seckey0) - seckey = seckey0 if has_square_y(P) else n - seckey0 - k0 = int_from_bytes(tagged_hash("BIPSchnorrDerive", bytes_from_int(seckey) + msg)) % n + seckey = seckey0 if has_even_y(P) else n - seckey0 + k0 = int_from_bytes(tagged_hash("BIP340/nonce", bytes_from_int(seckey) + bytes_from_point(P) + msg)) % n if k0 == 0: raise RuntimeError('Failure. This happens only with negligible probability.') R = point_mul(G, k0) k = n - k0 if not has_square_y(R) else k0 - e = int_from_bytes(tagged_hash("BIPSchnorr", bytes_from_point(R) + bytes_from_point(P) + msg)) % n + e = int_from_bytes(tagged_hash("BIP340/challenge", bytes_from_point(R) + bytes_from_point(P) + msg)) % n return bytes_from_point(R) + bytes_from_int((k + e * seckey) % n) def schnorr_verify(msg, pubkey, sig): @@ -103,14 +113,14 @@ def schnorr_verify(msg, pubkey, sig): raise ValueError('The public key must be a 32-byte array.') if len(sig) != 64: raise ValueError('The signature must be a 64-byte array.') - P = point_from_bytes(pubkey) + P = lift_x_even_y(pubkey) if (P is None): return False r = int_from_bytes(sig[0:32]) s = int_from_bytes(sig[32:64]) if (r >= p or s >= n): return False - e = int_from_bytes(tagged_hash("BIPSchnorr", sig[0:32] + pubkey + msg)) % n + e = int_from_bytes(tagged_hash("BIP340/challenge", sig[0:32] + pubkey + msg)) % n R = point_add(point_mul(G, s), point_mul(P, n - e)) if R is None or not has_square_y(R) or x(R) != r: return False diff --git a/bip-0340/test-vectors.csv b/bip-0340/test-vectors.csv index 3970803..096fe2e 100644 --- a/bip-0340/test-vectors.csv +++ b/bip-0340/test-vectors.csv @@ -1,16 +1,16 @@ index,secret key,public key,message,signature,verification result,comment -0,0000000000000000000000000000000000000000000000000000000000000001,79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,0000000000000000000000000000000000000000000000000000000000000000,528F745793E8472C0329742A463F59E58F3A3F1A4AC09C28F6F8514D4D0322A258BD08398F82CF67B812AB2C7717CE566F877C2F8795C846146978E8F04782AE,TRUE, -1,B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,667C2F778E0616E611BD0C14B8A600C5884551701A949EF0EBFD72D452D64E844160BCFC3F466ECB8FACD19ADE57D8699D74E7207D78C6AEDC3799B52A8E0598,TRUE, -2,C90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B14E5C9,DD308AFEC5777E13121FA72B9CC1B7CC0139715309B086C960E18FD969774EB8,5E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C,2D941B38E32624BF0AC7669C0971B990994AF6F9B18426BF4F4E7EC10E6CDF386CF646C6DDAFCFA7F1993EEB2E4D66416AEAD1DDAE2F22D63CAD901412D116C6,TRUE, -3,0B432B2677937381AEF05BB02A66ECD012773062CF3FA2549E44F58ED2401710,25D1DFF95105F5253C4022F628A996AD3A0D95FBF21D468A1B33F8C160D8F517,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,8BD2C11604B0A87A443FCC2E5D90E5328F934161B18864FB48CE10CB59B45FB9B5B2A0F129BD88F5BDC05D5C21E5C57176B913002335784F9777A24BD317CD36,TRUE,test fails if msg is reduced modulo p or n -4,,D69C3509BB99E412E68B0FE8544E72837DFA30746D8BE2AA65975F29D22DC7B9,4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703,00000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C63EE374AC7FAE927D334CCB190F6FB8FD27A2DDC639CCEE46D43F113A4035A2C7F,TRUE, -5,,EEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,667C2F778E0616E611BD0C14B8A600C5884551701A949EF0EBFD72D452D64E844160BCFC3F466ECB8FACD19ADE57D8699D74E7207D78C6AEDC3799B52A8E0598,FALSE,public key not on the curve -6,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9935554D1AA5F0374E5CDAACB3925035C7C169B27C4426DF0A6B19AF3BAEAB138,FALSE,has_square_y(R) is false -7,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,10AC49A6A2EBF604189C5F40FC75AF2D42D77DE9A2782709B1EB4EAF1CFE9108D7003B703A3499D5E29529D39BA040A44955127140F81A8A89A96F992AC0FE79,FALSE,negated message -8,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,667C2F778E0616E611BD0C14B8A600C5884551701A949EF0EBFD72D452D64E84BE9F4303C0B9913470532E6521A827951D39F5C631CFD98CE39AC4D7A5A83BA9,FALSE,negated s value -9,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,000000000000000000000000000000000000000000000000000000000000000099D2F0EBC2996808208633CD9926BF7EC3DAB73DAAD36E85B3040A698E6D1CE0,FALSE,sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 0 -10,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,000000000000000000000000000000000000000000000000000000000000000124E81D89F01304695CE943F7D5EBD00EF726A0864B4FF33895B4E86BEADC5456,FALSE,sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 1 -11,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D4160BCFC3F466ECB8FACD19ADE57D8699D74E7207D78C6AEDC3799B52A8E0598,FALSE,sig[0:32] is not an X coordinate on the curve -12,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F4160BCFC3F466ECB8FACD19ADE57D8699D74E7207D78C6AEDC3799B52A8E0598,FALSE,sig[0:32] is equal to field size -13,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,667C2F778E0616E611BD0C14B8A600C5884551701A949EF0EBFD72D452D64E84FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,FALSE,sig[32:64] is equal to curve order -14,,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC30,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,667C2F778E0616E611BD0C14B8A600C5884551701A949EF0EBFD72D452D64E844160BCFC3F466ECB8FACD19ADE57D8699D74E7207D78C6AEDC3799B52A8E0598,FALSE,public key is not a valid X coordinate because it exceeds the field size +0,0000000000000000000000000000000000000000000000000000000000000003,F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9,0000000000000000000000000000000000000000000000000000000000000000,514F0E96BB9AD56A245A7F4ED1030D4DE3FB0F5DE285116514292B2F910C979201D5C686A9D968E169C3ED1C2249C81F2BD27D53C42D15FA275EA6445389410A,TRUE, +1,B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,74556372D3369E8C53E6B84B5D7EE9AE0220EB37A6EA5501EF828FBFBA90A864092EF727796DACA51118BE8FBD70B3EC50536E65DB6F3B3B3FE1049862018B02,TRUE, +2,C90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B14E5C9,DD308AFEC5777E13121FA72B9CC1B7CC0139715309B086C960E18FD969774EB8,7E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C,FAD73AE779EDD67BA40772867FEF9F20F151EB4BFDDECC53B90DD3017FC5D6035670DB8C83BA96EAF51C069B2AA7CEEF556787AE897F84F8D822C4ED7115B851,TRUE, +3,0B432B2677937381AEF05BB02A66ECD012773062CF3FA2549E44F58ED2401710,25D1DFF95105F5253C4022F628A996AD3A0D95FBF21D468A1B33F8C160D8F517,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,60DC1A7E50D2269424060FF66361601075EB4B516DE89BF1D91B1D6AD78900DACDA5AC4B697491430CAA7604C8D819B2150DEC26E8D01E2981DDA071D7556CD3,TRUE,test fails if msg is reduced modulo p or n +4,,D69C3509BB99E412E68B0FE8544E72837DFA30746D8BE2AA65975F29D22DC7B9,4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703,00000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C630EC50E5363E227ACAC6F542CE1C0B186657E0E0D1A6FFE283A33438DE4738419,TRUE, +5,,EEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,74556372D3369E8C53E6B84B5D7EE9AE0220EB37A6EA5501EF828FBFBA90A864092EF727796DACA51118BE8FBD70B3EC50536E65DB6F3B3B3FE1049862018B02,FALSE,public key not on the curve +6,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F995A579DA959FA739FCE39E8BD16FECB5CDCF97060B2C73CDE60E87ABCA1AA5D9,FALSE,has_square_y(R) is false +7,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,0B3E00AF0641F28B4B52F7E7AD3DDEB9BD313F9E382563BA9C9A8274F45D3D72D8F733F2901432C8DD99C739B0C1EE4030E79A94318278EC4E7160A65CDE8015,FALSE,negated message +8,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,74556372D3369E8C53E6B84B5D7EE9AE0220EB37A6EA5501EF828FBFBA90A864F6D108D88692535AEEE74170428F4C126A5B6E80D3D965007FF159F46E34B63F,FALSE,negated s value +9,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,00000000000000000000000000000000000000000000000000000000000000009915EE59F07F9DBBAEDC31BFCC9B34AD49DE669CD24773BCED77DDA36D073EC8,FALSE,sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 0 +10,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,0000000000000000000000000000000000000000000000000000000000000001C7EC918B2B9CF34071BB54BED7EB4BB6BAB148E9A7E36E6B228F95DFA08B43EC,FALSE,sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 1 +11,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D092EF727796DACA51118BE8FBD70B3EC50536E65DB6F3B3B3FE1049862018B02,FALSE,sig[0:32] is not an X coordinate on the curve +12,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F092EF727796DACA51118BE8FBD70B3EC50536E65DB6F3B3B3FE1049862018B02,FALSE,sig[0:32] is equal to field size +13,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,74556372D3369E8C53E6B84B5D7EE9AE0220EB37A6EA5501EF828FBFBA90A864FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,FALSE,sig[32:64] is equal to curve order +14,,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC30,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,74556372D3369E8C53E6B84B5D7EE9AE0220EB37A6EA5501EF828FBFBA90A864092EF727796DACA51118BE8FBD70B3EC50536E65DB6F3B3B3FE1049862018B02,FALSE,public key is not a valid X coordinate because it exceeds the field size diff --git a/bip-0340/test-vectors.py b/bip-0340/test-vectors.py index 195b61b..d4674e9 100644 --- a/bip-0340/test-vectors.py +++ b/bip-0340/test-vectors.py @@ -2,14 +2,24 @@ import sys from reference import * def vector0(): - seckey = bytes_from_int(1) + seckey = bytes_from_int(3) msg = bytes_from_int(0) sig = schnorr_sign(msg, seckey) pubkey = pubkey_gen(seckey) - # The point reconstructed from the public key has an even Y coordinate. - pubkey_point = point_from_bytes(pubkey) - assert(pubkey_point[1] & 1 == 0) + # We should have at least one test vector where the seckey needs to be + # negated and one where it doesn't. In this one the seckey doesn't need to + # be negated. + x = int_from_bytes(seckey) + P = point_mul(G, x) + assert(y(P) % 2 == 0) + + # For historic reasons (pubkey tiebreaker was squareness and not evenness) + # we should have at least one test vector where the the point reconstructed + # from the public key has a square and one where it has a non-square Y + # coordinate. In this one Y is non-square. + pubkey_point = lift_x_even_y(pubkey) + assert(not has_square_y(pubkey_point)) return (seckey, pubkey, msg, sig, "TRUE", None) @@ -17,28 +27,33 @@ def vector1(): seckey = bytes_from_int(0xB7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF) msg = bytes_from_int(0x243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89) sig = schnorr_sign(msg, seckey) - pubkey = pubkey_gen(seckey) - - # The point reconstructed from the public key has an odd Y coordinate. - pubkey_point = point_from_bytes(pubkey) - assert(pubkey_point[1] & 1 == 1) - - return (seckey, pubkey, msg, sig, "TRUE", None) + return (seckey, pubkey_gen(seckey), msg, sig, "TRUE", None) def vector2(): seckey = bytes_from_int(0xC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B14E5C9) - msg = bytes_from_int(0x5E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C) + msg = bytes_from_int(0x7E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C) sig = schnorr_sign(msg, seckey) + # The point reconstructed from the public key has a square Y coordinate. + pubkey = pubkey_gen(seckey) + pubkey_point = lift_x_even_y(pubkey) + assert(has_square_y(pubkey_point)) + # This signature vector would not verify if the implementer checked the # squareness of the X coordinate of R instead of the Y coordinate. - R = point_from_bytes(sig[0:32]) + R = lift_x_square_y(sig[0:32]) assert(not is_square(R[0])) - return (seckey, pubkey_gen(seckey), msg, sig, "TRUE", None) + return (seckey, pubkey, msg, sig, "TRUE", None) def vector3(): seckey = bytes_from_int(0x0B432B2677937381AEF05BB02A66ECD012773062CF3FA2549E44F58ED2401710) + + # Need to negate this seckey before signing + x = int_from_bytes(seckey) + P = point_mul(G, x) + assert(y(P) % 2 != 0) + msg = bytes_from_int(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF) sig = schnorr_sign(msg, seckey) return (seckey, pubkey_gen(seckey), msg, sig, "TRUE", "test fails if msg is reduced modulo p or n") @@ -53,9 +68,9 @@ def insecure_schnorr_sign_fixed_nonce(msg, seckey0, k): if not (1 <= seckey0 <= n - 1): raise ValueError('The secret key must be an integer in the range 1..n-1.') P = point_mul(G, seckey0) - seckey = seckey0 if has_square_y(P) else n - seckey0 + seckey = seckey0 if has_even_y(P) else n - seckey0 R = point_mul(G, k) - e = int_from_bytes(tagged_hash("BIPSchnorr", bytes_from_point(R) + bytes_from_point(P) + msg)) % n + e = int_from_bytes(tagged_hash("BIP340/challenge", bytes_from_point(R) + bytes_from_point(P) + msg)) % n return bytes_from_point(R) + bytes_from_int((k + e * seckey) % n) # Creates a singature with a small x(R) by using k = 1/2 @@ -78,7 +93,7 @@ def vector5(): sig = schnorr_sign(msg, seckey) pubkey = bytes_from_int(0xEEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34) - assert(point_from_bytes(pubkey) is None) + assert(lift_x_even_y(pubkey) is None) return (None, pubkey, msg, sig, "FALSE", "public key not on the curve") @@ -156,7 +171,7 @@ def vector11(): # Replace R's X coordinate with an X coordinate that's not on the curve x_not_on_curve = bytes_from_int(0x4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D) - assert(point_from_bytes(x_not_on_curve) is None) + assert(lift_x_square_y(x_not_on_curve) is None) sig = x_not_on_curve + sig[32:64] return (None, pubkey_gen(seckey), msg, sig, "FALSE", "sig[0:32] is not an X coordinate on the curve") @@ -201,10 +216,10 @@ def vector14(): pubkey_int = p + 1 pubkey = bytes_from_int(pubkey_int) - assert(point_from_bytes(pubkey) is None) + assert(lift_x_even_y(pubkey) is None) # If an implementation would reduce a given public key modulo p then the # pubkey would be valid - assert(point_from_bytes(bytes_from_int(pubkey_int % p)) is not None) + assert(lift_x_even_y(bytes_from_int(pubkey_int % p)) is not None) return (None, pubkey, msg, sig, "FALSE", "public key is not a valid X coordinate because it exceeds the field size") -- cgit v1.2.3 From b6b5f58e6e919a485604ce7037f650e1ae54969f Mon Sep 17 00:00:00 2001 From: Jonas Nick Date: Mon, 3 Feb 2020 21:56:03 +0000 Subject: BIP 340: Use synthetic nonces in reference code and test vectors --- bip-0340/reference.py | 15 ++++++++--- bip-0340/test-vectors.csv | 32 +++++++++++----------- bip-0340/test-vectors.py | 68 ++++++++++++++++++++++++++--------------------- 3 files changed, 64 insertions(+), 51 deletions(-) diff --git a/bip-0340/reference.py b/bip-0340/reference.py index 9b5592e..1ada7f1 100644 --- a/bip-0340/reference.py +++ b/bip-0340/reference.py @@ -51,6 +51,9 @@ def bytes_from_int(x): def bytes_from_point(P): return bytes_from_int(x(P)) +def xor_bytes(b0, b1): + return bytes(x ^ y for (x, y) in zip(b0, b1)) + def lift_x_square_y(b): x = int_from_bytes(b) if x >= p: @@ -90,15 +93,18 @@ def pubkey_gen(seckey): P = point_mul(G, x) return bytes_from_point(P) -def schnorr_sign(msg, seckey0): +def schnorr_sign(msg, seckey0, aux_rand): if len(msg) != 32: raise ValueError('The message must be a 32-byte array.') seckey0 = int_from_bytes(seckey0) if not (1 <= seckey0 <= n - 1): raise ValueError('The secret key must be an integer in the range 1..n-1.') + if len(aux_rand) != 32: + raise ValueError('aux_rand must be 32 bytes instead of %i.' % len(aux_rand)) P = point_mul(G, seckey0) seckey = seckey0 if has_even_y(P) else n - seckey0 - k0 = int_from_bytes(tagged_hash("BIP340/nonce", bytes_from_int(seckey) + bytes_from_point(P) + msg)) % n + t = xor_bytes(bytes_from_int(seckey), tagged_hash("BIP340/aux", aux_rand)) + k0 = int_from_bytes(tagged_hash("BIP340/nonce", t + bytes_from_point(P) + msg)) % n if k0 == 0: raise RuntimeError('Failure. This happens only with negligible probability.') R = point_mul(G, k0) @@ -137,7 +143,7 @@ def test_vectors(): reader = csv.reader(csvfile) reader.__next__() for row in reader: - (index, seckey, pubkey, msg, sig, result, comment) = row + (index, seckey, pubkey, aux_rand, msg, sig, result, comment) = row pubkey = bytes.fromhex(pubkey) msg = bytes.fromhex(msg) sig = bytes.fromhex(sig) @@ -150,7 +156,8 @@ def test_vectors(): print(' * Failed key generation.') print(' Expected key:', pubkey.hex().upper()) print(' Actual key:', pubkey_actual.hex().upper()) - sig_actual = schnorr_sign(msg, seckey) + aux_rand = bytes.fromhex(aux_rand) + sig_actual = schnorr_sign(msg, seckey, aux_rand) if sig == sig_actual: print(' * Passed signing test.') else: diff --git a/bip-0340/test-vectors.csv b/bip-0340/test-vectors.csv index 096fe2e..beaef5a 100644 --- a/bip-0340/test-vectors.csv +++ b/bip-0340/test-vectors.csv @@ -1,16 +1,16 @@ -index,secret key,public key,message,signature,verification result,comment -0,0000000000000000000000000000000000000000000000000000000000000003,F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9,0000000000000000000000000000000000000000000000000000000000000000,514F0E96BB9AD56A245A7F4ED1030D4DE3FB0F5DE285116514292B2F910C979201D5C686A9D968E169C3ED1C2249C81F2BD27D53C42D15FA275EA6445389410A,TRUE, -1,B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,74556372D3369E8C53E6B84B5D7EE9AE0220EB37A6EA5501EF828FBFBA90A864092EF727796DACA51118BE8FBD70B3EC50536E65DB6F3B3B3FE1049862018B02,TRUE, -2,C90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B14E5C9,DD308AFEC5777E13121FA72B9CC1B7CC0139715309B086C960E18FD969774EB8,7E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C,FAD73AE779EDD67BA40772867FEF9F20F151EB4BFDDECC53B90DD3017FC5D6035670DB8C83BA96EAF51C069B2AA7CEEF556787AE897F84F8D822C4ED7115B851,TRUE, -3,0B432B2677937381AEF05BB02A66ECD012773062CF3FA2549E44F58ED2401710,25D1DFF95105F5253C4022F628A996AD3A0D95FBF21D468A1B33F8C160D8F517,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,60DC1A7E50D2269424060FF66361601075EB4B516DE89BF1D91B1D6AD78900DACDA5AC4B697491430CAA7604C8D819B2150DEC26E8D01E2981DDA071D7556CD3,TRUE,test fails if msg is reduced modulo p or n -4,,D69C3509BB99E412E68B0FE8544E72837DFA30746D8BE2AA65975F29D22DC7B9,4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703,00000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C630EC50E5363E227ACAC6F542CE1C0B186657E0E0D1A6FFE283A33438DE4738419,TRUE, -5,,EEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,74556372D3369E8C53E6B84B5D7EE9AE0220EB37A6EA5501EF828FBFBA90A864092EF727796DACA51118BE8FBD70B3EC50536E65DB6F3B3B3FE1049862018B02,FALSE,public key not on the curve -6,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F995A579DA959FA739FCE39E8BD16FECB5CDCF97060B2C73CDE60E87ABCA1AA5D9,FALSE,has_square_y(R) is false -7,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,0B3E00AF0641F28B4B52F7E7AD3DDEB9BD313F9E382563BA9C9A8274F45D3D72D8F733F2901432C8DD99C739B0C1EE4030E79A94318278EC4E7160A65CDE8015,FALSE,negated message -8,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,74556372D3369E8C53E6B84B5D7EE9AE0220EB37A6EA5501EF828FBFBA90A864F6D108D88692535AEEE74170428F4C126A5B6E80D3D965007FF159F46E34B63F,FALSE,negated s value -9,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,00000000000000000000000000000000000000000000000000000000000000009915EE59F07F9DBBAEDC31BFCC9B34AD49DE669CD24773BCED77DDA36D073EC8,FALSE,sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 0 -10,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,0000000000000000000000000000000000000000000000000000000000000001C7EC918B2B9CF34071BB54BED7EB4BB6BAB148E9A7E36E6B228F95DFA08B43EC,FALSE,sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 1 -11,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D092EF727796DACA51118BE8FBD70B3EC50536E65DB6F3B3B3FE1049862018B02,FALSE,sig[0:32] is not an X coordinate on the curve -12,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F092EF727796DACA51118BE8FBD70B3EC50536E65DB6F3B3B3FE1049862018B02,FALSE,sig[0:32] is equal to field size -13,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,74556372D3369E8C53E6B84B5D7EE9AE0220EB37A6EA5501EF828FBFBA90A864FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,FALSE,sig[32:64] is equal to curve order -14,,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC30,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,74556372D3369E8C53E6B84B5D7EE9AE0220EB37A6EA5501EF828FBFBA90A864092EF727796DACA51118BE8FBD70B3EC50536E65DB6F3B3B3FE1049862018B02,FALSE,public key is not a valid X coordinate because it exceeds the field size +index,secret key,public key,aux_rand,message,signature,verification result,comment +0,0000000000000000000000000000000000000000000000000000000000000003,F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9,0000000000000000000000000000000000000000000000000000000000000000,0000000000000000000000000000000000000000000000000000000000000000,067E337AD551B2276EC705E43F0920926A9CE08AC68159F9D258C9BBA412781C9F059FCDF4824F13B3D7C1305316F956704BB3FEA2C26142E18ACD90A90C947E,TRUE, +1,B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,0000000000000000000000000000000000000000000000000000000000000001,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,0E12B8C520948A776753A96F21ABD7FDC2D7D0C0DDC90851BE17B04E75EF86A47EF0DA46C4DC4D0D1BCB8668C2CE16C54C7C23A6716EDE303AF86774917CF928,TRUE, +2,C90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B14E5C9,DD308AFEC5777E13121FA72B9CC1B7CC0139715309B086C960E18FD969774EB8,C87AA53824B4D7AE2EB035A2B5BBBCCC080E76CDC6D1692C4B0B62D798E6D906,7E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C,FC012F9FB8FE00A358F51EF93DCE0DC0C895F6E9A87C6C4905BC820B0C3677616B8737D14E703AF8E16E22E5B8F26227D41E5128F82D86F747244CC289C74D1D,TRUE, +3,0B432B2677937381AEF05BB02A66ECD012773062CF3FA2549E44F58ED2401710,25D1DFF95105F5253C4022F628A996AD3A0D95FBF21D468A1B33F8C160D8F517,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,FC132D4E426DFF535AEC0FA7083AC5118BC1D5FFFD848ABD8290C23F271CA0DD11AEDCEA3F55DA9BD677FE29C9DDA0CF878BCE43FDE0E313D69D1AF7A5AE8369,TRUE,test fails if msg is reduced modulo p or n +4,,D69C3509BB99E412E68B0FE8544E72837DFA30746D8BE2AA65975F29D22DC7B9,,4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703,00000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C630EC50E5363E227ACAC6F542CE1C0B186657E0E0D1A6FFE283A33438DE4738419,TRUE, +5,,EEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,7036D6BFE1837AE919631039A2CF652A295DFAC9A8BBB0806014B2F48DD7C807941607B563ABBA414287F374A332BA3636DE009EE1EF551A17796B72B68B8A24,FALSE,public key not on the curve +6,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F995A579DA959FA739FCE39E8BD16FECB5CDCF97060B2C73CDE60E87ABCA1AA5D9,FALSE,has_square_y(R) is false +7,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,F8704654F4687B7365ED32E796DE92761390A3BCC495179BFE073817B7ED32824E76B987F7C1F9A751EF5C343F7645D3CFFC7D570B9A7192EBF1898E1344E3BF,FALSE,negated message +8,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,7036D6BFE1837AE919631039A2CF652A295DFAC9A8BBB0806014B2F48DD7C8076BE9F84A9C5445BEBD780C8B5CCD45C883D0DC47CD594B21A858F31A19AAB71D,FALSE,negated s value +9,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,00000000000000000000000000000000000000000000000000000000000000009915EE59F07F9DBBAEDC31BFCC9B34AD49DE669CD24773BCED77DDA36D073EC8,FALSE,sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 0 +10,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,0000000000000000000000000000000000000000000000000000000000000001C7EC918B2B9CF34071BB54BED7EB4BB6BAB148E9A7E36E6B228F95DFA08B43EC,FALSE,sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 1 +11,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D941607B563ABBA414287F374A332BA3636DE009EE1EF551A17796B72B68B8A24,FALSE,sig[0:32] is not an X coordinate on the curve +12,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F941607B563ABBA414287F374A332BA3636DE009EE1EF551A17796B72B68B8A24,FALSE,sig[0:32] is equal to field size +13,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,7036D6BFE1837AE919631039A2CF652A295DFAC9A8BBB0806014B2F48DD7C807FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,FALSE,sig[32:64] is equal to curve order +14,,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC30,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,7036D6BFE1837AE919631039A2CF652A295DFAC9A8BBB0806014B2F48DD7C807941607B563ABBA414287F374A332BA3636DE009EE1EF551A17796B72B68B8A24,FALSE,public key is not a valid X coordinate because it exceeds the field size diff --git a/bip-0340/test-vectors.py b/bip-0340/test-vectors.py index d4674e9..d1a52c8 100644 --- a/bip-0340/test-vectors.py +++ b/bip-0340/test-vectors.py @@ -4,7 +4,8 @@ from reference import * def vector0(): seckey = bytes_from_int(3) msg = bytes_from_int(0) - sig = schnorr_sign(msg, seckey) + aux_rand = bytes_from_int(0) + sig = schnorr_sign(msg, seckey, aux_rand) pubkey = pubkey_gen(seckey) # We should have at least one test vector where the seckey needs to be @@ -21,18 +22,21 @@ def vector0(): pubkey_point = lift_x_even_y(pubkey) assert(not has_square_y(pubkey_point)) - return (seckey, pubkey, msg, sig, "TRUE", None) + return (seckey, pubkey, aux_rand, msg, sig, "TRUE", None) def vector1(): seckey = bytes_from_int(0xB7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF) msg = bytes_from_int(0x243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89) - sig = schnorr_sign(msg, seckey) - return (seckey, pubkey_gen(seckey), msg, sig, "TRUE", None) + aux_rand = bytes_from_int(1) + + sig = schnorr_sign(msg, seckey, aux_rand) + return (seckey, pubkey_gen(seckey), aux_rand, msg, sig, "TRUE", None) def vector2(): seckey = bytes_from_int(0xC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B14E5C9) msg = bytes_from_int(0x7E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C) - sig = schnorr_sign(msg, seckey) + aux_rand = bytes_from_int(0xC87AA53824B4D7AE2EB035A2B5BBBCCC080E76CDC6D1692C4B0B62D798E6D906) + sig = schnorr_sign(msg, seckey, aux_rand) # The point reconstructed from the public key has a square Y coordinate. pubkey = pubkey_gen(seckey) @@ -44,7 +48,7 @@ def vector2(): R = lift_x_square_y(sig[0:32]) assert(not is_square(R[0])) - return (seckey, pubkey, msg, sig, "TRUE", None) + return (seckey, pubkey, aux_rand, msg, sig, "TRUE", None) def vector3(): seckey = bytes_from_int(0x0B432B2677937381AEF05BB02A66ECD012773062CF3FA2549E44F58ED2401710) @@ -55,8 +59,10 @@ def vector3(): assert(y(P) % 2 != 0) msg = bytes_from_int(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF) - sig = schnorr_sign(msg, seckey) - return (seckey, pubkey_gen(seckey), msg, sig, "TRUE", "test fails if msg is reduced modulo p or n") + aux_rand = bytes_from_int(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF) + + sig = schnorr_sign(msg, seckey, aux_rand) + return (seckey, pubkey_gen(seckey), aux_rand, msg, sig, "TRUE", "test fails if msg is reduced modulo p or n") # Signs with a given nonce. This can be INSECURE and is only INTENDED FOR # GENERATING TEST VECTORS. Results in an invalid signature if y(kG) is not @@ -79,10 +85,11 @@ def vector4(): seckey = bytes_from_int(0x763758E5CBEEDEE4F7D3FC86F531C36578933228998226672F13C4F0EBE855EB) msg = bytes_from_int(0x4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703) sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, one_half) - return (None, pubkey_gen(seckey), msg, sig, "TRUE", None) + return (None, pubkey_gen(seckey), None, msg, sig, "TRUE", None) default_seckey = bytes_from_int(0xB7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF) default_msg = bytes_from_int(0x243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89) +default_aux_rand = bytes_from_int(0xC87AA53824B4D7AE2EB035A2B5BBBCCC080E76CDC6D1692C4B0B62D798E6D906) # Public key is not on the curve def vector5(): @@ -90,12 +97,12 @@ def vector5(): # public key. seckey = default_seckey msg = default_msg - sig = schnorr_sign(msg, seckey) + sig = schnorr_sign(msg, seckey, default_aux_rand) pubkey = bytes_from_int(0xEEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34) assert(lift_x_even_y(pubkey) is None) - return (None, pubkey, msg, sig, "FALSE", "public key not on the curve") + return (None, pubkey, None, msg, sig, "FALSE", "public key not on the curve") def vector6(): seckey = default_seckey @@ -107,21 +114,21 @@ def vector6(): R = point_mul(G, k) assert(not has_square_y(R)) - return (None, pubkey_gen(seckey), msg, sig, "FALSE", "has_square_y(R) is false") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "has_square_y(R) is false") def vector7(): seckey = default_seckey msg = int_from_bytes(default_msg) neg_msg = bytes_from_int(n - msg) - sig = schnorr_sign(neg_msg, seckey) - return (None, pubkey_gen(seckey), bytes_from_int(msg), sig, "FALSE", "negated message") + sig = schnorr_sign(neg_msg, seckey, default_aux_rand) + return (None, pubkey_gen(seckey), None, bytes_from_int(msg), sig, "FALSE", "negated message") def vector8(): seckey = default_seckey msg = default_msg - sig = schnorr_sign(msg, seckey) + sig = schnorr_sign(msg, seckey, default_aux_rand) sig = sig[0:32] + bytes_from_int(n - int_from_bytes(sig[32:64])) - return (None, pubkey_gen(seckey), msg, sig, "FALSE", "negated s value") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "negated s value") def bytes_from_point_inf0(P): if P == None: @@ -140,7 +147,7 @@ def vector9(): sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, k) bytes_from_point.__code__ = bytes_from_point_tmp - return (None, pubkey_gen(seckey), msg, sig, "FALSE", "sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 0") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 0") def bytes_from_point_inf1(P): if P == None: @@ -159,7 +166,7 @@ def vector10(): sig = insecure_schnorr_sign_fixed_nonce(msg, seckey, k) bytes_from_point.__code__ = bytes_from_point_tmp - return (None, pubkey_gen(seckey), msg, sig, "FALSE", "sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 1") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sG - eP is infinite. Test fails in single verification if has_square_y(inf) is defined as true and x(inf) as 1") # It's cryptographically impossible to create a test vector that fails if run # in an implementation which merely misses the check that sig[0:32] is an X @@ -167,14 +174,14 @@ def vector10(): def vector11(): seckey = default_seckey msg = default_msg - sig = schnorr_sign(msg, seckey) + sig = schnorr_sign(msg, seckey, default_aux_rand) # Replace R's X coordinate with an X coordinate that's not on the curve x_not_on_curve = bytes_from_int(0x4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D) assert(lift_x_square_y(x_not_on_curve) is None) sig = x_not_on_curve + sig[32:64] - return (None, pubkey_gen(seckey), msg, sig, "FALSE", "sig[0:32] is not an X coordinate on the curve") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sig[0:32] is not an X coordinate on the curve") # It's cryptographically impossible to create a test vector that fails if run # in an implementation which merely misses the check that sig[0:32] is smaller @@ -182,12 +189,12 @@ def vector11(): def vector12(): seckey = default_seckey msg = default_msg - sig = schnorr_sign(msg, seckey) + sig = schnorr_sign(msg, seckey, default_aux_rand) # Replace R's X coordinate with an X coordinate that's equal to field size sig = bytes_from_int(p) + sig[32:64] - return (None, pubkey_gen(seckey), msg, sig, "FALSE", "sig[0:32] is equal to field size") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sig[0:32] is equal to field size") # It's cryptographically impossible to create a test vector that fails if run # in an implementation which merely misses the check that sig[32:64] is smaller @@ -195,12 +202,12 @@ def vector12(): def vector13(): seckey = default_seckey msg = default_msg - sig = schnorr_sign(msg, seckey) + sig = schnorr_sign(msg, seckey, default_aux_rand) # Replace s with a number that's equal to the curve order sig = sig[0:32] + bytes_from_int(n) - return (None, pubkey_gen(seckey), msg, sig, "FALSE", "sig[32:64] is equal to curve order") + return (None, pubkey_gen(seckey), None, msg, sig, "FALSE", "sig[32:64] is equal to curve order") # Test out of range pubkey # It's cryptographically impossible to create a test vector that fails if run @@ -212,8 +219,7 @@ def vector14(): # public key. seckey = default_seckey msg = default_msg - sig = schnorr_sign(msg, seckey) - + sig = schnorr_sign(msg, seckey, default_aux_rand) pubkey_int = p + 1 pubkey = bytes_from_int(pubkey_int) assert(lift_x_even_y(pubkey) is None) @@ -221,7 +227,7 @@ def vector14(): # pubkey would be valid assert(lift_x_even_y(bytes_from_int(pubkey_int % p)) is not None) - return (None, pubkey, msg, sig, "FALSE", "public key is not a valid X coordinate because it exceeds the field size") + return (None, pubkey, None, msg, sig, "FALSE", "public key is not a valid X coordinate because it exceeds the field size") vectors = [ vector0(), @@ -242,14 +248,14 @@ vectors = [ ] # Converts the byte strings of a test vector into hex strings -def bytes_to_hex(seckey, pubkey, msg, sig, result, comment): - return (seckey.hex().upper() if seckey is not None else None, pubkey.hex().upper(), msg.hex().upper(), sig.hex().upper(), result, comment) +def bytes_to_hex(seckey, pubkey, aux_rand, msg, sig, result, comment): + return (seckey.hex().upper() if seckey is not None else None, pubkey.hex().upper(), aux_rand.hex().upper() if aux_rand is not None else None, msg.hex().upper(), sig.hex().upper(), result, comment) -vectors = list(map(lambda vector: bytes_to_hex(vector[0], vector[1], vector[2], vector[3], vector[4], vector[5]), vectors)) +vectors = list(map(lambda vector: bytes_to_hex(vector[0], vector[1], vector[2], vector[3], vector[4], vector[5], vector[6]), vectors)) def print_csv(vectors): writer = csv.writer(sys.stdout) - writer.writerow(("index", "secret key", "public key", "message", "signature", "verification result", "comment")) + writer.writerow(("index", "secret key", "public key", "aux_rand", "message", "signature", "verification result", "comment")) for (i,v) in enumerate(vectors): writer.writerow((i,)+v) -- cgit v1.2.3 From 9bfa53e9fb4af9f17d63806fe0710f18203c94c9 Mon Sep 17 00:00:00 2001 From: Jonas Nick Date: Mon, 24 Feb 2020 17:01:19 +0000 Subject: BIP 340: Verify sig before returning it --- bip-0340/reference.py | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) diff --git a/bip-0340/reference.py b/bip-0340/reference.py index 1ada7f1..79f9578 100644 --- a/bip-0340/reference.py +++ b/bip-0340/reference.py @@ -110,7 +110,10 @@ def schnorr_sign(msg, seckey0, aux_rand): R = point_mul(G, k0) k = n - k0 if not has_square_y(R) else k0 e = int_from_bytes(tagged_hash("BIP340/challenge", bytes_from_point(R) + bytes_from_point(P) + msg)) % n - return bytes_from_point(R) + bytes_from_int((k + e * seckey) % n) + sig = bytes_from_point(R) + bytes_from_int((k + e * seckey) % n) + if not schnorr_verify(msg, bytes_from_point(P), sig): + raise RuntimeError('The signature does not pass verification.') + return sig def schnorr_verify(msg, pubkey, sig): if len(msg) != 32: -- cgit v1.2.3 From 4ea021f28c9f919679ae2774890b3061dd13fd6d Mon Sep 17 00:00:00 2001 From: Jonas Nick Date: Tue, 3 Mar 2020 12:06:55 +0000 Subject: BIP-0341: Avoid decompressing the output public key in script spends --- bip-0341.mediawiki | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) diff --git a/bip-0341.mediawiki b/bip-0341.mediawiki index c6efaab..6472430 100644 --- a/bip-0341.mediawiki +++ b/bip-0341.mediawiki @@ -75,8 +75,8 @@ The following rules only apply when such an output is being spent. Any other out **** If ''kj ≥ ej'': ''kj+1 = hashTapBranch(ej || kj)''. ** Let ''t = hashTapTweak(p || km)''. ** If ''t ≥ 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141'' (order of secp256k1), fail. -** Let ''Q = lift_x_even_y(int(q)) if (c[0] & 1) = 0 and -lift_x_even_y(int(q)) otherwise'''''Why is it necessary to reveal a bit to indicate if the point represented by the output public key is negated in a script path spend?''' The ''lift_x_even_y'' function (defined in [[bip-0340.mediawiki#design|BIP340]]) always constructs a point with an even Y coordinate, but because ''Q'' is constructed by adding the taproot tweak to the internal public key ''P'', it cannot easily be guaranteed that ''Q'' in fact has such a Y coordinate. Therefore, before verifying the taproot tweak the original point is restored by negating if necessary. We can not ignore the Y coordinate because it would prevent batch verification. Trying out multiple internal keys until there's such a ''Q'' is possible but undesirable and unnecessary since this information about the Y coordinate only consumes an unused bit.. Fail if this point is not on the curve. -** If ''Q ≠ P + int(t)G'', fail. +** Let ''Q = P + int(t)G''. +** If ''q ≠ x(Q)'' or ''c[0] & 1 ≠ y(Q) mod 2'', fail'''Why is it necessary to reveal a bit in a script path spend and check that it matches the parity of the Y coordinate of ''Q''?''' The parity of the Y coordinate is necessary to lift the X coordinate ''q'' to a unique point. While this is not strictly necessary for verifying the taproot commitment as described above, it is necessary to allow batch verification. Alternatively, ''Q'' could be forced to have an even Y coordinate, but that would require retrying with different internal public keys (or different messages) until ''Q'' has that property. There is no downside to adding the parity bit because otherwise the control block bit would be unused.. ** Execute the script, according to the applicable script rules'''What are the applicable script rules in script path spends?''' [[bip-0342.mediawiki|BIP342]] specifies validity rules that apply for leaf version 0xc0, but future proposals can introduce rules for other leaf versions., using the witness stack elements excluding the script ''s'', the control block ''c'', and the annex ''a'' if present, as initial stack. ''q'' is referred to as ''taproot output key'' and ''p'' as ''taproot internal key''. @@ -87,7 +87,7 @@ We first define a reusable common signature message calculation function, follow ==== Common signature message ==== -The function ''SigMsg(hash_type, ext_flag)'' computes the message being signed as a byte array. It is implicitly also a function of the spending transaction and the outputs it spends, but these are not listed to keep notation simple. +The function ''SigMsg(hash_type, ext_flag)'' computes the message being signed as a byte array. It is implicitly also a function of the spending transaction and the outputs it spends, but these are not listed to keep notation simple. The parameter ''hash_type'' is an 8-bit unsigned value. The SIGHASH encodings from the legacy script system are reused, including SIGHASH_ALL, SIGHASH_NONE, SIGHASH_SINGLE, and SIGHASH_ANYONECANPAY, plus the default ''hash_type'' value ''0x00'' which results in signing over the whole transaction just as for SIGHASH_ALL. The following restrictions apply, which cause validation failure if violated: * Using any undefined ''hash_type'' (not ''0x00'', ''0x01'', ''0x02'', ''0x03'', ''0x81'', ''0x82'', or ''0x83'''''Why reject unknown ''hash_type'' values?''' By doing so, it is easier to reason about the worst case amount of signature hashing an implementation with adequate caching must perform.). -- cgit v1.2.3 From a6301c5af08d39121c1e1e7dc9ad1b9e9fe45942 Mon Sep 17 00:00:00 2001 From: Tim Ruffing Date: Wed, 4 Mar 2020 21:21:36 +0100 Subject: Optionally print intermediate values in reference code and make reference code and pseudocode more consistent with each other --- bip-0340.mediawiki | 6 ++--- bip-0340/reference.py | 68 +++++++++++++++++++++++++++++++++++++++------------ 2 files changed, 56 insertions(+), 18 deletions(-) diff --git a/bip-0340.mediawiki b/bip-0340.mediawiki index 883ef3a..b4e5f60 100644 --- a/bip-0340.mediawiki +++ b/bip-0340.mediawiki @@ -136,9 +136,9 @@ Input: * The secret key ''sk'': a 32-byte array, freshly generated uniformly at random The algorithm ''PubKey(sk)'' is defined as: -* Let ''d = int(sk)''. -* Fail if ''d = 0'' or ''d ≥ n''. -* Return ''bytes(d⋅G)''. +* Let ''d' = int(sk)''. +* Fail if ''d' = 0'' or ''d' ≥ n''. +* Return ''bytes(d'⋅G)''. Note that we use a very different public key format (32 bytes) than the ones used by existing systems (which typically use elliptic curve points as public keys, or 33-byte or 65-byte encodings of them). A side effect is that ''PubKey(sk) = PubKey(bytes(n - int(sk))'', so every public key has two corresponding secret keys. diff --git a/bip-0340/reference.py b/bip-0340/reference.py index 79f9578..d6106fd 100644 --- a/bip-0340/reference.py +++ b/bip-0340/reference.py @@ -1,6 +1,15 @@ import hashlib import binascii +# Set DEBUG to True to get a detailed debug output including +# intermediate values during key generation, signing, and +# verification. This is implemented via calls to the +# debug_print_vars() function. +# +# If you want to print values on an individual basis, use +# the pretty() function, e.g., print(pretty(foo)). +DEBUG = False + p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 @@ -62,7 +71,7 @@ def lift_x_square_y(b): y = pow(y_sq, (p + 1) // 4, p) if pow(y, 2, p) != y_sq: return None - return [x, y] + return (x, y) def lift_x_even_y(b): P = lift_x_square_y(b) @@ -87,32 +96,37 @@ def has_even_y(P): return y(P) % 2 == 0 def pubkey_gen(seckey): - x = int_from_bytes(seckey) - if not (1 <= x <= n - 1): + d0 = int_from_bytes(seckey) + if not (1 <= d0 <= n - 1): + debug_print_vars() raise ValueError('The secret key must be an integer in the range 1..n-1.') - P = point_mul(G, x) + P = point_mul(G, d0) return bytes_from_point(P) -def schnorr_sign(msg, seckey0, aux_rand): +def schnorr_sign(msg, seckey, aux_rand): if len(msg) != 32: + debug_print_vars() raise ValueError('The message must be a 32-byte array.') - seckey0 = int_from_bytes(seckey0) - if not (1 <= seckey0 <= n - 1): + d0 = int_from_bytes(seckey) + if not (1 <= d0 <= n - 1): raise ValueError('The secret key must be an integer in the range 1..n-1.') if len(aux_rand) != 32: raise ValueError('aux_rand must be 32 bytes instead of %i.' % len(aux_rand)) - P = point_mul(G, seckey0) - seckey = seckey0 if has_even_y(P) else n - seckey0 - t = xor_bytes(bytes_from_int(seckey), tagged_hash("BIP340/aux", aux_rand)) + P = point_mul(G, d0) + d = d0 if has_even_y(P) else n - d0 + t = xor_bytes(bytes_from_int(d), tagged_hash("BIP340/aux", aux_rand)) k0 = int_from_bytes(tagged_hash("BIP340/nonce", t + bytes_from_point(P) + msg)) % n if k0 == 0: + debug_print_vars() raise RuntimeError('Failure. This happens only with negligible probability.') R = point_mul(G, k0) k = n - k0 if not has_square_y(R) else k0 e = int_from_bytes(tagged_hash("BIP340/challenge", bytes_from_point(R) + bytes_from_point(P) + msg)) % n - sig = bytes_from_point(R) + bytes_from_int((k + e * seckey) % n) + sig = bytes_from_point(R) + bytes_from_int((k + e * d) % n) if not schnorr_verify(msg, bytes_from_point(P), sig): + debug_print_vars() raise RuntimeError('The signature does not pass verification.') + debug_print_vars() return sig def schnorr_verify(msg, pubkey, sig): @@ -123,26 +137,29 @@ def schnorr_verify(msg, pubkey, sig): if len(sig) != 64: raise ValueError('The signature must be a 64-byte array.') P = lift_x_even_y(pubkey) - if (P is None): - return False r = int_from_bytes(sig[0:32]) s = int_from_bytes(sig[32:64]) - if (r >= p or s >= n): + if (P is None) or (r >= p) or (s >= n): + debug_print_vars() return False e = int_from_bytes(tagged_hash("BIP340/challenge", sig[0:32] + pubkey + msg)) % n R = point_add(point_mul(G, s), point_mul(P, n - e)) if R is None or not has_square_y(R) or x(R) != r: + debug_print_vars() return False + debug_print_vars() return True # # The following code is only used to verify the test vectors. # import csv +import os +import sys def test_vectors(): all_passed = True - with open('test-vectors.csv', newline='') as csvfile: + with open(os.path.join(sys.path[0], 'test-vectors.csv'), newline='') as csvfile: reader = csv.reader(csvfile) reader.__next__() for row in reader: @@ -185,5 +202,26 @@ def test_vectors(): print('Some test vectors failed.') return all_passed +# +# The following code is only used for debugging +# +import inspect + +def pretty(v): + if isinstance(v, bytes): + return '0x' + v.hex() + if isinstance(v, int): + return pretty(bytes_from_int(v)) + if isinstance(v, tuple): + return tuple(map(pretty, v)) + return v + +def debug_print_vars(): + if DEBUG: + frame = inspect.currentframe().f_back + print(' Variables in function ', frame.f_code.co_name, ' at line ', frame.f_lineno, ':', sep='') + for var_name, var_val in frame.f_locals.items(): + print(' ' + var_name.rjust(11, ' '), '==', pretty(var_val)) + if __name__ == '__main__': test_vectors() -- cgit v1.2.3 From 8c5be9197540e1673187ff099b5fe40ce09c9216 Mon Sep 17 00:00:00 2001 From: Tim Ruffing Date: Thu, 12 Mar 2020 21:13:09 +0100 Subject: Make code and output a little bit more readable --- bip-0340/reference.py | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/bip-0340/reference.py b/bip-0340/reference.py index d6106fd..346b639 100644 --- a/bip-0340/reference.py +++ b/bip-0340/reference.py @@ -33,13 +33,13 @@ def y(P): return P[1] def point_add(P1, P2): - if (P1 is None): + if P1 is None: return P2 - if (P2 is None): + if P2 is None: return P1 - if (x(P1) == x(P2) and y(P1) != y(P2)): + if (x(P1) == x(P2)) and (y(P1) != y(P2)): return None - if (P1 == P2): + if P1 == P2: lam = (3 * x(P1) * x(P1) * pow(2 * y(P1), p - 2, p)) % p else: lam = ((y(P2) - y(P1)) * pow(x(P2) - x(P1), p - 2, p)) % p @@ -49,7 +49,7 @@ def point_add(P1, P2): def point_mul(P, n): R = None for i in range(256): - if ((n >> i) & 1): + if (n >> i) & 1: R = point_add(R, P) P = point_add(P, P) return R @@ -90,7 +90,7 @@ def is_square(x): return pow(x, (p - 1) // 2, p) == 1 def has_square_y(P): - return not is_infinity(P) and is_square(y(P)) + return (not is_infinity(P)) and (is_square(y(P))) def has_even_y(P): return y(P) % 2 == 0 @@ -144,7 +144,7 @@ def schnorr_verify(msg, pubkey, sig): return False e = int_from_bytes(tagged_hash("BIP340/challenge", sig[0:32] + pubkey + msg)) % n R = point_add(point_mul(G, s), point_mul(P, n - e)) - if R is None or not has_square_y(R) or x(R) != r: + if (R is None) or (not has_square_y(R)) or (x(R) != r): debug_print_vars() return False debug_print_vars() @@ -168,7 +168,7 @@ def test_vectors(): msg = bytes.fromhex(msg) sig = bytes.fromhex(sig) result = result == 'TRUE' - print('\nTest vector #%-3i: ' % int(index)) + print('\nTest vector', ('#' + index).rjust(3, ' ') + ':') if seckey != '': seckey = bytes.fromhex(seckey) pubkey_actual = pubkey_gen(seckey) -- cgit v1.2.3 From 003d38cedbe1d8f550ea5032c16373c9779d28e3 Mon Sep 17 00:00:00 2001 From: Tim Ruffing Date: Thu, 12 Mar 2020 18:23:07 +0100 Subject: Fix typo --- bip-0340/test-vectors.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/bip-0340/test-vectors.py b/bip-0340/test-vectors.py index d1a52c8..9c029ec 100644 --- a/bip-0340/test-vectors.py +++ b/bip-0340/test-vectors.py @@ -15,7 +15,7 @@ def vector0(): P = point_mul(G, x) assert(y(P) % 2 == 0) - # For historic reasons (pubkey tiebreaker was squareness and not evenness) + # For historical reasons (pubkey tiebreaker was squareness and not evenness) # we should have at least one test vector where the the point reconstructed # from the public key has a square and one where it has a non-square Y # coordinate. In this one Y is non-square. -- cgit v1.2.3 From 07d938a214475929e08df17e725b3904a3429dbf Mon Sep 17 00:00:00 2001 From: Tim Ruffing Date: Tue, 17 Mar 2020 02:13:26 +0100 Subject: fixup! Optionally print intermediate values in reference code --- bip-0340/reference.py | 10 +++------- 1 file changed, 3 insertions(+), 7 deletions(-) diff --git a/bip-0340/reference.py b/bip-0340/reference.py index 346b639..da1e689 100644 --- a/bip-0340/reference.py +++ b/bip-0340/reference.py @@ -78,7 +78,7 @@ def lift_x_even_y(b): if P is None: return None else: - return [x(P), y(P) if y(P) % 2 == 0 else p - y(P)] + return (x(P), y(P) if y(P) % 2 == 0 else p - y(P)) def int_from_bytes(b): return int.from_bytes(b, byteorder="big") @@ -90,7 +90,7 @@ def is_square(x): return pow(x, (p - 1) // 2, p) == 1 def has_square_y(P): - return (not is_infinity(P)) and (is_square(y(P))) + return (not is_infinity(P)) and is_square(y(P)) def has_even_y(P): return y(P) % 2 == 0 @@ -98,14 +98,12 @@ def has_even_y(P): def pubkey_gen(seckey): d0 = int_from_bytes(seckey) if not (1 <= d0 <= n - 1): - debug_print_vars() raise ValueError('The secret key must be an integer in the range 1..n-1.') P = point_mul(G, d0) return bytes_from_point(P) def schnorr_sign(msg, seckey, aux_rand): if len(msg) != 32: - debug_print_vars() raise ValueError('The message must be a 32-byte array.') d0 = int_from_bytes(seckey) if not (1 <= d0 <= n - 1): @@ -117,16 +115,14 @@ def schnorr_sign(msg, seckey, aux_rand): t = xor_bytes(bytes_from_int(d), tagged_hash("BIP340/aux", aux_rand)) k0 = int_from_bytes(tagged_hash("BIP340/nonce", t + bytes_from_point(P) + msg)) % n if k0 == 0: - debug_print_vars() raise RuntimeError('Failure. This happens only with negligible probability.') R = point_mul(G, k0) k = n - k0 if not has_square_y(R) else k0 e = int_from_bytes(tagged_hash("BIP340/challenge", bytes_from_point(R) + bytes_from_point(P) + msg)) % n sig = bytes_from_point(R) + bytes_from_int((k + e * d) % n) + debug_print_vars() if not schnorr_verify(msg, bytes_from_point(P), sig): - debug_print_vars() raise RuntimeError('The signature does not pass verification.') - debug_print_vars() return sig def schnorr_verify(msg, pubkey, sig): -- cgit v1.2.3 From 72657270d8e4d6ef193878f1e743301edfae0e31 Mon Sep 17 00:00:00 2001 From: Tim Ruffing Date: Tue, 17 Mar 2020 02:30:39 +0100 Subject: When checking test vectors, handle RuntimeException in signing This is better for playing around with the code. Now these these exceptions can really be raised when the verification during signing fails. --- bip-0340/reference.py | 20 ++++++++++++-------- 1 file changed, 12 insertions(+), 8 deletions(-) diff --git a/bip-0340/reference.py b/bip-0340/reference.py index da1e689..6b1645c 100644 --- a/bip-0340/reference.py +++ b/bip-0340/reference.py @@ -122,7 +122,7 @@ def schnorr_sign(msg, seckey, aux_rand): sig = bytes_from_point(R) + bytes_from_int((k + e * d) % n) debug_print_vars() if not schnorr_verify(msg, bytes_from_point(P), sig): - raise RuntimeError('The signature does not pass verification.') + raise RuntimeError('The created signature does not pass verification.') return sig def schnorr_verify(msg, pubkey, sig): @@ -173,13 +173,17 @@ def test_vectors(): print(' Expected key:', pubkey.hex().upper()) print(' Actual key:', pubkey_actual.hex().upper()) aux_rand = bytes.fromhex(aux_rand) - sig_actual = schnorr_sign(msg, seckey, aux_rand) - if sig == sig_actual: - print(' * Passed signing test.') - else: - print(' * Failed signing test.') - print(' Expected signature:', sig.hex().upper()) - print(' Actual signature:', sig_actual.hex().upper()) + try: + sig_actual = schnorr_sign(msg, seckey, aux_rand) + if sig == sig_actual: + print(' * Passed signing test.') + else: + print(' * Failed signing test.') + print(' Expected signature:', sig.hex().upper()) + print(' Actual signature:', sig_actual.hex().upper()) + all_passed = False + except RuntimeError as e: + print(' * Signing test raised exception:', e) all_passed = False result_actual = schnorr_verify(msg, pubkey, sig) if result == result_actual: -- cgit v1.2.3 From 0916da6594609b811e31c1f666638d15c8bd7381 Mon Sep 17 00:00:00 2001 From: Jonas Nick Date: Fri, 27 Mar 2020 15:13:13 +0000 Subject: BIP-0341: Replace notion of is_negated with parity bit --- bip-0341.mediawiki | 16 +++++++--------- 1 file changed, 7 insertions(+), 9 deletions(-) diff --git a/bip-0341.mediawiki b/bip-0341.mediawiki index 6472430..564071f 100644 --- a/bip-0341.mediawiki +++ b/bip-0341.mediawiki @@ -59,7 +59,7 @@ The following rules only apply when such an output is being spent. Any other out * Let ''q'' be the 32-byte array containing the witness program (the second push in the scriptPubKey) which represents a public key according to [[bip-0340.mediawiki#design|BIP340]]. * Fail if the witness stack has 0 elements. -* If there are at least two witness elements, and the first byte of the last element is 0x50'''Why is the first byte of the annex 0x50?''' The 0x50 is chosen as it could not be confused with a valid P2WPKH or P2WSH spending. As the control block's initial byte's lowest bit is used to indicate the public key's Y oddness, each leaf version needs an even byte value and the immediately following odd byte value that are both not yet used in P2WPKH or P2WSH spending. To indicate the annex, only an "unpaired" available byte is necessary like 0x50. This choice maximizes the available options for future script versions., this last element is called ''annex'' ''a'''''What is the purpose of the annex?''' The annex is a reserved space for future extensions, such as indicating the validation costs of computationally expensive new opcodes in a way that is recognizable without knowing the scriptPubKey of the output being spent. Until the meaning of this field is defined by another softfork, users SHOULD NOT include annex in transactions, or it may lead to PERMANENT FUND LOSS. and is removed from the witness stack. The annex (or the lack of thereof) is always covered by the signature and contributes to transaction weight, but is otherwise ignored during taproot validation. +* If there are at least two witness elements, and the first byte of the last element is 0x50'''Why is the first byte of the annex 0x50?''' The 0x50 is chosen as it could not be confused with a valid P2WPKH or P2WSH spending. As the control block's initial byte's lowest bit is used to indicate the parity of the public key's Y coordinate, each leaf version needs an even byte value and the immediately following odd byte value that are both not yet used in P2WPKH or P2WSH spending. To indicate the annex, only an "unpaired" available byte is necessary like 0x50. This choice maximizes the available options for future script versions., this last element is called ''annex'' ''a'''''What is the purpose of the annex?''' The annex is a reserved space for future extensions, such as indicating the validation costs of computationally expensive new opcodes in a way that is recognizable without knowing the scriptPubKey of the output being spent. Until the meaning of this field is defined by another softfork, users SHOULD NOT include annex in transactions, or it may lead to PERMANENT FUND LOSS. and is removed from the witness stack. The annex (or the lack of thereof) is always covered by the signature and contributes to transaction weight, but is otherwise ignored during taproot validation. * If there is exactly one element left in the witness stack, key path spending is used: ** The single witness stack element is interpreted as the signature and must be valid (see the next section) for the public key ''q'' (see the next subsection). * If there are at least two witness elements left, script path spending is used: @@ -168,8 +168,8 @@ Alice will not be able to notice the script path, but Mallory can unilaterally s '''Computing the output script''' Once the spending conditions are split into an internal key internal_pubkey and a binary tree whose leaves are (leaf_version, script) tuples, the output script can be computed using the Python3 algorithms below. These algorithms take advantage of helper functions from the [bip-0340/referency.py BIP340 reference code] for integer conversion, point multiplication, and tagged hashes. First, we define taproot_tweak_pubkey for 32-byte [[bip-0340.mediawiki|BIP340]] public key arrays. -In addition to the tweaked public key byte array, the function returns a boolean indicating whether the public key represents the tweaked point or its negation. -This will be required for spending the output with a script path. +The function returns a bit indicating the tweaked public key's Y coordinate as well as the public key byte array. +The parity bit will be required for spending the output with a script path. In order to allow spending with the key path, we define taproot_tweak_seckey to compute the secret key for a tweaked public key. For any byte string h it holds that taproot_tweak_pubkey(pubkey_gen(seckey), h)[0] == pubkey_gen(taproot_tweak_seckey(seckey, h)). @@ -179,8 +179,7 @@ def taproot_tweak_pubkey(pubkey, h): if t >= SECP256K1_ORDER: raise ValueError Q = point_add(lift_x_even_y(int_from_bytes(pubkey)), point_mul(G, t)) - is_negated = not has_even_y(Q) - return bytes_from_int(x(Q)), is_negated + return 0 if has_even_y(Q) else 1, bytes_from_int(x(Q)) def taproot_tweak_seckey(seckey0, h): P = point_mul(G, int_from_bytes(seckey0)) @@ -226,7 +225,7 @@ def taproot_output_script(internal_pubkey, script_tree): To spend this output using script ''D'', the control block would contain the following data in this order: - + The TapTweak would then be computed as described [[bip-0341.mediawiki#script-validation-rules|above]] like so: @@ -258,9 +257,8 @@ This function returns the witness stack necessary and a sighash fun def taproot_sign_script(internal_pubkey, script_tree, script_num, inputs): info, h = taproot_tree_helper(script_tree) (leaf_version, script), path = info[script_num] - _, is_negated = taproot_tweak_pubkey(internal_pubkey, h) - output_pubkey_tag = 0 if is_negated else 1 - pubkey_data = bytes([output_pubkey_tag + leaf_version]) + internal_pubkey + output_pubkey_y_parity, _ = taproot_tweak_pubkey(internal_pubkey, h) + pubkey_data = bytes([output_pubkey_y_parity + leaf_version]) + internal_pubkey return inputs + [script, pubkey_data + path] -- cgit v1.2.3 From 756129cccfd539174b7a1b1a0203f1527d3c46c0 Mon Sep 17 00:00:00 2001 From: Janus Date: Wed, 18 Mar 2020 20:14:08 -0600 Subject: BIP-0340: Add typing annotations to reference.py Passes mypy's strict-mode with mypy 0.770. --- bip-0340/reference.py | 78 +++++++++++++++++++++++++++++---------------------- 1 file changed, 45 insertions(+), 33 deletions(-) diff --git a/bip-0340/reference.py b/bip-0340/reference.py index 6b1645c..f24963c 100644 --- a/bip-0340/reference.py +++ b/bip-0340/reference.py @@ -1,3 +1,4 @@ +from typing import Tuple, Optional, Any import hashlib import binascii @@ -17,22 +18,24 @@ n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # represented by the None keyword. G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8) +Point = Tuple[int, int] + # This implementation can be sped up by storing the midstate after hashing # tag_hash instead of rehashing it all the time. -def tagged_hash(tag, msg): +def tagged_hash(tag: str, msg: bytes) -> bytes: tag_hash = hashlib.sha256(tag.encode()).digest() return hashlib.sha256(tag_hash + tag_hash + msg).digest() -def is_infinity(P): +def is_infinity(P: Optional[Point]) -> bool: return P is None -def x(P): +def x(P: Point) -> int: return P[0] -def y(P): +def y(P: Point) -> int: return P[1] -def point_add(P1, P2): +def point_add(P1: Optional[Point], P2: Optional[Point]) -> Optional[Point]: if P1 is None: return P2 if P2 is None: @@ -46,7 +49,7 @@ def point_add(P1, P2): x3 = (lam * lam - x(P1) - x(P2)) % p return (x3, (lam * (x(P1) - x3) - y(P1)) % p) -def point_mul(P, n): +def point_mul(P: Optional[Point], n: int) -> Optional[Point]: R = None for i in range(256): if (n >> i) & 1: @@ -54,16 +57,16 @@ def point_mul(P, n): P = point_add(P, P) return R -def bytes_from_int(x): +def bytes_from_int(x: int) -> bytes: return x.to_bytes(32, byteorder="big") -def bytes_from_point(P): +def bytes_from_point(P: Point) -> bytes: return bytes_from_int(x(P)) -def xor_bytes(b0, b1): +def xor_bytes(b0: bytes, b1: bytes) -> bytes: return bytes(x ^ y for (x, y) in zip(b0, b1)) -def lift_x_square_y(b): +def lift_x_square_y(b: bytes) -> Optional[Point]: x = int_from_bytes(b) if x >= p: return None @@ -73,36 +76,40 @@ def lift_x_square_y(b): return None return (x, y) -def lift_x_even_y(b): +def lift_x_even_y(b: bytes) -> Optional[Point]: P = lift_x_square_y(b) if P is None: return None else: return (x(P), y(P) if y(P) % 2 == 0 else p - y(P)) -def int_from_bytes(b): +def int_from_bytes(b: bytes) -> int: return int.from_bytes(b, byteorder="big") -def hash_sha256(b): +def hash_sha256(b: bytes) -> bytes: return hashlib.sha256(b).digest() -def is_square(x): - return pow(x, (p - 1) // 2, p) == 1 +def is_square(x: int) -> bool: + return int(pow(x, (p - 1) // 2, p)) == 1 -def has_square_y(P): - return (not is_infinity(P)) and is_square(y(P)) +def has_square_y(P: Optional[Point]) -> bool: + infinity = is_infinity(P) + if infinity: return False + assert P is not None + return is_square(y(P)) -def has_even_y(P): +def has_even_y(P: Point) -> bool: return y(P) % 2 == 0 -def pubkey_gen(seckey): +def pubkey_gen(seckey: bytes) -> bytes: d0 = int_from_bytes(seckey) if not (1 <= d0 <= n - 1): raise ValueError('The secret key must be an integer in the range 1..n-1.') P = point_mul(G, d0) + assert P is not None return bytes_from_point(P) -def schnorr_sign(msg, seckey, aux_rand): +def schnorr_sign(msg: bytes, seckey: bytes, aux_rand: bytes) -> bytes: if len(msg) != 32: raise ValueError('The message must be a 32-byte array.') d0 = int_from_bytes(seckey) @@ -111,12 +118,14 @@ def schnorr_sign(msg, seckey, aux_rand): if len(aux_rand) != 32: raise ValueError('aux_rand must be 32 bytes instead of %i.' % len(aux_rand)) P = point_mul(G, d0) + assert P is not None d = d0 if has_even_y(P) else n - d0 t = xor_bytes(bytes_from_int(d), tagged_hash("BIP340/aux", aux_rand)) k0 = int_from_bytes(tagged_hash("BIP340/nonce", t + bytes_from_point(P) + msg)) % n if k0 == 0: raise RuntimeError('Failure. This happens only with negligible probability.') R = point_mul(G, k0) + assert R is not None k = n - k0 if not has_square_y(R) else k0 e = int_from_bytes(tagged_hash("BIP340/challenge", bytes_from_point(R) + bytes_from_point(P) + msg)) % n sig = bytes_from_point(R) + bytes_from_int((k + e * d) % n) @@ -125,7 +134,7 @@ def schnorr_sign(msg, seckey, aux_rand): raise RuntimeError('The created signature does not pass verification.') return sig -def schnorr_verify(msg, pubkey, sig): +def schnorr_verify(msg: bytes, pubkey: bytes, sig: bytes) -> bool: if len(msg) != 32: raise ValueError('The message must be a 32-byte array.') if len(pubkey) != 32: @@ -153,26 +162,26 @@ import csv import os import sys -def test_vectors(): +def test_vectors() -> bool: all_passed = True with open(os.path.join(sys.path[0], 'test-vectors.csv'), newline='') as csvfile: reader = csv.reader(csvfile) reader.__next__() for row in reader: - (index, seckey, pubkey, aux_rand, msg, sig, result, comment) = row - pubkey = bytes.fromhex(pubkey) - msg = bytes.fromhex(msg) - sig = bytes.fromhex(sig) - result = result == 'TRUE' + (index, seckey_hex, pubkey_hex, aux_rand_hex, msg_hex, sig_hex, result_str, comment) = row + pubkey = bytes.fromhex(pubkey_hex) + msg = bytes.fromhex(msg_hex) + sig = bytes.fromhex(sig_hex) + result = result_str == 'TRUE' print('\nTest vector', ('#' + index).rjust(3, ' ') + ':') - if seckey != '': - seckey = bytes.fromhex(seckey) + if seckey_hex != '': + seckey = bytes.fromhex(seckey_hex) pubkey_actual = pubkey_gen(seckey) if pubkey != pubkey_actual: print(' * Failed key generation.') print(' Expected key:', pubkey.hex().upper()) print(' Actual key:', pubkey_actual.hex().upper()) - aux_rand = bytes.fromhex(aux_rand) + aux_rand = bytes.fromhex(aux_rand_hex) try: sig_actual = schnorr_sign(msg, seckey, aux_rand) if sig == sig_actual: @@ -207,7 +216,7 @@ def test_vectors(): # import inspect -def pretty(v): +def pretty(v: Any) -> Any: if isinstance(v, bytes): return '0x' + v.hex() if isinstance(v, int): @@ -216,9 +225,12 @@ def pretty(v): return tuple(map(pretty, v)) return v -def debug_print_vars(): +def debug_print_vars() -> None: if DEBUG: - frame = inspect.currentframe().f_back + current_frame = inspect.currentframe() + assert current_frame is not None + frame = current_frame.f_back + assert frame is not None print(' Variables in function ', frame.f_code.co_name, ' at line ', frame.f_lineno, ':', sep='') for var_name, var_val in frame.f_locals.items(): print(' ' + var_name.rjust(11, ' '), '==', pretty(var_val)) -- cgit v1.2.3