IntersectMBO / IntersectMBO/cardano-coin-selection

migration algorithm exits without processing all inputs.

Open
#85 0 comments 0 reactions 0 assignees View on GitHub
bug confirmed
Dominant language
Haskell
Stars
19
Forks
10
PR merge metrics
No merged PRs in 30d

Description

# Context

The migration algorithm is an iterative algorithm, which attempts to construct several coin selections in order to deplete a wallet. An initial "ideal batch size" is calculated beforehand, and then, the algorithm proceed to construct selections from batch of inputs of that ideal size (modulo the last batch).

Constructing a selection also means _balancing it_. Here, the algorithm will depletes change outputs until reaching an equilibrium and will take care of filtering out dust coins that are below a certain threshold.

There are cases where a given selection could not produce any value (all change output are below the threshold).

# Expected Behavior

The algorithm should discard such "no-value" selections, and continue processing next batches until it has traversed all batches.

# Current Behavior

The algorithm stops at the first "no-value" selections and returns, with whatever selections has been accumulated this far, possibly leaving many inputs behind.

# Resolution

https://github.com/input-output-hk/cardano-coin-selection/blob/cff368d674fe58bc1a12e6564a26ccea21eb5aac/src/library/Cardano/CoinSelection/Algorithm/Migration.hs#L108-L112

The issue is the handling of the `Nothing` branch :point_up: which should not be `pure []` (terminal case of the recursion) but simply `migrate`, discarding the ongoing selection, but continuing migrating others.

Contributor guide

Open the contributing guide

Research direction

The migration loop is in src/library/Cardano/CoinSelection/Algorithm/Migration.hs; start by reading lines 108-112, especially the Nothing branch, and trace how migrate processes batches. Done means a no-value selection is discarded while later batches continue processing, so all inputs are traversed.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
blockchain
Issue type
Bug
Difficulty
1/5
Estimated time
Under an hour
Activity status
Stale
Clarity
Clearly specified
Newbie friendliness
52/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.