A library of algorithms for coin selection and fee balancing.
License: Apache License 2.0
![iohk-bors[bot] avatar](https://avatars.githubusercontent.com/in/17473?v=4 "iohk-bors[bot]")
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:
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.
Make the cardano-wallet library depend upon the Hackage version of cardano-coin-selection, and remove all local copies of coin selection code.
The cardano-wallet library must depend upon the Hackage version of cardano-coin-selection.
The cardano-wallet library must not duplicate code that is included within the published cardano-coin-selection library.
The cardano-wallet library must continue to implement the algorithm fallback policy currently in place (Currently, this is from Random-Improve to Largest-First) and there must be tests in place to determine that this policy activates appropriately.
Section to be added.
Section to be added.
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).
The algorithm should discard such "no-value" selections, and continue processing next batches until it has traversed all batches.
The algorithm stops at the first "no-value" selections and returns, with whatever selections has been accumulated this far, possibly leaving many inputs behind.
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.
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.
Revise the types used in the cardano-coin-selection library, replacing concrete types with abstract types (or interfaces) where it makes sense.
Cardano.CoinSelection.CoinSelectionLimit
This was originally defined in terms of Word8. It has been widened to Word16.
TxIn (used in the inputs of a CoinSelection)
Since coin selection algorithms are agnostic to the type of input identifier, this has been replaced with the type variable i.
Address (used in the outputs of a CoinSelection)
Since coin selection algorithms are agnostic to the type of output identifier, this has been replaced with a type variable o.
UTxO
This has been replaced with CoinMap i, where i refers to an input identifier type.
[TxOut]
This has been replaced with CoinMap o, where o refers to an output identifier type.
Hash
This has been removed, as it was part of TxIn which has also been removed.
Coin
This was originally defined in terms of Word64, and has now been redefined in terms of Natural.
Fee
This was originally defined in terms of Word64, and has now been redefined in terms of Coin (which is defined in terms of Natural).
DustThreshold
This was originally defined in terms of Word64, and has now been redefined in terms of Coin (which is defined in terms of Natural).
The test suite should fail (somewhere).
The test suite passes.
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.
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
wherediff --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 inputCountMaxdiff --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
wherediff --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)We should:
test
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.
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.
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.
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.
There are a few areas of missing code coverage in the cardano-coin-selection library.
adjustForFee.distributeFee.Cardano.Fee.splitCoin.Cardano.Fee.reduceChangeOutputs.Cardano.Fee.distributeFee.Address these areas of missing code coverage with property test or unit tests, as appropriate.
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.
Revise the public documentation for the cardano-coin-selection library.
cardano-coin-selection library must explain the basic purpose of the library. This page can delegate to source code documentation where appropriate, to avoid duplication.relatively-balanced in function idealBatchSize. See this comment. (We eventually solved this by referring to idealBatchSize as an automatic way to generate a suitable batch size for selectCoins. See https://input-output-hk.github.io/cardano-coin-selection/haddock/cardano-coin-selection-1.0.0/Cardano-CoinSelection-Algorithm-Migration.html#v:selectCoins.)Section to be added.
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.
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.
Module structure
The migration algorithm, while designed to select coins, doesn't have the same type as other algorithms such as Largest-First or Random-Improve, despite sharing a common Cardano.CoinSelection parent module.
The Fee module 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 Buildable instances
These have been moved out of the public API, and restricted to just the test code.
CoinSelectionError type
We have:
Word64.Fixed in #53.
ErrAdjustForFee type
We now:
Fee type, rather than Word64. CoinSelectionAlgorithm fall-back/delegation
The Random-Improve algorithm no longer delegates to Largest-First if 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 the cardano-coin-selection from that library. This requirement has been captured on the acceptance criteria here: #20
Types module
This module has been merged into CoinSelection.
ShowFmt type
This has been removed from the public API.
Dom type
This has been removed from the public API.
excluding, isSubsetOf, restrictedBy, restrictedTo functions
These have been removed from the public API.
distance function
This has been removed from the public API.
invariant function
This has been removed from the public API.
CoinSelection type
Both inputs and outputs are now of type CoinMap.
HasCallStack constraints
We should examine whether all of these are required, or only some, and remove those that are not necessary.
TODO comments
There 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.
The documentation for Largest-First reports that it can (in some cases) return the following errors:
InputCountInsufficientErrorInputsExhaustedErrorHowever, with the recent changes introduced by PR #73, these error conditions can now never occur.
We should either:
CoinSelectionAlgorithm to be parameterized, which is a breaking change to the API.)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.
Add code coverage support to the cardano-coin-selection library.
master branch.cardano-coin-selection home page.Section to be added.
This issue collects together tasks relating to simplifying the test suite for cardano-coin-selection.
TxIn and Address types (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 Show instance of TxIn is very noisy, making output of tests very difficult to read.
Arbitrary instances
Many of these are duplicates of one another, or very similar. We should consider whether or not it would be worth merging similar instances.
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.
Produce a human-readable specification of the coin selection and fee balancing algorithms used by cardano-wallet.
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.
Release the library to both Hackage and Stackage.
The following issues must be closed before we can make a release:
From cardano-wallet:
From cardano-coin-selection:
cardano-coin-selection library must be available on Hackage, including Haddock documentation.cardano-coin-selection library must be available on Stackage, including Haddock documentation.cardano-coin-selection library to Hackage.cardano-coin-selection library to Stackage.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
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 failureHackage 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
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 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.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
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.