Rename is_y_square to is_negated in taproot signing

1 files changed, 6 insertions, 5 deletions

diff --git a/bip-taproot.mediawiki b/bip-taproot.mediawiki
index 1119785..a8106fc 100644
--- a/bip-taproot.mediawiki
+++ b/bip-taproot.mediawiki
@@ -68,7 +68,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'' and ''[:]'' are 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 ''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>
+* The low bit is used to denote whether the point represented by public key ''q'' is negated before verifying the taproot tweak.<ref>'''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-schnorr) 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.</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>.
@@ -180,7 +180,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 Python3 algorithms below. These algorithms take advantage of helper functions from the [https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr/reference.py 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 squareness 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 indicating whether the public key represents the tweaked point or its negation.
 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>.
@@ -191,7 +191,8 @@ def taproot_tweak_pubkey(pubkey, h):
     if t >= SECP256K1_ORDER:
         raise ValueError
     Q = point_add(point(pubkey), point_mul(G, t))
-    return bytes_from_int(x(Q)), has_square_y(Q)
+    is_negated = not has_square_y(Q)
+    return bytes_from_int(x(Q)), is_negated
 
 def taproot_tweak_seckey(seckey0, h):
     P = point_mul(G, int_from_bytes(seckey0))
@@ -255,8 +256,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_square = taproot_tweak_pubkey(internal_pubkey, h)
-    output_pubkey_tag = 0 if is_y_square else 1
+    _, 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
     return inputs + [script, pubkey_data + path]
 </source>