De nombreux portefeuilles Bitcoin lors du choix des pièces à envoyer préfèrent utiliser une grande pièce, dont le solde est supérieur au montant envoyé. Après chacune de ces transactions, une pièce de monnaie de change est formée. Après un certain temps, le portefeuille entier est envahi par de telles pièces de l'ordre de 0,001 (~ 10 $ pour le moment), sur lesquelles il n'y a déjà rien à dépenser. Lorsque, une fois de plus, j'ai eu besoin de faire une transaction, il m'est venu à l'esprit s'il était possible de monter la transaction afin qu'il n'y ait pas de changement. Le portefeuille a obstinément proposé de "couper" une autre pièce plus grande, j'ai donc décidé de choisir des pièces avec mes mains pour collecter le montant nécessaire. Cependant, cela ne s'est pas avéré si simple: la somme s'est avérée inférieure à la valeur souhaitée ou l'a dépassée trop. En conséquence, j'ai décidé qu'il devrait y avoir un algorithme avec lequel vous pouvez collecter le montant souhaité des pièces ou un peu plus. Il s'est avéré que ce n'est pas seulement possible, mais fonctionne si bien que m'a fait écrire cet article. Mais tout d'abord.
Problème de sac à dos
Le problème du sac à dos est largement connu: emballer autant d'objets de valeur que possible dans un sac à dos, à condition que la capacité du sac à dos soit limitée. Dans ce cas, nous avons le cas du problème de sac à dos 0-1 , car chaque article (pièce) n'est disponible pour être emballé dans le sac à dos qu'une seule fois. De plus, le poids de chaque «élément» coïncide avec sa valeur, nous avons donc affaire à un cas encore plus spécial, le problème de la somme des sous-ensembles . Wikipédia suggère d'utiliser un algorithme génétique, mais j'ai décidé de chercher une solution exacte en utilisant la programmation dynamique, car cela est tout à fait réalisable en termes de ressources et semble simple.
Pour réduire le problème du choix des pièces à la tâche d'un sac à dos, vous devez effectuer une petite conversion des données d'entrée. Le fait est que la résolution du problème du sac à dos (plus précisément, la somme des sous-ensembles) nous donnera un sous-ensemble de l'ensemble d'origine qui a une quantité maximale ne dépassant pas le paramètre (capacité de charge du sac à dos). Mais nous ne sommes pas satisfaits de la combinaison de pièces, ce qui donne un montant inférieur au montant que nous voulons envoyer. Cependant, nous sommes à l'aise avec des combinaisons légèrement supérieures. Par exemple, si nous devons envoyer 0,005 bitcoins et que nous avons trouvé une combinaison qui donne 0,00499, cela nous est inutile, car il est inférieur au montant souhaité par le vendeur. Mais si nous trouvons 0,005001, c'est vrai. Extra satoshiki peut être utilisé comme une commission (nous en parlerons en détail ci-dessous) ou le donner au vendeur s'il permet d'envoyer un montant plus important. Par conséquent, avec l'aide du problème du sac à dos, nous devons choisir non pas les pièces qui doivent être envoyées , mais celles qui doivent être laissées . Ensuite, la "pénurie" au maximum se transformera en "buste" en termes de problème d'origine.
Un exemple. Supposons que nous ayons de telles pièces: 0,1 BTC, 0,002 BTC, 0,00832423 BTC. Et nous devons envoyer 0,01 BTC. Nous trouverons de telles pièces, dont la somme sera maximale, mais inférieure ou égale au montant total de nos pièces moins le montant envoyé, c'est-à-dire un tel nombre: 0,1 + 0,002 + 0,00832423 - 0,01 = 0,10032423. Dans ce cas, une simple recherche révèle qu'il s'agit d'une pièce de 0,1. Nous le laissons, ce qui signifie que nous envoyons le reste: 0,002 BTC et 0,00832423 BTC, ce qui donne au total 0,01032423 BTC, ce qui est supérieur à 0,01 BTC et nous convient. (Certes, la commission est sortie à environ 3 $, mais disons que le réseau est occupé et que nous voulons rendre l'envoi aussi rapide que possible.)
Les commissions
Pour tenir compte des frais de transaction, j'ai modifié chaque pièce d'entrée, réduisant son solde du montant qui devrait être payé pour son inclusion dans la transaction en tant qu'entrée. Cela peut être fait en connaissant la taille de l'entrée et la commission (par exemple, 2 satoshi par octet). De plus, j'ai modifié le montant à envoyer, en y ajoutant le prix de la partie de la transaction qui ne dépend pas des pièces sélectionnées: rubrique et sortie (s). L'utilisateur peut spécifier tous ces paramètres à l'aide de drapeaux. Vous pouvez également désactiver l'ajustement pour les commissions en général en spécifiant une commission de 0 Satoshi par octet.
J'ai pris des informations sur les tailles des entrées et des sorties dans différentes versions d'adresses (segwit classique, enveloppé et segwit natif d'ici: https://bitcoin.stackexchange.com/a/84006
Algorithmes et implémentation
J'ai immédiatement abandonné l'algorithme génétique, peut-être en vain. Concentré sur des algorithmes précis. Ma première tentative a été de réaliser à travers une recherche exhaustive de toutes les combinaisons, mais même sur 40 pièces, cela a fonctionné pendant des heures et a dû l'abandonner. J'ai ensuite essayé la programmation dynamique proposée sur Wikipédia . Dans ce document, vous ne pouvez pas garder en mémoire la matrice entière, mais uniquement les lignes actuelles et précédentes. De plus, nous n'avons pas besoin de stocker la valeur, car elle coïncide avec le poids et est le numéro de colonne. Mais nous devons nous souvenir de la combinaison - j'ai décidé de la stocker sous la forme d'un jeu de bits. De plus, vous ne pouvez stocker qu'une seule ligne, en créant la ligne suivante en place. Chaque enregistrement de ligne non nul reste à sa place et est copié (avec l'ajout du bit correspondant) dans une autre cellule un certain nombre de cellules à droite (s'il y était vide auparavant). Si vous allez dans l'ordre inverse, en triant la cellule dans laquelle va le «saut», vous pouvez tout remplir correctement:
Chaque cellule non nulle de la ligne actuelle génère dans la ligne suivante elle-même et une autre cellule pour un certain nombre de cellules (égal à la valeur de la pièce ajoutée) à droite. S'il y a déjà une valeur dans cette cellule, alors l'option avec le plus grand nombre de pièces sélectionnées (c'est-à-dire non incluses dans la transaction) «gagne», car nous voulons envoyer le moins de pièces possible, toutes choses étant égales par ailleurs.
Sur une cellule, je dépense 8 octets pour un jeu de bits, et le nombre de cellules est égal au nombre possible de soldes de 0 au montant des pièces moins le montant envoyé. Par exemple, s'il n'y a qu'un bitcoin dans le portefeuille et que 0,1 est envoyé, alors il y aura 100'000'000-10'000'000 = 90'000'000 cellules, chacune de 8 octets, soit 720 mégaoctets - un peu pour un ordinateur moderne. Si le nombre de pièces est inférieur à 32, il serait alors possible d'utiliser 4 octets par pièce, mais je ne l'ai pas optimisé. De plus, s'il y a plus de 64 pièces, le programme ne fonctionne pas - cela devrait également être corrigé en créant un jeu de bits de longueur arbitraire. Enfin, vous pouvez défausser le dernier signe des soldes, perdant un peu de précision, mais gagnant 10 fois en mémoire. Mais jusqu'à présent, cela suffira.
J'ai appelé le programme immuable et l'ai placé sur le gitlab: gitlab.com/starius/changeless . Il est écrit en Go, assemblé en utilisant go get , comme d'habitude. Les binaires pour Linux, Windows, Mac , collectés dans CI sont disponibles.
Lorsque j'ai lancé le programme avec de vraies pièces, j'ai été étonné de la précision avec laquelle elle a choisi la combinaison nécessaire. Lorsque le nombre de pièces est élevé, presque n'importe quel montant proportionnel aux soldes des pièces peut être sélectionné avec précision jusqu'à satoshi! Vous modifiez le montant requis pour 1 satoshi et le programme donne une combinaison complètement différente de pièces exactement pour ce montant. Vous trouverez ci-dessous un exemple de travail sur 50 pièces aléatoires avec des soldes de 0 à 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).
Le programme a réussi à ramasser des combinaisons de pièces pour envoyer exactement 10 bitcoins et exactement 10.00000001 bitcoins (10 bitcoins et 1 satoshi). Pour voir cela, vous devez soustraire la commission du montant des pièces: 10.00004651 - 0.00004651 = 10, 10.00004652 - 0.00004651 = 10.00000001.
Comment obtenir une liste des soldes de pièces
Pour le programme Electrum, j'ai trouvé cette façon (commande console):
' '.join((x["value"]) for x in listunspent())
Si vous souhaitez exclure certaines pièces, par exemple à une certaine adresse, cela peut être fait comme ceci:
' '.join((x["value"]) for x in listunspent() if x["address"] != "bad address")
Pour les autres portefeuilles, je n'ai pas trouvé un moyen aussi simple et j'ai dû le retaper avec mes mains.