Sporadic migration property failure.

[jonathanknowles]

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 failure

[jonathanknowles]

Anecdotally, this test seems to be failing more often than in the past.

On my machine, it fails around 10% of the time.

Perhaps it would be worth doing a git bisect on the code base to figure out if there was a definite point in time where the failure rate increased.

[jonathanknowles]

The failure occurs even in 3181ddc (PR #62).

Reproduction:

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:128:9: 
  1) Cardano.CoinSelection.Algorithm.Migration, selectCoins properties, Total input UTxO value >= sum of selection change coins
       Falsifiable (after 6811 tests and 7 shrinks):
         (DustThreshold (Coin 9),RequireMinimalFee)
         1
         CoinMap (fromList [(Wrapped {unwrap = TxIn {txinId = Hash "\r\b \FS\EM\v\ENQ\t\SO\SO\f\NUL\f\r\t\STX\ETB\SUB\SI\EM\GS\SI\a\SOH\DC1\DC4\ACK\SUB\v\EOT\DC1\NAK", txinIx = 1}},Coin 1)])
         Selections: [CoinSelection {inputs = CoinMap (fromList [(Wrapped {unwrap = TxIn {txinId = Hash "\r\b \FS\EM\v\ENQ\t\SO\SO\f\NUL\f\r\t\STX\ETB\SUB\SI\EM\GS\SI\a\SOH\DC1\DC4\ACK\SUB\v\EOT\DC1\NAK", txinIx = 1}},Coin 1)]), outputs = CoinMap (fromList []), change = [Coin 9]}]
         Total UTxO balance: Coin 1
         Total change balance: Coin 9

  To rerun use: --match "/Cardano.CoinSelection.Algorithm.Migration/selectCoins properties/Total input UTxO value >= sum of selection change coins/"

Randomized with seed 1272323524

Finished in 4.5685 seconds
1 example, 1 failure

I haven't yet been able to reproduce this error with the version of the migration algorithm currently used by cardano-wallet.

[jonathanknowles]

In all the failures seen so far:

1. the set of change contains just a single value equal to the dust threshold.
2. the RequireMinimalFee policy is in effect. (But that could be a coincidence.)

This section of code might be relevant (it creates a starting change set with the dust threshold as its sole element):

    mkCoinSelection :: [CoinMapEntry i] -> CoinSelection i o
    mkCoinSelection inps = CoinSelection
        { inputs = coinMapFromList inps
        , outputs = mempty
        , change =
            let chgs = mapMaybe (noDust . entryValue) inps
            in if null chgs then [threshold] else chgs
        }

https://github.com/input-output-hk/cardano-coin-selection/blob/master/src/library/Cardano/CoinSelection/Algorithm/Migration.hs#L115-L122

[jonathanknowles]

In all the cases found by QuickCheck, the UTxO has a single input, where the value of that input is lower than the dust threshold.

I experimented with adding a simple guard to Migration.selectCoins of the form:

selectCoins options (BatchSize batchSize) utxo
    | coinMapValue utxo < unDustThreshold dustThreshold = []
    | otherwise = evalState migrate (coinMapToList utxo)

However, QuickCheck rapidly finds a new counterexample:

  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 88612 tests and 6 shrinks):
         (DustThreshold (Coin 6),RequireMinimalFee)
         BatchSize 1
         CoinMap (fromList [(Wrapped {unwrap = TxIn {txinId = Hash "\RS\b\ESC\NAK\t\NUL\DC4\ENQ\ENQ\SYN\ETB\ENQ\SUB\US\NUL\FS\n\b\NAK\ESC\DLE\DC4\SO\NAK\f\CAN\NUL\ACK\ETX\DC1\NAK\DC3", txinIx = 2}},Coin 3),(Wrapped {unwrap = TxIn {txinId = Hash "\US\STX\DC1\DC1\SO\EM\f\v\CAN\ETB\RS\FS\a\EM\NAK\EOT\f\RS\ETX\GS\US\a\v\SO\ETX\RS\b\a\US\US\STX\RS", txinIx = 1}},Coin 11072)])
         Selections: [CoinSelection {inputs = CoinMap (fromList [(Wrapped {unwrap = TxIn {txinId = Hash "\RS\b\ESC\NAK\t\NUL\DC4\ENQ\ENQ\SYN\ETB\ENQ\SUB\US\NUL\FS\n\b\NAK\ESC\DLE\DC4\SO\NAK\f\CAN\NUL\ACK\ETX\DC1\NAK\DC3", txinIx = 2}},Coin 3)]), outputs = CoinMap (fromList []), change = [Coin 6]},CoinSelection {inputs = CoinMap (fromList [(Wrapped {unwrap = TxIn {txinId = Hash "\US\STX\DC1\DC1\SO\EM\f\v\CAN\ETB\RS\FS\a\EM\NAK\EOT\f\RS\ETX\GS\US\a\v\SO\ETX\RS\b\a\US\US\STX\RS", txinIx = 1}},Coin 11072)]), outputs = CoinMap (fromList []), change = [Coin 11072]}]
         Total UTxO balance: Coin 11075
         Total change balance: Coin 11078

In the above counterexample:

• UTxO = {3, 11072}
• Batch size = 1
• Dust threshold = 6
• Generated Selections:
  • Selection 1: change = {6} <-- Note that 3 has been replaced by the dust threshold.
  • Selection 2: change = {11072}