Каков алгоритм выбора монет?

Я нигде не мог найти записанные результаты выбора монет и только что собрал их по кусочкам из кода. Это работает, как упомянул Дэвид , но здесь подробнее.

Логика алгоритма выбора монет для перевода Целевой суммы

1. Если какой-либо из ваших UTXO ² соответствует Target¹, он будет использован.
2. Если «сумма всех ваших UTXO меньше, чем цель» совпадает с целью, они будут использоваться. (Это в том случае, если вы подметаете полный кошелек.)
3. Если «сумма всех ваших UTXO меньше целевого значения» не превышает целевого значения, будет использоваться наименьшее значение UTXO, превышающее целевое значение.

4. В противном случае Bitcoin Core выполняет 1000 раундов случайного объединения неизрасходованных выходов транзакций, пока их сумма не станет больше или равна цели. Если случается найти точное совпадение, он останавливается раньше и использует его.
   В противном случае он, наконец, соглашается на минимум

   • наименьший UTXO больше, чем цель
   • наименьшая комбинация UTXO, обнаруженная на шаге 4.

Как упомянул Дэвид, проблема подмножества сначала ограничивается UTXO, у которых есть хотя бы одно подтверждение, если оно отправлено вами, или шесть подтверждений, если оно получено из другого кошелька, а затем ослабляет эти требования за два дополнительных прохода, если не может быть обнаружен подходящий набор UTXO. .

Некоторые примеры

У Алисы четыре UTXO:
• UTXO_A 0,1 BTC
• UTXO_B 0,3 BTC
• UTXO_C 0,5 BTC
• UTXO_D 1 BTC

Я буду игнорировать комиссии за транзакции для простоты.

Пример 1:

Алиса хочет отправить 0,3 BTC .
Bitcoin Core обнаруживает, что UTXO_B соответствует цели, и использует только UTXO_B в качестве входных данных.

Пример 2:

Алиса хочет отправить 0,4 BTC .
Bitcoin Core считает, что UTXO_C — это наименьший UTXO, превышающий цель, и что сумма всех UTXO меньше цели (т . е UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4. ) соответствует здесь цели. И UTXO_A, и UTXO_B используются в качестве входов.

Пример 3:

Алиса хочет отправить 0,45 BTC .
Bitcoin Core считает, что UTXO_C — это наименьший UTXO, превышающий цель, и что сумма всех UTXO меньше цели (т . е UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4. ) не превосходит цель. UTXO_C используется как единственный вход, являясь следующим наименьшим входом, большим, чем Target.

Пример 4:

Алиса хочет отправить 0,35 BTC .
Bitcoin Core обнаруживает, что UTXO_C — это наименьший UTXO, превышающий цель, и что сумма всех UTXO меньше цели (т . е UTXO_A + UTXO_B = 0.1 + 0.3 = 0.4. ) не соответствует цели. Он суммирует случайно выбранные UTXO 1000 раз, пока они не превзойдут Target, запоминая наименьшую достаточную комбинацию. Затем наименьшая достаточная комбинация сравнивается с наименьшим единичным входом, превышающим целевое значение. Предполагая, что он находит здесь наилучшую комбинацию, которая будет равна UTXO_A + UTXO_B, он находит ее Target < UTXO_A + UTXO_B < UTXO_Cи использует UTXO_A и UTXO_B в качестве входных данных.

Пример 5:

Алиса хочет отправить 0,6 BTC .
Bitcoin Core обнаруживает, что UTXO_D — это наименьший UTXO, превышающий цель, и что сумма всех UTXO меньше цели (т . е UTXO_A + UTXO_B + UTXO_C = 0.1 + 0.3 + 0.5 = 0.9. ) не соответствует цели. Он по-прежнему начинает пробовать случайные комбинации и в этой ситуации, вероятно, обнаружит, что UTXO_A + UTXO_C = Target. Как только он находит комбинацию, которая соответствует Цели, он ломается и сразу же идет с этой комбинацией. UTXO_A и UTXO_C используются как входы.

¹ _{«Цель» используется здесь для обозначения суммы, которую нужно потратить.}
² _{UTXO = вывод неизрасходованных транзакций}

Да, это именно то, что делает клиент. Для этого он использует эвристику, решая задачу подмножества/суммы или рюкзака.

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

Обратите внимание, что учитываются все монеты в вашем кошельке. В модели учета, которую использует биткойн-клиент, определенные монеты не принадлежат конкретным счетам.

Если вы хотите проверить код самостоятельно, ищите SelectCoinsв wallet.cpp.