Sélection des pièces

Définition

La sélection des pièces (coin selection) est le processus algorithmique par lequel un wallet Bitcoin choisit quels UTXO parmi tous ceux qu'il contrôle utiliser comme inputs pour construire une nouvelle transaction. C'est un problème d'optimisation combinatoire similaire au problème du sac à dos : trouver un sous-ensemble dont la somme couvre le montant à payer plus les frais, idéalement avec le moins de change possible.

Pourquoi c'est important

Le choix des UTXO influence directement trois propriétés :

1. Frais payés : moins d'inputs = transaction plus petite = moins de frais.
2. Confidentialité : combiner plusieurs UTXO révèle qu'ils appartiennent au même propriétaire (heuristique du "common-input-ownership").
3. Empreinte UTXO future : un change "trop arrondi" ou "trop précis" peut fuiter la valeur de paiement.

Un mauvais algorithme peut payer 50 % de frais en plus, ou détruire la confidentialité d'années de séparation soigneuse.

Principaux algorithmes

| Algorithme | Optimise | Inconvénient | |------------|----------|--------------| | Branch and Bound (Murch, 2016) | "Changeless" (zéro change) | Échoue si pas de match exact | | Single Random Draw (SRD) | Simplicité, privacy moyenne | Sélection sub-optimale | | Knapsack solver (Bitcoin Core historique) | Pseudo-aléa | Vieux, biais détectables | | Largest First | Réduire frais | Concentration des fonds | | Smallest First / FIFO | "Used coins" | Inputs nombreux, frais élevés | | Privacy-focused (random + filter) | Anonset | Moins économe |

Bitcoin Core actuel utilise une combinaison de Branch-and-Bound puis SRD en fallback, avec un score qui pondère ces critères.

Branch and Bound : le standard

L'algorithme Branch and Bound de Murch (2016) parcourt l'arbre des sous-ensembles possibles et coupe ("bound") les branches qui ne peuvent pas mener à une transaction sans change ou avec un change minimal. Résultat : on obtient souvent une transaction zero-change, qui :

• Ne révèle pas le montant exact du paiement (pas de change identifiable).
• Économise un output (~30-40 octets).
• Brise l'heuristique "round-change" qui distingue paiement de change.

L'effet sur la confidentialité

Considérons un wallet avec :

• UTXO_A : 0.5 BTC (acheté sur Kraken, lié à votre identité).
• UTXO_B : 0.3 BTC (gagné sur Mining Pool, anonyme).

Si vous devez payer 0.6 BTC et que le wallet sélectionne A + B, vous venez de prouver que A et B sont contrôlés par la même entité. C'est pourquoi des wallets privacy-focused (Wasabi historique, Joinmarket, Sparrow avec coin control activé) permettent de sélectionner manuellement les UTXO, et de regrouper par "labels" pour éviter les croisements.

Le rôle du change

Tout reliquat d'une transaction crée un nouvel UTXO de change, normalement vers une adresse fraîche du même wallet. Mais le change est analysable :

• Heuristique de "round payment" : si l'output non-arrondi est 0.6 BTC et l'autre 0.07452 BTC, le second est probablement le change.
• Heuristique de "script type" : si le payeur est P2WPKH et un output est P2WPKH, l'autre P2TR, le P2WPKH est probablement le change.

À retenir

La sélection des pièces est l'un de ces détails techniques invisibles qui font la différence entre un wallet pédagogiquement correct et un wallet réellement utile. Pour un usage privacy-conscious, le coin control manuel reste l'option la plus robuste face aux algorithmes automatiques.