intersectmbo / cardano-coin-selection Goto Github PK
View Code? Open in Web Editor NEWA library of algorithms for coin selection and fee balancing.
License: Apache License 2.0
cardano-coin-selection's People
Contributors
![iohk-bors[bot] avatar](https://avatars.githubusercontent.com/in/17473?v=4 "iohk-bors[bot]")
Stargazers
Watchers
Forkers
crptmppt turbomack jonathanknowles gokyo rmourey26 trueblueaddie input-output-global crypto2099 nilismithcardano-coin-selection's Issues
Release `cardano-coin-selection` library to Hackage and Stackage.
Context
As part of the work to create a separate coin selection and fee balancing library, we'd like for the library to be consumable by the wider Haskell community.
Decision
Release the library to both Hackage and Stackage.
Prerequisites
The following issues must be closed before we can make a release:
From cardano-wallet:
From cardano-coin-selection:
Acceptance Criteria
- The
cardano-coin-selectionlibrary must be available on Hackage, including Haddock documentation. - The
cardano-coin-selectionlibrary must be available on Stackage, including Haddock documentation.
Development
- Release the
cardano-coin-selectionlibrary to Hackage. - Release the
cardano-coin-selectionlibrary to Stackage.
Address areas of missing code coverage for coin selection.
Context
There are a few areas of missing code coverage in the cardano-coin-selection library.
Areas discovered from mutation testing
- Fix issues outlined in #8
Other (potential) areas of missing coverage
- Add a test for the invariant of function
adjustForFee. - Add a test for the invariant of function
distributeFee. - Add property tests for function
Cardano.Fee.splitCoin. - Add property tests for function
Cardano.Fee.reduceChangeOutputs. - Add test of fairness for function
Cardano.Fee.distributeFee.
Decision
Address these areas of missing code coverage with property test or unit tests, as appropriate.
test
test
Revise documentation for `cardano-coin-selection` library.
Context
As part of the work to create a separate coin selection and fee balancing library, we'd like the library to be documented in a way that's consistent with good practices used by other popular libraries in the Haskell ecosystem.
Decision
Revise the public documentation for the cardano-coin-selection library.
Acceptance Criteria
Source Code Documentation (Haddock)
- Every public module should have a clear summary to state its purpose.
- Every exported function should have a clear comment to illustrate its purpose.
- Every exported type should have a clear comment to illustrate its purpose.
- Every exported constructor should have a clear comment to illustrate its purpose.
Other Documentation
- The home page for the
cardano-coin-selectionlibrary must explain the basic purpose of the library. This page can delegate to source code documentation where appropriate, to avoid duplication.
Development
- Remove Cardano-specific blockchain limitations from comments. For example:
https://github.com/input-output-hk/cardano-coin-selection/blob/f62d069062f196d3b251ac6e7a039a0030d929d6/src/library/Cardano/CoinSelection/Migration.hs#L19-L21 - State what is meant by
relatively-balancedin functionidealBatchSize. See this comment. (We eventually solved this by referring toidealBatchSizeas an automatic way to generate a suitable batch size forselectCoins. See https://input-output-hk.github.io/cardano-coin-selection/haddock/cardano-coin-selection-1.0.0/Cardano-CoinSelection-Algorithm-Migration.html#v:selectCoins.) - Check for obvious grammar and spelling errors.
QA
Section to be added.
The Largest-First algorithm should pay for outputs collectively.
Context
The Largest-First algorithm is used as a fall-back for cases when more sophisticated algorithms fail to produce a coin selection.
However, our current implementation is broken in a subtle way. Rather than considering the total collective value of all outputs when attempting to find a selection of inputs (as it should), our implementation instead considers each output independently, and for each output, attempts to find a selection of inputs to cover just that output.
This leads to an unnecessary cardinality restriction, namely that a single unique input can only be used to pay for at most one unique output, which means that any set of n outputs can only be paid for if the UTxO has at least n inputs. Under this restriction, the algorithm can fail even if the total value of inputs is sufficient to cover the required outputs.
Suggested Fix
We should adjust our current implementation so that the algorithm considers the total value of all outputs collectively, rather than considering them individually.
Under this relaxed scheme, it will always be possible to pay for a given set of outputs of total value v if the total value u of the UTxO satisfies u >= v.
Repo Preparation for MBO
This repo has been marked as core tech and is part of initiative of repo preparation, part of this includes adding needed missing documentation.
This repo in particular needs:
- Explain how to make a contribution (Contributing MD)
- Include the Standard Code of Conduct
- Identify the Core Maintainers
Potential areas of missing test coverage.
Reproduction Steps
- Compile and run the test suite. (Observe that it passes.)
- Apply any of the diffs in the section below.
- Re-compile and re-run the test suite.
Expected Behaviour
The test suite should fail (somewhere).
Actual Behaviour
The test suite passes.
Analysis
It's likely that we are lacking test coverage in certain areas.
Currently, most tests are unit-based, but we could consider adding property-based tests capable of covering more cases.
Cases
Largest-First Algorithm
- Checking that UTxO is appropriately depleted (fixed in PR #81)
Details
diff --git a/src/Cardano/CoinSelection/LargestFirst.hs b/src/Cardano/CoinSelection/LargestFirst.hs
index 5cc95aa..581640e 100644
--- a/src/Cardano/CoinSelection/LargestFirst.hs
+++ b/src/Cardano/CoinSelection/LargestFirst.hs
@@ -173,9 +173,9 @@ largestFirst
-> ExceptT (ErrCoinSelection e) m (CoinSelection, UTxO)
largestFirst options outputsRequested utxo =
case foldM atLeast (utxoDescending, mempty) outputsDescending of
- Just (utxoRemaining, selection) ->
+ Just (_utxoRemaining, selection) ->
validateSelection selection $>
- (selection, UTxO $ Map.fromList utxoRemaining)
+ (selection, utxo)
Nothing ->
throwE errorCondition
where- Checking that the input limit has not been exceeded.
Details
diff --git a/src/Cardano/CoinSelection/LargestFirst.hs b/src/Cardano/CoinSelection/LargestFirst.hs
index 5cc95aa..7bca28f 100644
--- a/src/Cardano/CoinSelection/LargestFirst.hs
+++ b/src/Cardano/CoinSelection/LargestFirst.hs
@@ -184,7 +184,7 @@ largestFirst options outputsRequested utxo =
ErrUtxoBalanceInsufficient amountAvailable amountRequested
| utxoCount < outputCount =
ErrUtxoNotFragmentedEnough utxoCount outputCount
- | utxoCount <= inputCountMax =
+ | utxoCount < inputCountMax =
ErrUxtoFullyDepleted
| otherwise =
ErrMaximumInputCountExceeded inputCountMaxRandom-Improve Algorithm
- Checking that UTxO is appropriately depleted (fixed in PR #81)
Details
diff --git a/src/Cardano/CoinSelection/Random.hs b/src/Cardano/CoinSelection/Random.hs
index 7aeead1..6bd2741 100644
--- a/src/Cardano/CoinSelection/Random.hs
+++ b/src/Cardano/CoinSelection/Random.hs
@@ -120,9 +120,9 @@ random opt outs utxo = do
foldM makeSelection (maxN, utxo, []) (descending outs)
case randomMaybe of
Just (maxN', utxo', res) -> do
- (_, sel, remUtxo) <- lift $
+ (_, sel, _remUtxo) <- lift $
foldM improveTxOut (maxN', mempty, utxo') (reverse res)
- guard sel $> (sel, remUtxo)
+ guard sel $> (sel, utxo)
Nothing ->
largestFirst opt outs utxo
where- Checking that the input limit has not been exceeded.
Details
diff --git a/src/Cardano/CoinSelection/Random.hs b/src/Cardano/CoinSelection/Random.hs
index 7aeead1..be7944f 100644
--- a/src/Cardano/CoinSelection/Random.hs
+++ b/src/Cardano/CoinSelection/Random.hs
@@ -147,7 +147,7 @@ makeSelection (maxNumInputs, utxo0, selection) txout = do
=> ([(TxIn, TxOut)], UTxO)
-> MaybeT m ([(TxIn, TxOut)], UTxO)
coverRandomly (inps, utxo)
- | L.length inps > (fromIntegral maxNumInputs) =
+ | L.length inps >= (fromIntegral maxNumInputs) =
MaybeT $ return Nothing
| balance' inps >= targetMin (mkTargetRange txout) =
MaybeT $ return $ Just (inps, utxo)migration algorithm exits without processing all inputs.
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
The issue is the handling of the Nothing branch ☝️ which should not be pure [] (terminal case of the recursion) but simply migrate, discarding the ongoing selection, but continuing migrating others.
Revise public API of `cardano-coin-selection` library.
Context
As part of the work to create a separate coin selection and fee balancing library, we need to ensure that the public API and source code is consistent with best practices generally adopted by the Haskell community.
Decision
Conduct an examination of the public API and source code, and revise it as necessary to bring it into line with best practices adopted within the Haskell community.
Development
Areas to revise
-
Module structure
The migration algorithm, while designed to select coins, doesn't have the same type as other algorithms such as
Largest-FirstorRandom-Improve, despite sharing a commonCardano.CoinSelectionparent module.The
Feemodule is also not a coin selection algorithm per se, so it should probably not be at the same level as the coin selection algorithms.We decided to adopt the following module hierarchy:
Cardano └── CoinSelection ├── Algorithm │ ├── LargestFirst │ ├── Migration │ └── RandomImprove └── Fee
-
BuildableinstancesThese have been moved out of the public API, and restricted to just the test code.
-
CoinSelectionErrortypeWe have:
- Added record fields to disambiguate the constructor arguments.
- Used specific types for currency values, rather than
Word64. - Embedded more information in each error, where possible.
Fixed in #53.
-
ErrAdjustForFeetypeWe now:
- Use the
Feetype, rather thanWord64.
- Use the
-
CoinSelectionAlgorithmfall-back/delegationThe
Random-Improvealgorithm no longer delegates toLargest-Firstif it fails to find a selection. (See #44).If a library user wishes to implement fallback themselves, it's trivial to implement by calling one algorithm after the other.
For
cardano-wallet, it's important that existing fallback behaviour is preserved when we eventually consume thecardano-coin-selectionfrom that library. This requirement has been captured on the acceptance criteria here: #20 -
TypesmoduleThis module has been merged into
CoinSelection. -
ShowFmttypeThis has been removed from the public API.
-
DomtypeThis has been removed from the public API.
-
excluding,isSubsetOf,restrictedBy,restrictedTofunctionsThese have been removed from the public API.
-
distancefunctionThis has been removed from the public API.
-
invariantfunctionThis has been removed from the public API.
-
CoinSelectiontypeBoth
inputsandoutputsare now of typeCoinMap. -
HasCallStackconstraintsWe should examine whether all of these are required, or only some, and remove those that are not necessary.
-
TODOcommentsThere are no more TODO comments within library source code. (All issues have been addressed.) There are some TODO comments within the test code relating to reduction of code duplication, but these do not prevent publication of the library.
Tests fail with ghc 9.6 on stackage nightly
Add to expected test failures for now.
Test suite failure for package cardano-coin-selection-1.0.1
unit: exited with: ExitFailure 1
Full log available at /var/stackage/work/unpack-dir/.stack-work/logs/cardano-coin-selection-1.0.1-test.log
Cardano.CoinSelection
CoinMap properties
CoinMap coverage is adequate [✔]
+++ OK, passed 200 tests:
39.0% coin map has multiple entries
39.0% coin map has several unique values
34.0% coin map has one entry
34.0% coin map has one unique value
27.0% coin map is empty
CoinMapEntry coverage is adequate [✔]
+++ OK, passed 3200 tests:
86.72% coin map entry list has multiple entries
86.34% coin map entry list has multiple unique keys
40.16% coin map entry list has multiple duplicate keys
27.56% coin map entry list has no duplicate keys
15.69% coin map entry list has one duplicate key
11.34% coin map entry list has two duplicate keys
5.25% coin map entry list is empty
4.53% coin map entry list has one unique key
4.38% coin map entry list has one entry
3.88% coin map entry list has two unique keys
3.66% coin map entry list has two entries
coinMapFromList preserves total value for each unique key [✔]
+++ OK, passed 100 tests.
coinMapFromList preserves total value [✔]
+++ OK, passed 100 tests.
coinMapToList preserves total value [✔]
+++ OK, passed 100 tests.
coinMapFromList . coinMapToList = id [✔]
+++ OK, passed 100 tests.
coinMapToList . coinMapFromList = id (when no keys duplicated) [✔]
+++ OK, passed 100 tests.
coinMapToList order deterministic [✔]
+++ OK, passed 100 tests (43% shuffled).
CoinSelection properties
monoidal append preserves keys [✔]
+++ OK, passed 100 tests.
monoidal append preserves value [✔]
+++ OK, passed 100 tests.
CoinSelectionData properties
CoinSelectionData coverage is adequate [✔]
+++ OK, passed 200 tests (98.5% amountAvailable ≥ amountRequested).
Cardano.CoinSelection.Algorithm.LargestFirst
Coin selection: largest-first algorithm: unit tests
Expect success: case #1:
max=100, UTxO=[10,10,17], Output=[17] --> Right [17] [✔]
Expect success: case #2:
max=100, UTxO=[12,10,17], Output=[1] --> Right [17] [✔]
Expect success: case #3:
max=100, UTxO=[12,10,17], Output=[18] --> Right [12,17] [✔]
Expect success: case #4:
max=100, UTxO=[12,10,17], Output=[30] --> Right [10,12,17] [✔]
Expect success: case #5:
max=3, UTxO=[1,2,10,6,5], Output=[11,1] --> Right [6,10] [✔]
Expect success: case #6:
max=100, UTxO=[12,20,17], Output=[40,1,1,1] --> Right [12,17,20] [✔]
Expect success: case #7:
max=100, UTxO=[12,20,17], Output=[40,1] --> Right [12,17,20] [✔]
Expect success: case #8:
max=100, UTxO=[20,20,10,5], Output=[41,6] --> Right [10,20,20] [✔]
Expect success: case #9:
max=2, UTxO=[1,2,10,6,5], Output=[11,1] --> Right [6,10] [✔]
Expect success: fewer inputs than outputs: case #1:
max=1000, UTxO=[100,100], Output=[1,2,3,4] --> Right [100] [✔]
Expect success: fewer inputs than outputs: case #2:
max=1000, UTxO=[100,10], Output=[1,2,3,4] --> Right [100] [✔]
Expect success: fewer inputs than outputs: case #3:
max=1000, UTxO=[10,10], Output=[1,2,3,4] --> Right [10] [✔]
Expect success: fewer inputs than outputs: case #4:
max=1, UTxO=[100], Output=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] --> Right [100] [✔]
UTxO balance not sufficient: case #1:
max=100, UTxO=[12,10,17], Output=[40] --> Left (InputValueInsufficient (InputValueInsufficientError {inputValueAvailable = Coin 39, inputValueRequired = Coin 40})) [✔]
UTxO balance not sufficient: case #2:
max=100, UTxO=[12,10,17], Output=[40,1,1,1] --> Left (InputValueInsufficient (InputValueInsufficientError {inputValueAvailable = Coin 39, inputValueRequired = Coin 43})) [✔]
UTxO balance sufficient, but maximum input count exceeded:
max=9, UTxO=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], Output=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] --> Left (InputLimitExceeded (InputLimitExceededError {calculatedInputLimit = 9})) [✔]
Coin selection: largest-first algorithm: properties
forall (UTxO, NonEmpty TxOut), for all selected input, there's no bigger input in the UTxO that is not already in the selected inputs [✔]
+++ OK, passed 100 tests; 1 discarded.
The algorithm selects just enough inputs and no more. [✔]
+++ OK, passed 10000 tests; 81 discarded.
The algorithm produces the correct set of change. [✘]
Cardano.CoinSelection.Algorithm.Migration
idealBatchSize
Eventually converge for decreasing functions [✔]
+++ OK, passed 100 tests:
47% BatchSize 42
27% BatchSize 32768
26% BatchSize 21845
accuracy of selectCoins
dust=1% [✔]
+++ OK, passed 1000 tests:
89.9% MEDIOCRE (<= 99%)
9.8% PERFECT (== 100%)
0.3% OKAY (> 99%)
dust=5% [✔]
+++ OK, passed 1000 tests:
72.5% PERFECT (== 100%)
23.1% MEDIOCRE (<= 99%)
4.4% OKAY (> 99%)
dust=10% [✔]
+++ OK, passed 1000 tests:
89.5% PERFECT (== 100%)
6.6% MEDIOCRE (<= 99%)
3.9% OKAY (> 99%)
dust=25% [✔]
+++ OK, passed 1000 tests:
96.6% PERFECT (== 100%)
2.2% OKAY (> 99%)
1.2% MEDIOCRE (<= 99%)
dust=50% [✔]
+++ OK, passed 1000 tests:
98.6% PERFECT (== 100%)
1.1% OKAY (> 99%)
0.3% MEDIOCRE (<= 99%)
selectCoins properties
No coin selection has outputs [✔]
+++ OK, passed 10000 tests.
Every coin in the selection change > dust threshold [✔]
+++ OK, passed 10000 tests.
Total input UTxO value >= sum of selection change coins [✔]
+++ OK, passed 10000 tests.
Every selection input is unique [✔]
+++ OK, passed 10000 tests.
Every selection input is a member of the UTxO [✔]
+++ OK, passed 10000 tests.
Every coin selection is well-balanced [✔]
+++ OK, passed 10000 tests.
selectCoins regressions
regression #1 [✔]
+++ OK, passed 1 test.
Cardano.CoinSelection.Algorithm.RandomImprove
Coin selection : random algorithm unit tests
Cardano.CoinSelectionSpec[355:5] [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
cannot cover aim, but only min:
max=4, UTxO=[1,1,1,1,1,1], Output=[3] --> Right [1,1,1,1] [✔]
REG CO-450: no fallback:
max=4, UTxO=[1000000,1000000,1000000,1000000], Output=[2000000,500000] --> Right [1000000,1000000,1000000,1000000] [✔]
enough funds, proper fragmentation, inputs depleted:
max=100, UTxO=[10,10,10,10], Output=[38,1] --> Left (InputsExhausted InputsExhaustedError) [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
each output needs <maxNumOfInputs:
max=9, UTxO=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], Output=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] --> Left (InputLimitExceeded (InputLimitExceededError {calculatedInputLimit = 9})) [✔]
each output needs >maxNumInputs:
max=9, UTxO=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], Output=[10,10,10,10,10,10,10,10,10,10] --> Left (InputLimitExceeded (InputLimitExceededError {calculatedInputLimit = 9})) [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
Cardano.CoinSelectionSpec[355:5] [✔]
Coin selection properties : random algorithm
forall (UTxO, NonEmpty TxOut), running algorithm gives not less UTxO fragmentation than LargestFirst algorithm [✔]
+++ OK, passed 100 tests; 2 discarded.
forall (UTxO, NonEmpty TxOut), running algorithm gives the same errors as LargestFirst algorithm [✔]
+++ OK, passed 100 tests.
Cardano.CoinSelection.Fee
Fee calculation : unit tests
CoinSelection (inps=[20]outs=[17]chngs=[3]), UTxO=[]), fee=3 --> Right (FeeOutput {csInps = [20], csOuts = [17], csChngs = []}) [✔]
CoinSelection (inps=[20,20]outs=[16,18]chngs=[4,2]), UTxO=[]), fee=6 --> Right (FeeOutput {csInps = [20,20], csOuts = [16,18], csChngs = []}) [✔]
CoinSelection (inps=[20,20]outs=[18,18]chngs=[2,2]), UTxO=[]), fee=2 --> Right (FeeOutput {csInps = [20,20], csOuts = [18,18], csChngs = [1,1]}) [✔]
CoinSelection (inps=[20,20]outs=[17,18]chngs=[3,2]), UTxO=[]), fee=2 --> Right (FeeOutput {csInps = [20,20], csOuts = [17,18], csChngs = [2,1]}) [✔]
CoinSelection (inps=[20,20,20]outs=[14,18,19]chngs=[6,2,1]), UTxO=[]), fee=3 --> Right (FeeOutput {csInps = [20,20,20], csOuts = [14,18,19], csChngs = [4,1,1]}) [✔]
CoinSelection (inps=[20,20,20]outs=[14,18,19]chngs=[6,2,1]), UTxO=[]), fee=3 --> Right (FeeOutput {csInps = [20,20,20], csOuts = [14,18,19], csChngs = [6]}) [✔]
CoinSelection (inps=[20]outs=[17]chngs=[3]), UTxO=[]), fee=4 --> Left (CannotCoverFee (Fee (Coin 1))) [✔]
CoinSelection (inps=[10]outs=[7]chngs=[3]), UTxO=[1]), fee=5 --> Left (CannotCoverFee (Fee (Coin 1))) [✔]
CoinSelection (inps=[10]outs=[7]chngs=[3]), UTxO=[1,1]), fee=5 --> Right (FeeOutput {csInps = [10,1,1], csOuts = [7], csChngs = []}) [✔]
CoinSelection (inps=[10]outs=[7]chngs=[3]), UTxO=[3]), fee=5 --> Right (FeeOutput {csInps = [10,3], csOuts = [7], csChngs = [1]}) [✔]
CoinSelection (inps=[10,10]outs=[7,7]chngs=[3,3]), UTxO=[2,2]), fee=10 --> Right (FeeOutput {csInps = [10,10,2,2], csOuts = [7,7], csChngs = []}) [✔]
CoinSelection (inps=[10,10]outs=[7,7]chngs=[3,3]), UTxO=[3,3]), fee=10 --> Right (FeeOutput {csInps = [10,10,3,3], csOuts = [7,7], csChngs = [1,1]}) [✔]
CoinSelection (inps=[20,20]outs=[16,18]chngs=[4,2]), UTxO=[]), fee=6 --> Right (FeeOutput {csInps = [20,20], csOuts = [16,18], csChngs = []}) [✔]
CoinSelection (inps=[1]outs=[1]chngs=[]), UTxO=[2]), fee=1 --> Right (FeeOutput {csInps = [1,2], csOuts = [1], csChngs = [1]}) [✔]
CoinSelection (inps=[]outs=[]chngs=[]), UTxO=[3]), fee=3 --> Right (FeeOutput {csInps = [3], csOuts = [], csChngs = []}) [✔]
CoinSelection (inps=[]outs=[]chngs=[]), UTxO=[2,2]), fee=3 --> Right (FeeOutput {csInps = [2,2], csOuts = [], csChngs = [1]}) [✔]
CoinSelection (inps=[]outs=[]chngs=[]), UTxO=[2,2]), fee=3 --> Right (FeeOutput {csInps = [2,2], csOuts = [], csChngs = [1]}) [✔]
Fee Calculation: Generators
Arbitrary CoinSelection [✔]
+++ OK, passed 100 tests.
Fee Adjustment properties
Fee adjustment is deterministic when there's no extra inputs [✔]
+++ OK, passed 100 tests.
Adjusting for fee (/= 0) reduces the change outputs or increase inputs [✔]
+++ OK, passed 100 tests; 10 discarded.
distributeFee
fee portions are all within unity of ideal unrounded portions [✔]
+++ OK, passed 100 tests.
fee portions are allocated optimally [✔]
+++ OK, passed 100 tests.
Σ fst (distributeFee fee outs) == fee [✔]
+++ OK, passed 3200 tests.
properties (6400 in total):
50.00% fee > 0
40.55% nOuts=2+
4.88% nOuts=1
4.58% nOuts=2
snd (distributeFee fee outs) == outs [✔]
+++ OK, passed 3200 tests.
properties (6400 in total):
50.00% fee > 0
40.55% nOuts=2+
4.88% nOuts=1
4.58% nOuts=2
expectFailure: not (any null (fst <$> distributeFee fee outs)) [✔]
+++ OK, failed as expected. Falsified (after 1264 tests and 49 shrinks):
(Fee (Coin 1),Coin 1 :| [Coin 1])
coalesceDust
sum coins = sum (coalesceDust threshold coins) [✔]
+++ OK, passed 12800 tests:
91.016% sum coins ≠ 0
8.984% sum coins = 0
all (/= Coin 0) (coalesceDust threshold coins) [✔]
+++ OK, passed 12800 tests:
91.141% ∃ coin ∈ coins . coin = 0
8.984% ∀ coin ∈ coins . coin = 0
8.859% ∀ coin ∈ coins . coin > 0
leaves at most one dust coin [✔]
+++ OK, passed 12800 tests:
52.805% length result ≥ 2
38.211% length result = 1
26.687% ∀ coin ∈ coins . coin ≠ threshold
13.891% have mixture of coin values in relation to threshold
8.984% length result = 0
8.906% ∀ coin ∈ coins . coin = threshold
7.953% ∀ coin ∈ coins . coin < threshold
3.180% ∀ coin ∈ coins . coin > threshold
length coins >= (coalesceDust threshold coins) [✔]
+++ OK, passed 100 tests.
reduceChangeOutputs
data coverage is adequate [✔]
+++ OK, passed 400 tests:
100.0% fee >= 0
51.5% several non-empty coins
30.8% fee = 0
23.5% 0 < fee < sum coins
21.8% fee > sum coins
21.2% fee = sum coins
21.2% two non-empty coins
15.5% one non-empty coin
the fee balancing algorithm converges for any coin selection [✔]
+++ OK, passed 100000 tests.
splitCoin
data coverage is adequate [✔]
+++ OK, passed 200 tests:
73.0% coin to split is non-zero
54.0% list of coins has at least one non-zero coin
42.5% list of coins has at least one zero coin
37.0% list of coins has multiple entries
33.5% coin to split is smaller than number of coins to increase
33.5% list of coins is empty
29.5% list of coins is singleton
27.0% coin to split is zero
preserves the total sum [✔]
+++ OK, passed 100 tests.
results are all within unity of ideal unrounded results [✔]
+++ OK, passed 100 tests.
Cardano.CoinSelection.Types
Lemma 2.1 - Properties of UTxO operations
2.1.1) ins⊲ u ⊆ u [✔]
+++ OK, passed 100 tests (78% dom u ⋂ ins ≠ ∅).
2.1.2) ins⋪ u ⊆ u [✔]
+++ OK, passed 100 tests (78% dom u ⋂ ins ≠ ∅).
2.1.3) u ⊳ outs ⊆ u [✔]
+++ OK, passed 100 tests (81% u ⋂ outs ≠ ∅).
2.1.4) ins⊲ (u ⋃ v) = (ins⊲ u) ⋃ (ins⊲ v) [✔]
+++ OK, passed 100 tests (92% (dom u ⋃ dom v) ⋂ ins ≠ ∅).
2.1.5) ins⋪ (u ⋃ v) = (ins⋪ u) ⋃ (ins⋪ v) [✔]
+++ OK, passed 100 tests (92% (dom u ⋃ dom v) ⋂ ins ≠ ∅).
2.1.6) (dom u ⋂ ins) ⊲ u = ins⊲ u [✔]
+++ OK, passed 100 tests (78% dom u ⋂ ins ≠ ∅).
2.1.7) (dom u ⋂ ins) ⋪ u = ins⋪ u [✔]
+++ OK, passed 100 tests (78% dom u ⋂ ins ≠ ∅).
2.1.8) (dom u ⋃ ins) ⋪ (u ⋃ v) = (ins ⋃ dom u) ⋪ v [✔]
+++ OK, passed 100 tests (78% dom u ⋂ ins ≠ ∅).
2.1.9) ins⋪ u = (dom u \ ins)⊲ u [✔]
+++ OK, passed 100 tests (78% dom u ⋂ ins ≠ ∅).
Lemma 2.6 - Properties of balance
2.6.1) dom u ⋂ dom v ==> balance (u ⋃ v) = balance u + balance v [✔]
+++ OK, passed 200 tests (67.0% u ≠ ∅ , v ≠ ∅).
2.6.2) balance (ins⋪ u) = balance u - balance (ins⊲ u) [✔]
+++ OK, passed 100 tests (78% dom u ⋂ ins ≠ ∅).
Internal.Coin
Coin properties
Only construction of non-negative values is possible. [✔]
+++ OK, passed 3200 tests:
50.03% input is negative
46.53% input is positive
3.44% input is zero
Coverage of generated values is acceptable. [✔]
+++ OK, passed 100 tests:
45% value is more than one
28% value is zero
27% value is one
Addition [✔]
+++ OK, passed 100 tests.
Multiplication [✔]
+++ OK, passed 6400 tests:
48.64% scaling factor is positive
48.20% scaling factor is negative
3.16% scaling factor is zero
Subtraction [✔]
+++ OK, passed 100 tests:
50% x > y
29% x < y
21% values are equal
Division [✔]
+++ OK, passed 6400 tests:
48.64% denominator is positive
48.20% denominator is negative
3.16% denominator is zero
Modulus [✔]
+++ OK, passed 6400 tests:
48.64% denominator is positive
48.20% denominator is negative
3.16% denominator is zero
Distance [✔]
+++ OK, passed 100 tests:
50% x > y
29% x < y
21% values are equal
Test.Vector.Shuffle
shuffle
every list can be shuffled, ultimately [✔]
+++ OK, passed 100 tests (91% shuffled).
shuffle is non-deterministic [✔]
+++ OK, passed 100 tests (95% not deterministic).
sort (shuffle xs) == sort xs [✔]
+++ OK, passed 100 tests (98% non-empty).
shuffleNonEmpty
every non-empty list can be shuffled, ultimately [✔]
+++ OK, passed 100 tests (91% shuffled).
shuffleNonEmpty is non-deterministic [✔]
+++ OK, passed 100 tests (92% not deterministic).
sort (shuffleNonEmpty xs) == sort xs [✔]
+++ OK, passed 100 tests (100% non-empty).
shuffleWith / mkSeed
shuffling with the same seed is deterministic [✔]
+++ OK, passed 100 tests (98% non singleton).
different seed means different shuffles [✔]
+++ OK, passed 200 tests; 23 discarded:
89.5% different
66.0% big list
29.0% small list
5.0% singleton
Failures:
src/test/Cardano/CoinSelection/Algorithm/LargestFirstSpec.hs:274:9:
1) Cardano.CoinSelection.Algorithm.LargestFirst, Coin selection: largest-first algorithm: properties, The algorithm produces the correct set of change.
*** Gave up! Passed only 51199 tests; 416 discarded tests:
98.742% amountSelected > amountRequired
1.258% amountSelected = amountRequired
To rerun use: --match "/Cardano.CoinSelection.Algorithm.LargestFirst/Coin selection: largest-first algorithm: properties/The algorithm produces the correct set of change./"
Randomized with seed 624635623
Finished in 43.6456 seconds
121 examples, 1 failure
Reuse `cardano-coin-selection` library within `cardano-wallet`.
Context
When the work to create a separate coin selection and fee balancing library is complete, we'd like to be able to reuse the library internally within the cardano-wallet library.
Decision
Make the cardano-wallet library depend upon the Hackage version of cardano-coin-selection, and remove all local copies of coin selection code.
Acceptance Criteria
-
The
cardano-walletlibrary must depend upon the Hackage version ofcardano-coin-selection. -
The
cardano-walletlibrary must not duplicate code that is included within the publishedcardano-coin-selectionlibrary. -
The
cardano-walletlibrary must continue to implement the algorithm fallback policy currently in place (Currently, this is fromRandom-ImprovetoLargest-First) and there must be tests in place to determine that this policy activates appropriately.
Development
Section to be added.
QA
Section to be added.
Revise and simplify test suite.
Context
This issue collects together tasks relating to simplifying the test suite for cardano-coin-selection.
Tasks
-
TxInandAddresstypes (used for testing)These can be simplified, as the tests only rely on the fact that generated values are unique and can be ordered. (The internal structure of these types is not relevant.)
In particular, the
Showinstance ofTxInis very noisy, making output of tests very difficult to read. -
ArbitraryinstancesMany of these are duplicates of one another, or very similar. We should consider whether or not it would be worth merging similar instances.
Port `remainingFee` calculation fix from `cardano-wallet`.
Coin Selection: Public Specification
Motivation
As a developer or researcher, I'd like to be able to understand Cardano's coin selection and fee balancing algorithms without having to read through and understand source code.
Task
Produce a human-readable specification of the coin selection and fee balancing algorithms used by cardano-wallet.
Acceptance Criteria
- The specification must provide human-readable explanations of the following coin selection algorithms:
- Largest-First;
- Random-Improve;
- Migration.
- The specification must provide a human-readable explanation of the following fee balancing algorithm:
- Sender Pays Fee.
- The specification should specify test vectors for each of the included algorithms.
- The specification should specify the properties that we expect each of the included algorithms to obey.
- The specification should have an obvious format in the sense that we don't need a meta-specification to explain how the specification is structured.
Add code coverage to `cardano-coin-selection` library.
Context
As part of the work to create a separate coin selection and fee balancing library, it would be helpful to be able to monitor the proportion of code that is being covered by tests.
Decision
Add code coverage support to the cardano-coin-selection library.
Acceptance Criteria
- The continuous integration system must generate a code coverage report for each build of the
masterbranch. - It must be possible to view the level of code coverage for the latest build from the
cardano-coin-selectionhome page.
Development
- Add a badge to the README showing code coverage of latest build.
QA
Section to be added.
API docs for Largest-First include impossible error conditions.
The documentation for Largest-First reports that it can (in some cases) return the following errors:
InputCountInsufficientErrorInputsExhaustedError
However, with the recent changes introduced by PR #73, these error conditions can now never occur.
We should either:
- Revise the docs to remove references to these errors.
- Revise the error type to not include these errors. (But this will require the error type of
CoinSelectionAlgorithmto be parameterized, which is a breaking change to the API.)
Generalize types within `cardano-coin-selection` library.
Context
The cardano-coin-selection library currently duplicates some of the types that are defined within the cardano-wallet library.
It would be desirable to replace these duplicated types with abstract types or interfaces, allowing consumers of the library (including cardano-wallet) to use their own concrete types.
Decision
Revise the types used in the cardano-coin-selection library, replacing concrete types with abstract types (or interfaces) where it makes sense.
Types to Generalize
-
Cardano.CoinSelection.CoinSelectionLimit
This was originally defined in terms ofWord8. It has been widened toWord16. -
TxIn(used in the inputs of aCoinSelection)
Since coin selection algorithms are agnostic to the type of input identifier, this has been replaced with the type variablei. -
Address(used in the outputs of aCoinSelection)
Since coin selection algorithms are agnostic to the type of output identifier, this has been replaced with a type variableo. -
UTxO
This has been replaced withCoinMap i, whereirefers to an input identifier type. -
[TxOut]
This has been replaced withCoinMap o, whereorefers to an output identifier type. -
Hash
This has been removed, as it was part ofTxInwhich has also been removed. -
Coin
This was originally defined in terms ofWord64, and has now been redefined in terms ofNatural. -
Fee
This was originally defined in terms ofWord64, and has now been redefined in terms ofCoin(which is defined in terms ofNatural). -
DustThreshold
This was originally defined in terms ofWord64, and has now been redefined in terms ofCoin(which is defined in terms ofNatural).
Hackage unable to build package.
Hackage is unable to build version 1.0.0 of the cardano-coin-selection package.
Extract from build log:
src/library/Cardano/CoinSelection/Fee.hs:351:31: error:
• Couldn't match type ‘m’ with ‘Data.Functor.Identity.Identity’
‘m’ is a rigid type variable bound by
the type signature for:
senderPaysFee :: forall i o (m :: * -> *).
(Ord i, MonadRandom m) =>
FeeOptions i o
-> CoinMap i
-> CoinSelection i o
-> ExceptT (FeeAdjustmentError i o) m (CoinSelection i o)
at src/library/Cardano/CoinSelection/Fee.hs:(334,1)-(339,61)
Expected type: StateT
(CoinMap i)
(ExceptT (FeeAdjustmentError i o) m)
(CoinSelection i o, Fee)
Actual type: StateT
(CoinMap i)
(ExceptT (FeeAdjustmentError i o) Data.Functor.Identity.Identity)
(CoinSelection i o, Fee)Source: https://hackage.haskell.org/package/cardano-coin-selection-1.0.0/reports/1
Add Haddock documentation to the README.
We should:
- generate Haddock documentation as part of the build.
- add a link to the documentation from the README.
Minimum bound for `Coin` inconsistent with specification.
The specification states that:
A coin value is a positive integer value that represents a number of
Lovelace.
However, our Haskell source code has the following definition for Coin:
-- | A non-negative integer value that represents a number of Lovelace.
--
-- One Ada is equal to 1,000,000 Lovelace.
--
newtype Coin = Coin
{ getCoin :: Word64 }
deriving stock (Eq, Generic, Ord)
deriving Show via (Quiet Coin)
instance NFData Coin
instance Bounded Coin where
minBound = Coin 0
maxBound = Coin 45000000000000000
coinIsValid :: Coin -> Bool
coinIsValid c = c >= minBound && c <= maxBound We should consider whether this inconsistency matters, and if necessary, revise the definition or the specification so that they agree with one another.
Sporadic migration property failure.
Seen on master (commit 08694ea).
cardano-coin-selection> test (suite: unit, args: -m "Total input UTxO value")
Cardano.CoinSelection.Algorithm.Migration
selectCoins properties
Total input UTxO value >= sum of selection change coins FAILED [1]
Failures:
src/test/Cardano/CoinSelection/Algorithm/MigrationSpec.hs:127:9:
1) Cardano.CoinSelection.Algorithm.Migration, selectCoins properties, Total input UTxO value >= sum of selection change coins
Falsified (after 4413 tests and 7 shrinks):
(DustThreshold (Coin 8),RequireMinimalFee)
BatchSize 1
CoinMap (fromList [(Wrapped {unwrap = TxIn {txinId = Hash "\GS\STX.\t\CAN\STX*/\DC3'@@7$;)4\STX\DC2*@+\RS0/=-\SUB%\b\RS?", txinIx = 1}},Coin 7)])
Selections: [CoinSelection {inputs = CoinMap (fromList [(Wrapped {unwrap = TxIn {txinId = Hash "\GS\STX.\t\CAN\STX*/\DC3'@@7$;)4\STX\DC2*@+\RS0/=-\SUB%\b\RS?", txinIx = 1}},Coin 7)]), outputs = CoinMap (fromList []), change = [Coin 8]}]
Total UTxO balance: Coin 7
Total change balance: Coin 8
To rerun use: --match "/Cardano.CoinSelection.Algorithm.Migration/selectCoins properties/Total input UTxO value >= sum of selection change coins/"
Randomized with seed 293953155
Finished in 2.2406 seconds
1 example, 1 failureAdd code coverage to the README.
Code coverage was formerly available at https://input-output-hk.github.io/cardano-coin-selection/coverage/hpc_index.html. But in recent builds this stopped working, resulting in a broken link from the home page.
Task
- Fix the build to generate working code coverage.
- Check that the link from the home page is working.
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.