Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Fix coin selection. #2724

Merged
merged 3 commits into from
Nov 29, 2023
Merged

Fix coin selection. #2724

merged 3 commits into from
Nov 29, 2023

Conversation

gmart7t2
Copy link
Contributor

Fixes #2723.

@gmart7t2 gmart7t2 mentioned this pull request Nov 22, 2023
Closed
@casey
Copy link
Collaborator

casey commented Nov 23, 2023

Thanks for the PR! I added a couple of tests. Do they look right to you?

@casey
Copy link
Collaborator

casey commented Nov 23, 2023

I pushed some tests, but it looks like you force-pushed the branch. This needs tests before it can be merged, so that we can be sure that it fixes the issue, and so that we can be sure we don't break it in the future. Here are the tests I added:

  #[test]
  fn prefer_further_away_utxos_if_they_are_under_target() {
    let utxos = vec![
      (outpoint(1), Amount::from_sat(500)),
      (outpoint(2), Amount::from_sat(300)),
    ];

    let mut tx_builder = TransactionBuilder::new(
      satpoint(0, 0),
      BTreeMap::new(),
      utxos.into_iter().collect(),
      BTreeSet::new(),
      recipient(),
      [change(0), change(1)],
      FeeRate::try_from(1.0).unwrap(),
      Target::Value(Amount::from_sat(10_000)),
    );

    assert_eq!(
      tx_builder
        .select_cardinal_utxo(Amount::from_sat(400), true)
        .unwrap()
        .0,
      outpoint(2),
    );
  }

  #[test]
  fn prefer_further_away_utxos_if_they_are_over_target() {
    let utxos = vec![
      (outpoint(1), Amount::from_sat(300)),
      (outpoint(2), Amount::from_sat(500)),
    ];

    let mut tx_builder = TransactionBuilder::new(
      satpoint(0, 0),
      BTreeMap::new(),
      utxos.into_iter().collect(),
      BTreeSet::new(),
      recipient(),
      [change(0), change(1)],
      FeeRate::try_from(1.0).unwrap(),
      Target::Value(Amount::from_sat(10_000)),
    );

    assert_eq!(
      tx_builder
        .select_cardinal_utxo(Amount::from_sat(400), false)
        .unwrap()
        .0,
      outpoint(2),
    );
  }

Please confirm that the test the issue that's being fixed here, and if they do, add them to the PR.

@raphjaph
Copy link
Collaborator

@gmart7t2

@gmart7t2
Copy link
Contributor Author

I will check the test and add it to the PR.

Basically the issue is that if you are looking for an output bigger than or equal to 10, and you see outputs of size 9 and 20, in that order, the code will take the 9 output as the best, and refuse to switch to the 20 because even though it is the first one that is big enough, it isn't closer to the target than the current best. So the coin selection will select the 9, which isn't big enough.

@gmart7t2
Copy link
Contributor Author

I've added the tests. I added the word "newly" to the test names to capture the fact that we only drop the "closer" requirement when setting a utxo that meets the target for the first time.

I changed the sizes such that the not-closer output is further than the current best, not an equal distance away.

I also rebased to the current master branch.

I confirmed that both tests fail without the PR:

---- subcommand::wallet::transaction_builder::tests::prefer_further_away_utxos_if_they_are_newly_over_target stdout ----
==> looking for bigger cardinal worth 0.000005 BTC
==> found cardinal worth 0.0000049 BTC
thread 'subcommand::wallet::transaction_builder::tests::prefer_further_away_utxos_if_they_are_newly_over_target' panicked at src/subcommand/wallet/transaction_builder.rs:2028:5:
assertion `left == right` failed
  left: OutPoint { txid: 0x1111111111111111111111111111111111111111111111111111111111111111, vout: 1 }
 right: OutPoint { txid: 0x2222222222222222222222222222222222222222222222222222222222222222, vout: 2 }

---- subcommand::wallet::transaction_builder::tests::prefer_further_away_utxos_if_they_are_newly_under_target stdout ----
==> looking for smaller cardinal worth 0.000005 BTC
==> found cardinal worth 0.0000051 BTC
thread 'subcommand::wallet::transaction_builder::tests::prefer_further_away_utxos_if_they_are_newly_under_target' panicked at src/subcommand/wallet/transaction_builder.rs:2001:5:
assertion `left == right` failed
  left: OutPoint { txid: 0x1111111111111111111111111111111111111111111111111111111111111111, vout: 1 }
 right: OutPoint { txid: 0x2222222222222222222222222222222222222222222222222222222222222222, vout: 2 }

@casey
Copy link
Collaborator

casey commented Nov 29, 2023

Nice, thank you!

@casey casey merged commit 55916b8 into ordinals:master Nov 29, 2023
6 checks passed
thedoublejay pushed a commit to sadoprotocol/ord that referenced this pull request Dec 1, 2023
@joundy @raphjaph
@duttydeedz @casey @terror @elocremarc @eagr @veryordinally @cberner @rot13maxi @vuittont60 @gmart7t2 @xiaolou86
Joundy/upgrade 0.12.2 (#3)
e3be41f 
* Fix lost sats bug (ordinals#2666)

* Add Hindi version of handbook (ordinals#2648)

* Remove Index::index_block_inscription_numbers (ordinals#2667)

* Hide protocol inscriptions (ordinals#2674)

* Don't color links in headers (ordinals#2678)

* Add inscription charms (ordinals#2681)

* Group rune server tests (ordinals#2685)

* Add inscription compression (ordinals#1713)

* Fix media table formatting (ordinals#2686)

* Update schema version for charms (ordinals#2687)

* Fix unbound outpoint server error (ordinals#2479)

* Add binary media type (ordinals#2671)

* Clean up install.sh (ordinals#2669)

* Add /collections Page (ordinals#2561)

* Preview font inscriptions (ordinals#2692)

* Only load used language highlight module in code preview (ordinals#2696)

* Only try to create the database if it wasn't found (ordinals#2703)

* Move postage into batch file (ordinals#2705)

* Add destination field to batch (ordinals#2701)

* Use sequence numbers database keys (ordinals#2664)

* Update redb to 1.4.0 (ordinals#2714)

* Refactor inscriptions paginations (ordinals#2715)

* Display table stats in `ord index info` (ordinals#2711)

* Use redb's recovery callback API (ordinals#2584)

* Allow setting CSP origin (ordinals#2708)

* Remove default file path from `ord index export --tsv` (ordinals#2717)

* Use icons in nav bar (ordinals#2722)

* Add Debian packaging instructions (ordinals#2725)

* Add Homebrew install instructions to readme (ordinals#2726)

* Add sat recursive endpoints with index and pagination (ordinals#2680)

* Only accept sat number in recursive endpoint (ordinals#2732)

* Fix typo in docs/src/inscriptions/metadata.md (ordinals#2731)

* Add docs for metadata recursive endpoint (ordinals#2734)

* Remove `RUNE` from <h1> on /rune (ordinals#2728)

* Add /r/children recursive endpoint (ordinals#2431)

* Add docs and examples for sat recursive endpoint (ordinals#2735)

* Ignore flaky test (ordinals#2742)

* Update docs to include all fields, including content-encoding (ordinals#2740)

* Add docs for child recursive endpoint (ordinals#2743)

* Hide JSON and .btc (ordinals#2744)

* Release 0.12.0 (ordinals#2746)

* Hide all text (ordinals#2753)

* Add batch to preview command (ordinals#2752)

* Add stuttering curse (ordinals#2745)

* Batch inscribe on same sat (ordinals#2749)

* Allow setting the sat to inscribe (ordinals#2765)

* Select further away coins which meet target (ordinals#2724)

* Fix typos (ordinals#2768)

* Add ability to specify sat to batch inscribe (ordinals#2770)

* Add commands to etch and list runes (ordinals#2544)

* Set CSP origin in deploy script (ordinals#2764)

Co-authored-by: raph <raphjaph@protonmail.com>

* Add `public` to /content Cache-Control headers (ordinals#2773)

* Release 0.12.1 (ordinals#2776)

* Bless cursed inscriptions after Jubilee height (ordinals#2656)

* Hide /content/<INSCRIPTION_ID> HTML inscriptions (ordinals#2778)

* Release 0.12.2 (ordinals#2780)

* fix(test): error test from version 0.12.2

---------

Co-authored-by: raph <raphjaph@protonmail.com>
Co-authored-by: duttydeedz <142775511+duttydeedz@users.noreply.github.com>
Co-authored-by: Casey Rodarmor <casey@rodarmor.com>
Co-authored-by: liam <31192478+terror@users.noreply.github.com>
Co-authored-by: Eloc <42568538+elocremarc@users.noreply.github.com>
Co-authored-by: Julian Eager <eagr@tutanota.com>
Co-authored-by: ordinally <11798624+veryordinally@users.noreply.github.com>
Co-authored-by: Christopher Berner <me@cberner.com>
Co-authored-by: Rijndael <115941166+rot13maxi@users.noreply.github.com>
Co-authored-by: vuittont60 <81072379+vuittont60@users.noreply.github.com>
Co-authored-by: gmart7t2 <49558347+gmart7t2@users.noreply.github.com>
Co-authored-by: xiaolou86 <20718693+xiaolou86@users.noreply.github.com>
popcnt1 pushed a commit to popcnt1/ord that referenced this pull request Jan 11, 2025
@gmart7t2
Select further away coins which meet target (ordinals#2724)
931b2db
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@raphjaph raphjaph raphjaph approved these changes

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.

Coin selection sometimes fails
3 participants
@gmart7t2 @casey @raphjaph