Хабрахабр

Как сделать BTC-транзакцию без сдачи из мелких монет

Задача: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена

После каждой такой транзакции образуется монета-сдача. Многие кошельки биткоина при выборе монет для отправки предпочитают использовать крупную монету, баланс которой больше отправляемой суммы. 001 (~10 долларов на текущий момент), которые уже и не на что потратить. Через какое-то время весь кошелёк зарастает такими монетами порядка 0. Кошелёк упрямо предлагал «распилить» ещё одну более крупную монету, так что я решил руками выбрать монеты, чтобы насобирать необходимую сумму. Когда в очередной раз мне понадобилось сделать транзакцию, мне пришла в голову мысль, а нельзя ли собрать транзакцию так, чтобы сдачи не было. В итоге я решил, что должен быть алгоритм, с помощью которого из монет можно собрать нужную сумму или чуть больше. Однако это оказалось не так просто: сумма или получалась меньше нужного значения или слишком сильно его превосходила. Но обо всём по порядку. Оказалось, что это не только возможно, но работает настолько хорошо, что сподвигло меня написать эту статью.

Задача о рюкзаке

В данном случае мы имеем случай задачи о рюкзаке 0-1, так как каждый предмет (монета) доступен для укладки в рюкзак всего один раз. Широко известна задача о рюкзаке: уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость рюкзака ограничена. В википедии предлагается использовать генетический алгоритм, однако я решил искать точное решение с помощью динамического программирования, так как это вполне достижимо по ресурсам и выглядит просто. Кроме того, вес каждого «предмета» совпадает с его стоимостью, поэтому мы имеем дело с ещё более частным случаем, задачей о сумме подмножеств.

Дело в том, что решение задачи о ранце (точнее, о сумме подмножеств) даст нам подмножество исходного множества, обладающее максимальной суммой, не превосходящей параметр (грузоподъёмность рюкзака). Чтобы свести задачу о выборе монет к задаче о рюкзаке, надо совершить небольшое преобразование входных данных. Однако нас устраивают комбинации, слегка превосходящие. А нас не устраивают комбинации монет, дающие сумму меньше того количества, которое мы хотим отправить. 005 биткоина, а мы нашли комбинацию, дающую 0. К примеру, если нам нужно отправить 0. А вот если мы найдём 0. 00499, то нам она бесполезна, так как меньше суммы, которую хочет продавец. Лишние сатошики можно использовать в качестве комиссии (о ней подробно поговорим ниже) или подарить продавцу, если он допускает отправку большей суммы. 005001, это подходит. Тогда «недобор» до максимума превратится в «перебор» в терминах исходной задачи. Поэтому нам надо с помощью задачи о рюкзаке выбирать не те монеты, которые надо отправить, а те, которые надо оставить.

Автоматический и ручной выбор монет для отправки

Допустим, у нас есть такие монеты: 0. Пример. 002 BTC, 0. 1 BTC, 0. А отправить нам надо 0. 00832423 BTC. Найдём такие монеты, сумма которых будет будет максимальна, но меньше или равна общей сумме наших монет минус отправляемая сумма, то есть вот такого числа: 0. 01 BTC. 002 + 0. 1 + 0. 01 = 0. 00832423 — 0. В данном случае простым перебором находим, что это монета 0. 10032423. Её мы оставляем, а значит отправляем остальные: 0. 1. 00832423 BTC, которые в сумме дают 0. 002 BTC и 0. 01 BTC и нас устраивает. 01032423 BTC, что больше 0. (Правда, комиссия вышла примерно 3 доллара, но, допустим, что сеть загружена и мы хотим сделать отправку как можно быстрее.)

Комиссии

Это можно сделать, зная размер входа и комиссию (например 2 сатоши за байт). Чтобы учесть комиссии за транзакцию, я модифицировал каждую входную монету, уменьшив её баланс на сумму, которую придётся выложить за её включение в транзакцию в качестве входа. Все эти параметры пользователь может указывать с помощью флагов. Кроме того, я модифировал отправляемую сумму, приплюсовав к ней цену части транзакции, не зависящей от выбранных монет: заголовка и выхода(ов). Также можно отключить поправку на комиссии вообще, указав комиссию 0 сатоши за байт.

Информацию о размерах входов и выходов в разных версиях адресов (классические, обёрнутый segwit и нативный segwit) я взял отсюда: https://bitcoin.stackexchange.com/a/84006

Алгоритмы и реализация

Сосредоточился на точных алгоритмах. Генетический алгоритм я сразу отбросил, может и зря. Затем я попробовал динамическое программирование, предложенное в википедии. Первой моей попыткой была реализация через полный перебор всех комбинаций, но даже на 40 монетах он работал часами и пришлось отказаться от него. Кроме того, нам не нужно хранить ценность, так как она совпадает с весом и является номером столбца. В нём можно не держать в памяти всю матрицу, а только текущий и предыдущий ряды. Кроме того, можно хранить всего один ряд, строя из него следующий ряд in-place. Зато нам нужно помнить комбинацию — её я решил хранить в виде битсета. Если идти в обратном порядке, перебирая ячейку, в которую идёт «прыжок», то можно всё правильно заполнить: Каждая ненулевая запись ряда остаётся на своём месте и копируется (с добавлением соответствующего бита) в другую ячейку на определённое число ячеек правее (если там до этого было пусто).

Если в той ячейке уже есть значение, то «побеждает» вариант с наибольшим количеством выбранных (то есть не включённых в транзакцию) монет, так как мы хотим при прочих равных отправить как можно меньше монет. Иллюстрация перехода к следующему ряду, то есть добавление ещё одной монеты к динамическому программированию
Каждая ненулевая ячейка в текущем ряду порождает в следующем ряду себя же и ещё одну ячейку на определённое число ячеек (равное достоинству добавляемой монеты) правее.

К примеру если в кошельке всего 1 биткоин, а отправляется 0. На одну ячейку я трачу 8 байт под битсет, а число ячеек равно возможному количеству балансов от 0 до суммы монет минус отправляемая сумма. Если число монет меньше 32, то можно было бы использовать по 4 байта на монету, но я не стал это оптимизировать. 1, то будет 100'000'000-10'000'000 = 90'000'000 ячеек, каждая по 8 байт, то есть 720 мегабайт — немного для современного компьютера. Наконец можно отбросить последний знак в балансах, потеряв немного в точности, но выиграв в 10 раз в памяти. Кроме того, если монет больше, чем 64, то программа не работает — это тоже надо бы исправить, сделав битсет произвольной длины. Но пока и так сойдёт.

Написана она на Go, собирается с помощью go get, как обычно. Программу я назвал changeless и разместил на гитлабе: gitlab.com/starius/changeless. Доступны бинарники для Linux, Windows, Mac, собранные в CI.

Когда число монет большое, практически любую сумму, соразмерную балансам монет, можно подобрать с точностью вплоть до сатоши! Когда я запустил программу с реальными монетами, я был поражён, как точно она подобрала необходимую комбинацию. Ниже пример работы на 50 случайных монетах с балансами от 0 до 1 биткоина. Меняешь требуемую сумму на 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).

00000001 биткоинов (10 биткоинов и 1 сатоши). Программа сумела подобрать комбинации монет для отправки ровно 10 биткоинов и ровно 10. 00004651 — 0. Чтобы это увидеть, надо вычесть из суммы монет комиссии: 10. 00004652 — 0. 00004651 = 10, 10. 00000001. 00004651 = 10.

Как получить список балансов монет

Для программы Electrum я нашёл такой способ (команда консоли):

' '.join((x["value"]) for x in listunspent())

Если хочется исключить определённые монеты, например на определённом адресе, то это можно сделать так:

' '.join((x["value"]) for x in listunspent() if x["address"] != "bad address")

Для других кошельков я такого простого способа не нашёл и пришлось перепечатывать руками.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть