Path-Finding Algorithm

What Is a Path-Finding Algorithm?

A path-finding algorithm is the process a sender uses to discover a route for a payment across a network of interconnected payment channels. In the Lightning Network, payments travel from sender to receiver through a series of intermediate routing nodes, each forwarding the payment along the next channel in the path. The algorithm decides which sequence of nodes and channels to use, optimizing for low fees, high reliability, and minimal timelock exposure.

Lightning uses source-based routing: the sender computes the entire path before initiating the payment. No intermediate node knows the full route. Each hop only learns which node sent it the payment and which node to forward it to, thanks to onion routing (defined in BOLT 4). This preserves privacy but places the full burden of route computation on the sender.

Path-finding is one of the hardest problems in payment channel networks. The sender must choose a path using incomplete information: total channel capacities are public, but the actual balance distribution within each channel is private. This means every routing attempt is partly a guess, and payments can fail partway through when a channel along the path lacks sufficient liquidity.

How It Works

Path-finding begins with the sender constructing a local copy of the network graph from data received through the gossip protocol (BOLT 7). This graph contains every publicly announced channel, along with the fee policies and timelock requirements advertised by each node. The algorithm then searches this graph for the lowest-cost path from sender to receiver.

Information Available for Routing

The gossip protocol provides three types of messages that form the routing graph:

• Channel announcements: prove a channel exists on-chain, containing the short channel ID and four cryptographic signatures (two node keys, two funding keys)
• Channel updates (per direction): advertise fee policies including base fee (fee_base_msat), proportional fee rate (fee_proportional_millionths), CLTV expiry delta, and HTLC size limits
• Node announcements: contain alias, color, and network addresses for each node

The fee for forwarding through a channel is calculated as:

fee = base_fee_msat + (amount_msat × fee_rate_ppm / 1,000,000)

The critical limitation: gossip broadcasts total channel capacity but not the current balance split between the two sides. A 10 million satoshi channel might have 9 million on one side and 1 million on the other, but the sender cannot know this without attempting a payment.

The Core Algorithm

All major Lightning implementations build on Dijkstra's shortest-path algorithm, adapted for Lightning's specific constraints. Because fees accumulate backward (each hop adds its fee on top of the downstream amount), the algorithm runs in reverse from the receiver back to the sender.

Each implementation defines a cost function for edges that combines three factors:

1. Fee cost: the base fee plus proportional fee charged by the routing node
2. Timelock cost: the CLTV delta converted to a virtual fee, since locked funds carry an opportunity cost
3. Reliability penalty: a cost derived from the estimated probability that the channel has enough liquidity to forward the payment

The algorithm finds the path with the minimum total cost across all hops. However, the pathfinding problem with real-world constraints (fee limits, timelock limits, minimum success probability) is NP-complete. No variant of Dijkstra's algorithm can guarantee globally optimal solutions under these constraints, so implementations rely on heuristic approaches that work well in practice.

Probability Models by Implementation

The most consequential difference between Lightning implementations is how they estimate the probability that a channel can forward a given amount:

LND's bimodal model (based on Pickhardt's research) assumes channel liquidity clusters at the extremes: channels tend to be mostly full or mostly empty. Small payments receive high success probability, while amounts approaching channel capacity receive near-zero probability. LND's Mission Control subsystem records up to 1,000 payment attempt results per channel pair, feeding historical data back into probability estimates with a 7-day decay.

CLN takes a fundamentally different approach with its minimum-cost flow (MCF) solver (implemented in the xpay/askrene plugins). Rather than finding one best path, it computes the optimal way to split a payment across multiple channels simultaneously, treating the routing problem as a flow optimization. This is theoretically superior for multi-path payments.

LDK's ProbabilisticScorer maintains per-channel liquidity bounds (lower and upper) adjusted from payment history. It tracks historical liquidity distribution across 32 variable-sized buckets per channel direction, with finer granularity near the edges where liquidity tends to cluster.

Multi-Path Splitting

Multi-path payments (MPP) allow splitting a single payment into smaller shards routed independently across different paths. This transforms the routing problem from "find one path with enough capacity" to "find a set of paths whose combined capacity covers the payment."

LND uses a divide-and-conquer strategy: attempt the full amount on the best path, and if it fails due to insufficient capacity, halve the amount and route each half independently. CLN's MCF solver computes the optimal split across all channels simultaneously.

At the receiver, individual HTLC shards are held without settling until all shards arrive. Once the full amount is received, all HTLCs settle atomically using the same payment preimage.

Use Cases

Wallet Payment Delivery

Every Lightning wallet runs a path-finding algorithm when a user pays an invoice. The wallet queries its local channel graph, computes the best route, constructs an onion-encrypted packet, and dispatches the HTLC. If the payment fails at any hop, the wallet updates its probability model and retries on an alternative path, often transparently to the user.

Trampoline Routing for Mobile

Mobile wallets often lack the storage and bandwidth to maintain a full channel graph. The trampoline routing proposal (deployed in production by Eclair and the Phoenix wallet) allows lightweight clients to delegate path-finding to well-connected trampoline nodes. The sender routes to a trampoline node, which computes the remaining path to the destination.

Payment Probing

Some implementations use payment probes to test channel liquidity before sending real payments. A probe sends an HTLC with an invalid payment hash: it will never settle, but the error response reveals whether each hop had sufficient balance. Probe results feed back into the scoring model to improve future routing decisions.

Liquidity Service Providers

LSPs and routing node operators use path-finding data to make business decisions: which channels to open, where to allocate liquidity, and how to set fee policies. Understanding the network graph and traffic patterns helps operators position their nodes for maximum routing revenue.

Risks and Considerations

Unknown Balances and Payment Failures

The fundamental challenge of Lightning path-finding is that channel balances are hidden for privacy. The sender must estimate liquidity from indirect signals and accept that many payment attempts will fail. For small payments (under 100,000 sats), success rates are generally high. For larger payments, multiple retries and path splitting are often necessary, adding latency that can degrade user experience.

Stale Routing Data

Channel updates propagate through gossip with variable latency. By the time a sender's graph reflects a fee policy change or channel closure, the actual network state may have moved. Payments routed through stale data fail at the first out-of-date hop, requiring graph updates and retries.

Balance Probing Attacks

An attacker can discover a channel's balance distribution using binary search probing: send HTLCs with invalid payment hashes through a target channel, adjusting amounts based on whether the error indicates insufficient liquidity. This typically takes under a minute per channel and costs nothing since probes never settle. Multi-path payments partially mitigate this by splitting amounts across channels, making balance inference harder.

Scalability of the Gossip Protocol

The current gossip protocol uses flood-fill propagation: every node relays every channel update to every peer. As the network grows, the bandwidth and storage required to maintain a full graph increase. Work on gossip v2 using minisketch-based set reconciliation aims to reduce sync overhead, but the protocol is not yet standardized. Technologies like rapid gossip sync provide interim solutions for mobile clients.

How Spark Eliminates Routing

Not all Bitcoin Layer 2 solutions require path-finding. Spark uses a statechain-based architecture where transfers work by reassigning signing authority over an existing on-chain UTXO rather than forwarding payments through a network of channels. When Alice sends to Bob, the Spark operators (secured via FROST threshold signatures) generate a new key for Bob and mathematically adjust the operator key. The Bitcoin never moves on-chain, and no routing is involved.

This eliminates the fundamental problem that makes Lightning path-finding so difficult: there is no channel graph to search, no gossip to synchronize, no liquidity to estimate, and no payment failures from insufficient channel balance. For a deeper comparison, see Lightning vs. Spark and the Lightning Network routing deep dive.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.