Add coin-grinder #69
Closed
Add coin-grinder #69
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
27ddcd2 to
635b0c8
Compare
c72d8a0 to
f714814
Compare
yancyribbens
commented
Jan 7, 2025
18608d3 to
da4235f
Compare
da4235f to
9b3a7bc
Compare
3ff7975 to
0d201e3
Compare
e2ff094 to
6aaa3a7
Compare
291fe91 to
70c6aa5
Compare
bda2072 to
a4a5aad
Compare
1a474ca to
d1726c2
Compare
This is a preparatory step. Preferably, the effective_value function from rust-bitcoin would be used, however in an upcoming commit, the library transitions to use weight instead of satisfaction_weight. Therefore, while the rust-bitcoin upstream effective_value uses satisfaction_weight, a local version of effective_value using weight is added.
Simplify by using a trait method which requires only argument instead of three.
Core uses just weight in coin-grinder, and it's complicated to maintain using both satisfaction_weight and weight. Therefore, switch to just weight units for all algorithms. As a consequence, two tests in SRD needed to be revised. Now that Weight is used instead, if no Weight is defined in the test, the default Weight is zero since 160 is no longer added as the base_weight. This means that the default weight for all UTXOs in the tests is now zero where in previously the default was 160 if not otherwise defined.
Simplify code base by using an upstream method instead of creating a local method that does the same thing.
5fc6455 to
041957d
Compare
Provide a DFS-based selection algorithm which optimizes for transaction weight and creates a change output.
If the currently selected input does not contribute to a valid solution, and the next input to be evaluated is of the same construction (same value and weight), then skip (do not evaluate). Therefore, this optimization significantly improves performance when a candidate input set contains many identical inputs. See also: bitcoin/bitcoin@451be19
It can be estimated that if we continue adding inputs that no better solution than the current best solution will be forthcoming. See also: bitcoin/bitcoin@13161ec
A UTXO pool that contains multiple values that when added together produce an overflow. Instead of panic, return None in order to safely handle such cases.
041957d to
b740740
Compare
|
There's a lot of scar tissue on this one, so re-opening since now I consider this a merge candidate. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Add Coin Grinder, A Rust DFS-based selection algorithm which optimizes for transaction
weight and creates a change output.
This is a Rust implementation of the C++ version bitcoin/bitcoin#27877
I plan to follow up and add fuzz tests, property tests and benchmarks before a release. While i've made a best attempt to guard against possible overflows by using checked arithmetic, I suspect more will be uncovered once fuzz tests are added. Every instance of checked arithmetic slows the performance, therefore I've left places unchecked for now that are not obvious.