| Age | Commit message (Collapse) | Author |
|---|
|
-BEGIN VERIFY SCRIPT-
sed -i 's/\<LogPrint\>/LogDebug/g' $( git grep -l '\<LogPrint\>' -- ./contrib/ ./src/ ./test/ ':(exclude)src/logging.h' )
-END VERIFY SCRIPT-
|
|
funding options (take 2)
734076c6de1781f957c8bc3bf7ed6951920cfcf6 [wallet, rpc]: add `max_tx_weight` to tx funding options (ismaelsadeeq)
b6fc5043c16c2467a2a6768a6ca9b18035fc400f [wallet]: update the data type of `change_output_size`, `change_spend_size` and `tx_noinputs_size` to `int` (ismaelsadeeq)
baab0d2d43049a71dc90176bc4d72062f7b2ce19 [doc]: update reason for deducting change output weight (ismaelsadeeq)
7f61d31a5cec8fc61328bee43f90d3f1dcb0a035 [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 734076c6de1781f957c8bc3bf7ed6951920cfcf6
furszy:
utACK 734076c6de1781f957c8bc3bf7ed6951920cfcf6
rkrux:
reACK [734076c](https://github.com/bitcoin/bitcoin/pull/29523/commits/734076c6de1781f957c8bc3bf7ed6951920cfcf6)
Tree-SHA512: 013501aa443d239ee2ac01bccfc5296490c27b4edebe5cfca6b96c842375e895e5cfeb5424e82e359be581460f8be92095855763a62779a18ccd5bdfdd7ddce7
|
|
Benchmarks show it is no longer faster with modern standard C++ libraries,
and the debug-mode failure due to self-move has been fixed as well.
|
|
This allows a transaction's weight to be bound under a certain
weight if possible and desired. This can be beneficial for future
RBF attempts, or whenever a more restricted spend topology is
desired.
Co-authored-by: Greg Sanders <gsanders87@gmail.com>
|
|
- This commit renames the coin selection algorithms input parameter `max_weight`
to `max_selection_weight` for clarity.
The parameter represent the maximum weight of the UTXOs the coin selection algorithm
should select, not the transaction maximum weight.
- The commit updates the parameter docstring to provide correct description.
- Also updates coin selection unit and fuzzing test variables to match the new name.
|
|
Both `GetSelectionWaste()` and `ComputeAndSetWaste()` now are part of
`SelectionResult`. Instead of `ComputeAndSetWaste()` being a wrapper for
`GetSelectionWaste()`, we combine them to a new function
`RecalculateWaste()`.
As I was combining the logic of the two functions, I noticed that
`GetSelectionWaste()` was making the odd assumption that the
`change_cost` being set to zero means that no change is created.
However, if we build transactions at a feerate of zero with the
`discard_feerate` also set to zero, we'd organically have a
`change_cost` of zero, even when we create change on a transaction.
This commit cleans up this duplicate meaning of `change_cost` and relies
on `GetChange()` to figure out whether there is change on basis of the
`min_viable_change` and whatever is left after deducting fees.
Since this broke a bunch of tests that relied on the double-meaning of
`change_cost` a bunch of tests had to be fixed.
|
|
Given a lot of small amount UTXOs it is possible that the lookahead
indicates sufficient funds, but any combination of them would push us
beyond the current best_weight.
We can estimate a lower bound for the minimal necessary weight to reach
target from the maximal amount and minimal weight in the tail of the
UTXO pool: if adding a number of hypothetical UTXOs of this maximum
amount and minimum weight would not be able to beat `best_weight`, we
can SHIFT to the omission branch, and CUT if the last selected UTXO is
not heavier than the minimum weight of the remainder.
|
|
Initialize `best_selection_weight` as `max_weight` allows us to skip the
separate `max_weight` check on every loop.
|
|
In situations where we have UTXO groups of various weight, we can CUT
rather than SHIFT when we exceeded the max_weight or the best
selection’s weight while the last step was equal to the minimum weight
in the lookahead.
|
|
When two successive UTXOs differ in weight but match in effective value,
we can skip the second if the first is not selected, because all input
sets we can generate by swapping out a lighter UTXOs with a heavier UTXO
of matching effective value would be strictly worse.
|
|
|
|
When two successive UTXOs match in effective value and weight, we can
skip the second if the prior is not selected: adding it would create an
equivalent input set to a previously evaluated.
E.g. if we have three UTXOs with effective values {5, 3, 3} of the same
weight each, we want to evaluate
{5, _, _}, {5, 3, _}, {5, 3, 3}, {_, 3, _}, {_, 3, 3},
but skip {5, _, 3}, and {_, _, 3}, because the first 3 is not selected,
and we therefore do not need to evaluate the second 3 at the same
position in the input set.
If we reach the end of the branch, we must SHIFT the previously selected
UTXO group instead.
|
|
Introduces a dedicated data structure to track the total
effective_value available in the remaining UTXOs at each index of the
UTXO pool. In contrast to the approach in BnB, this allows us to
immediately jump to a lower index instead of visiting every UTXO to add
back their eff_value to the lookahead.
|
|
Once we exceed the weight of the current best selection, we can always
shift as adding more inputs can never yield a better solution.
|
|
CoinGrinder may not be able to exhaustively search all potentially
interesting combinations for large UTXO pools, so we keep track of
whether the search was terminated by the iteration limit.
|
|
CoinGrinder is a DFS-based coin selection algorithm that
deterministically finds the input set with the lowest weight creating a
change output.
|
|
Since we are searching for the minimal waste, we sort UTXOs with equal
effective value by ascending waste to be able to cut barren branches
earlier.
|
|
|
|
At the end of coin selection reduce the fees by the difference between
the individual bump fee estimates and the collective bump fee estimate.
|
|
When a transaction uses an unconfirmed input, preceding this commit it
would not consider the feerate of the parent transaction. Given a parent
transaction with a lower ancestor feerate, this resulted in the new
transaction's ancestor feerate undershooting the target feerate.
This commit changes how we calculate the effective value of unconfirmed UTXOs.
The effective value of unconfirmed UTXOs is decreased by the fee
necessary to bump its ancestry to the target feerate. This also impacts
the calculation of the waste metric: since the estimate for the current
fee is increased by the bump fees, unconfirmed UTXOs current fees appear less
favorable compared to their unchanged long term fees.
This has one caveat: if multiple UTXOs have overlapping ancestries, each
of their individual estimates will account for bumping all ancestors.
|
|
GetSelectionWaste will need to access more context within a selection
result, and so should be a private member function rather than a static
function. It's only use outside of SelectionResult was for tests which
have now been updated to just make a SelectionResult.
Co-authored-by: Murch <murch@murch.one>
|
|
I discovered via fuzzing of another coin selection approach that at
extremely high feerates SRD may find input sets that lead to
transactions without change outputs. This is an unintended outcome since
SRD is meant to always produce a transaction with a change output—we use
other algorithms to specifically search for changeless solutions.
The issue occures when the flat allowance of 50,000 ṩ for change is
insufficient to pay for the creation of a change output with a non-dust
amount, at and above 1,613 ṩ/vB. Increasing the change budget by
change_fees makes SRD behave as expected at any feerates.
|
|
Since the kernel library no longer depends on the system file, move it
to the common library instead in accordance to the diagram in
doc/design/libraries.md.
|
|
be55f545d53d44fdcf2d8ae802e9eae551d120c6 move-only: Extract common/args and common/config.cpp from util/system (TheCharlatan)
Pull request description:
This pull request is part of the `libbitcoinkernel` project https://github.com/bitcoin/bitcoin/issues/24303 https://github.com/bitcoin/bitcoin/projects/18 and more specifically its "Step 2: Decouple most non-consensus code from libbitcoinkernel". It is part of a series of patches splitting up the `util/system` files. Its preceding pull request is https://github.com/bitcoin/bitcoin/pull/27254.
The pull request contains an extraction of ArgsManager related functions from util/system into their own common/ file.
The background of this commit is an ongoing effort to decouple the libbitcoinkernel library from the ArgsManager. The ArgsManager belongs into the common library, since the kernel library should not depend on it. See [doc/design/libraries.md](https://github.com/bitcoin/bitcoin/blob/master/doc/design/libraries.md) for more information on this rationale.
ACKs for top commit:
MarcoFalke:
re-ACK be55f545d53d44fdcf2d8ae802e9eae551d120c6 🚲
ryanofsky:
Code review ACK be55f545d53d44fdcf2d8ae802e9eae551d120c6. Just small cleanups since the last review.
hebasto:
ACK be55f545d53d44fdcf2d8ae802e9eae551d120c6, I have reviewed the code and it looks OK, I agree it can be merged.
Tree-SHA512: 90eb03334af0155b823030b4f2ecf286d35058d700ee2ddbbaa445be19e31eb0fe982656f35bd14ecee3ad2c3d0db3746855cb8f3777eff7253713e42873e111
|
|
that exceed the max allowed weight
25ab14712b9d80276016f9fc9bff7fb9c1d09635 refactor: coinselector_tests, unify wallet creation code (furszy)
ba9431c505e1590db6103b9632134985cd4704dc test: coverage for bnb max weight (furszy)
5a2bc45ee0b123e461c5191322ed0b43524c3d82 wallet: clean post coin selection max weight filter (furszy)
2d112584e384de10021c64e4700455d71326824e coin selection: BnB, don't return selection if exceeds max allowed tx weight (furszy)
d3a1c098e4b5df2ebbae20c6e390c3d783950e93 test: coin selection, add coverage for SRD (furszy)
9d9689e5a657956db8a30829c994600ec7d3098b coin selection: heap-ify SRD, don't return selection if exceeds max tx weight (furszy)
6107ec2229c5f5b4e944a6b10d38010c850094ac coin selection: knapsack, select closest UTXO above target if result exceeds max tx size (furszy)
1284223691127e76135a46d251c52416104f0ff1 wallet: refactor coin selection algos to return util::Result (furszy)
Pull request description:
Coming from the following comment https://github.com/bitcoin/bitcoin/pull/25729#discussion_r1029324367.
The reason why we are adding hundreds of UTXO from different sources when the target
amount is covered only by one of them is because only SRD returns a usable result.
Context:
In the test, we create 1515 UTXOs with 0.033 BTC each, and 1 UTXO with 50 BTC. Then
perform Coin Selection to fund 49.5 BTC.
As the selection of the 1515 small UTXOs exceeds the max allowed tx size, the
expectation here is to receive a selection result that only contain the big UTXO.
Which is not happening for the following reason:
Knapsack returns a result that exceeds the max allowed transaction size, when
it should return the closest utxo above the target, so we fallback to SRD who
selects coins randomly up until the target is met. So we end up with a selection
result with lot more coins than what is needed.
ACKs for top commit:
S3RK:
ACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635
achow101:
ACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635
Xekyo:
reACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635
theStack:
Code-review ACK 25ab14712b9d80276016f9fc9bff7fb9c1d09635
Tree-SHA512: 2425de4cc479b4db999b3b2e02eb522a2130a06379cca0418672a51c4076971a1d427191173820db76a0f85a8edfff100114e1c38fb3b5dc51598d07cabe1a60
|
|
This is an extraction of ArgsManager related functions from util/system
into their own common file.
Config file related functions are moved to common/config.cpp.
The background of this commit is an ongoing effort to decouple the
libbitcoinkernel library from the ArgsManager. The ArgsManager belongs
into the common library, since the kernel library should not depend on
it. See doc/design/libraries.md for more information on this rationale.
|
|
|
|
Uses a min-effective-value heap, so we can remove the least valuable input/s
while the selected weight exceeds the maximum allowed weight.
Co-authored-by: Murch <murch@murch.one>
|
|
max tx size
The simplest scenario where this is useful is on the 'check_max_weight' unit test
already:
We create 1515 UTXOs with 0.033 BTC each, and 1 UTXO with 50 BTC. Then perform
Coin Selection.
As the selection of the 1515 small UTXOs exceeds the max allowed tx size, the
expectation here is to receive a selection result that only contain the big
UTXO (which is not happening for the reasons stated below).
As knapsack returns a result that exceeds the max allowed transaction size, we
fallback to SRD, which selects coins randomly up until the target is met. So
we end up with a selection result with lot more coins than what is needed.
|
|
CWallet::DummySignTx, OutputGroupTypeMap::find
|
|
so the selection processes can retrieve different errors and not
uninformative std::nullopt
|
|
The 'GroupOutputs()' function performs the same
calculations for only-positive and mixed groups,
the only difference is that when we look for
only-positive groups, we discard negative utxos.
So, instead of wasting resources calling GroupOutputs()
for positive-only first, then call it again to include
the negative ones in the result, we can execute
GroupOutputs() only once, including in the response
both group types (positive-only and mixed).
|
|
Initial steps towards sharing COutput instances across all possible
OutputGroups (instead of copying them time after time).
|
|
And not hide it inside the `OutputGroup::Insert` method.
This method does not return anything if insertion fails.
We can know before calling `Insert` whether the coin
will be accepted or not.
|
|
messages
76dc547ee7b05864e7b1b6c55fc0301d47aa3a15 gui: create tx, launch error dialog if backend throws runtime_error (furszy)
f4d79477ff0946b0bd340ade9251fa38e3b95dd7 wallet: coin selection, add duplicated inputs checks (furszy)
0aa065b14e67592d5be8f46ebbe5d59a083ff0a5 wallet: return accurate error messages from Coin Selection (furszy)
7e8340ab1a970a14e180b1fcf420b46a5657b062 wallet: make SelectCoins flow return util::Result (furszy)
e5e147fe97f706e82bc51358f8bdc355f355be57 wallet: refactor eight consecutive 'AttemptSelection' calls into a loop (furszy)
Pull request description:
Work decoupled from #25806, which cleanup and improves the Coin Selection flow further.
Adding the capability to propagate specific error messages from the Coin Selection process to the user.
Instead of always returning the general "Insufficient funds" message which is not always accurate to what happened internally.
Letting us instruct the user how to proceed under certain circumstances.
The following error messages were added:
1) If the selection result exceeds the maximum transaction weight,
we now will return:
-> "The inputs size exceeds the maximum weight. Please try sending
a smaller amount or manually consolidating your wallet's UTXOs".
2) If the user pre-selected inputs and disallowed the automatic coin
selection process (no other inputs are allowed), we now will
return:
-> "The preselected coins total amount does not cover the transaction
target. Please allow other inputs to be automatically selected or include
more coins manually".
3) The double-counted preset inputs during Coin Selection error will now
throw an "internal bug detected" message instead of crashing the node.
The essence of this work comes from several comments:
1. https://github.com/bitcoin/bitcoin/pull/26560#discussion_r1037395665
2. https://github.com/bitcoin/bitcoin/pull/25729#discussion_r940619491
3. https://github.com/bitcoin/bitcoin/pull/25269#pullrequestreview-1135240825
4. https://github.com/bitcoin/bitcoin/issues/23144 (which is connected to #24845)
ACKs for top commit:
ishaanam:
crACK 76dc547ee7b05864e7b1b6c55fc0301d47aa3a15
achow101:
ACK 76dc547ee7b05864e7b1b6c55fc0301d47aa3a15
aureleoules:
ACK 76dc547ee7b05864e7b1b6c55fc0301d47aa3a15
theStack:
ACK 76dc547ee7b05864e7b1b6c55fc0301d47aa3a15 :city_sunrise:
Tree-SHA512: 9de30792d7a5849cae77747aa978e70390b66ee9d082779a56088a024f82e725b0af050e6603aece0ac8229f6d73bc471ba97b4ab69dc7eddf419f5f56ae89a5
|
|
81d4a2b14ff65fe07085ef2a967a466015370ce3 refactor: Move feerate comparison invariant outside of the loop (yancy)
365aca40453995163bbd17231251512f9f9a103b refactor: Simplify feerate comparison statement (yancy)
Pull request description:
This is a small nit, however I think it's more understandable to write:
`utxo_pool.at(0).fee > utxo_pool.at(0).long_term_fee`
vs
`(utxo_pool.at(0).fee - utxo_pool.at(0).long_term_fee) > 0`
ACKs for top commit:
Xekyo:
ACK 81d4a2b14ff65fe07085ef2a967a466015370ce3
achow101:
ACK 81d4a2b14ff65fe07085ef2a967a466015370ce3
aureleoules:
ACK 81d4a2b14ff65fe07085ef2a967a466015370ce3
Tree-SHA512: 3e89377989c36716b53114fe40178261671dde5688075fab1c21ec173ac310f8c84ed6af90354d7c329176cb7262dfcaa7191fd19847d3b7147a9a10c3e31176
|
|
-BEGIN VERIFY SCRIPT-
./contrib/devtools/copyright_header.py update ./
-END VERIFY SCRIPT-
Commits of previous years:
- 2021: f47dda2c58b5d8d623e0e7ff4e74bc352dfa83d7
- 2020: fa0074e2d82928016a43ca408717154a1c70a4db
- 2019: aaaaad6ac95b402fe18d019d67897ced6b316ee0
|
|
As no process should be able to trigger this error
using the regular transaction creation process, throw
a runtime_error if happens to tell users/devs to
report the bug if happens.
|
|
Co-authored-by: Andrew Chow <github@achow101.com>
|
|
|
|
First step towards decoupling the pre-selected-inputs fetching functionality
from `SelectCoins`. Which, will let us not waste resources calculating the
available coins if one of the pre-set inputs has an error.
(right now, if one of the pre-set inputs is invalid, we first walk through
the entire wallet txes map just to end up failing right after it finish)
|
|
|
|
|
|
|
|
|
|
|
|
SelectionResult::m_target should be equal to actual selection target.
Selection target is the sum of all recipient amounts plus non input fees.
So we need to remove change_fee from the m_target. It's safe because change
target is always greater than the change fee, so we can always cover fees
if change output is created.
|
|
|
|
This reverts commit 9b5950db8683f9b4be03f79ee0aae8a780b01a4b.
Waste can be negative. At feerates lower than long_term_feerate this
means that a waste of 0 may be a suboptimal solution and this causes the
search to exit prematurely.
Only when the feerate is equal to the long_term_feerate would achieving
a waste of 0 indicate that we have achieved an optimal solution,
because it would mean that the excess is 0. It seems unlikely
that this would ever occur outside of test cases, and even then we
should prefer solutions with more inputs over solutions with fewer
according to previous decisions—but solutions with more inputs are found
later in the branch exploration.
The "optimization" described in #18257 and implemented in #18262 is
therefore a premature exit on a suboptimal solution and should be reverted.
|
|
Messages with level `WARN` or higher should be logged even when
the category is not provided with `-debug=`, to make sure important
warnings are not lost.
|
