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

achow101 · 2021-11-13T01:57:53Z

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.

DrahtBot · 2021-11-14T03:19:19Z

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.

sipa · 2021-11-23T20:51:32Z

src/script/sign.cpp

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


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

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

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.

src/script/sign.cpp

flack · 2022-01-29T16:49:00Z

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.

aureleoules

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

aureleoules · 2022-10-07T12:13:40Z

src/script/sign.cpp

+                smallest_result_stack = result_stack;
+                smallest_result_stack_size = stack_size;
+            }
+            if (use_largest && (largest_result_stack.size() == 0 ||


nit 7f927b7
same above and below

Suggested change

if (use_largest && (largest_result_stack.size() == 0 ||

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

aureleoules · 2022-10-07T12:14:08Z

src/script/sign.cpp

    for (const auto& [key, control_blocks] : sigdata.tr_spenddata.scripts) {
        const auto& [script, leaf_ver] = key;
        std::vector<std::vector<unsigned char>> result_stack;
        if (SignTaprootScript(provider, creator, sigdata, leaf_ver, script, result_stack)) {
            result_stack.emplace_back(std::begin(script), std::end(script)); // Push the script
            result_stack.push_back(*control_blocks.begin()); // Push the smallest control block
+            uint64_t stack_size = GetSerializeSize(result_stack, PROTOCOL_VERSION);
            if (smallest_result_stack.size() == 0 ||


if you retouch

Suggested change

if (smallest_result_stack.size() == 0 ||

if (smallest_result_stack.empty() ||

src/script/sign.cpp

instagibbs · 2022-10-11T18:14:19Z

src/script/sign.h

@@ -32,6 +32,9 @@ class BaseSignatureCreator {
    /** Create a singular (non-script) signature. */
    virtual bool CreateSig(const SigningProvider& provider, std::vector<unsigned char>& vchSig, const CKeyID& keyid, const CScript& scriptCode, SigVersion sigversion) const =0;
    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;
+
+    /** Choose the largest stack size for worst case size estimation when using this signer */
+    virtual bool UseLargest() const =0;


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

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

test/functional/test_framework/util.py

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.

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

aureleoules

reACK 5345b80

darosior

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: rust-bitcoin/rust-miniscript#481.

achow101 · 2022-12-15T20:42:48Z

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 · 2022-12-16T12:55:24Z

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)

murchandamus

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?

murchandamus · 2023-04-07T18:46:00Z

src/script/sign.cpp

+            if (smallest_result_stack.empty() ||
+                stack_size < smallest_result_stack_size) {
+                smallest_result_stack = result_stack;
+                smallest_result_stack_size = stack_size;
+            }
+            if (use_largest && (largest_result_stack.empty() ||
+                stack_size > largest_result_stack_size)) {
+                largest_result_stack = result_stack;
+                largest_result_stack_size = stack_size;


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

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.

achow101 · 2023-04-10T13:48:55Z

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 · 2023-09-07T18:58:54Z

Superseded by #26573

fanquake added the Wallet label Nov 13, 2021

achow101 force-pushed the tr-low-fee-est branch from c61221d to bec622b Compare November 15, 2021 20:19

achow101 marked this pull request as ready for review November 15, 2021 20:22

achow101 force-pushed the tr-low-fee-est branch from bec622b to f0a9151 Compare November 15, 2021 20:23

DrahtBot mentioned this pull request Nov 16, 2021

Simplify BaseSignatureChecker virtual functions and GenericTransactionSignatureChecker constructors #22793

Closed

DrahtBot mentioned this pull request Nov 23, 2021

Add external signer taproot support #23578

Merged

sipa reviewed Nov 23, 2021

View reviewed changes

achow101 force-pushed the tr-low-fee-est branch from f0a9151 to 6c2f69d Compare December 6, 2021 19:51

bitcoin deleted a comment from 2310Mas Dec 7, 2021

laanwj reviewed Dec 17, 2021

View reviewed changes

src/script/sign.cpp Outdated Show resolved Hide resolved

achow101 force-pushed the tr-low-fee-est branch from 6c2f69d to ca85b71 Compare January 10, 2022 20:54

DrahtBot mentioned this pull request Jan 12, 2022

Add (sorted)multi_a descriptor for k-of-n multisig inside tr #24043

Merged

This was referenced Jan 24, 2022

Deprecate SubtractFeeFromOutputs #24142

Closed

Signing support for Miniscript Descriptors #24149

Merged

DrahtBot added the Needs rebase label Mar 4, 2022

achow101 force-pushed the tr-low-fee-est branch from ca85b71 to 7bc52ab Compare March 4, 2022 16:48

DrahtBot removed the Needs rebase label Mar 4, 2022

DrahtBot added the Needs rebase label Jun 28, 2022

achow101 force-pushed the tr-low-fee-est branch from 7bc52ab to 7f927b7 Compare June 28, 2022 19:40

DrahtBot removed the Needs rebase label Jun 28, 2022

DrahtBot mentioned this pull request Jul 29, 2022

tests: Use test utils each time that it is possible #25732

Closed

DrahtBot mentioned this pull request Sep 17, 2022

script: create V1SigVersion for functions which should only accept taproot/tapscript #26101

Closed

aureleoules approved these changes Oct 7, 2022

View reviewed changes

fanquake requested a review from instagibbs October 10, 2022 07:36

instagibbs reviewed Oct 11, 2022

View reviewed changes

achow101 force-pushed the tr-low-fee-est branch from 7f927b7 to 60b61f8 Compare October 17, 2022 15:02

DrahtBot mentioned this pull request Oct 20, 2022

test: Use consistent assert functions #26356

Closed

DrahtBot mentioned this pull request Oct 31, 2022

Fix signing of multi_a and rawtr scripts with wallets that only have corresponding keys #26418

Merged

DrahtBot added the Needs rebase label Nov 4, 2022

achow101 added 3 commits November 4, 2022 15:38

sign: Include sighash byte for Schnorr sigs with DUMMY_MAX_SIG_CREATOR

0b33bbe

Add UseLargest function to BaseSignatureCreator

58a988d

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.

achow101 force-pushed the tr-low-fee-est branch from 60b61f8 to 5345b80 Compare November 4, 2022 20:32

DrahtBot removed the Needs rebase label Nov 4, 2022

aureleoules approved these changes Nov 17, 2022

View reviewed changes

darosior mentioned this pull request Nov 25, 2022

Wallet: don't underestimate the fees when spending a Taproot output #26573

Closed

darosior reviewed Nov 25, 2022

View reviewed changes

DrahtBot mentioned this pull request Jan 26, 2023

build: no-longer disable WARN_CXXFLAGS when CXXFLAGS is set #25972

Merged

fanquake mentioned this pull request Mar 8, 2023

combinepsbt RPC does not work with P2TR inputs #27219

Open

murchandamus reviewed Apr 7, 2023

View reviewed changes

DrahtBot mentioned this pull request Aug 4, 2023

test: verify spend from 999-of-999 taproot multisig wallet #28212

Closed

achow101 closed this Sep 7, 2023

bitcoin locked and limited conversation to collaborators Sep 6, 2024

	if (use_largest && (largest_result_stack.size() == 0 \|\|
	if (use_largest && (largest_result_stack.empty() \|\|

	if (smallest_result_stack.size() == 0 \|\|
	if (smallest_result_stack.empty() \|\|

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

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

Uh oh!

Conversation

achow101 commented Nov 13, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Nov 14, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Reviews

Conflicts

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

flack commented Jan 29, 2022

Uh oh!

aureleoules left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

aureleoules left a comment

Choose a reason for hiding this comment

Uh oh!

darosior left a comment

Choose a reason for hiding this comment

Uh oh!

achow101 commented Dec 15, 2022

Uh oh!

FractalEncrypt commented Dec 16, 2022

Uh oh!

murchandamus left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

achow101 commented Apr 10, 2023

Uh oh!

achow101 commented Sep 7, 2023

Uh oh!

Uh oh!

achow101 commented Nov 13, 2021 •

edited

Loading

DrahtBot commented Nov 14, 2021 •

edited

Loading