Многие кошельки биткоина при выборе монет для отправки предпочитают использовать крупную монету, баланс которой больше отправляемой суммы. После каждой такой транзакции образуется монета-сдача. Через какое-то время весь кошелёк зарастает такими монетами порядка 0.001 (~10 долларов на текущий момент), которые уже и не на что потратить. Когда в очередной раз мне понадобилось сделать транзакцию, мне пришла в голову мысль, а нельзя ли собрать транзакцию так, чтобы сдачи не было. Кошелёк упрямо предлагал «распилить» ещё одну более крупную монету, так что я решил руками выбрать монеты, чтобы насобирать необходимую сумму. Однако это оказалось не так просто: сумма или получалась меньше нужного значения или слишком сильно его превосходила. В итоге я решил, что должен быть алгоритм, с помощью которого из монет можно собрать нужную сумму или чуть больше. Оказалось, что это не только возможно, но работает настолько хорошо, что сподвигло меня написать эту статью. Но обо всём по порядку.
Задача о рюкзаке
Широко известна задача о рюкзаке: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. В данном случае мы имеем случай задачи о рюкзаке 0-1, так как каждый предмет (монета) доступен для укладки в рюкзак всего один раз. Кроме того, вес каждого «предмета» совпадает с его стоимостью, поэтому мы имеем дело с ещё более частным случаем, задачей о сумме подмножеств. В википедии предлагается использовать генетический алгоритм, однако я решил искать точное решение с помощью динамического программирования, так как это вполне достижимо по ресурсам и выглядит просто.
Чтобы свести задачу о выборе монет к задаче о рюкзаке, надо совершить небольшое преобразование входных данных. Дело в том, что решение задачи о ранце (точнее, о сумме подмножеств) даст нам подмножество исходного множества, обладающее максимальной суммой, не превосходящей параметр (грузоподъёмность рюкзака). А нас не устраивают комбинации монет, дающие сумму меньше того количества, которое мы хотим отправить. Однако нас устраивают комбинации, слегка превосходящие. К примеру, если нам нужно отправить 0.005 биткоина, а мы нашли комбинацию, дающую 0.00499, то нам она бесполезна, так как меньше суммы, которую хочет продавец. А вот если мы найдём 0.005001, это подходит. Лишние сатошики можно использовать в качестве комиссии (о ней подробно поговорим ниже) или подарить продавцу, если он допускает отправку большей суммы. Поэтому нам надо с помощью задачи о рюкзаке выбирать не те монеты, которые надо отправить, а те, которые надо оставить. Тогда «недобор» до максимума превратится в «перебор» в терминах исходной задачи.
Пример. Допустим, у нас есть такие монеты: 0.1 BTC, 0.002 BTC, 0.00832423 BTC. А отправить нам надо 0.01 BTC. Найдём такие монеты, сумма которых будет будет максимальна, но меньше или равна общей сумме наших монет минус отправляемая сумма, то есть вот такого числа: 0.1 + 0.002 + 0.00832423 — 0.01 = 0.10032423. В данном случае простым перебором находим, что это монета 0.1. Её мы оставляем, а значит отправляем остальные: 0.002 BTC и 0.00832423 BTC, которые в сумме дают 0.01032423 BTC, что больше 0.01 BTC и нас устраивает. (Правда, комиссия вышла примерно 3 доллара, но, допустим, что сеть загружена и мы хотим сделать отправку как можно быстрее.)
Комиссии
Чтобы учесть комиссии за транзакцию, я модифицировал каждую входную монету, уменьшив её баланс на сумму, которую придётся выложить за её включение в транзакцию в качестве входа. Это можно сделать, зная размер входа и комиссию (например 2 сатоши за байт). Кроме того, я модифировал отправляемую сумму, приплюсовав к ней цену части транзакции, не зависящей от выбранных монет: заголовка и выхода(ов). Все эти параметры пользователь может указывать с помощью флагов. Также можно отключить поправку на комиссии вообще, указав комиссию 0 сатоши за байт.
Информацию о размерах входов и выходов в разных версиях адресов (классические, обёрнутый segwit и нативный segwit) я взял отсюда: https://bitcoin.stackexchange.com/a/84006
Алгоритмы и реализация
Генетический алгоритм я сразу отбросил, может и зря. Сосредоточился на точных алгоритмах. Первой моей попыткой была реализация через полный перебор всех комбинаций, но даже на 40 монетах он работал часами и пришлось отказаться от него. Затем я попробовал динамическое программирование, предложенное в википедии. В нём можно не держать в памяти всю матрицу, а только текущий и предыдущий ряды. Кроме того, нам не нужно хранить ценность, так как она совпадает с весом и является номером столбца. Зато нам нужно помнить комбинацию — её я решил хранить в виде битсета. Кроме того, можно хранить всего один ряд, строя из него следующий ряд in-place. Каждая ненулевая запись ряда остаётся на своём месте и копируется (с добавлением соответствующего бита) в другую ячейку на определённое число ячеек правее (если там до этого было пусто). Если идти в обратном порядке, перебирая ячейку, в которую идёт «прыжок», то можно всё правильно заполнить:
Каждая ненулевая ячейка в текущем ряду порождает в следующем ряду себя же и ещё одну ячейку на определённое число ячеек (равное достоинству добавляемой монеты) правее. Если в той ячейке уже есть значение, то «побеждает» вариант с наибольшим количеством выбранных (то есть не включённых в транзакцию) монет, так как мы хотим при прочих равных отправить как можно меньше монет.
На одну ячейку я трачу 8 байт под битсет, а число ячеек равно возможному количеству балансов от 0 до суммы монет минус отправляемая сумма. К примеру если в кошельке всего 1 биткоин, а отправляется 0.1, то будет 100'000'000-10'000'000 = 90'000'000 ячеек, каждая по 8 байт, то есть 720 мегабайт — немного для современного компьютера. Если число монет меньше 32, то можно было бы использовать по 4 байта на монету, но я не стал это оптимизировать. Кроме того, если монет больше, чем 64, то программа не работает — это тоже надо бы исправить, сделав битсет произвольной длины. Наконец можно отбросить последний знак в балансах, потеряв немного в точности, но выиграв в 10 раз в памяти. Но пока и так сойдёт.
Программу я назвал changeless и разместил на гитлабе: gitlab.com/starius/changeless. Написана она на Go, собирается с помощью go get, как обычно. Доступны бинарники для Linux, Windows, Mac, собранные в CI.
Когда я запустил программу с реальными монетами, я был поражён, как точно она подобрала необходимую комбинацию. Когда число монет большое, практически любую сумму, соразмерную балансам монет, можно подобрать с точностью вплоть до сатоши! Меняешь требуемую сумму на 1 сатоши и программы выдаёт совершенно другую комбинацию монет точно под эту сумму. Ниже пример работы на 50 случайных монетах с балансами от 0 до 1 биткоина.
$ cat coins50.txt
0.01331611 0.03906237 0.04847086 0.08453118 0.09748168
0.10395389 0.10619825 0.12156721 0.12923149 0.13587973
0.14798976 0.16053788 0.19011834 0.21570038 0.21946913
0.31861430 0.33435508 0.33718842 0.33789473 0.35976748
0.37360122 0.44944553 0.47572926 0.49927495 0.50992142
0.53062326 0.53079433 0.53542072 0.54715225 0.55019714
0.55313907 0.56656642 0.56673333 0.65879650 0.66228482
0.68424322 0.70436496 0.75638055 0.79095597 0.82438005
0.83684407 0.85151564 0.86862948 0.90054250 0.90239402
0.91636213 0.93087757 0.93579251 0.97207439 0.98248384
$ changeless -amount 10.00000000 -coins coins50.txt
Processing item 50/50.
0.09748168 + 0.33435508 + 0.47572926 + 0.53542072 + 0.66228482 +
0.70436496 + 0.75638055 + 0.82438005 + 0.9005425 + 0.90239402 +
0.91636213 + 0.93579251 + 0.97207439 + 0.98248384 = 10.00004651
Tx size: 2118 vBytes. Total fees: 0.00004651 BTC (2.2 sats/vByte).
$ changeless -amount 10.00000001 -coins coins50.txt
Processing item 50/50.
0.01331611 + 0.09748168 + 0.53079433 + 0.56656642 + 0.70436496 +
0.75638055 + 0.82438005 + 0.86862948 + 0.9005425 + 0.91636213 +
0.93087757 + 0.93579251 + 0.97207439 + 0.98248384 = 10.00004652
Tx size: 2118 vBytes. Total fees: 0.00004651 BTC (2.2 sats/vByte).Программа сумела подобрать комбинации монет для отправки ровно 10 биткоинов и ровно 10.00000001 биткоинов (10 биткоинов и 1 сатоши). Чтобы это увидеть, надо вычесть из суммы монет комиссии: 10.00004651 — 0.00004651 = 10, 10.00004652 — 0.00004651 = 10.00000001.
Как получить список балансов монет
Для программы Electrum я нашёл такой способ (команда консоли):
' '.join((x["value"]) for x in listunspent())Если хочется исключить определённые монеты, например на определённом адресе, то это можно сделать так:
' '.join((x["value"]) for x in listunspent() if x["address"] != "bad address")Для других кошельков я такого простого способа не нашёл и пришлось перепечатывать руками.
