dépenses : Quels sont les compromis entre les différents algorithmes pour décider quels UTXO dépenser ?


Le défi pour choisir un algorithme de sélection de pièces est qu’il y a plusieurs objectifs à optimiser pour  :

Intimité

Le comportement par défaut d’un portefeuille doit être raisonnablement propice à la confidentialité financière des utilisateurs. La sélection de pièces doit révéler le moins possible sur le contenu du portefeuille. Les portefeuilles doivent éviter de lier trop d’adresses, ne pas révéler de fonds excessifs lorsqu’ils ne sont pas nécessaires, minimiser les modèles et les empreintes digitales discernables, mais également conserver suffisamment d’UTXO pour répartir le solde. Les portefeuilles ne doivent jamais réutiliser les adresses.

Frais de transaction

La sélection de pièces doit viser à réduire les frais de transaction pour les transactions courantes, mais également à minimiser les frais de transaction totaux à long terme. Étant donné que chaque UTXO doit être dépensé en fin de compte, il peut parfois être opportun de dépenser plus d’UTXO à un tarif bas maintenant qu’à un tarif élevé plus tard.

dépenses : Quels sont les compromis entre les différents algorithmes pour décider quels UTXO dépenser ?

Mise en forme de piscine UTXO

La poussière doit toujours être évitée, mais généralement les petits UTXO auront un coût relatif important à des débits élevés. En règle générale, les portefeuilles ne doivent pas créer d’UTXO qui coûtent une part importante de leur valeur à des tarifs modérés. Visez que le changement soit d’au moins 20 à 50 000 sats (moins pour les petits scripts d’entrée, plus pour les gros scripts d’entrée).

Réduire la taille de l’ensemble UTXO

Tous les UTXO doivent être stockés sur chaque nœud complet, et tous les UTXO doivent être dépensés à terme. Un portefeuille doit conserver suffisamment d’UTXO pour maintenir la confidentialité financière, mais aussi peu que possible pour minimiser les futures données de blockchain, les frais et les coûts de stockage en cours sur chaque nœud complet.

Malheureusement, certains de ces objectifs sont antagoniques et, par conséquent, chaque solution doit trouver un équilibre approprié pour ses priorités.

Passons en revue certains des algorithmes les plus courants pour la sélection de pièces, ainsi que leurs avantages et leurs inconvénients.

  • Le plus ancien en premier (FIFO)
  • Le plus récent en premier (LIFO)
  • Le plus petit d’abord
  • Le plus grand en premier
  • Aléatoire
  • Sac à dos (utilisé par Bitcoin Core)
  • Branch and Bound (utilisé par Bitcoin Core)
  • Multi-algorithme (utilisé par Bitcoin Core)

Le plus ancien en premier (FIFO)

Choisissez les UTXO dans l’ordre décroissant du nombre de confirmations.

Bien

  • Consolidera éventuellement les petits UTXO au fur et à mesure de leur apparition
  • Les ensembles d’entrées sont représentatifs de la composition de votre pool UTXO, ni particulièrement petit ni grand
  • Passera le pool UTXO du portefeuille au nouveau format de sortie lorsqu’un nouveau type de sortie est adopté pour la réception
  • Passera ensemble des UTXO de la même période, ce qui peut réduire le mélange d’empreintes digitales en raison de différentes versions de logiciel

Mal

  • Donne une date pour le plus ancien UTXO du portefeuille, qui révèle par exemple depuis combien de temps un utilisateur utilise au moins ce portefeuille
  • Les valeurs et l’espacement du nombre de confirmations des UTXO peuvent être utilisés pour estimer le solde total du portefeuille
  • Les plages d’horodatage sur différentes transactions peuvent former un modèle en série permettant d’associer différentes transactions d’un même portefeuille et de lever l’ambiguïté d’autres portefeuilles utilisant le même logiciel (puisque les plages d’horodatage ne doivent jamais se chevaucher, sauf dans la dernière ou la première hauteur de confirmation)
  • Peut être utilisé pour déduire des informations sur un portefeuille en regardant quand une sortie connue est dépensée
  • Ne minimisera pas les frais de transaction

Le plus récent en premier (LIFO)

Choisissez d’abord les UTXO avec le plus petit nombre de confirmations.

Bien

  • La plupart des UTXO ont un petit graphique de transaction, ce qui peut être bénéfique pour la confidentialité
  • Les UTXO dépensés sont les plus proches en valeur d’acquisition de la valeur au moment de l’achat, ce qui entraîne le plus petit gain/perte effectif

Mal

  • Pratiquement aucune consolidation si les fonds du portefeuille augmentent avec le temps
  • Broie le dernier UTXO jusqu’à ce qu’un nouveau soit reçu ou qu’il soit épuisé. Il peut en résulter que le pool d’UTXO du portefeuille contient de nombreux petits UTXO
  • Combinera les graphiques de transactions étendus de plusieurs UTXO les plus jeunes lorsqu’un montant plus important est envoyé
  • Reliera toutes vos activités récentes en réutilisant toujours la sortie de modification la plus récente
  • Ne minimise pas les frais de transaction

Le plus petit d’abord

Choisissez les UTXO par ordre croissant de valeur.

Bien

  • Consolide les petits UTXO dès que possible, limitant le pool d’UTXO du portefeuille et minimisant les coûts de dépenses futurs

Mal

  • Révèle la limite inférieure des valeurs UTXO actuelles dans le portefeuille
  • Maximise les ensembles d’entrées, ce qui augmente les frais de transaction pour la transaction en cours
  • Tend à surconsolider le pool UXTO, réduisant la confidentialité financière
  • Relie de nombreuses adresses
  • Diminue la plage de valeur du pool UTXO du portefeuille

Le plus grand en premier

Choisissez les UTXO par ordre décroissant de valeur.

Bien

  • Frais de transaction minimes pour la transaction en cours
  • Liens quelques adresses
  • Susceptible de créer des résultats de changement importants

Mal

  • Révèle la limite supérieure de la valeur UTXO dans le portefeuille
  • Peut révéler que le portefeuille contient beaucoup plus de fonds que nécessaire pour effectuer le paiement en cours
  • Relie les transactions consécutives alors que la sortie de changement est toujours la plus grande UTXO
  • Diffère la consolidation des petits UTXO, maximisant les coûts futurs
  • Le pool UTXO du portefeuille Bloats (et l’ensemble UTXO global) car les dépenses d’un seul destinataire sont généralement de ± 0 sur le nombre de pools UTXO (moins une entrée, plus une sortie de changement), mais les transactions entrantes augmentent le pool UTXO

Aléatoire

Rédigez des UTXO avec une chance égale au hasard parmi tous ceux disponibles.

Bien

  • Les UTXO sélectionnés n’ont pas d’empreintes digitales cohérentes comme l’âge ou la valeur
  • Les ensembles d’entrées sont représentatifs de manière probabiliste de la composition du pool d’UTXO du portefeuille, devenant plus consolidants lorsque plus de petits UTXO sont présents
  • Facile à mettre en œuvre
  • Les quantités de sortie de changement aléatoire augmentent la diversité de valeur

Mal

  • Ne minimise pas les frais
  • Peut présenter des empreintes digitales au hasard, comme révéler des fonds beaucoup plus importants dans le portefeuille que nécessaire pour le paiement

Sac à dos (utilisé par Bitcoin Core)

Cet algorithme (qui ne résout d’ailleurs pas un problème de sac à dos) aborde la sélection de pièces en triant tous les UTXO par valeur et en exécutant 1000 itérations de sélections en choisissant au hasard des UTXO avec 50% de chances du plus grand au plus petit. Chaque fois qu’il dépasse la cible, il désélectionne le dernier UTXO inclus et continue avec des UTXO plus petits. L’algorithme est décrit de manière exhaustive dans Qu’est-ce que l’algorithme de sélection de pièces.

Bien

  • Produit une petite piscine UTXO
  • La sélection pseudo-aléatoire des UTXO révèle peu d’informations sur le portefeuille

Mal

  • Consolide de manière agressive les minuscules UTXO, y compris les sorties non économiques
  • Vise toujours des sorties de changement de 10 mBTC (empreintes digitales et inutilement grandes)
  • Avec beaucoup de petits UTXO dans votre portefeuille, susceptibles d’entraîner de gros frais de transaction
  • Calcul inutilement coûteux

Branch and Bound (utilisé par Bitcoin Core depuis la v0.17)

Recherchez de manière déterministe dans l’espace de combinaison du pool UTXO l’ensemble d’entrées évitant les modifications qui entraîne le moins de gaspillage. Puisqu’il n’y a pas toujours un ensemble d’entrées immuable, Bitcoin Core revient à l’approche « Knapsack » décrite ci-dessus dans ce cas.

Bien

  • Crée une sortie sans changement qui réduit les frais actuels, les frais futurs, réduit le graphique des transactions pour le portefeuille et a un effet de consolidation sur le pool UTXO du portefeuille
  • Utilise un ensemble minimal d’entrées parmi les candidats viables, réduisant ainsi les liens d’adresse et les frais
  • Les UTXO sélectionnés n’ont pas d’empreintes digitales cohérentes comme l’âge ou la valeur
  • Utilise plus d’intrants à des débits inférieurs et moins d’intrants à des débits plus élevés en raison de la mesure des déchets
  • Préfère dépenser des types de sortie moins efficaces en termes d’espace de bloc à des taux de frais inférieurs et des types de sortie plus efficaces à des taux de frais plus élevés en raison de la métrique de gaspillage

Mal

  • Ne produit pas toujours une solution
  • L’expéditeur ne peut pas CPFP car il n’y a pas de sortie de changement
  • Plus compliqué à mettre en œuvre et coûteux à calculer

Multi-algorithme (à utiliser par Bitcoin Core v23+)

La prochaine version après Bitcoin Core 22.0 exécutera la sélection de pièces Knapsack, Single Random Draw et Branch and Bound en parallèle, puis choisira parmi les trois candidats de l’ensemble d’entrées résultant celui qui obtiendra le meilleur score en fonction de l’heuristique de gaspillage, qui était auparavant déjà utilisée pour choisissez la meilleure solution Branch and Bound.

Bien

  • Dépense plus d’intrants à des tarifs bas, moins à des tarifs élevés, ce qui réduit les frais totaux
  • Consolide les petits intrants lorsque cela est économiquement raisonnable
  • Étant donné que les ensembles d’entrées proviennent de plusieurs approches, les modèles sont plus difficiles à identifier
  • Évite souvent le changement, améliore la confidentialité, les frais et réduit les liens

Mal

  • Complexe à mettre en œuvre et à tester
  • Calcul intensif à calculer
  • Utilise toujours un changement minimum assez élevé de 10 mBTC (lorsque le changement est produit)

Mise à jour en novembre 2021  :

  • Supprimer l’utilisation ambiguë du terme « poussière »
  • Réécriture complète pour mettre à jour ma compréhension actuelle
  • Ajoutez Random Selection, Branch and Bound et l’approche multi-algorithme de Bitcoin Core

Mise à jour en 2021  :

  • Suppression de quelques allusions à Coin Age Priority en tant que politique de sélection des transactions dans la construction de blocs qui a été supprimée dans Bitcoin Core 0.12.0 en 2016
  • Suppression de l’allégation erronée selon laquelle dépenser plusieurs entrées à partir de la même adresse est moins cher

Notez que Bitcoin Core a utilisé le solveur Knapsack comme seul algorithme jusqu’en 2017, mais a depuis ajouté un algorithme amélioré proposé par l’auteur de cette réponse.

Mise à jour en 2014  :

J’ai cherché à trouver un meilleur algorithme de sélection de pièces, mais je n’en ai pas encore trouvé qui améliore considérablement l’algorithme de sélection du client principal.

Voici quelques idées pour l’améliorer :

  • Lorsqu’un UTXO est sélectionné au hasard, ajoutez également tous les autres UTXO associés à la même adresse : moins de liaisons de transactions améliore la confidentialité, consolide potentiellement les UTXO en moins
  • Au lieu de sélectionner le plus petit changement, on pourrait viser à créer un changement de la même ampleur que l’objectif de dépenses. En supposant que les gens envoient principalement des montants utiles, cela créerait de nouveaux UTXO de valeur utile au lieu des plus petits changements possibles comme c’est le cas actuellement. Cela rend également plus difficile de deviner quel était le changement et quel était le paiement
  • Sélectionnez UTXO défini pour minimiser les frais de transaction, au lieu de minimiser la sortie des modifications