Skip to content

Conversation

instagibbs
Copy link
Member

This allows a transaction's weight to be bound under
a certain weight if possible an desired. This
can be beneficial for future RBF attempts, or
whenever a more restricted spend topology is
desired.

See https://delvingbitcoin.org/t/lightning-transactions-with-v3-and-ephemeral-anchors/418/11?u=instagibbs for more discussion.

Seeking concept ACK and maybe some help on approach for testing.

@DrahtBot
Copy link
Contributor

DrahtBot commented Jan 17, 2024

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
Stale ACK 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:

  • #28985 (Avoid changeless input sets when SFFO is active by murchandamus)
  • #28560 (wallet, rpc: FundTransaction refactor by josibake)
  • #28201 (Silent Payments: sending by josibake)

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
Copy link
Contributor

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the
documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being
incompatible with the current code in the target branch). If so, make sure to rebase on the latest
commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

Debug: https://github.com/bitcoin/bitcoin/runs/20589487266

@@ -335,12 +337,18 @@ util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, c
for (const auto& group : applicable_groups) {
result.AddInput(group);
}
// We may still fail if max is low
if (result.GetWeight() > max_weight) return ErrorMaxWeightExceeded();
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Would this be giving up too early? We could still find a different solution further down the function, no?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

yeah I was mostly hot-patching here, making sure it never returns too big(because it did very often)

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

should be mitigated?

Copy link
Contributor

@murchandamus murchandamus left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Concept ACK, but instead of bailing immediately, it would be better to extend the conditions that immediately return a result to also require adhering to the max_weight.

Copy link
Contributor

@murchandamus murchandamus left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Continuing…

Got some more suggestions how you can give Knapsack a bit of a fighting chance, although we should get rid of Knapsack instead of improving it.

Also, Knapsack initializes its result with returning the entire UTXO pool, so you might want need to change that in case that’s more than max_weight to either be empty or fail before returning.

@instagibbs instagibbs force-pushed the 2024-01-max-tx-weight branch 2 times, most recently from 35bc649 to 069c165 Compare January 19, 2024 17:43
Copy link
Contributor

@murchandamus murchandamus left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ACK 069c165

Thanks for cleanly distinguishing max_tx_weight and max_input_weight!

@@ -74,7 +74,7 @@ struct {
static const size_t TOTAL_TRIES = 100000;

util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change,
int max_weight)
int max_input_weight)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ah, yeah max_input_weight is a much better name. Thanks!

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@murchandamus, I'm not entirely sure about this naming change. At this point, we are placed at the coin selection algos level, which are situated a level below the transaction creation process. There is no concept of transaction weight here; only selection weight.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

max_selection_weight is also fine I think, both are better than status quo

}

// If we have a bigger coin and (either the stochastic approximation didn't find a good solution,
// or the next bigger coin is closer), return the bigger coin
if (lowest_larger &&
((nBest != nTargetValue && nBest < nTargetValue + change_target) || lowest_larger->GetSelectionAmount() <= nBest)) {
result.AddInput(*lowest_larger);

// We may still fail if max is low
if (result.GetWeight() > max_input_weight) return ErrorMaxWeightExceeded();
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don’t think we can ever hit this if block since we only set lowest_larger when it’s weight is less than the max_input_weight.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

makes sense, removed

Comment on lines 390 to 391
// We may still fail if max is low
if (result.GetWeight() > max_input_weight) return ErrorMaxWeightExceeded();
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I don’t think this condition can be hit.

AFAICT, there is only be a single scenario in which vfBest can contain an input selection that is in excess of the max_input_weight: ApproximateBestSubset initializes vfBest with all of applicable_groups without checking the weight. If it then never finds a better input selection throughout the exploration, it would be possible that it returns an overweight vfBest. Since lowest_larger is only set when it adheres to the weight limit, we either have replaced vfBest with an adequate lowest_larger at this point, or have already returned ErrorMaxWeightExceeded.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

makes sense, removed

This allows a transaction's weight to be bound under
 a certain weight if possible an desired. This
can be beneficial for future RBF attempts, or
whenever a more restricted spend topology is
desired.
@instagibbs instagibbs force-pushed the 2024-01-max-tx-weight branch from 069c165 to 7bfc80b Compare January 19, 2024 19:57
@instagibbs
Copy link
Member Author

fixed up the fuzz test, which was attempting larger than MAX_STANDARD_TX_WEIGHT coins and not actually rejecting them as they should have previously, causing fuzz failure. Invariants in test should work now.

@@ -112,22 +112,25 @@ FUZZ_TARGET(coinselection)
std::vector<OutputGroup> group_all;
GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all);

// Calculate upperbound of given input weight, allow all to be selected
int total_input_weight{0};
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It would be better to make max_input_weight a fuzzed value.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If you do, please also add an assert that checks whether the fuzzed value is greater than or equal to the result’s weight.

}

if (nTotalLower < nTargetValue) {
if (!lowest_larger) return util::Error();
if (!lowest_larger) return util::Error{Untranslated(strprintf("Only %d coins to cover target value of %d", nTotalLower, nTargetValue))};
Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

hmmm, this change to give a useful error message seems to break tests; I start getting failures in rpc_psbt.py

Can I get some assistance on how this stuff is supposed to bubble up @murchandamus

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is the breakage not an actual issue: https://cirrus-ci.com/task/6124189116006400?logs=ci#L3274

test_framework.authproxy.JSONRPCException: Only 4999872180 coins to cover target value of 5100000840 (-4)

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I can turn the error on and off locally by adding/removing the string from the error.

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The wallet code seems to be the only place where this pattern of util::Error() is used. Everywhere actual error strings are always provided.

Copy link
Member

@furszy furszy Jan 24, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The empty util::Error() is used to retrieve a "no solution found for the provided inputs set". If you specify an error message, then the wallet coin selection procedure treats it as a real error and bubble it up when no other selection algorithm succeeded.

The goal of this distinction is to differentiate between errors that should be bubbled up and coin selection algorithms' partial solutions. Remember that we are running each coin selection algorithm up to 7 times, extending the input set on every round. The "no solution found" return isn't definitive; it varies depending on the algorithm and the filtered coin set. That's why other errors, like the max weight exceeded, are stored and take precedence if no solution is found after running all selection rounds.

I haven't gone deeper over this PR yet but the message you are adding here doesn't seems like an error. It is just describing the "no solution found for the provided input set" transient situation.

Copy link
Member

@furszy furszy Jan 24, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The empty util::Error() is used to retrieve a "no solution found for the provided inputs set". If you specify an error message, then the wallet coin selection procedure treats it as a real error and bubble it up when no other selection algorithm succeeded.

Ok. So then this is just a (confusing) misuse of the Util:: API, where the wallet code is shoehorning non-error handling into an error handler.

Ideally, we should retrieve more info within the "no solution found" return path and not just the string message. I was waiting until we expand the result class functionality to accept a generic error return type. E.g. having util::Result<M, E> would let us do something like util::Result<SelectionResult, SelectionError>, where SelectionError would contain the string msg and a severity level int value. Which would help us differentiate the different outcomes and bubble up the highest severity error (if any). I actually left a comment for this in the code.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I haven't gone deeper over this PR yet but the message you are adding here doesn't seems like an error. It is just describing the "no solution found for the provided input set" transient situation.

Are you saying it's not confusing to give insufficient funds message on failure to stay within the weight limits given? I guess that's fine for now?

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I haven't gone deeper over this PR yet but the message you are adding here doesn't seems like an error. It is just describing the "no solution found for the provided input set" transient situation.

Are you saying it's not confusing to give insufficient funds message on failure to stay within the weight limits given? I guess that's fine for now?

Not really. I was only referring to this line in question. Which, in a first glance, isn't retrieving an exceeded weight limit error. Still, give me a day to review the PR in-detail and will join the efforts here.

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

still waiting on some feedback on this point before moving forward with the PR

Copy link
Member

@furszy furszy Jan 30, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

still waiting on some feedback on this point before moving forward with the PR

@instagibbs, see furszy@b2d3ac3. It makes the process consistent, returning the same "weight exceeded" error message when such scenario occurs.

Still, I would like to revisit this PR further after you tackle #29264 (comment) and most other comments.

@@ -799,6 +808,8 @@ RPCHelpMan fundrawtransaction()
},
},
},
{"max_tx_weight", RPCArg::Type::NUM, RPCArg::Default{MAX_STANDARD_TX_WEIGHT}, "The maximum acceptable transaction weight.\n"
"Transaction selection will fail if this can not be satisfied."},
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think you meant either "Transaction building" or "Coin selection" here:

Suggested change
"Transaction selection will fail if this can not be satisfied."},
"Transaction building will fail if this can not be satisfied."},
Suggested change
"Transaction selection will fail if this can not be satisfied."},
"Coin selection will fail if this can not be satisfied."},

@@ -1239,6 +1250,8 @@ RPCHelpMan send()
{"vout_index", RPCArg::Type::NUM, RPCArg::Optional::OMITTED, "The zero-based output index, before a change output is added."},
},
},
{"max_tx_weight", RPCArg::Type::NUM, RPCArg::Default{MAX_STANDARD_TX_WEIGHT}, "The maximum acceptable transaction weight.\n"
"Transaction selection will fail if this can not be satisfied."},
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

As above

@@ -1337,6 +1353,8 @@ RPCHelpMan sendall()
{"send_max", RPCArg::Type::BOOL, RPCArg::Default{false}, "When true, only use UTXOs that can pay for their own fees to maximize the output amount. When 'false' (default), no UTXO is left behind. send_max is incompatible with providing specific inputs."},
{"minconf", RPCArg::Type::NUM, RPCArg::Default{0}, "Require inputs with at least this many confirmations."},
{"maxconf", RPCArg::Type::NUM, RPCArg::Optional::OMITTED, "Require inputs with at most this many confirmations."},
{"max_tx_weight", RPCArg::Type::NUM, RPCArg::Default{MAX_STANDARD_TX_WEIGHT}, "The maximum acceptable transaction weight.\n"
"Transaction selection will fail if this can not be satisfied."},
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

As above

@@ -1679,6 +1708,8 @@ RPCHelpMan walletcreatefundedpsbt()
{"vout_index", RPCArg::Type::NUM, RPCArg::Optional::OMITTED, "The zero-based output index, before a change output is added."},
},
},
{"max_tx_weight", RPCArg::Type::NUM, RPCArg::Default{MAX_STANDARD_TX_WEIGHT}, "The maximum acceptable transaction weight.\n"
"Transaction selection will fail if this can not be satisfied."},
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

As above

@@ -112,22 +112,25 @@ FUZZ_TARGET(coinselection)
std::vector<OutputGroup> group_all;
GroupCoins(fuzzed_data_provider, utxo_pool, coin_params, /*positive_only=*/false, group_all);

// Calculate upperbound of given input weight, allow all to be selected
int total_input_weight{0};
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

If you do, please also add an assert that checks whether the fuzzed value is greater than or equal to the result’s weight.

max_send_psbt_result = self.nodes[0].sendall(sendall_dest, options={"psbt": True})
max_send_weight = self.nodes[0].decoderawtransaction(max_send_psbt_result["hex"])['weight']
assert_raises_rpc_error(-4, "Requested max tx weight exceeded:", self.nodes[0].sendall, sendall_dest, options={"max_tx_weight": max_send_weight - 1, "psbt": True})
self.nodes[0].sendall(sendall_dest, options={"max_tx_weight": max_send_weight + 4, "psbt": True}) # off by 4 sometimes?
Copy link
Contributor

@murchandamus murchandamus Jan 23, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

My first thought would be that we are perhaps not counting the empty witness stack of a non-witness input? 🤔

Is this a blocker that needs to be addressed first?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

if this is a bit of overcounting, that's probably ok?

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Mh, it’s a bit of a smell if we cannot explain this.
I considered input counter, empty witness stack, that we might estimate for a high-R signature in a PSBT, because we didn’t sign it, and that we sometimes get a lower r value in the signature and therefore one of the two values is a byte shorter. But our default address type would be at least wrapped segwit, so that would only explain a weight difference of 1. I don’t have a good idea at the moment. @achow101: Do you perhaps have an idea why this is happening?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

would still like a good explanation for this

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I verified that this behavior happened, intermittently I get the weight of the transaction off by 4 bytes.
I spent sometime debugging but did not figure why yet.


Going by this suggestion #29264 (comment) the test is now gone in the new PR #29523 , I believe the issue is unrelated.

Should I open an issue for this?

@DrahtBot
Copy link
Contributor

🐙 This pull request conflicts with the target branch and needs rebase.

@@ -320,13 +323,13 @@ util::Result<SelectionResult> KnapsackSolver(std::vector<OutputGroup>& groups, c
Shuffle(groups.begin(), groups.end(), rng);

for (const OutputGroup& group : groups) {
if (group.GetSelectionAmount() == nTargetValue) {
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

suggestion, add

if (group.m_weight <= max_input_weight) continue;

on top of the for loop instead of checking within each condition.

Currently, you add groups that are above weight to applicable_groups

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think you mean

if (group.m_weight > max_input_weight) continue;

This way we jusk skip group whose weight is larger than max_input_weight and avoid checking the weight limit for all the conditional branches below.

result.AddInput(*lowest_larger);
return result;
if (result.GetWeight() <= max_input_weight) return result;
Copy link
Contributor

@S3RK S3RK Jan 25, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

nit: lowest_larger can't be above max_input_weight. You already checked it above. And in other similar cases below you don't check it second time.

I prefer if we filter above weight inputs once at the top of the function.

Comment on lines +1493 to +1502
// Cap tx weight based on estimated size if requested
if (options.exists("max_tx_weight")) {
const auto max_tx_weight = options["max_tx_weight"].getInt<int>();
if (max_tx_weight < 0 || max_tx_weight > MAX_STANDARD_TX_WEIGHT) {
throw JSONRPCError(RPC_WALLET_ERROR, strprintf("Invalid parameter, max tx weight must be between 0 %d", MAX_STANDARD_TX_WEIGHT));
}
if (max_tx_weight < tx_size.weight) {
throw JSONRPCError(RPC_WALLET_ERROR, strprintf("Requested max tx weight exceeded: %d vs %s", options["max_tx_weight"].getInt<int>(), tx_size.weight));
}
}
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This does not seem to be necessary. As sendall() doesn't make use of the internal coin selection procedures, wouldn't make more sense to return the weight in the command result and let the user decide whether to broadcast the tx based on it?

Comment on lines +119 to +120
//! Caps weight of resulting tx
int m_max_tx_weight{MAX_STANDARD_TX_WEIGHT};
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

To not add policy/policy.h dependency, which comes with other dependencies (script/interpreter.h, script/solver.h, etc..), would suggest to make this field optional. Treating std::nullopt as MAX_STANDARD_TX_WEIGHT internally. This is what we already do for other default values.

Comment on lines +181 to +186
int32_t m_max_tx_weight{MAX_STANDARD_TX_WEIGHT};

CoinSelectionParams(FastRandomContext& rng_fast, size_t change_output_size, size_t change_spend_size,
CAmount min_change_target, CFeeRate effective_feerate,
CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial)
CFeeRate long_term_feerate, CFeeRate discard_feerate, size_t tx_noinputs_size, bool avoid_partial,
int32_t max_tx_weight=MAX_STANDARD_TX_WEIGHT)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Same as above, the policy.h dependency generates some noise on me. Would suggest to not default initialize m_max_tx_weight. Callers are already forced to provide the weight in the constructor.

@@ -74,7 +74,7 @@ struct {
static const size_t TOTAL_TRIES = 100000;

util::Result<SelectionResult> SelectCoinsBnB(std::vector<OutputGroup>& utxo_pool, const CAmount& selection_target, const CAmount& cost_of_change,
int max_weight)
int max_input_weight)
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@murchandamus, I'm not entirely sure about this naming change. At this point, we are placed at the coin selection algos level, which are situated a level below the transaction creation process. There is no concept of transaction weight here; only selection weight.

}

if (nTotalLower < nTargetValue) {
if (!lowest_larger) return util::Error();
if (!lowest_larger) return util::Error{Untranslated(strprintf("Only %d coins to cover target value of %d", nTotalLower, nTargetValue))};
Copy link
Member

@furszy furszy Jan 30, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

still waiting on some feedback on this point before moving forward with the PR

@instagibbs, see furszy@b2d3ac3. It makes the process consistent, returning the same "weight exceeded" error message when such scenario occurs.

Still, I would like to revisit this PR further after you tackle #29264 (comment) and most other comments.

@instagibbs instagibbs marked this pull request as draft February 12, 2024 17:27
@instagibbs
Copy link
Member Author

I'm not looking to push this forward for now, if someone wants to take it over be my guest. Draft for now.

@ismaelsadeeq
Copy link
Member

ismaelsadeeq commented Mar 1, 2024

I'm not looking to push this forward for now, if someone wants to take it over be my guest. Draft for now.

I opened #29523, which took over from this, and addressed the review comments here.

@fanquake fanquake closed this Mar 1, 2024
achow101 added a commit that referenced this pull request Jul 17, 2024
…ons (take 2)

734076c [wallet, rpc]: add `max_tx_weight` to tx funding options (ismaelsadeeq)
b6fc504 [wallet]: update the data type of `change_output_size`, `change_spend_size` and `tx_noinputs_size` to `int` (ismaelsadeeq)
baab0d2 [doc]: update reason for deducting change output weight (ismaelsadeeq)
7f61d31 [refactor]: update coin selection algorithms input parameter `max_weight` name (ismaelsadeeq)

Pull request description:

  This PR taken over from #29264

  The PR added an option `max_tx_weight` to transaction funding RPC's that ensures the resulting transaction weight does not exceed the specified `max_tx_weight` limit.

  If `max_tx_weight` is not given `MAX_STANDARD_TX_WEIGHT` is used as the max threshold.

  This PR addressed outstanding review comments in #29264

  For more context and rationale behind this PR see https://delvingbitcoin.org/t/lightning-transactions-with-v3-and-ephemeral-anchors/418/11?u=instagibbs

ACKs for top commit:
  achow101:
    ACK 734076c
  furszy:
    utACK 734076c
  rkrux:
    reACK [734076c](734076c)

Tree-SHA512: 013501aa443d239ee2ac01bccfc5296490c27b4edebe5cfca6b96c842375e895e5cfeb5424e82e359be581460f8be92095855763a62779a18ccd5bdfdd7ddce7
@bitcoin bitcoin locked and limited conversation to collaborators Mar 8, 2025
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

Successfully merging this pull request may close these issues.

8 participants