Pathfinding

Le problème

Sur le Lightning Network, un paiement entre Alice et Bob passe par une chaîne de canaux intermédiaires. Pour qu'il aboutisse, le wallet d'Alice doit trouver une route qui :

• relie effectivement Alice à Bob
• a assez de liquidité dans la bonne direction sur chaque saut
• minimise les frais et la latence

Aucun annuaire central n'existe : chaque nœud doit calculer la route à partir de sa connaissance locale du graphe. C'est un problème de plus court chemin dans un graphe partiellement observable.

Les données disponibles

Le wallet construit son graphe local à partir du protocole de gossip Lightning (BOLT-7) :

• Tous les canaux publics sont annoncés : channel_announcement.
• Les politiques de frais et timelock sont mises à jour : channel_update.
• Les nœuds s'annoncent : node_announcement.

En 2025, le graphe Lightning compte environ 15 000 nœuds publics et 50 000 canaux publics, soit ~50 Mo de données.

Algorithmes

Les principaux clients utilisent des variantes de Dijkstra modifié, pondéré par un coût composite :

coût d'un saut = frais + risque * timelock + pénalité d'échec

Quelques implémentations notables :

| Implémentation | Algorithme | Particularité | |----------------|------------|---------------| | LND | Dijkstra modifié | Apprentissage des échecs (mission control) | | CLN | Dijkstra | Plugins (clboss, csflow) | | Eclair | Yen's k-shortest paths | Multi-route parallèle | | LDK | Dijkstra heuristique | Optimisé pour mobile |

Le défi de la liquidité cachée

La grosse difficulté : on ne sait pas combien de liquidité a chaque côté d'un canal. Le canal annonce sa capacité totale (par exemple 1 BTC), mais pas son solde 700k/300k qui change à chaque paiement.

Conséquence : un wallet doit essayer une route, encaisser les échecs et apprendre. C'est ce que LND appelle mission control : un journal local des canaux fiables/défaillants.

Stratégies modernes

• Multi-Path Payments (MPP) : diviser un gros paiement en plusieurs petits empruntant des routes différentes.
• AMP (Atomic Multipath Payments) : variante qui supprime le besoin de connaître la facture avant la division.
• Trampoline routing : déléguer le calcul de route à un nœud trampoline.
• Probing : envoyer des paiements fictifs (sans preimage) pour mesurer la liquidité d'une route.

Latence et UX

Un pathfinding lent dégrade l'UX : un utilisateur ne supporte pas 10 secondes pour payer un café. Les wallets mobiles utilisent souvent :

• Rapid Gossip Sync (RGS) pour ingestion rapide du graphe
• Trampoline pour éviter de stocker tout le graphe
• Channel hints fournis par l'invoice BOLT-11

Limites

• Canaux privés invisibles dans le graphe public (mais inclus comme hints dans l'invoice).
• Liquidité dynamique : la situation change à chaque paiement.
• Confidentialité : observer les échecs permet d'inférer la topologie.

À retenir

Le pathfinding est le cœur algorithmique de Lightning. Il transforme un graphe incomplet et évolutif en une route de paiement viable, en quelques centaines de millisecondes. C'est là que se joue 90 % de l'UX Lightning et c'est encore un domaine de R&D actif.