Quando viene effettuato un pagamento sulla rete Lightning Network, il pagamento deve attraversare uno o più canali dal nodo del mittente del pagamento a quello del destinatario.

La ricerca del percorso dal mittente al destinatario è un processo chiamato Pathfinding. Poiché l'instradamento viene effettuato dal mittente, quest'ultimo deve trovare un percorso adeguato per raggiungere la destinazione.

Pathfinding (la ricerca del percorso), path selection (la selezione del percorso), MPP multipart payments (i pagamenti multiparte) e il ciclo di tentativi di pagamento per tentativi ed errori occupano la maggior parte del livello di pagamento nella parte superiore della suite del protocollo Lightning.

Il termine pathfinding può essere un po' fuorviante, perché suggerisce che venga ricercato un unico percorso che colleghi due nodi.

Se il mittente e il destinatario sono collegati ad altri nodi ben connessi e dispongono di almeno un canale con capacità adeguata, ci saranno migliaia di percorsi. Il problema diventa selezionare il percorso migliore che riuscirà a consegnare il pagamento, tra migliaia di percorsi possibili.

Per selezionare il percorso migliore, dobbiamo innanzitutto definire cosa intendiamo per "migliore".

I criteri possono essere molti e diversi, come ad esempio:

• Percorsi con sufficiente liquidità. Ovviamente, se un percorso non ha abbastanza liquidità per instradare il nostro pagamento, non è un percorso adatto.
• Percorsi con fee basse. Se abbiamo diversi candidati, potremmo voler selezionare quelli con fee più basse.
• Percorsi con timelock brevi. Potremmo voler evitare di bloccare i nostri fondi per troppo tempo e quindi selezionare percorsi con timelock più brevi.

Non c'è certezza sul bilanciamento dei canali: se conoscessimo gli esatti balance di ogni canale, potremmo calcolare uno o più percorsi di pagamento usando uno qualsiasi degli algoritmi standard di pathfinding. Ma non conosciamo i balance dei canali; conosciamo solo la capacità aggregata dei canali, che viene comunicata dai nodi. Affinché un pagamento abbia successo, deve esserci un balance adeguato sul lato di invio del canale. Se non sappiamo come è distribuita la capacità tra i partner del canale, non sappiamo se c'è un balance sufficiente nella direzione in cui stiamo cercando di inviare il pagamento.

I balance non vengono annunciati negli aggiornamenti del canale per due motivi: privacy e scalabilità. In primo luogo, l'annuncio dei balance ridurrebbe la privacy della Lightning Network, perché consentirebbe di sorvegliare i pagamenti attraverso l'analisi statistica delle variazioni dei balance. In secondo luogo, se i nodi annunciassero i balance (a livello globale) a ogni pagamento, la scalabilità della Lightning Network sarebbe pari a quella delle transazioni Bitcoin on-chain, che vengono trasmesse a tutti i partecipanti. Pertanto, i balance non vengono annunciati.

Il nodo Lightning crea una lista di percorsi candidati, li filtra e li ordina in base ad alcuni parametri (ad esempio tenendo conto dei nodi attraverso i quali ha già inviato pagamenti con successo) e li prova in sequenza. Se tutti i nodi si comportano bene, verificare di un singolo percorso dovrebbe essere veloce (~ 1 secondo) indipendentemente dalla dimensione della rete, ma se i nodi non si comportano bene, il tempo di verifica può crescere esponenzialmente.

Calcolare il percorso più economico può essere una funzione complicata, e Rene Pickhardt e Stefan Richter hanno effettuato uno studio che ha rilevato che, se nella funzione di pagamento è inclusa una base_fee maggiore di 0, la complessità di questo calcolo è tale da poter essere definito un problema NP-completo (nella teoria della complessità computazionale i problemi NP-completi sono i più difficili problemi nella classe NP "problemi non deterministici in tempo polinomiale").

Per questo motivo è nata l'iniziativa Zero Base Fee, che promuove l'impostazione base_fee a 0 per migliorare le prestazioni di Lightning Network, consentendo di effettuare anche pagamenti per importi che senza tale impostazione hanno alte probabilità di fallire.