test: refactor out same-txid-diff-wtxid tx to reuse in other tests #32385

Could use elif, but as the effect is the same, better to roll this into one if, i think:

if (low_s and s > secp256k1.GE.ORDER_HALF) or (not low_s and s < secp256k1.GE.ORDER_HALF):
    s = ORDER - s

All in all this defines not low_s as "high_s" instead of "any s". This doesn't cause problems as the test framework doesn't use low_s=False anywhere else. Still, it might be clearer to add a new flag?

Could use elif, but as the effect is the same, better to roll this into one if, i think:

nice, I've used this.

All in all this defines not low_s as "high_s" instead of "any s". This doesn't cause problems as the test framework doesn't use low_s=False anywhere else. Still, it might be clearer to add a new flag?

oh right - just added a comment for now, since the low_s=False option isn't used elsewhere and can't think of a scenario where non-determinism from allowing "any s" (returning high s sometimes, low s other times) would be needed. here's the diff.

Right it's fine, it's documented well enough now, if anyone needs that functionality in the future they can add it then.

I can imagine that malleating a transaction does not require the private key and a re-sign.

Currently there is this function:

def create_malleated_version(self, tx)

which fills garbage. Could it be extended to take a boolean argument, indicating whether to fill with garbage like now, or flip s to ORDER - s? For this it would have to extract s like done on line 97 here:

https://github.com/bitcoin/bitcoin/blob/baa848b8d38187ce6b24a57cfadf1ea180209711/test/functional/test_framework/key.py#L59-L97

flip it to ORDER - s and re-do the DER encoding like:

https://github.com/bitcoin/bitcoin/blob/baa848b8d38187ce6b24a57cfadf1ea180209711/test/functional/test_framework/key.py#L184-L189

For the caller it would be useful to know if the new flipped s is low or high. I guess this can be indicated somehow by create_malleated_version() or there could be a separate function which takes a signed transaction and returns whether s is low or high.

@vasild, agree that it was hard to use before. I like the new approach much better and tried it out in the private broadcast tests! See https://github.com/stratospher/bitcoin/commit/c14812402aa370b448a46efad1b0e5a5af1199ee

Isn't multisig kind of out-of-scope for creating a valid malleated transaction? I don't mind some extra tests, but those might make this PR more difficult to review. Maybe omit those if there is no review interest for some time.

oh included it because high-s transactions are non-standard and I was worried they wouldn't be relayed and we couldn't test private broadcast behaviour.

Now I see! Multisig is another way to create "same_txid, different_wtxid" even though it does not fiddle with the s value. And so, both transactions are relayable. Cool. Best would be to have a function that produces those two transactions. That would need the private keys. I guess better be separate from create_malleated_version().

[04:14:16.859]  AttributeError: 'CTransaction' object has no attribute 'rehash'

Unrelated to this PR since it's a refactor, but if we e.g. ever need more than two same-txid-different-wtxid transactions, we could remove the OP_IF branching and use something simpler like OP_DROP OP_TRUE as witness script.

The name build_malleated_children might be confusing since there is nothing "malleated" in those transactions. They are created as such and never changed or malleated afterwards.

Also in the name of ValidWitnessMalleatedTx.

ok agree the terms are confusing - I liked this explanation of different possible forms of malleability.

thinking of doing s/build_malleated_children/build_children_tx_pair and s/ValidWitnessMalleatedTx/DifferentWtxidTx in next push unless anyone has better suggestions!

This works! Following the hint from #29415 (review) I could integrate it into the tests of #29415 to try to send two transactions that have the same txid and different wtxid.

However using it is a bit involved - one has to create a new dedicated parent transaction, get it in the mempool and then broadcast the two children. Also, one has to handle the fees manually. Like this:

self.log.info("Sending a pair of transactions with same txid and different and valid wtxid via RPC")
txgen = ValidWitnessMalleatedTx()
funding = wallet.get_utxo()
fee_sat = 1000
siblings_parent = txgen.build_parent_tx(funding["txid"], amount=funding["value"] * COIN - fee_sat)
sibling1, sibling2 = txgen.build_malleated_children(siblings_parent.txid_hex, amount=siblings_parent.vout[0].nValue - fee_sat)
self.log.info(f"  - sibling1: txid={sibling1.txid_hex}, wtxid={sibling1.wtxid_hex}")
self.log.info(f"  - sibling2: txid={sibling2.txid_hex}, wtxid={sibling2.wtxid_hex}")
wallet.sign_tx(siblings_parent)
tx_returner.send_without_ping(msg_tx(siblings_parent))
self.wait_until(lambda: len(tx_originator.getrawmempool()) > 1)
self.log.info("  - siblings' parent added to the mempool")
assert_equal(sibling1.txid_hex, sibling2.txid_hex)
assert_not_equal(sibling1.wtxid_hex, sibling2.wtxid_hex)
tx_originator.sendrawtransaction(hexstring=sibling1.serialize_with_witness().hex(), maxfeerate=0.1)
self.log.info(f"  - sent sibling1: ok")
ignoring_msg = f"Ignoring unnecessary request to schedule an already scheduled transaction: txid={sibling2.txid_hex}, wtxid={sibling2.wtxid_hex}"
with tx_originator.busy_wait_for_debug_log(expected_msgs=[ignoring_msg.encode()]):
    tx_originator.sendrawtransaction(hexstring=sibling2.serialize_with_witness().hex(), maxfeerate=0.1)
self.log.info(f"  - sibling2 rejected because it has the same txid: ok")

Given that the test already has a transaction that has been sent, I imagined it could be simpler:

self.log.info("Sending a malleated transaction with a valid witness via RPC")
malleated_valid = malleate_tx(txs[0], valid_witness=True)
ignoring_msg = f"Ignoring unnecessary request to schedule an already scheduled transaction: txid={malleated_valid.txid_hex}, wtxid={malleated_valid.wtxid_hex}"
with tx_originator.busy_wait_for_debug_log(expected_msgs=[ignoring_msg.encode()]):                                                                 
    tx_originator.sendrawtransaction(hexstring=malleated_valid.serialize_with_witness().hex(), maxfeerate=0.1)                                 

Here is an incomplete wip that tries to do that:

<details> <summary>[patch] malleate an existent transaction by flipping s to ORDER - s</summary>

diff --git i/test/functional/test_framework/key.py w/test/functional/test_framework/key.py
index 682c2de35f..af62dc353a 100644
--- i/test/functional/test_framework/key.py
+++ w/test/functional/test_framework/key.py
@@ -26,12 +26,49 @@ def TaggedHash(tag, data):
     ss = hashlib.sha256(tag.encode('utf-8')).digest()
     ss += ss
     ss += data
     return hashlib.sha256(ss).digest()
 
 
+def extract_r_and_s_from_der_sig(sig):
+    """
+    Extract r and s from the DER formatted signature. Return False for any DER encoding errors.
+    """
+    if (sig[1] + 2 != len(sig)):
+        return False
+    if (len(sig) < 4):
+        return False
+    if (sig[0] != 0x30):
+        return False
+    if (sig[2] != 0x02):
+        return False
+    rlen = sig[3]
+    if (len(sig) < 6 + rlen):
+        return False
+    if rlen < 1 or rlen > 33:
+        return False
+    if sig[4] >= 0x80:
+        return False
+    if (rlen > 1 and (sig[4] == 0) and not (sig[5] & 0x80)):
+        return False
+    r = int.from_bytes(sig[4:4+rlen], 'big')
+    if (sig[4+rlen] != 0x02):
+        return False
+    slen = sig[5+rlen]
+    if slen < 1 or slen > 33:
+        return False
+    if (len(sig) != 6 + rlen + slen):
+        return False
+    if sig[6+rlen] >= 0x80:
+        return False
+    if (slen > 1 and (sig[6+rlen] == 0) and not (sig[7+rlen] & 0x80)):
+        return False
+    s = int.from_bytes(sig[6+rlen:6+rlen+slen], 'big')
+    return (r, s)
+
+
 class ECPubKey:
     """A secp256k1 public key"""
 
     def __init__(self):
         """Construct an uninitialized public key"""
         self.p = None
@@ -60,44 +97,17 @@ class ECPubKey:
         """Verify a strictly DER-encoded ECDSA signature against this pubkey.
 
         See https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm for the
         ECDSA verifier algorithm"""
         assert self.is_valid
 
-        # Extract r and s from the DER formatted signature. Return false for
-        # any DER encoding errors.
-        if (sig[1] + 2 != len(sig)):
-            return False
-        if (len(sig) < 4):
-            return False
-        if (sig[0] != 0x30):
-            return False
-        if (sig[2] != 0x02):
-            return False
-        rlen = sig[3]
-        if (len(sig) < 6 + rlen):
-            return False
-        if rlen < 1 or rlen > 33:
-            return False
-        if sig[4] >= 0x80:
-            return False
-        if (rlen > 1 and (sig[4] == 0) and not (sig[5] & 0x80)):
-            return False
-        r = int.from_bytes(sig[4:4+rlen], 'big')
-        if (sig[4+rlen] != 0x02):
-            return False
-        slen = sig[5+rlen]
-        if slen < 1 or slen > 33:
-            return False
-        if (len(sig) != 6 + rlen + slen):
-            return False
-        if sig[6+rlen] >= 0x80:
-            return False
-        if (slen > 1 and (sig[6+rlen] == 0) and not (sig[7+rlen] & 0x80)):
+        rs = extract_r_and_s_from_der_sig(sig)
+        if not rs:
             return False
-        s = int.from_bytes(sig[6+rlen:6+rlen+slen], 'big')
+        r = rs[0]
+        s = rs[1]
 
         # Verify that r and s are within the group order
         if r < 1 or s < 1 or r >= ORDER or s >= ORDER:
             return False
         if low_s and s >= secp256k1.GE.ORDER_HALF:
             return False
diff --git i/test/functional/test_framework/messages.py w/test/functional/test_framework/messages.py
index fc36bd3c9e..643680fcd7 100755
--- i/test/functional/test_framework/messages.py
+++ w/test/functional/test_framework/messages.py
@@ -25,13 +25,15 @@ from io import BytesIO
 import math
 import random
 import socket
 import time
 import unittest
 
+from test_framework.crypto import secp256k1
 from test_framework.crypto.siphash import siphash256
+from test_framework.key import extract_r_and_s_from_der_sig
 from test_framework.util import (
     assert_equal,
     assert_not_equal,
 )
 
 MAX_LOCATOR_SZ = 101
@@ -245,27 +247,48 @@ def from_hex(obj, hex_string):
 
 def tx_from_hex(hex_string):
     """Deserialize from hex string to a transaction object"""
     return from_hex(CTransaction(), hex_string)
 
 
-def malleate_tx(tx):
+def get_der_sig(tx):
+    return ""
+
+
+def malleate_tx(tx, valid=False):
     """
-    Create a malleated version of the tx where the witness is replaced with garbage data.
+    Create a malleated version of the tx where the witness is replaced with
+    - same witness with flipped `s` to `ORDER - s` (valid=True)
+    - garbage data (valid=False)
     Returns a CTransaction object.
     """
-    tx_bad_wit = tx_from_hex(tx["hex"])
-    tx_bad_wit.wit.vtxinwit = [CTxInWitness()]
-    # Add garbage data to witness 0. We cannot simply strip the witness, as the node would
-    # classify it as a transaction in which the witness was missing rather than wrong.
-    tx_bad_wit.wit.vtxinwit[0].scriptWitness.stack = [b'garbage']
+    malleated_tx = tx_from_hex(tx["hex"])
+    if valid:
+        sig = get_der_sig(malleated_tx)
+        rs = extract_r_and_s_from_der_sig(sig)
+        r = rs[0]
+        s = rs[1]
+
+        s = secp256k1.GE.ORDER - s
+
+        # copied from test/functional/test_framework/key.py:194
+        rb = r.to_bytes((r.bit_length() + 8) // 8, 'big')
+        sb = s.to_bytes((s.bit_length() + 8) // 8, 'big')
+        malleated_sig = b'\x30' + bytes([4 + len(rb) + len(sb), 2, len(rb)]) + rb + bytes([2, len(sb)]) + sb
+
+        # put malleated_sig into malleated_tx
+    else:
+        malleated_tx.wit.vtxinwit = [CTxInWitness()]
+        # Add garbage data to witness 0. We cannot simply strip the witness, as the node would
+        # classify it as a transaction in which the witness was missing rather than wrong.
+        malleated_tx.wit.vtxinwit[0].scriptWitness.stack = [b'garbage']
 
-    assert_equal(tx["txid"], tx_bad_wit.txid_hex)
-    assert_not_equal(tx["wtxid"], tx_bad_wit.wtxid_hex)
+    assert_equal(tx["txid"], malleated_tx.txid_hex)
+    assert_not_equal(tx["wtxid"], malleated_tx.wtxid_hex)
 
-    return tx_bad_wit
+    return malleated_tx
 
 
 # like from_hex, but without the hex part
 def from_binary(cls, stream):
     """deserialize a binary stream (or bytes object) into an object"""
     # handle bytes object by turning it into a stream

</details>

I like how the interface is simpler! but what about this comment though? - #32385 (review)

transactions constructed using this method would be non-standard. so when we try to sendrawtransaction a high-S signature transaction, mempool accept fails and an error would be returned here.

test_framework.authproxy.JSONRPCException: non-mandatory-script-verify-flag (Non-canonical signature: S value is unnecessarily high), input 0 of 5609730c35a6fc00eb7e5a81b5c1c5db845660724fd5a542ad37a4fa7a1b3a00 (wtxid 8781dc707de437308cdd1b3238cd8fdf5588ce33f577918e4393b046933a2bb8), spending e895effc8ead9753865bd3fd748e756d9a78fda92b914b4f7fbbaedc1a8776bc:0 (-26)