I need to select best bitcoin transaction combination for sending. I achieved result using PHP, but it uses a lot of memory and there is huge possibility that database will handle that better.
Whole list of transactions:
+------------------+------+--------+
| Transaction ID | Vout | Amount |
+------------------+------+--------+
| transactionid1 | 0 | 10 |
| transactionid1 | 1 | 1.5 |
| transactionid2 | 0 | 0.5 |
| transactionid3 | 0 | 0.7 |
+------------------+------+--------+
I need to create some kind of function or select query which will return me following row when i provide amount = 0.4
+------------------+------+--------+
| Transaction ID | Vout | Amount |
+------------------+------+--------+
| transactionid2 | 0 | 0.5 |
+------------------+------+--------+
When i provide amount = 2.1
+------------------+------+--------+
| Transaction ID | Vout | Amount |
+------------------+------+--------+
| transactionid1 | 1 | 1.5 |
| transactionid3 | 0 | 0.7 |
+------------------+------+--------+
So it's kind of Knapsack problem with leftover. Here is how i resolved my problem using combinatorics. I've flatten transaction data into $key => $value array, where $key is transactionid_vout and value is amount.
$flatterTransactions = array(4) ( [transactionid1_0] => (int) 10 [transactionid1_1] => (float) 1.5 [transactionid2_0] => (float) 0.5 [transactionid3_0] => (float) 0.7 )
Then i create combinations from that transactions
$combinations = array(15) (
[0] => Array
(
[transactionid1_0] => 10
)
[1] => Array
(
[transactionid1_1] => 1.5
)
[2] => Array
(
[transactionid2_0] => 0.5
)
[3] => Array
(
[transactionid3_0] => 0.7
)
[4] => Array
(
[transactionid1_0] => 10
[transactionid1_1] => 1.5
)
[5] => Array
(
[transactionid1_0] => 10
[transactionid2_0] => 0.5
)
[6] => Array
(
[transactionid1_0] => 10
[transactionid3_0] => 0.7
)
[7] => Array
(
[transactionid1_1] => 1.5
[transactionid2_0] => 0.5
)
[8] => Array
(
[transactionid1_1] => 1.5
[transactionid3_0] => 0.7
)
[9] => Array
(
[transactionid2_0] => 0.5
[transactionid3_0] => 0.7
)
[10] => Array
(
[transactionid1_0] => 10
[transactionid1_1] => 1.5
[transactionid2_0] => 0.5
)
[11] => Array
(
[transactionid1_0] => 10
[transactionid1_1] => 1.5
[transactionid3_0] => 0.7
)
[12] => Array
(
[transactionid1_0] => 10
[transactionid2_0] => 0.5
[transactionid3_0] => 0.7
)
[13] => Array
(
[transactionid1_1] => 1.5
[transactionid2_0] => 0.5
[transactionid3_0] => 0.7
)
[14] => Array
(
[transactionid1_0] => 10
[transactionid1_1] => 1.5
[transactionid2_0] => 0.5
[transactionid3_0] => 0.7
)
)
Then i go through combinations and create summed combination array with scoring. Scoring goal here is to use less transactions.
$summedCombinations[$key] = array(
'sum' => $sum,
'count' => count($combination),
'score' => $sum * (count($combination) * 2)
);
After all i filter array by sum field to leave only transactions which cover my amount. Order by score and receiving best match.
Best is a bit problematic here, but here's how I would go about it. No matter how you do it, you have to deal with an algorithm for selecting the combination.
WITH target AS (select ? as target),
RECURSIVE largest_txs AS (
select transaction_id, vout, amount, amount as running_total
from transactions
CROSS JOIN target
where amount < target.target
order by amount desc limit 1
UNION ALL
SELECT t.transaction_id, t.vout, t.amount, t.amount + l.running_total
FROM transactions
JOIN (select * from largest_txs order by amount asc limit 1) l
CROSS JOIN target
WHERE amount < target.target + l.running_total AND t.transaction_id NOT IN
(select transaction_id from largest_txs)
)
SELECT transaction_id, vout, amount, running_total FROM largest_txs
UNION
SELECT t.transaction_id, t.vout, t.amount, null
FROM transactions t
WHERE t.transaction_id NOT IN (select transaction_id from largest_txs)
ORDER BY amount asc limit 1;
This should perform as well as can be expected. You will definitely want an index on amount if the table gets to be of any size though.