Muitas carteiras de bitcoin ao escolher moedas para enviar preferem usar uma moeda grande, cujo saldo é maior que o valor enviado. Após cada transação, uma moeda de troca é formada. Depois de algum tempo, toda a carteira está cheia de moedas da ordem de 0,001 (~ US $ 10 no momento), nas quais não há mais nada para gastar. Quando, mais uma vez, precisei fazer uma transação, ocorreu-me se era possível montar a transação para que não houvesse alterações. A carteira teimosamente se ofereceu para "cortar" outra moeda maior, então decidi pegar moedas com as mãos para coletar a quantia necessária. No entanto, isso acabou não sendo tão simples: a soma acabou sendo menor que o valor desejado ou o excedeu demais. Como resultado, decidi que deveria haver um algoritmo com o qual você pudesse coletar a quantidade desejada de moedas ou um pouco mais. Aconteceu que isso não é apenas possível, mas funciona tão bem que me fez escrever este artigo. Mas as primeiras coisas primeiro.
Problema com mochila
O problema da mochila é amplamente conhecido: colocar o máximo de coisas valiosas possível em uma mochila, desde que a capacidade da mochila seja limitada. Nesse caso, temos o caso do problema da mochila 0-1 , pois cada item (moeda) está disponível para embalagem na mochila apenas uma vez. Além disso, o peso de cada "item" coincide com o seu valor, por isso estamos lidando com um caso ainda mais especial, o problema da soma dos subconjuntos . A Wikipedia sugere o uso de um algoritmo genético, mas decidi procurar uma solução exata usando programação dinâmica, pois isso é bastante possível em termos de recursos e parece simples.
Para reduzir o problema de escolher moedas para a tarefa de uma mochila, você precisa fazer uma pequena conversão dos dados de entrada. O fato é que resolver o problema da mochila (mais precisamente, a soma dos subconjuntos) nos dará um subconjunto do conjunto original com uma quantidade máxima que não excede o parâmetro (capacidade de transporte da mochila). Mas não estamos satisfeitos com a combinação de moedas, fornecendo a quantia menor que a quantia que queremos enviar. No entanto, estamos confortáveis com combinações ligeiramente superiores. Por exemplo, se precisarmos enviar 0,005 bitcoins e encontrarmos uma combinação que dê 0,00499, será inútil para nós, pois é menor que a quantidade que o vendedor deseja. Mas se encontrarmos 0,005001, está certo. O satoshiki extra pode ser usado como uma comissão (falaremos sobre isso em detalhes abaixo) ou entregá-lo ao vendedor se ele permitir o envio de uma quantia maior. Portanto, com a ajuda do problema da mochila, precisamos escolher não as moedas que precisam ser enviadas , mas as que precisam ser deixadas . Então a "escassez" ao máximo se transformará em "falência" em termos do problema original.
Um exemplo Suponha que tenhamos essas moedas: 0,1 BTC, 0,002 BTC, 0,00832423 BTC. E precisamos enviar 0,01 BTC. Nós encontraremos essas moedas, cuja quantidade será máxima, mas menor ou igual à quantidade total de nossas moedas menos a quantidade enviada, ou seja, esse número: 0,1 + 0,002 + 0,00832423 - 0,01 = 0,110032423. Nesse caso, uma pesquisa simples descobre que é uma moeda de 0,1. Deixamos, o que significa que enviamos o restante: 0,002 BTC e 0,00832423 BTC, que no total dão 0,01032423 BTC, que é mais de 0,01 BTC e nos convém. (É verdade que a comissão saiu em torno de US $ 3, mas digamos que a rede esteja ocupada e queremos fazer o envio o mais rápido possível.)
Comissões
Para levar em conta as taxas de transação, modifiquei cada moeda de entrada, reduzindo seu saldo pelo valor que teria que ser pago pela sua inclusão na transação como entrada. Isso pode ser feito sabendo o tamanho da entrada e a comissão (por exemplo, 2 satoshi por byte). Além disso, modifiquei o valor a ser enviado, acrescentando o preço da parte da transação que não depende das moedas selecionadas: título e saída (ões). O usuário pode especificar todos esses parâmetros usando sinalizadores. Você também pode desativar o ajuste para comissões em geral, especificando uma comissão de 0 Satoshi por byte.
Peguei informações sobre os tamanhos de entradas e saídas em diferentes versões de endereços (clássico, segwit empacotado e segwit nativo a partir daqui: https://bitcoin.stackexchange.com/a/84006
Algoritmos e implementação
Abandonei imediatamente o algoritmo genético, talvez em vão. Focado em algoritmos precisos. Minha primeira tentativa foi realizar uma busca exaustiva de todas as combinações, mas mesmo com 40 moedas funcionou por horas e teve que abandoná-la. Então eu tentei a programação dinâmica sugerida na Wikipedia . Nele, você não pode manter na memória toda a matriz, mas apenas as linhas atuais e anteriores. Além disso, não precisamos armazenar o valor, pois ele coincide com o peso e é o número da coluna. Mas precisamos lembrar a combinação - decidi armazená-la na forma de um bitset. Além disso, você pode armazenar apenas uma linha, construindo a próxima linha no local a partir dela. Cada registro de linha diferente de zero permanece em seu lugar e é copiado (com a adição do bit correspondente) para outra célula em um determinado número de células à direita (se ele estivesse vazio antes). Se você for na ordem inversa, classificando através da célula na qual o "salto" vai, poderá preencher tudo corretamente:
Cada célula diferente de zero na linha atual gera na própria linha seguinte e outra célula para um determinado número de células (igual ao valor da moeda adicionada) à direita. Se essa célula já tiver um valor, a opção com o maior número de moedas selecionadas (ou seja, não incluídas na transação) ganha "ganha", pois queremos enviar o mínimo de moedas possível, outras coisas iguais.
Em uma célula, gasto 8 bytes para um conjunto de bits, e o número de células é igual ao número possível de saldos de 0 à quantidade de moedas menos a quantidade enviada. Por exemplo, se houver apenas 1 bitcoin na carteira e 0,1 for enviado, haverá 100'000'000-10'000'000 = 90'000'000 células, cada uma com 8 bytes, ou seja, 720 megabytes - um pouco para um computador moderno. Se o número de moedas for menor que 32, seria possível usar 4 bytes por moeda, mas não o otimizei. Além disso, se houver mais de 64 moedas, o programa não funcionará - isso também teria que ser corrigido criando um conjunto de bits de comprimento arbitrário. Por fim, você pode descartar o último sinal da balança, perdendo um pouco de precisão, mas ganhando 10 vezes na memória. Mas até agora isso serve.
Chamei o programa de imutável e o coloquei no gitlab: gitlab.com/starius/changeless . Está escrito em Go, montado usando go get , como de costume. Binários para Linux, Windows, Mac , coletados no IC estão disponíveis.
Quando lancei o programa com moedas reais, fiquei impressionado com a precisão com que ela pegou a combinação necessária. Quando o número de moedas é grande, quase qualquer quantia proporcional aos saldos das moedas pode ser selecionada com precisão até satoshi! Você altera a quantidade necessária para 1 satoshi e o programa fornece uma combinação completamente diferente de moedas exatamente para essa quantidade. Abaixo está um exemplo de trabalho em 50 moedas aleatórias com saldos de 0 a 1 bitcoin.
$ 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).
O programa conseguiu pegar combinações de moedas para enviar exatamente 10 bitcoins e exatamente 10.00000001 bitcoins (10 bitcoins e 1 satoshi). Para ver isso, você deve subtrair a comissão da quantidade de moedas: 10.00004651 - 0.00004651 = 10, 10.00004652 - 0.00004651 = 10.00000001.
Como obter uma lista de saldos de moedas
Para o programa Electrum, encontrei este caminho (comando do console):
' '.join((x["value"]) for x in listunspent())
Se você deseja excluir determinadas moedas, por exemplo, em um determinado endereço, isso pode ser feito assim:
' '.join((x["value"]) for x in listunspent() if x["address"] != "bad address")
Para outras carteiras, não achei uma maneira tão fácil e tive que digitá-la novamente com as mãos.