Line data    Source code

       1              : library coin_selection;
       2              : 
       3              : import 'dart:math';
       4              : 
       5              : ///
       6              : /// https://murch.one/wp-content/uploads/2016/11/erhardt2016coinselection.pdf
       7              : ///
       8              : 
       9              : import 'package:walletkit_dart/src/domain/exceptions.dart';
      10              : import 'package:walletkit_dart/walletkit_dart.dart';
      11              : 
      12              : const kMinInputs = 2;
      13              : 
      14            1 : List<ElectrumOutput> singleRandomDrawUTXOSelection(
      15              :   List<ElectrumOutput> utxos,
      16              :   BigInt targetAmount,
      17              : ) {
      18            1 :   List<ElectrumOutput> selectedUTXOs = [];
      19            1 :   BigInt selectedAmount = BigInt.zero;
      20            1 :   Random random = Random();
      21              : 
      22              :   // try to use at least 2 UTXOs if possible
      23            1 :   while (selectedAmount < targetAmount ||
      24            3 :       (selectedUTXOs.length < kMinInputs && utxos.isNotEmpty)) {
      25            1 :     if (utxos.isEmpty) {
      26            0 :       throw SendFailure('Insufficient UTXOs to reach the target amount');
      27              :     }
      28              : 
      29              :     // Randomly select a UTXO and remove it from the available list.
      30            2 :     int randomIndex = random.nextInt(utxos.length);
      31            1 :     ElectrumOutput selectedUTXO = utxos.removeAt(randomIndex);
      32              : 
      33              :     // Add the chosen UTXO to the selected list and update the selected amount.
      34            1 :     selectedUTXOs.add(selectedUTXO);
      35            2 :     selectedAmount += selectedUTXO.value;
      36              :   }
      37              :   return selectedUTXOs;
      38              : }
      39              : 
      40            1 : List<ElectrumOutput> smallestFirstUTXOSelection(
      41              :   List<ElectrumOutput> utxos,
      42              :   BigInt targetAmount,
      43              : ) {
      44              :   // Sort UTXOs by value, smallest first.
      45            5 :   utxos.sort((a, b) => a.value.compareTo(b.value));
      46              : 
      47            1 :   List<ElectrumOutput> selectedUTXOs = [];
      48            1 :   BigInt selectedAmount = BigInt.zero;
      49              : 
      50            2 :   for (ElectrumOutput utxo in utxos) {
      51            1 :     selectedUTXOs.add(utxo);
      52            2 :     selectedAmount += utxo.value;
      53              : 
      54            1 :     if (selectedAmount >= targetAmount) {
      55              :       break;
      56              :     }
      57              :   }
      58              : 
      59            1 :   if (selectedAmount < targetAmount) {
      60            0 :     throw Exception('Insufficient UTXOs to reach the target amount');
      61              :   }
      62              : 
      63              :   return selectedUTXOs;
      64              : }
      65              : 
      66              : ///
      67              : /// FIFO: TODO: Get blockheigt information for each Input
      68              : ///
      69              : // List<Input> fifoUTXOSelection(List<Input> utxos, int targetAmount) {
      70              : //   // Sort UTXOs by block height, older first.
      71              : //   utxos.sort((a, b) => a.blockHeight.compareTo(b.blockHeight));
      72              : 
      73              : //   List<Input> selectedUTXOs = [];
      74              : //   int selectedAmount = 0;
      75              : 
      76              : //   for (Input utxo in utxos) {
      77              : //     selectedUTXOs.add(utxo);
      78              : //     selectedAmount += utxo.vout;
      79              : 
      80              : //     if (selectedAmount >= targetAmount) {
      81              : //       break;
      82              : //     }
      83              : //   }
      84              : 
      85              : //   if (selectedAmount < targetAmount) {
      86              : //     throw Exception('Insufficient UTXOs to reach the target amount');
      87              : //   }
      88              : 
      89              : //   return selectedUTXOs;
      90              : // }
      91              : 
      92              : ///
      93              : ///
      94              : ///
      95            0 : List<ElectrumOutput> fillUpToTargetAmount(
      96              :   List<ElectrumOutput> alreadyUsedUTXOs,
      97              :   List<ElectrumOutput> utxos,
      98              :   BigInt targetAmount,
      99              : ) {
     100            0 :   List<ElectrumOutput> selectedUTXOs = [...alreadyUsedUTXOs];
     101            0 :   BigInt selectedAmount = selectedUTXOs.fold(
     102            0 :     BigInt.zero,
     103            0 :     (preV, utxo) => preV + utxo.value,
     104              :   );
     105              : 
     106              :   /// Remove already used UTXOs from the available list.
     107            0 :   utxos.removeWhere((element) => alreadyUsedUTXOs.contains(element));
     108              : 
     109              :   // try to use at least 2 UTXOs if possible
     110            0 :   while (selectedAmount < targetAmount ||
     111            0 :       (selectedUTXOs.length < kMinInputs && utxos.isNotEmpty)) {
     112            0 :     if (utxos.isEmpty) {
     113            0 :       throw SendFailure(
     114            0 :         'Insufficient UTXOs for Fee + Target Amount ($targetAmount)',
     115              :       );
     116              :     }
     117              : 
     118            0 :     final max = utxos.reduce(
     119            0 :       (value, element) => value.value > element.value ? value : element,
     120              :     );
     121              : 
     122            0 :     utxos.remove(max);
     123              : 
     124              :     // Add the chosen UTXO to the selected list and update the selected amount.
     125            0 :     selectedUTXOs.add(max);
     126            0 :     selectedAmount += max.value;
     127              :   }
     128              :   return selectedUTXOs;
     129              : }