Settle on notation: is_square(y), has_square_y(P)

4 files changed, 33 insertions, 31 deletions

diff --git a/bip-schnorr.mediawiki b/bip-schnorr.mediawiki
index 3d85754..61414f5 100644
--- a/bip-schnorr.mediawiki
+++ b/bip-schnorr.mediawiki
@@ -106,8 +106,8 @@ The following conventions are used, with constants as defined for [https://www.s
 ** The function ''bytes(P)'', where ''P'' is a point, returns ''bytes(x(P))'.
 ** The function ''int(x)'', where ''x'' is a 32-byte array, returns the 256-bit unsigned integer whose most significant byte first encoding is ''x''.
 ** The function ''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 Legendre symbol ''(x / p) = x<sup>(p-1)/2</sup> mod p'' being equal to ''1'' (see [https://en.wikipedia.org/wiki/Euler%27s_criterion Euler's criterion])<ref>For points ''P'' on the secp256k1 curve it holds that ''x<sup>(p-1)/2</sup> &ne; 0 mod p''.</ref>.
-** The function ''is_positive(P)'', where ''P'' is a point, is defined as ''not is_infinite(P) and is_square(y(P))''<ref>For points ''P'' on the secp256k1 curve it holds that ''is_positive(P) = not is_positive(-P)''.</ref>.
-** The function ''lift_x(x)'', where ''x'' is an integer in range ''0..p-1'', returns the point ''P'' for which ''x(P) = x'' and ''is_positive(P)'', or fails if no such point exists<ref>Given an 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''.  Given a candidate ''x'', the valid Y coordinates are the square roots of ''c = x<sup>3</sup> + 7 mod p'' and they can be computed as ''y = &plusmn;c<sup>(p+1)/4</sup> mod p'' (see [https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus Quadratic residue]) if they exist, which can be checked by squaring and comparing with ''c''. Due to [https://en.wikipedia.org/wiki/Euler%27s_criterion Euler's criterion] it then holds that ''c<sup>(p-1)/2</sup> = 1 mod p''. The same criterion applied to ''y'' results in ''y<sup>(p-1)/2</sup> mod p = &plusmn;c<sup>((p+1)/4)((p-1)/2)</sup> mod p = &plusmn;1 mod p''. Therefore ''y = +c<sup>(p+1)/4</sup> mod p'' is a quadratic residue and ''-y mod p'' is not.</ref>. The function ''lift_x(x)'' is equivalent to the following pseudocode:
+** The function ''has_square_y(P)'', where ''P'' is a point, is defined as ''not is_infinite(P) and is_square(y(P))''<ref>For points ''P'' on the secp256k1 curve it holds that ''has_square_y(P) = not has_square_y(-P)''.</ref>.
+** The function ''lift_x(x)'', where ''x'' is an integer in range ''0..p-1'', returns the point ''P'' for which ''x(P) = x'' and ''has_square_y(P)'', or fails if no such point exists<ref>Given an 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''.  Given a candidate ''x'', the valid Y coordinates are the square roots of ''c = x<sup>3</sup> + 7 mod p'' and they can be computed as ''y = &plusmn;c<sup>(p+1)/4</sup> mod p'' (see [https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus Quadratic residue]) if they exist, which can be checked by squaring and comparing with ''c''. Due to [https://en.wikipedia.org/wiki/Euler%27s_criterion Euler's criterion] it then holds that ''c<sup>(p-1)/2</sup> = 1 mod p''. The same criterion applied to ''y'' results in ''y<sup>(p-1)/2</sup> mod p = &plusmn;c<sup>((p+1)/4)((p-1)/2)</sup> mod p = &plusmn;1 mod p''. Therefore ''y = +c<sup>(p+1)/4</sup> mod p'' is a quadratic residue and ''-y mod p'' is not.</ref>. The function ''lift_x(x)'' is equivalent to the following pseudocode:
 *** Let ''c = x<sup>3</sup> + 7 mod p''.
 *** Let ''y = c<sup>(p+1)/4</sup> mod p''.
 *** Fail if ''c &ne; y<sup>2</sup> mod p''.
@@ -139,11 +139,11 @@ The algorithm ''Sign(sk, m)'' is defined as:
 * Let ''d' = int(sk)''
 * Fail if ''d' = 0'' or ''d' &ge; n''
 * Let ''P = d'⋅G''
-* Let ''d = d' '' if ''is_positive(P)'', otherwise let ''d = n - d' ''.
+* Let ''d = d' '' if ''has_square_y(P)'', otherwise let ''d = n - d' ''.
 * Let ''k' = int(hash<sub>BIPSchnorrDerive</sub>(bytes(d) || m)) mod n''<ref>Note that in general, taking the output of a hash function modulo the curve order will produce an unacceptably biased result. However, for the secp256k1 curve, the order is sufficiently close to ''2<sup>256</sup>'' that this bias is not observable (''1 - n / 2<sup>256</sup>'' is around ''1.27 * 2<sup>-128</sup>'').</ref>.
 * Fail if ''k' = 0''.
 * Let ''R = k'G''.
-* Let ''k = k' '' if ''is_positive(R)'', otherwise let ''k = n - k' ''.
+* Let ''k = k' '' if ''has_square_y(R)'', otherwise let ''k = n - k' ''.
 * Let ''e = int(hash<sub>BIPSchnorr</sub>(bytes(R) || bytes(P) || m)) mod n''.
 * Return the signature ''bytes(R) || bytes((k + ed) mod n)''.
 
@@ -171,12 +171,12 @@ The algorithm ''Verify(pk, m, sig)'' is defined as:
 * Let ''s = int(sig[32:64])''; fail if ''s &ge; n''.
 * Let ''e = int(hash<sub>BIPSchnorr</sub>(bytes(r) || bytes(P) || m)) mod n''.
 * Let ''R = s⋅G - e⋅P''.
-* Fail if ''not is_positive(R)'' or ''x(R) &ne; r''.
+* Fail if ''not has_square_y(R)'' or ''x(R) &ne; r''.
 * Return success iff no failure occurred before reaching this point.
 
 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 positive point (i.e., 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 negative point is used. While it is possible to correct for this by negating negative points 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 ''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.
 
 ==== Batch Verification ====
 
@@ -206,7 +206,7 @@ Many techniques are known for optimizing elliptic curve implementations. Several
 '''Squareness testing''' The function ''is_square(x)'' is defined as above, but can be computed more efficiently using an [https://en.wikipedia.org/wiki/Jacobi_symbol#Calculating_the_Jacobi_symbol extended GCD algorithm].
 
 '''Jacobian coordinates''' Elliptic Curve operations can be implemented more efficiently by using [https://en.wikibooks.org/wiki/Cryptography/Prime_Curve/Jacobian_Coordinates Jacobian coordinates]. Elliptic Curve operations implemented this way avoid many intermediate modular inverses (which are computationally expensive), and the scheme proposed in this document is in fact designed to not need any inversions at all for verification. When operating on a point ''P'' with Jacobian coordinates ''(x,y,z)'' which is not the point at infinity and for which ''x(P)'' is defined as ''x / z<sup>2</sup>'' and ''y(P)'' is defined as ''y / z<sup>3</sup>'':
-* ''is_positive(P)'' can be implemented as ''is_square(yz mod p)''.
+* ''has_square_y(P)'' can be implemented as ''is_square(yz mod p)''.
 * ''x(P) &ne; r'' can be implemented as ''(0 &le; r < p) and (x &ne; z<sup>2</sup>r mod p)''.
 
 == Applications ==
diff --git a/bip-schnorr/reference.py b/bip-schnorr/reference.py
index e5d9557..7de37c2 100644
--- a/bip-schnorr/reference.py
+++ b/bip-schnorr/reference.py
@@ -11,6 +11,9 @@ def tagged_hash(tag, msg):
     tag_hash = hashlib.sha256(tag.encode()).digest()
     return hashlib.sha256(tag_hash + tag_hash + msg).digest()
 
+def is_infinity(P):
+    return P is None
+
 def x(P):
     return P[0]
 
@@ -59,11 +62,11 @@ def int_from_bytes(b):
 def hash_sha256(b):
     return hashlib.sha256(b).digest()
 
-def jacobi(x):
-    return pow(x, (p - 1) // 2, p)
+def is_square(x):
+    return pow(x, (p - 1) // 2, p) == 1
 
-def is_quad(x):
-    return jacobi(x) == 1
+def has_square_y(P):
+    return not is_infinity(P) and is_square(y(P))
 
 def pubkey_gen(seckey):
     x = int_from_bytes(seckey)
@@ -79,12 +82,12 @@ 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 is_quad(y(P)) else n - seckey0
+    seckey = seckey0 if has_square_y(P) else n - seckey0
     k0 = int_from_bytes(tagged_hash("BIPSchnorrDerive", bytes_from_int(seckey) + msg)) % n
     if k0 == 0:
         raise RuntimeError('Failure. This happens only with negligible probability.')
     R = point_mul(G, k0)
-    k = n - k0 if not is_quad(y(R)) else 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
     return bytes_from_point(R) + bytes_from_int((k + e * seckey) % n)
 
@@ -104,7 +107,7 @@ def schnorr_verify(msg, pubkey, sig):
         return False
     e = int_from_bytes(tagged_hash("BIPSchnorr", sig[0:32] + pubkey + msg)) % n
     R = point_add(point_mul(G, s), point_mul(P, n - e))
-    if R is None or not is_quad(y(R)) or x(R) != r:
+    if R is None or not has_square_y(R) or x(R) != r:
         return False
     return True
 
diff --git a/bip-schnorr/test-vectors.py b/bip-schnorr/test-vectors.py
index 52e3b05..768d9f1 100644
--- a/bip-schnorr/test-vectors.py
+++ b/bip-schnorr/test-vectors.py
@@ -30,10 +30,10 @@ def vector2():
     msg = bytes_from_int(0x5E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C)
     sig = schnorr_sign(msg, seckey)
 
-    # This singature vector would not verify if the implementer checked the
-    # jacobi symbol of the X coordinate of R instead of the Y coordinate.
+    # 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])
-    assert(jacobi(R[0]) != 1)
+    assert(not is_square(R[0]))
 
     return (bytes_from_int(seckey), pubkey_gen(seckey), msg, sig, "TRUE", None)
 
@@ -43,15 +43,14 @@ def vector3():
     sig = schnorr_sign(msg, seckey)
     return (bytes_from_int(seckey), pubkey_gen(seckey), msg, sig, "TRUE", "test fails if msg is reduced modulo p or n")
 
-# Signs with a given nonce. Results in an invalid signature if y(kG) is not a
-# quadratic residue.
+# Signs with a given nonce. Results in an invalid signature if y(kG) is not a square
 def schnorr_sign_fixed_nonce(msg, seckey0, k):
     if len(msg) != 32:
         raise ValueError('The message must be a 32-byte array.')
     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 (jacobi(P[1]) == 1) else n - seckey0
+    seckey = seckey0 if has_square_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
     return bytes_from_point(R) + bytes_from_int((k + e * seckey) % n)
@@ -84,9 +83,9 @@ def vector6():
     k = 3
     sig = schnorr_sign_fixed_nonce(msg, seckey, k)
 
-    # Y coordinate of R is not a quadratic residue
+    # Y coordinate of R is not a square
     R = point_mul(G, k)
-    assert(jacobi(R[1]) != 1)
+    assert(not has_square_y(R))
 
     return (None, pubkey_gen(seckey), msg, sig, "FALSE", "incorrect R residuosity")
 
@@ -121,7 +120,7 @@ def vector9():
     sig = 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 jacobi(y(inf)) is defined as 1 and x(inf) as 0")
+    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")
 
 def bytes_from_point_inf1(P):
     if P == None:
@@ -140,7 +139,7 @@ def vector10():
     sig = 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 jacobi(y(inf)) is defined as 1 and x(inf) as 1")
+    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")
 
 # 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
diff --git a/bip-taproot.mediawiki b/bip-taproot.mediawiki
index fd25b77..0e27724 100644
--- a/bip-taproot.mediawiki
+++ b/bip-taproot.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-schnorr.
 * 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<ref>'''Why is the first byte of the annex <code>0x50</code>?''' Like the <code>0xc0</code> constant, <code>0x50</code> 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 quadratic residuosity, each script version needs two subsequence byte values that are both not yet used in P2WPKH or P2WSH spending. To indicate the annex, only an "unpaired" available byte is necessary like <code>0x50</code>. This choice maximizes the available options for future script versions.</ref>, this last element is called ''annex'' ''a''<ref>'''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 outputs being spent. Until the meaning of this field is defined by another softfork, users SHOULD NOT include <code>annex</code> in transactions, or it may lead to PERMANENT FUND LOSS.</ref> and is removed from the witness stack. The annex (or the lack of thereof) is always covered by the transaction digest 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<ref>'''Why is the first byte of the annex <code>0x50</code>?''' Like the <code>0xc0</code> constant, <code>0x50</code> 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 script version needs two subsequence byte values that are both not yet used in P2WPKH or P2WSH spending. To indicate the annex, only an "unpaired" available byte is necessary like <code>0x50</code>. This choice maximizes the available options for future script versions.</ref>, this last element is called ''annex'' ''a''<ref>'''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 outputs being spent. Until the meaning of this field is defined by another softfork, users SHOULD NOT include <code>annex</code> in transactions, or it may lead to PERMANENT FUND LOSS.</ref> and is removed from the witness stack. The annex (or the lack of thereof) is always covered by the transaction digest 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'' and taproot transaction digest (to be defined hereinafter) as message. Fail if it is not. Otherwise pass.
 * If there are at least two witness elements left, script path spending is used:
@@ -67,7 +67,7 @@ The following rules only apply when such an output is being spent. Any other out
 ** 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<ref>'''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 ''log<sub>2</sub>(1/probability)'', but to have branches longer than 128 you would need to have scripts with an execution chance below 1 in ''2<sup>128</sup>''. As that is our security bound, scripts that truly have such a low chance can probably be removed entirely.</ref>, inclusive. Fail if it does not have such a length.
 ** Let ''p = c[1:33]'' and let ''P = point(p)'' where ''point'' is defined as in bip-schnorr. Fail if this point is not on the curve.
 ** Let ''l = c[0] & 0xfe'', the leaf version<ref>'''What is the purpose of the first byte of the control block?''' The first byte of the control block has three distinct functions:
-* The low bit is used to denote whether the ''Q'' point's Y coordinate is a quadratic residue.<ref>'''Why is the quadratic residuosity of the output public key's Y coordinate required in a script path spend?''' The ''point'' function always constructs a point with Y coordinate having that property, 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. 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.</ref>
+* The low bit is used to denote whether the ''has_square_y(Q)'' holds.<ref>'''Why is the squareness of the output public key's Y coordinate required in a script path spend?''' The ''point'' function always constructs a point with Y coordinate having that property, 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. 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.</ref>
 * By keeping the top two bits set to true, it can be guaranteed that scripts can be recognized without knowledge of the UTXO being spent, simplifying analysis. This is because such values cannot occur as first byte of the final stack element in either P2WPKH or P2WSH spends.
 * The remaining five bits are used for introducing new script versions that are not observable unless actually executed.
 </ref>.
@@ -179,7 +179,7 @@ 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 <code>internal_pubkey</code> and a binary tree whose leaves are (leaf_version, script) tuples, the output script can be computed using the following Python3 algorithms with helper functions from the bip-schnorr reference code for integer conversion, point multiplication and tagged hashes.
 
 First, we define <code>taproot_tweak_pubkey</code> for 32-byte bip-schnorr public key arrays.
-In addition to the tweaked public key byte array, the function returns a boolean for the quadratic residuosity of the tweaked points' Y coordinate modulo the secp256k1 field order.
+In addition to the tweaked public key byte array, the function returns a boolean for the squareness of the tweaked points' Y coordinate modulo the secp256k1 field order.
 This will be required for spending the output with a script path.
 In order to allow spending with the key path, we define <code>taproot_tweak_seckey</code> to compute the secret key for a tweaked public key.
 For any byte string <code>h</code> it holds that <code>taproot_tweak_pubkey(pubkey_gen(seckey), h)[0] == pubkey_gen(taproot_tweak_seckey(seckey, h))</code>.
@@ -190,11 +190,11 @@ def taproot_tweak_pubkey(pubkey, h):
     if t >= SECP256K1_ORDER:
         raise ValueError
     Q = point_mul(point(pubkey), t)
-    return bytes_from_int(x(Q)), is_quad(y(Q))
+    return bytes_from_int(x(Q)), has_square_y(Q)
 
 def taproot_tweak_seckey(seckey0, h):
     P = point_mul(G, int_from_bytes(seckey0))
-    seckey = SECP256K1_ORDER - seckey0 if not is_quad(y(R)) else seckey
+    seckey = SECP256K1_ORDER - seckey0 if not has_square_y(R) else seckey
     t = int_from_bytes(tagged_hash("TapTweak", bytes_from_int(x(P)) + h))
     if t >= SECP256K1_ORDER:
         raise ValueError
@@ -254,8 +254,8 @@ This function returns the witness stack necessary and a <code>sighash</code> 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_y_quad = taproot_tweak_pubkey(internal_pubkey, t)
-    output_pubkey_tag = 0 if is_y_quad else 1
+    _, is_y_square = taproot_tweak_pubkey(internal_pubkey, t)
+    output_pubkey_tag = 0 if is_y_square else 1
     pubkey_data = bytes([output_pubkey_tag + leaf_version]) + internal_pubkey
     return inputs + [script, pubkey_data + path]
 </source>