Branch-and-Bound
Branch-and-Bound est l'algorithme de sélection de pièces par défaut de Bitcoin Core depuis 0.17. Il cherche un sous-ensemble d'UTXO sans change. Améliore confidentialité et coût. Fallback Knapsack si pas de solution exacte.
Le problème de la sélection d'UTXO
Quand un wallet construit une transaction, il doit choisir parmi ses UTXO un sous-ensemble dont la somme couvre le montant à envoyer plus les frais. Mauvais choix = output de change inutile, fuite de confidentialité, frais élevés. C'est un problème NP-difficile : le « subset sum problem ». Toute la qualité d'un wallet se joue ici, même si l'utilisateur ne le voit pas.
L'algorithme Branch-and-Bound
Proposé par Mark Erhardt en 2016, intégré à Bitcoin Core en version 0.17 (octobre 2018), Branch-and-Bound (BnB) explore l'espace des combinaisons d'UTXO via un parcours arborescent. À chaque nœud de l'arbre, l'algorithme décide d'inclure ou non un UTXO, et élague (« bound ») les branches qui ne peuvent plus aboutir à une solution acceptable. L'objectif : trouver un sous-ensemble dont la somme tombe exactement dans la fenêtre [montant_cible ; montant_cible + cost_of_change], ce qui permet d'éviter la création d'un output de change.
Pourquoi éviter le change
Un output de change est un signal très exploitable par les chaînalystes :
- Heuristique du change : « le plus petit output non rond est souvent le change »
- Heuristique du type d'adresse : le change reprend souvent le même script type que les inputs
- Réutilisation : les wallets paresseux réutilisent une adresse change
En supprimant le change, on casse ces heuristiques et on réduit la taille de la transaction, donc les frais.
Fallback Knapsack puis SRD
Si BnB ne trouve aucune combinaison exacte dans le budget de calcul alloué, Bitcoin Core retombe sur le Knapsack solver, un algorithme aléatoire plus ancien. Depuis Core 22.0, un troisième algorithme appelé SRD (Single Random Draw) s'est ajouté, qui pioche des UTXO au hasard jusqu'à dépasser la cible. Bitcoin Core choisit ensuite la meilleure des trois solutions selon une métrique de score (effective value, anonymity set).
| Algorithme | Optimise | Fallback | |------------|----------|----------| | Branch-and-Bound | Exact match sans change | Si trouvé | | Knapsack | Combinaisons aléatoires | Si BnB échoue | | SRD | Tirage aléatoire pur | Comparé avec les autres |
Limites
BnB échoue souvent quand le wallet contient peu d'UTXO ou des montants très inégaux. Il est aussi sensible au paramètre cost_of_change qui dépend du fee rate : à fee élevé, Core acceptera plus volontiers de payer un peu plus pour éviter un output supplémentaire. Sparrow et Wasabi implémentent leurs propres variantes optimisées pour la privacy.
À retenir
Branch-and-Bound est le moteur silencieux qui rend les transactions Bitcoin plus privées et moins chères. C'est un bel exemple de progrès invisible à l'utilisateur mais aux effets cumulés énormes pour l'écosystème.
Termes lies
- Sélection des piècesLa sélection des pièces (coin selection) est l'algorithme qui choisit les UTXO à dépenser. Branch-and-Bound, Knapsack ou Single-random-draw sont les principaux. Influence frais et confidentialité. À paramétrer selon les priorités utilisateur.
- Knapsack solverLe Knapsack solver est un algorithme historique de sélection de pièces de Bitcoin Core. Il choisit aléatoirement plusieurs combinaisons et garde la meilleure. Encore utilisé en fallback. Moins efficace que Branch-and-Bound.
- Change avoidanceLe change avoidance consiste à éviter de produire un output de change quand c'est possible. Permet une meilleure confidentialité (heuristique de change cassée). Implémenté par Branch-and-Bound dans Bitcoin Core. Fonctionne uniquement quand un input correspond exactement.
Glossaire inspire du dictionnaire de Loic Morel sur Pandul.fr.