Knapsack solver
Le 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.
Algorithme historique de Bitcoin Core
Le knapsack solver est un algorithme de coin selection longtemps utilisé par Bitcoin Core. Il cherche un sous-ensemble d'UTXO dont la somme couvre le montant cible avec le moins de change possible.
Inspiration et limites
Le nom évoque le célèbre problème du sac à dos en informatique. L'algorithme procède par itérations aléatoires et garde la meilleure solution rencontrée. Il fonctionne mais ne minimise pas toujours frais et confidentialité.
Branch and Bound et alternatives
Bitcoin Core utilise désormais en priorité l'algorithme Branch and Bound, plus performant pour trouver des solutions sans change. Le knapsack reste un fallback dans certains cas.
Impact sur la confidentialité
Le choix de coin selection influence ce qu'un observateur peut déduire. Un knapsack mal calibré peut produire des transactions qui révèlent involontairement la stratégie du wallet.
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.
- Branch-and-BoundBranch-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.
Glossaire inspire du dictionnaire de Loic Morel sur Pandul.fr.