It’s useful to easily create transactions with same txid, different wtxid and valid witness for testing scenarios in other places in the codebase (ex: private broadcast connections, see #29415 (review))
So refactor out the current same-txid-diff-wtxid transaction in mempool_accept_wtxid.py so that it can be reused.
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/32385.
See the guideline for information on the review process.
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.
180@@ -181,6 +181,8 @@ def sign_ecdsa(self, msg, low_s=True, rfc6979=False):
181 s = (pow(k, -1, ORDER) * (z + self.secret * r)) % ORDER
182 if low_s and s > secp256k1.GE.ORDER_HALF:
Could use elif, but as the effect is the same, better to roll this into one if, i think:
0if (low_s and s > secp256k1.GE.ORDER_HALF) or (not low_s and s < secp256k1.GE.ORDER_HALF):
1 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.
2106+
2107+ # 2. Create and sign a transaction spending from the P2WPKH output (bad high-S signature)
2108+ spending_tx = create_tx(funding_p2wpkh_tx.sha256, 0, amount - 1000, script_pubkey)
2109+ pubkey_hash = hash160(pubkey)
2110+ p2pkh_script = keyhash_to_p2pkh_script(pubkey_hash)
2111+ sign_witness_input(spending_tx, 0, p2pkh_script, amount, low_s=False)
I can imagine that malleating a transaction does not require the private key and a re-sign.
Currently there is this function:
0def 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:
flip it to ORDER - s and re-do the DER encoding like:
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.
2123+ assert_not_equal(prev_wtxid, spending_tx.getwtxid())
2124+ # Transaction should now be accepted
2125+ test_transaction_acceptance(self.nodes[1], self.test_node, spending_tx, with_witness=True, accepted=True)
2126+ self.generate(self.nodes[0], 1)
2127+
2128+ # Example 2: P2WSH 1-of-2 multisig transaction where each signature applied to tx results in different wtxid
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().
Concept ACK
Seems useful to create a pair of valid “same-txid-different-wtxid” transactions for testing purposes.
Didn’t try that yet, but I think another possibility to create these without having to involve signatures at all would be a “trivial math puzzle”-like locking script of e.g. “OP_ADD 5 OP_EQUAL” (in a p2wsh or p2tr script-path) and swapped witness data elements ([1,4] and [4,1]) in the spending txs.
2077+
2078+ def create_tx(prev_txid, prev_index, amount, script_pubkey):
2079+ tx = CTransaction()
2080+ tx.vin.append(CTxIn(COutPoint(prev_txid, prev_index), b""))
2081+ tx.vout.append(CTxOut(amount, script_pubkey))
2082+ tx.rehash()
useful to easily create transactions with same txid, different
wtxid and valid witness for testing scenarios in other places
(ex: private broadcast connections)
review ACK afaaba69eddd50bc22b94ca7c0f9195773aaa111 📎
Signature:
0untrusted comment: signature from minisign secret key on empty file; verify via: minisign -Vm "${path_to_any_empty_file}" -P RWTRmVTMeKV5noAMqVlsMugDDCyyTSbA3Re5AkUrhvLVln0tSaFWglOw -x "${path_to_this_whole_four_line_signature_blob}"
1RUTRmVTMeKV5npGrKx1nqXCw5zeVHdtdYURB/KlyA/LMFgpNCs+SkW9a8N95d+U4AP1RJMi+krxU1A3Yux4bpwZNLvVBKy0wLgM=
2trusted comment: review ACK afaaba69eddd50bc22b94ca7c0f9195773aaa111 📎
3w44y4qKZmXzcguTW5prhwG9RaYGgH9OHX1jY8LvGM8uNagph12jUxir9RBvQEygHsFYJoYCA815jxbITO6+/AA==
So I changed the approach in the PR. mempool_accept_wtxid.py already was dealing with same-txid-different-wtxid scenario and I’ve simply refactored it out.
Here’s an example of how it can be used in the private broadcast tests - https://github.com/stratospher/bitcoin/commit/c14812402aa370b448a46efad1b0e5a5af1199ee
Didn’t try that yet, but I think another possibility to create these without having to involve signatures at all would be a “trivial math puzzle”-like locking script of e.g. “OP_ADD 5 OP_EQUAL” (in a p2wsh or p2tr script-path) and swapped witness data elements ([1,4] and [4,1]) in the spending txs.
Yes! This P2TR locking script worked and I honestly liked it better than the current P2WSH one we have (more compact + cleaner). I didn’t change it though for easier review and both give same-txid-different-wtxid anyways.
150+ - Parent transaction with a script supporting 2 branches
151+ - 2 child transactions with the same txid but different wtxids
152+ """
153+ def __init__(self):
154+ hashlock = hash160(b'Preimage')
155+ self.witness_script = CScript([OP_IF, OP_HASH160, hashlock, OP_EQUAL, OP_ELSE, OP_TRUE, OP_ENDIF])
162+ parent = CTransaction()
163+ parent.vin.append(CTxIn(COutPoint(int(funding_txid, 16), 0), b""))
164+ parent.vout.append(CTxOut(int(amount), script_pubkey))
165+ return parent
166+
167+ def build_malleated_children(self, signed_parent_txid, amount):
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!
143@@ -131,6 +144,45 @@ def check_script(script):
144 assert False
145
146
147+class ValidWitnessMalleatedTx:
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:
0self.log.info("Sending a pair of transactions with same txid and different and valid wtxid via RPC")
1txgen = ValidWitnessMalleatedTx()
2funding = wallet.get_utxo()
3fee_sat = 1000
4siblings_parent = txgen.build_parent_tx(funding["txid"], amount=funding["value"] * COIN - fee_sat)
5sibling1, sibling2 = txgen.build_malleated_children(siblings_parent.txid_hex, amount=siblings_parent.vout[0].nValue - fee_sat)
6self.log.info(f" - sibling1: txid={sibling1.txid_hex}, wtxid={sibling1.wtxid_hex}")
7self.log.info(f" - sibling2: txid={sibling2.txid_hex}, wtxid={sibling2.wtxid_hex}")
8wallet.sign_tx(siblings_parent)
9tx_returner.send_without_ping(msg_tx(siblings_parent))
10self.wait_until(lambda: len(tx_originator.getrawmempool()) > 1)
11self.log.info(" - siblings' parent added to the mempool")
12assert_equal(sibling1.txid_hex, sibling2.txid_hex)
13assert_not_equal(sibling1.wtxid_hex, sibling2.wtxid_hex)
14tx_originator.sendrawtransaction(hexstring=sibling1.serialize_with_witness().hex(), maxfeerate=0.1)
15self.log.info(f" - sent sibling1: ok")
16ignoring_msg = f"Ignoring unnecessary request to schedule an already scheduled transaction: txid={sibling2.txid_hex}, wtxid={sibling2.wtxid_hex}"
17with tx_originator.busy_wait_for_debug_log(expected_msgs=[ignoring_msg.encode()]):
18 tx_originator.sendrawtransaction(hexstring=sibling2.serialize_with_witness().hex(), maxfeerate=0.1)
19self.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:
0self.log.info("Sending a malleated transaction with a valid witness via RPC")
1malleated_valid = malleate_tx(txs[0], valid_witness=True)
2ignoring_msg = f"Ignoring unnecessary request to schedule an already scheduled transaction: txid={malleated_valid.txid_hex}, wtxid={malleated_valid.wtxid_hex}"
3with tx_originator.busy_wait_for_debug_log(expected_msgs=[ignoring_msg.encode()]):
4 tx_originator.sendrawtransaction(hexstring=malleated_valid.serialize_with_witness().hex(), maxfeerate=0.1)
Here is an incomplete wip that tries to do that:
0diff --git i/test/functional/test_framework/key.py w/test/functional/test_framework/key.py
1index 682c2de35f..af62dc353a 100644
2--- i/test/functional/test_framework/key.py
3+++ w/test/functional/test_framework/key.py
4@@ -26,12 +26,49 @@ def TaggedHash(tag, data):
5 ss = hashlib.sha256(tag.encode('utf-8')).digest()
6 ss += ss
7 ss += data
8 return hashlib.sha256(ss).digest()
9
10
11+def extract_r_and_s_from_der_sig(sig):
12+ """
13+ Extract r and s from the DER formatted signature. Return False for any DER encoding errors.
14+ """
15+ if (sig[1] + 2 != len(sig)):
16+ return False
17+ if (len(sig) < 4):
18+ return False
19+ if (sig[0] != 0x30):
20+ return False
21+ if (sig[2] != 0x02):
22+ return False
23+ rlen = sig[3]
24+ if (len(sig) < 6 + rlen):
25+ return False
26+ if rlen < 1 or rlen > 33:
27+ return False
28+ if sig[4] >= 0x80:
29+ return False
30+ if (rlen > 1 and (sig[4] == 0) and not (sig[5] & 0x80)):
31+ return False
32+ r = int.from_bytes(sig[4:4+rlen], 'big')
33+ if (sig[4+rlen] != 0x02):
34+ return False
35+ slen = sig[5+rlen]
36+ if slen < 1 or slen > 33:
37+ return False
38+ if (len(sig) != 6 + rlen + slen):
39+ return False
40+ if sig[6+rlen] >= 0x80:
41+ return False
42+ if (slen > 1 and (sig[6+rlen] == 0) and not (sig[7+rlen] & 0x80)):
43+ return False
44+ s = int.from_bytes(sig[6+rlen:6+rlen+slen], 'big')
45+ return (r, s)
46+
47+
48 class ECPubKey:
49 """A secp256k1 public key"""
50
51 def __init__(self):
52 """Construct an uninitialized public key"""
53 self.p = None
54@@ -60,44 +97,17 @@ class ECPubKey:
55 """Verify a strictly DER-encoded ECDSA signature against this pubkey.
56
57 See https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm for the
58 ECDSA verifier algorithm"""
59 assert self.is_valid
60
61- # Extract r and s from the DER formatted signature. Return false for
62- # any DER encoding errors.
63- if (sig[1] + 2 != len(sig)):
64- return False
65- if (len(sig) < 4):
66- return False
67- if (sig[0] != 0x30):
68- return False
69- if (sig[2] != 0x02):
70- return False
71- rlen = sig[3]
72- if (len(sig) < 6 + rlen):
73- return False
74- if rlen < 1 or rlen > 33:
75- return False
76- if sig[4] >= 0x80:
77- return False
78- if (rlen > 1 and (sig[4] == 0) and not (sig[5] & 0x80)):
79- return False
80- r = int.from_bytes(sig[4:4+rlen], 'big')
81- if (sig[4+rlen] != 0x02):
82- return False
83- slen = sig[5+rlen]
84- if slen < 1 or slen > 33:
85- return False
86- if (len(sig) != 6 + rlen + slen):
87- return False
88- if sig[6+rlen] >= 0x80:
89- return False
90- if (slen > 1 and (sig[6+rlen] == 0) and not (sig[7+rlen] & 0x80)):
91+ rs = extract_r_and_s_from_der_sig(sig)
92+ if not rs:
93 return False
94- s = int.from_bytes(sig[6+rlen:6+rlen+slen], 'big')
95+ r = rs[0]
96+ s = rs[1]
97
98 # Verify that r and s are within the group order
99 if r < 1 or s < 1 or r >= ORDER or s >= ORDER:
100 return False
101 if low_s and s >= secp256k1.GE.ORDER_HALF:
102 return False
103diff --git i/test/functional/test_framework/messages.py w/test/functional/test_framework/messages.py
104index fc36bd3c9e..643680fcd7 100755
105--- i/test/functional/test_framework/messages.py
106+++ w/test/functional/test_framework/messages.py
107@@ -25,13 +25,15 @@ from io import BytesIO
108 import math
109 import random
110 import socket
111 import time
112 import unittest
113
114+from test_framework.crypto import secp256k1
115 from test_framework.crypto.siphash import siphash256
116+from test_framework.key import extract_r_and_s_from_der_sig
117 from test_framework.util import (
118 assert_equal,
119 assert_not_equal,
120 )
121
122 MAX_LOCATOR_SZ = 101
123@@ -245,27 +247,48 @@ def from_hex(obj, hex_string):
124
125 def tx_from_hex(hex_string):
126 """Deserialize from hex string to a transaction object"""
127 return from_hex(CTransaction(), hex_string)
128
129
130-def malleate_tx(tx):
131+def get_der_sig(tx):
132+ return ""
133+
134+
135+def malleate_tx(tx, valid=False):
136 """
137- Create a malleated version of the tx where the witness is replaced with garbage data.
138+ Create a malleated version of the tx where the witness is replaced with
139+ - same witness with flipped `s` to `ORDER - s` (valid=True)
140+ - garbage data (valid=False)
141 Returns a CTransaction object.
142 """
143- tx_bad_wit = tx_from_hex(tx["hex"])
144- tx_bad_wit.wit.vtxinwit = [CTxInWitness()]
145- # Add garbage data to witness 0. We cannot simply strip the witness, as the node would
146- # classify it as a transaction in which the witness was missing rather than wrong.
147- tx_bad_wit.wit.vtxinwit[0].scriptWitness.stack = [b'garbage']
148+ malleated_tx = tx_from_hex(tx["hex"])
149+ if valid:
150+ sig = get_der_sig(malleated_tx)
151+ rs = extract_r_and_s_from_der_sig(sig)
152+ r = rs[0]
153+ s = rs[1]
154+
155+ s = secp256k1.GE.ORDER - s
156+
157+ # copied from test/functional/test_framework/key.py:194
158+ rb = r.to_bytes((r.bit_length() + 8) // 8, 'big')
159+ sb = s.to_bytes((s.bit_length() + 8) // 8, 'big')
160+ malleated_sig = b'\x30' + bytes([4 + len(rb) + len(sb), 2, len(rb)]) + rb + bytes([2, len(sb)]) + sb
161+
162+ # put malleated_sig into malleated_tx
163+ else:
164+ malleated_tx.wit.vtxinwit = [CTxInWitness()]
165+ # Add garbage data to witness 0. We cannot simply strip the witness, as the node would
166+ # classify it as a transaction in which the witness was missing rather than wrong.
167+ malleated_tx.wit.vtxinwit[0].scriptWitness.stack = [b'garbage']
168
169- assert_equal(tx["txid"], tx_bad_wit.txid_hex)
170- assert_not_equal(tx["wtxid"], tx_bad_wit.wtxid_hex)
171+ assert_equal(tx["txid"], malleated_tx.txid_hex)
172+ assert_not_equal(tx["wtxid"], malleated_tx.wtxid_hex)
173
174- return tx_bad_wit
175+ return malleated_tx
176
177
178 # like from_hex, but without the hex part
179 def from_binary(cls, stream):
180 """deserialize a binary stream (or bytes object) into an object"""
181 # handle bytes object by turning it into a stream
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.
0test_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)
ACK afaaba69eddd50bc22b94ca7c0f9195773aaa111
The code seems to do what is intended and I confirm that it works. I guess it is useful as a generic tool to create a new transaction and two new children of it that have the same txid and different wtxid.
That is useful for the tests of #29415 too. However those tests already have a transaction and it would be easier for them and less code, if malleate_tx() could create a malleated/changed version of an existent transaction with a valid witness. See the comment below.
Thanks!