test: fix MiniWallet script-path spend (missing parity bit in leaf version)

theStack commented at 10:52 pm on May 9, 2024: contributor

This PR fixes a dormant bug in MiniWallet that exists since support for P2TR was initially added in #23371 (see commit 041abfebe49ae5e3e882c00cc5caea1365a27a49).

In the course of spending the output, the leaf version byte of the control block in the witness stack doesn’t set the parity bit, i.e. we were so far just lucky that the used combinations of relevant data (internal pubkey, leaf script / version) didn’t result in a tweaked pubkey with odd y-parity. If that was the case, we’d get the following validation error:

mandatory-script-verify-flag-failed (Witness program hash mismatch) (-26)

Since MiniWallets can now optionally be tagged (#29939), resulting in different internal pubkeys, the issue is more prevalent now. Fix it by passing the parity bit, as specified in BIP341.

Can be tested with the following patch (fails on master, succeeds on PR):

 0diff --git a/test/functional/test_framework/mempool_util.py b/test/functional/test_framework/mempool_util.py
 1index 148cc935ed..7ebe858681 100644
 2--- a/test/functional/test_framework/mempool_util.py
 3+++ b/test/functional/test_framework/mempool_util.py
 4@@ -42,7 +42,7 @@ def fill_mempool(test_framework, node):
 5     # Generate UTXOs to flood the mempool
 6     # 1 to create a tx initially that will be evicted from the mempool later
 7     # 75 transactions each with a fee rate higher than the previous one
 8-    ephemeral_miniwallet = MiniWallet(node, tag_name="fill_mempool_ephemeral_wallet")
 9+    ephemeral_miniwallet = MiniWallet(node, tag_name="fill_mempool_ephemeral_wallet3")
10     test_framework.generate(ephemeral_miniwallet, 1 + num_of_batches * tx_batch_size)
11 
12     # Mine enough blocks so that the UTXOs are allowed to be spent

In addition to that, another bug is fixed where the internal key derivation failed, as not every pseudorandom hash results in a valid x-only pubkey. Fix this by treating the hash result as private key and calculate the x-only public key out of that, to be used then as internal key.

Fixes #30528.

DrahtBot commented at 10:52 pm on May 9, 2024: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	glozow, rkrux, hodlinator

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#29371 (test: Add leaf_version parameter to taproot_tree_helper() by Christewart)
#29221 (Implement 64 bit arithmetic op codes in the Script interpreter by Christewart)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

DrahtBot added the label Tests on May 9, 2024

in test/functional/test_framework/wallet.py:189 in e4abac2fce outdated

185@@ -187,7 +186,11 @@ def sign_tx(self, tx, fixed_length=True):
186         elif self._mode == MiniWalletMode.ADDRESS_OP_TRUE:
187             tx.wit.vtxinwit = [CTxInWitness()] * len(tx.vin)
188             for i in tx.wit.vtxinwit:
189-                i.scriptWitness.stack = [CScript([OP_TRUE]), bytes([LEAF_VERSION_TAPSCRIPT]) + self._internal_key]
190+                leaf_info = self._taproot_info.leaves["only-path"]

rkrux commented at 12:23 pm on May 10, 2024:

I feel we should tie this only-path here to taproot_construct call in address.py, either by passing it as a parameter or creating it as a constant. Otherwise, it makes you wonder here at this line where did only-path come from.

theStack commented at 6:40 am on May 11, 2024:

Good point. I think what we could do here is first asserting that there is only a single entry in the _taproot_info.leaves dictionary and then using that entry, so we don’t even need the “only-path” magic string. Will look into it.

rkrux commented at 7:21 am on May 12, 2024:

Yes, this is also good.

in test/functional/test_framework/wallet.py:202 in e4abac2fce outdated

185@@ -187,7 +186,11 @@ def sign_tx(self, tx, fixed_length=True):
186         elif self._mode == MiniWalletMode.ADDRESS_OP_TRUE:
187             tx.wit.vtxinwit = [CTxInWitness()] * len(tx.vin)
188             for i in tx.wit.vtxinwit:
189-                i.scriptWitness.stack = [CScript([OP_TRUE]), bytes([LEAF_VERSION_TAPSCRIPT]) + self._internal_key]
190+                leaf_info = self._taproot_info.leaves["only-path"]
191+                i.scriptWitness.stack = [
192+                    leaf_info.script,
193+                    bytes([leaf_info.version | self._taproot_info.negflag]) + self._taproot_info.internal_pubkey,
194+                ]

rkrux commented at 12:23 pm on May 10, 2024:

Would love to see the corresponding cpp reference code, share if you know?

theStack commented at 6:48 am on May 11, 2024:

The corresponding C++ code in Core for creating the control block (second item on the witness stack) can be found in the signingprovider module, see function TaprootBuilder::GetSpendData(): https://github.com/bitcoin/bitcoin/blob/2cedb42a928fbf3a1e0e8715e918497cbe64af0d/src/script/signingprovider.cpp#L414-L417

The actual witness stack, consisting of script and control block, is assembled in the SignTaproot function: https://github.com/bitcoin/bitcoin/blob/2cedb42a928fbf3a1e0e8715e918497cbe64af0d/src/script/sign.cpp#L379-L380

The validation counter-part for taproot script-path spends is found here: https://github.com/bitcoin/bitcoin/blob/2cedb42a928fbf3a1e0e8715e918497cbe64af0d/src/script/interpreter.cpp#L1923-L1932

rkrux commented at 7:22 am on May 12, 2024:

Great, thanks for sharing, I’m digging into this!

rkrux approved

rkrux commented at 12:26 pm on May 10, 2024: none

tACK e4abac2

Reviewing #29939 previously made it easy for me to review this one!

Make successful and all functional tests pass on this branch. Using the shared patch, I can see these 2 tests fail in master branch.

0feature_versionbits_warning.py                         | ✖ Failed  | 3 s
1wallet_fundrawtransaction.py --descriptors             | ✖ Failed  | 17 s
2
3ALL                                                    | ✖ Failed  | 2752 s (accumulated)

theStack force-pushed on May 11, 2024

theStack commented at 4:51 pm on May 11, 2024: contributor

Thanks for the review @rkrux! Addressed your comment #30076 (review); the single taproot leaf is now accessed directly rather than by name, so there is no magic string involved anymore. Note that the leaf name (second parameter to taproot_construct) still had to be changed from None to some string, as otherwise no entry in the taproot_info.leaves dictionary would be created.

rkrux commented at 7:41 am on May 12, 2024: none

@theStack Thanks for the quick update on this, reACK 57eb590

DrahtBot added the label Needs rebase on Jun 11, 2024

test: refactor: return TaprootInfo from P2TR address creation routine

Rather than only returning the internal key from the P2TR anyone-can-spend
address creation routine, provide the whole TaprootInfo object, which in turn
contains a dictionary of TaprootLeafInfo object for named leaves.

This data is used in MiniWallet for the default ADDRESS_OP_TRUE mode, in order
to deduplicate the witness script and leaf version of the control block.

7774c314fb

test: fix MiniWallet script-path spend (missing parity bit in leaf version)

This commit fixes a dormant bug in MiniWallet that exists since
support for P2TR was initially added in #23371 (see commit
041abfebe49ae5e3e882c00cc5caea1365a27a49).

In the course of spending the output, the leaf version byte of the
control block in the witness stack doesn't set the parity bit, i.e.
we were so far just lucky that the used combinations of relevant
data (internal pubkey, leaf script / version) didn't result in a
tweaked pubkey with odd y-parity. If that was the case, we'd get the
following validation error:

`mandatory-script-verify-flag-failed (Witness program hash mismatch) (-26)`

Since MiniWallets can now optionally be tagged (#29939), resulting
in different internal pubkeys, the issue is more prevalent now.
Fix it by passing the parity bit, as specified in BIP341.

c9f7364ab2

test: fix MiniWallet internal key derivation for tagged instances

Not every pseudorandom hash result is a valid x-only public key,
so the pubkey tweaking in the course of creating the output public
key would fail about every second time.

Fix this by treating the hash result as private key and calculate
the x-only public key out of that, to be used then as internal key.

3162c917e9

test: add functional test for tagged MiniWallet instances e4b0dabb21

theStack force-pushed on Jun 11, 2024

theStack commented at 4:58 pm on June 11, 2024: contributor

Rebased on master, after the merge of #30162. Adding a functional test for tagged wallets to the new feature_framework_miniwallet.py (see commit e4b0dabb2115dc74e9c5794ddca3822cd8301c72) revealed another bug w.r.t. the internal key derivation. The code on master wrongly assumes that every pseudorandom hash results in a valid x-only pubkey. Fix this by treating the hash result as private key and calculate the x-only public key out of that, to be used then as internal key (see commit 3162c917e93fde4bea6e4627bb0c3c7cdc37386c).

DrahtBot removed the label Needs rebase on Jun 11, 2024

glozow commented at 4:28 pm on June 17, 2024: member

ACK e4b0dabb2115dc74e9c5794ddca3822cd8301c72

Not an expert but: Checked that test_wallet_tagging fails without the fix on “mandatory-script-verify-flag-failed (Witness program hash mismatch) (-26)”. Reviewed the test by editing the parity check in VerifyTaprootCommitment to make it pass on master and examining bytes(version + negflag) while running.

DrahtBot requested review from rkrux on Jun 17, 2024

rkrux approved

rkrux commented at 8:25 pm on June 17, 2024: none

reACK e4b0dab

Applied the shared patch again and the following tests fail on master with the mentioned error. Though I’ve not been able to go through the corresponding control block C++ code yet :(

0raise JSONRPCException(response['error'], status)
1test_framework.authproxy.JSONRPCException: mandatory-script-verify-flag-failed (Witness program hash mismatch) (-26)

0mempool_limit.py                                         | ✖ Failed  | 1 s
1p2p_1p1c_network.py                                      | ✖ Failed  | 5 s
2p2p_opportunistic_1p1c.py                                | ✖ Failed  | 1 s
3p2p_tx_download.py                                       | ✖ Failed  | 31 s
4rpc_packages.py                                          | ✖ Failed  | 3 s

in test/functional/feature_framework_miniwallet.py:42 in e4b0dabb21

33@@ -31,6 +34,20 @@ def test_tx_padding(self):
34                 assert_greater_than_or_equal(tx.get_weight(), target_weight)
35                 assert_greater_than_or_equal(target_weight + 3, tx.get_weight())
36 
37+    def test_wallet_tagging(self):
38+        """Verify that tagged wallet instances are able to send funds."""
39+        self.log.info(f"Test tagged wallet instances...")
40+        node = self.nodes[0]
41+        untagged_wallet = self.wallets[0][1]
42+        for i in range(10):

rkrux commented at 8:30 pm on June 17, 2024:

Is the sole reason for creating 10 tagged wallets to be thorough? Or is there any other reason as well?

rkrux commented at 8:31 pm on June 17, 2024:

i.e. to test for the following assumption

we were so far just lucky that the used combinations of relevant data (internal pubkey, leaf script / version) didn’t result in a tweaked pubkey with odd y-parity.

theStack commented at 1:13 am on June 18, 2024:

Is the sole reason for creating 10 tagged wallets to be thorough? Or is there any other reason as well?

Yes it’s thoroughness, no other reason. Since the fixed bugs only occur with a certain probability, creating several random tagged wallets in a row increase the likelihood of catching the bugs in a single test run (nothing special about the number 10 though).

rkrux commented at 5:36 am on June 18, 2024: none

Got it, nice.

On Tue, Jun 18, 2024, 06:43 Sebastian Falbesoner @.***> wrote:

@.**** commented on this pull request.

In test/functional/feature_framework_miniwallet.py https://github.com/bitcoin/bitcoin/pull/30076#discussion_r1643600316:

@@ -31,6 +34,20 @@ def test_tx_padding(self): assert_greater_than_or_equal(tx.get_weight(), target_weight) assert_greater_than_or_equal(target_weight + 3, tx.get_weight())
def test_wallet_tagging(self):
   """Verify that tagged wallet instances are able to send funds."""
   self.log.info(f"Test tagged wallet instances...")
   node = self.nodes[0]
   untagged_wallet = self.wallets[0][1]
   for i in range(10):
Is the sole reason for creating 10 tagged wallets to be thorough? Or is there any other reason as well?

Yes it’s thoroughness, no other reason. Since the fixed bugs only occur with a certain probability, creating several random tagged wallets in a row increase the likelihood of catching the bugs in a single test run (nothing special about the number 10 though).

— Reply to this email directly, view it on GitHub https://github.com/bitcoin/bitcoin/pull/30076#discussion_r1643600316, or unsubscribe https://github.com/notifications/unsubscribe-auth/ABNPILUIX2ZRNELG5ECQDSLZH6CT3AVCNFSM6AAAAABHPTP73OVHI2DSMVQWIX3LMV43YUDVNRWFEZLROVSXG5CSMV3GSZLXHMZDCMRUGE2TAMBSGE . You are receiving this because you were mentioned.Message ID: @.***>

DrahtBot added the label CI failed on Jul 17, 2024

DrahtBot removed the label CI failed on Jul 23, 2024

hodlinator approved

hodlinator commented at 9:06 am on July 26, 2024: contributor

ACK e4b0dabb2115dc74e9c5794ddca3822cd8301c72

Confirmed to fix #30528 which I discovered independently. Rebased my test commit from there on top of this PR and verified that exceptions are no longer raised for the 2 cases I found.

Re-ran feature_framework_miniwallet.py without my changes on top and verified it passed. Also ran with --randomseed <X> to verify that tag names are generated deterministically.

Passed test_runner.py (other tests are using MiniWallet indirectly, and mempool_util.py specifically was already using a tag_name value that still works).

Not an expert on Taproot so haven’t fully understood the context around the fixes, but they look small & safe and only touch functional test Python code.

Sorry again for not finding this PR before creating the issue. Eager to use this fix to fearlessly create multiple tagged wallets in upcoming tests. :)

glozow merged this on Jul 26, 2024

glozow closed this on Jul 26, 2024

theStack deleted the branch on Jul 26, 2024

test: fix MiniWallet script-path spend (missing parity bit in leaf version) #30076

Code Coverage

Reviews

Conflicts

@.**** commented on this pull request.