User:Gmaxwell/coin selection

Improved coin selection would lower user transaction fees, speed up transaction processing for users, improve user privacy, reduce blockchain bloat and/or any mixture of these positive results.

The reference client uses a heuristic subset-sum knapsack solver to try to minimize transaction size. It is fee blind, though its run multiple times excluding less confirmed coins which may sometimes help avoid fees if there are many larger inputs available and minimizing sizes helps with fees (but does not guarantee low fees). Minimizing the current transaction size also does nothing to reduce the amount of data a pruning bitcoin node needs to keep around, in fact it usually does the opposite.

Optimal coin selection is generally a mixed-interger non-linear program. These kinds of problems are often NP-complete, though there are heuristic-based solvers which can usually find excellent solutions quickly.

In these problems most of constraints are linear but the fee calculation is non-linear because the use of an input both contributes the transaction's coins-days-destroyed as well as increases the transaction size.

The problem of fee/priority-blind coin selection can have entirely linear constraints and so should achieve good (or exact) solutions through basic MIP techniques like branch/bound/cut[1].

Below is an example AMPL[2] input which can be used with solvers like Bonmin[3] to find good coin selections.

AMPL program

This program finds a zero fee mixture of inputs which _minimizes_ the priority, subject to being zero-fee and meeting the required output and not making a txn which is excessively large or has more than a maximum amount of change. By minimizing the priority we avoid burning priority excessively, resulting in paying more fees in the future. The minimizing process also tends to sweep the wallet of small inputs as a side effect.

set coins ordered;

param f_min {coins} >= 0, default 0;
param f_max {j in coins} >= f_min[j], default 1;

param value {coins} >= 0;
param age {coins} >= 0;
param sigsz {coins} >= 0;

param target >= 0;
param target_max >= 0;
param thresh_prio >= 0;
param max_outputs >= 0, default Infinity;
param min_out >= 0;
param basesz >= 0;

# --------------------------------------------------------

var Use {j in coins} integer >= f_min[j], <= f_max[j];

# --------------------------------------------------------

minimize priority: sum {j in coins} value[j] * age[j] * Use[j]
                     / (basesz+(sum {i in coins} sigsz[i] * Use[i]));

# --------------------------------------------------------

subject to Free:
   thresh_prio <=  sum {j in coins} value[j] * age[j] * Use[j]
                     / (basesz+(sum {i in coins} sigsz[i] * Use[i]));

subject to Enough:
   target <= sum {j in coins} value[j] * Use[j];

subject to NotTooMuch:
   target_max >= sum {j in coins} value[j] * Use[j];

subject to size:
   max_outputs >= sum {j in coins} Use[j];

subject to NoDustChange:
   min_out <= sum {j in coins} value[j] * Use[j]
                - target;

#subject to NoChange:
#    target = sum {j in coins} value[j] * Use[j];

Example AMPL problem data

If there are multiple identical inputs they should be only put in once and given a fmax equal to the number of duplicates.

param target      := 150000000;
param target_max  := 500000000;
param thresh_prio := 100;
param min_out     := 1000000;
param max_outputs := 100;
param basesz      := 100;

param:  coins:                  value       age  sigsz f_min  f_max :=
  "aaaa"                    100000001         1   100      .      .  
  "aaab"                     50000000     20000   100      .      .  
  "aaac"                    100000000         2    50      .      .  
  "aaad"                            1         1   100      .      . ;