wallet: Avoid underpaying transaction fees when signing taproot spends

achow101 commented at 1:57 am on November 13, 2021: member

The current taproot signing code will end up creating transactions which do not meet the feerate target. This is primarily seen when spending a taproot output with the script path. In this scenario, because the public key is known, the dummy signer would incorrectly choose to create a dummy signed transaction that used the key path spend when the actual transaction would use script path. This results in a transaction that has a significantly lower fee rate because script path spends are much larger than key path spends. This is fixed by choosing the witness with the largest stack size rather than the smallest when doing size estimation.

Unfortunately this change can result in massively overestimating the transaction fees which is undesirable. More discussion is needed to find a good solution to avoiding that problem.

There is an additional issue in the PSBT workflow where the sighash type would be appended during finalizing, but not during size estimation. That results in a transaction that is slightly larger than estimated so there is a lower feerate. This is resolved by having the DUMMY_MAXIMUM_SIGNATURE_CREATOR include the sighash type so that when funding with a watchonly wallet, we will estimate enough fee for the largest possible signature (as we do for ECDSA with high R).

Tests are updated to catch these case. wallet_taproot.py will now use a set feerate and check if the result meets that feerate.

fanquake added the label Wallet on Nov 13, 2021

DrahtBot commented at 3:19 am on November 14, 2021: contributor

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

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	aureleoules
Concept ACK	darosior, murchandamus

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:

#28212 (test: verify spend from 999-of-999 taproot multisig wallet by eriknylund)

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.

achow101 force-pushed on Nov 15, 2021

achow101 marked this as ready for review on Nov 15, 2021

achow101 force-pushed on Nov 15, 2021

in src/script/sign.cpp:652 in 46dc1e68fe outdated

570@@ -570,14 +571,17 @@ class DummySignatureCreator final : public BaseSignatureCreator {
571     bool CreateSchnorrSig(const SigningProvider& provider, std::vector<unsigned char>& sig, const XOnlyPubKey& pubkey, const uint256* leaf_hash, const uint256* tweak, SigVersion sigversion) const override
572     {
573         sig.assign(64, '\000');
574+        if (m_include_sighash) {
575+            sig.push_back((unsigned char)SIGHASH_ALL);

sipa commented at 8:51 pm on November 23, 2021:

Could just do sig.assign(64 + m_include_sighash, '\000'); in the previous line.

achow101 commented at 7:31 pm on December 5, 2021:

IMO that’s a bit harder to read and I don’t like the implicit bool to int conversion.

laanwj commented at 2:35 pm on December 17, 2021:

Have to agree with @achow101 here. Even though the alternative formulation is shorter ,and correct, I understand the intent of the code better this way.

in src/script/sign.cpp:229 in 899185d5f1 outdated

186@@ -187,6 +187,11 @@ static bool SignTaproot(const SigningProvider& provider, const BaseSignatureCrea
187         sigdata.tr_spenddata.Merge(spenddata);
188     }
189 
190+    // Detect if this is the dummy signer. If so, we want to choose the largest stack size for worst case size estimation

sipa commented at 8:52 pm on November 23, 2021:

That’s pretty ugly. What about adding a “bool ForFeeEstimation()” to all SignatureCreator instances, and calling that instead?

achow101 commented at 7:51 pm on December 6, 2021:

I added an IsDummy and changed to check that instead.

achow101 force-pushed on Dec 6, 2021

bitcoin deleted a comment on Dec 7, 2021

in src/script/sign.cpp:601 in 6c2f69d595 outdated

592@@ -570,14 +593,18 @@ class DummySignatureCreator final : public BaseSignatureCreator {
593     bool CreateSchnorrSig(const SigningProvider& provider, std::vector<unsigned char>& sig, const XOnlyPubKey& pubkey, const uint256* leaf_hash, const uint256* tweak, SigVersion sigversion) const override
594     {
595         sig.assign(64, '\000');
596+        if (m_include_sighash) {
597+            sig.push_back((unsigned char)SIGHASH_ALL);
598+        }
599         return true;
600     }
601+    bool IsDummy() const override { return true; }

laanwj commented at 2:50 pm on December 17, 2021:

Adding a method to ask an interface if it’s a certain class seems like a design inversion to me. If we can’t move the actual responsibility into the class, is there some more semantic name that we could consider? I see it’s assigned to use_largest, so maybe UseLargest? (then further describe in the doc-comment Choose the largest stack size for worst case size estimation when using this signer.).

achow101 commented at 8:54 pm on January 10, 2022:

Changed to UseLargest

achow101 force-pushed on Jan 10, 2022

flack commented at 4:49 pm on January 29, 2022: contributor

Not sure if I understand this correctly, but the underestimation could also lead to a situation where minrelaytxfee is not met, right? If so, maybe a good first step would be to prevent that.

DrahtBot added the label Needs rebase on Mar 4, 2022

achow101 force-pushed on Mar 4, 2022

DrahtBot removed the label Needs rebase on Mar 4, 2022

DrahtBot added the label Needs rebase on Jun 28, 2022

achow101 force-pushed on Jun 28, 2022

DrahtBot removed the label Needs rebase on Jun 28, 2022

in src/script/sign.cpp:277 in 7f927b7577 outdated

276-                smallest_result_stack = std::move(result_stack);
277+                stack_size < smallest_result_stack_size) {
278+                smallest_result_stack = result_stack;
279+                smallest_result_stack_size = stack_size;
280+            }
281+            if (use_largest && (largest_result_stack.size() == 0 ||

aureleoules commented at 12:13 pm on October 7, 2022:

nit 7f927b757748e03234d451a09309e5d788cb77d2 same above and below

0            if (use_largest && (largest_result_stack.empty() ||

in src/script/sign.cpp:272 in 7f927b7577 outdated

269         std::vector<std::vector<unsigned char>> result_stack;
270         if (SignTaprootScript(provider, creator, sigdata, leaf_ver, script, result_stack)) {
271             result_stack.emplace_back(std::begin(script), std::end(script)); // Push the script
272             result_stack.push_back(*control_blocks.begin()); // Push the smallest control block
273+            uint64_t stack_size = GetSerializeSize(result_stack, PROTOCOL_VERSION);
274             if (smallest_result_stack.size() == 0 ||

aureleoules commented at 12:14 pm on October 7, 2022:

if you retouch

0            if (smallest_result_stack.empty() ||

aureleoules approved

aureleoules commented at 12:17 pm on October 7, 2022: member

ACK 7f927b757748e03234d451a09309e5d788cb77d2 - LGTM I also verified the test does not pass on master.

fanquake requested review from instagibbs on Oct 10, 2022

in src/script/sign.cpp:632 in caf5db2b65 outdated

629 }
630 
631-const BaseSignatureCreator& DUMMY_SIGNATURE_CREATOR = DummySignatureCreator(32, 32);
632-const BaseSignatureCreator& DUMMY_MAXIMUM_SIGNATURE_CREATOR = DummySignatureCreator(33, 32);
633+const BaseSignatureCreator& DUMMY_SIGNATURE_CREATOR = DummySignatureCreator(32, 32, false);
634+const BaseSignatureCreator& DUMMY_MAXIMUM_SIGNATURE_CREATOR = DummySignatureCreator(33, 32, true);

instagibbs commented at 6:12 pm on October 11, 2022:

annotate these args?

achow101 commented at 3:02 pm on October 17, 2022:

Done

in src/script/sign.h:37 in 8d8d092a73 outdated

31@@ -32,6 +32,9 @@ class BaseSignatureCreator {
32     /** Create a singular (non-script) signature. */
33     virtual bool CreateSig(const SigningProvider& provider, std::vector<unsigned char>& vchSig, const CKeyID& keyid, const CScript& scriptCode, SigVersion sigversion) const =0;
34     virtual bool CreateSchnorrSig(const SigningProvider& provider, std::vector<unsigned char>& sig, const XOnlyPubKey& pubkey, const uint256* leaf_hash, const uint256* merkle_root, SigVersion sigversion) const =0;
35+
36+    /** Choose the largest stack size for worst case size estimation when using this signer */
37+    virtual bool UseLargest() const =0;

instagibbs commented at 6:14 pm on October 11, 2022:

slightly philosophical question: If the wallet knows how to satisfy two script paths, will it use the more expensive one?

achow101 commented at 3:02 pm on October 17, 2022:

No. This change only affects dummy signing, but for actual signing, it will still use smallest solution.

in test/functional/test_framework/util.py:53 in 7f927b7577 outdated

45@@ -46,6 +46,13 @@ def assert_fee_amount(fee, tx_size, feerate_BTC_kvB):
46         raise AssertionError("Fee of %s BTC too high! (Should be %s BTC)" % (str(fee), str(target_fee)))
47 
48 
49+def assert_fee_enough(fee, tx_size, feerate_BTC_kvB):
50+    """Assert the fee meets the feerate"""
51+    target_fee = get_fee(tx_size, feerate_BTC_kvB)
52+    if fee < target_fee:
53+        raise AssertionError("Fee of %s BTC too low! (Should be %s BTC)" % (str(fee), str(target_fee)))

instagibbs commented at 6:19 pm on October 11, 2022:

should be at least*

achow101 commented at 3:03 pm on October 17, 2022:

Done

achow101 force-pushed on Oct 17, 2022

DrahtBot added the label Needs rebase on Nov 4, 2022

sign: Include sighash byte for Schnorr sigs with DUMMY_MAX_SIG_CREATOR 0b33bbe1ac

Add UseLargest function to BaseSignatureCreator

Sometimes we need to know whether we should be choosing the largest
stack size for worse case size estimation. BaseSignatureCreator can
report that to us as we only need to do this when using
DummySignatureCreator.

58a988dda1

Use largest stack size when estimating size

When estimating the size of a taproot witness (i.e.
DummySignatureCreator is being used), use the largest stack size rather
than the smallest. This avoids underpaying fees.

Also updates the tests to make sure that Taproot spends do not
underestimate the fee

5345b80005

achow101 force-pushed on Nov 4, 2022

DrahtBot removed the label Needs rebase on Nov 4, 2022

aureleoules approved

aureleoules commented at 4:36 pm on November 17, 2022: member

reACK 5345b800053963eab2b4cf61662258e8821456b6

darosior commented at 12:44 pm on November 25, 2022: member

Concept ACK. But for the approach i would prefer something like #26573 instead of making the signing logic still more intricate. But that can also happen afterward.

Regarding having a more accurate estimation, i think we should eventually hint to what material in a descriptor will be available at signing time. But i’m not sure yet how. For your interest elsewhere people are testing some approaches to solve this problem: https://github.com/rust-bitcoin/rust-miniscript/pull/481.

achow101 commented at 8:42 pm on December 15, 2022: member

Concept ACK. But for the approach i would prefer something like #26573 instead of making the signing logic still more intricate. But that can also happen afterward.

The approach in this PR also has a few useful side effects. Notably, right now a PSBT that has script paths will not fill in pubkey details for the scripts. However the changes in this PR should also fix that.

FractalEncrypt commented at 12:55 pm on December 16, 2022: none

Concept ACK. But for the approach i would prefer something like #26573 instead of making the signing logic still more intricate. But that can also happen afterward.

The approach in this PR also has a few useful side effects. Notably, right now a PSBT that has script paths will not fill in pubkey details for the scripts. However the changes in this PR should also fix that.

This is my first time commenting on a PR, so I apologize if I am breaking any protocol or etiquette here. I compiled and ran this branch and it completely solved this issue described above (PSBT script paths with missing pubkey details);

Further details; I created a multisig address using deriveaddresses and funded it. Then I tried to create a PSBT to spend from the funded address. I was unable to create a PSBT that could be properly processed in 24.0.1. After creating the PSBT and using walletprocesspsbt in my wallet with private keys disabled, it created PSBTs missing the ’taproot_bip32_derivs’ on all the multisig inputs, so my signing wallets couldn’t sign the transaction. This is kinda crazy since I was able to create a multisig address and fund it - but now I can’t spend from it.

The code in this PR solved my issue completely. I compiled this branch and was able to easily create the PSBT with the proper input data, sign it and broadcast. Here is the signet Txid-> 72632a6c09ece682e2fe07796497ca5235280d908d027ee6900a6273e33dd2ae

I’m not knowledgeable or skilled enough to know more about this code, but as a user, I know it solved my problem. (And as a user there’s no bigger problem then when you can’t spend from an address that you control the keys to)

in src/script/sign.cpp:284 in 5345b80005

284+                smallest_result_stack_size = stack_size;
285+            }
286+            if (use_largest && (largest_result_stack.empty() ||
287+                stack_size > largest_result_stack_size)) {
288+                largest_result_stack = result_stack;
289+                largest_result_stack_size = stack_size;

murchandamus commented at 6:46 pm on April 7, 2023:

These make sense to me, but if we correctly estimated the maximum and minimum, how would they ever get used?

achow101 commented at 1:50 pm on April 10, 2023:

I don’t quite follow your question.

The estimated stack size is used to choose which result to return as multiple results could be valid. In normal signing, we use the smallest valid stack. In estimating, we use the largest.

murchandamus commented at 6:49 pm on April 7, 2023: contributor

Concept ACK

How would this behave in the context of changeless transactions? Would we be overestimating the target and dropping an excess to the fees? Does that get recognized when we compare coin selection solutions?

achow101 commented at 1:48 pm on April 10, 2023: member

How would this behave in the context of changeless transactions? Would we be overestimating the target and dropping an excess to the fees?

All overages due to size estimation differences are dropped to fees. The output values are set based upon the estimated size and they cannot be changed after signing. Once signing is completed and the final transaction created, if it ends up being smaller than estimated, whatever could have been saved will not be saved.

Does that get recognized when we compare coin selection solutions?

No. Prior to actual signing, all sizes use the size estimator, which this PR changes to use the worst case scenario.

achow101 commented at 6:58 pm on September 7, 2023: member

Superseded by #26573

achow101 closed this on Sep 7, 2023

wallet: Avoid underpaying transaction fees when signing taproot spends #23502

Reviews

Conflicts