Turns out, this is a really hard problem (the "subset sum problem"). But I think we can really simplify it to the point that, well, it isn't that hard of a problem.

1. Denominate on Sync

All coins should always be denominated by default. Mixing denom and non-denom is really difficult - as in approaching O(2^n) difficult.

2. Calc by mdash value, not sat value

{
  "satoshis": 837422585,
  "value": 837400000,
  "stamps": 112,
  "dust": 185
}

A payment request for 8.37422585 is instead calculated (and sent) as a request for 8.375, using Math.ceil().

3. XPub / Multi-Address Send

Sent to multiple addresses by default. Error if not enough addresses can be generated.

8.375 becomes

where each coin also has many unseen transaction "stamps".

(tending towards just 1.7 coins per digit with a mostly even distribution, but less with the natural distribution - 10.99+tax, or 15 for a sale)

digit	coins	#
9	5, 2, 2	3
8	5, 2, 1	3
7	5, 2	2
6	5, 1	2
5	5	1
4	2, 2	2
3	2, 1	2
2	2	1
1	1	1
0	-	0

17 coins / 10 digits = 1.7 coins per digit

It's okay if change comes back by these means. It will be difficult to tell which is the change.

4. Single Address Send

We can send multiple coins to a single address if absolutely necessary.

5. Exact Send to a single address

This is tricky because we may want to include the stamp values as part of the calculation rather than rolling over (since they all get donated to the network anyway).

A request for 8.37422585 should be calculated as 8.374:

5.000, s*13
2.000, s*13
1.000, s*12
0.200, s*13
0.100, s*12
0.050, s*12
0.020, s*13
0.002, s*12
0.002, s*12

But if the stamp values fail to meet the target + fees, then it should be calculated as 8.375:

5.000, s*14
2.000, s*14
1.000, s*14
0.200, s*14
0.100, s*14
0.050, s*14
0.020, s*14
0.005, s*14

Interim Selection Algorithm

We need to tend away from creating a surplus number of rarely useful tiny coins.

Ceiling the value: 1.73300001 => 1.734
Break into coins: 1, 0.5, 0.2, 0.02, 0.01, 0.02, 0.02
Find inputs less than or equal to the total value: 1.734
Pick the input that can be fully spent, which has the most coins in common
If none, pick a larger value and break change (donate up to 0.002 to avoid change)
Repeat at 3 until the value is < 0.

Alternate

Ceiling the value: 1.73300001 => 1.734
Break into coins: 1, 0.5, 0.2, 0.02, 0.01, 0.02, 0.02
Find the smallest inputs that will match completely, but prefer more filled slots per coin.
If the selection would return change, but the total is less than the target, try to get coins fewer by using the largest value and filling in the missing bits.

Distance

There also needs to be some sort of weight - how many coins it would take to make up the change between a coin and a target value

Value	Distance from 1
50	5
20	4
10	3
5	2
2	1
1	0
0.5	1
0.2	4
0.1	9
-	-
1.5	1
1.55	2
1.559	5

I don't know if that's even quite right, but something like that should help us identify whether a certain coin is worth trying to aggregate. We'd want to use up coins that are closer to the target value before coins that are further away.

Example: Paying 1.734

Inputs:

1.299
1.125 => 1, 0.1, 0.02, 0.005
//1.002
//1.001  => 1.000, 0.001
0.711
0.5
0.234 => 0.2, 0.02, 0.01, 0.02. 0.02
0.2
0.2
0.1
0.02
0.02
0.005
0.002
0.001

Slightly over output, no change (3 coins total, or 3+1 to keep change):

1.001
0.5
0.234

Well over output, with change (3+3 coins):

1.125 => 1 (0.1, 0.02, 0.005)
0.5
0.234

2nd pass, but too much change (6+3 or 6+4): \ (I like this because it uses a tiny coin)

1.125 => 1.0, 0.02 (0.1, 0.005)
0.5
0.2
0.02
0.02 (0.01)
0.005 (0.001)

3rd pass, breaking change of change (5+4 or 5+3):

1.125 => 1.0, 0.02 (0.1, 0.005)
0.5
0.2
0.02
0.02 (0.05, 0.001)

dashhive / DashWallet.js

doc: How to Denominate #41