The Lightning Network Routing Problem: Pathfinding, MPP, and Trampoline

#algorithms #bitcoin #computerscience #distributedsystems

Finding a path in the Lightning Network is not a solved problem. It looks like it should be, you have a graph of nodes and edges with weights, which is textbook Dijkstra, but the actual constraints make standard shortest-path algorithms insufficient.

This post covers what makes Lightning routing hard, how current implementations approach it, and what multipart payments and trampoline routing add to the picture.

Why Standard Shortest Path Does Not Work

In a standard weighted graph, you run Dijkstra from source to destination and you are done. Lightning adds several constraints that break this:

Channel capacity is private. The Lightning gossip protocol advertises channels with their total capacity, but not with individual balances. You do not know how much liquidity sits on each side of a channel. A 1 BTC channel between Alice and Bob might have 0.99 BTC on Alice's side and 0.01 BTC on Bob's side. A payment of 0.5 BTC would fail at that edge, but you have no way to know this before trying.

Balances change continuously. Even if you could query balances, they shift with every HTLC. By the time you compute a path and send a payment, the balance may have changed.

Fees are route-dependent. Routing fees are charged per hop, and the fee depends on the amount being forwarded. The optimal route for a 1,000 sat payment may be entirely different from the optimal route for 1,000,000 sat.

CLTV deltas accumulate. Each hop adds a CLTV delta to the timelock. A route with 10 hops might accumulate 400 blocks of timelock, which is a real cost (your HTLC is locked for ~400 blocks if something goes wrong).

Routing is probabilistic. The channel you pick might fail. You need a strategy for retrying on different paths after failure.

The Probability Model

The core insight in modern Lightning pathfinding is to treat routing as a probability problem. Each channel has some probability of successfully forwarding a given amount. Your goal is to find the path with the highest probability of success.

The probability of a channel forwarding an amount x given total capacity c follows a uniform distribution if you have no prior information:

P(channel can forward x) = (c - x) / c

If the channel has capacity 1,000,000 sat and you want to forward 300,000 sat, the naive probability is 0.7. But this ignores the distribution of channel balances in practice since most channels are not uniformly balanced.

LND's pathfinding uses a Bayesian model that updates estimates based on payment outcomes:

from dataclasses import dataclass
from typing import Optional

@dataclass
class ChannelLiquidityBounds:
    """
    Tracks our knowledge about a channel's available liquidity.
    min_htlc: we know at least this much is available
    max_htlc: we know less than this much is available
    """
    capacity_msat: int
    min_available_msat: int = 0
    max_available_msat: Optional[int] = None
    last_updated: int = 0  # unix timestamp

    def __post_init__(self):
        if self.max_available_msat is None:
            self.max_available_msat = self.capacity_msat

    def probability_of_success(self, amount_msat: int) -> float:
        """
        Estimate probability this channel can forward amount_msat.
        Uses uniform distribution between known bounds.
        """
        if amount_msat < self.min_available_msat:
            return 1.0  # we know this succeeds
        if amount_msat >= self.max_available_msat:
            return 0.0  # we know this fails

        # Uniform distribution between bounds
        available_range = self.max_available_msat - self.min_available_msat
        if available_range == 0:
            return 0.5
        above_min = amount_msat - self.min_available_msat
        return 1.0 - (above_min / available_range)

    def record_success(self, amount_msat: int, timestamp: int) -> None:
        """Payment succeeded: update lower bound."""
        self.min_available_msat = max(self.min_available_msat, amount_msat)
        self.last_updated = timestamp

    def record_failure(self, amount_msat: int, timestamp: int) -> None:
        """Payment failed at this channel: update upper bound."""
        self.max_available_msat = min(self.max_available_msat, amount_msat)
        self.last_updated = timestamp

    def decay(self, current_time: int, half_life_seconds: int = 3600) -> None:
        """
        Decay bounds toward the naive uniform estimate over time.
        As time passes, our information becomes less reliable.
        """
        elapsed = current_time - self.last_updated
        decay_factor = 0.5 ** (elapsed / half_life_seconds)

        # Decay lower bound toward 0
        self.min_available_msat = int(self.min_available_msat * decay_factor)
        # Decay upper bound toward capacity
        gap = self.capacity_msat - self.max_available_msat
        self.max_available_msat = self.capacity_msat - int(gap * decay_factor)

The decay function is critical: a failure you observed an hour ago is much less informative than one you observed a second ago. Channel balances change continuously.

Pathfinding With Probabilistic Cost

Standard Dijkstra minimizes a single weight. For Lightning, the weight function must combine:

Fee cost (base fee + proportional fee * amount)
Success probability (penalize low-probability channels)
CLTV delta accumulation
Number of hops (shorter is generally better)

The combined cost function used by LND and similar implementations:

import math
from dataclasses import dataclass

@dataclass
class Edge:
    source: str
    destination: str
    short_channel_id: str
    capacity_msat: int
    fee_base_msat: int
    fee_proportional_millionths: int
    cltv_expiry_delta: int
    liquidity: ChannelLiquidityBounds

def edge_cost(
    edge: Edge,
    amount_msat: int,
    probability_weight: float = 0.5,
    cltv_weight: float = 0.001,
) -> float:
    """
    Compute the cost of forwarding amount_msat through this edge.
    Returns a scalar suitable for Dijkstra minimization.
    Lower is better.
    """
    # Fee in millisatoshis
    fee_msat = (
        edge.fee_base_msat +
        (amount_msat * edge.fee_proportional_millionths // 1_000_000)
    )

    # Probability penalty: -log(p) maps probability to additive cost
    # P=1.0 → cost=0, P=0.5 → cost=0.69, P=0.1 → cost=2.30
    p = edge.liquidity.probability_of_success(amount_msat)
    if p <= 0:
        return float('inf')
    probability_penalty = -math.log(p) * probability_weight * amount_msat

    # CLTV penalty: each block of delay has a small cost
    cltv_penalty = edge.cltv_expiry_delta * cltv_weight * amount_msat

    return fee_msat + probability_penalty + cltv_penalty

def find_path(
    graph: dict[str, list[Edge]],
    source: str,
    destination: str,
    amount_msat: int,
    max_hops: int = 20
) -> list[Edge]:
    """
    Dijkstra's algorithm with probabilistic cost function.
    graph: adjacency list of {node_id: [Edge]}
    """
    import heapq

    dist = {source: 0.0}
    prev = {}
    pq = [(0.0, source)]

    while pq:
        cost, node = heapq.heappop(pq)

        if node == destination:
            # Reconstruct path
            path = []
            while node in prev:
                edge = prev[node]
                path.append(edge)
                node = edge.source
            return list(reversed(path))

        if cost > dist.get(node, float('inf')):
            continue

        for edge in graph.get(node, []):
            if edge.destination == destination or True:  # hop count check omitted for clarity
                new_cost = cost + edge_cost(edge, amount_msat)
                if new_cost < dist.get(edge.destination, float('inf')):
                    dist[edge.destination] = new_cost
                    prev[edge.destination] = edge
                    heapq.heappush(pq, (new_cost, edge.destination))

    return []  # No path found

Multipart Payments (MPP)

Even with the best pathfinding, a large payment often cannot find a single path with sufficient liquidity. Multipart payments (MPP, BOLT 11 feature bit 16) solve this by splitting a payment into multiple parts, each following a different route.

The recipient accepts MPP payments by returning the preimage only after receiving parts totaling the full amount. The payment secret (BOLT 11 field s) is the mechanism, all parts must include the same payment secret, and the recipient waits until the total matches before releasing it.

@dataclass
class PaymentPart:
    payment_hash: str
    payment_secret: str
    amount_msat: int
    path: list[Edge]

def split_payment(
    total_amount_msat: int,
    graph: dict[str, list[Edge]],
    source: str,
    destination: str,
    max_parts: int = 16,
    min_part_msat: int = 1000
) -> list[PaymentPart]:
    """
    Split a payment across multiple paths.
    Simple approach: try full amount, then binary split if needed.
    Production implementations use more sophisticated splitting.
    """
    payment_hash = secrets.token_bytes(32).hex()
    payment_secret = secrets.token_bytes(32).hex()

    # Try full amount first
    path = find_path(graph, source, destination, total_amount_msat)
    if path:
        return [PaymentPart(
            payment_hash=payment_hash,
            payment_secret=payment_secret,
            amount_msat=total_amount_msat,
            path=path
        )]

    # Split into parts
    parts = []
    remaining_msat = total_amount_msat
    part_amount = total_amount_msat // 2

    while remaining_msat > 0 and len(parts) < max_parts:
        amount = min(part_amount, remaining_msat)
        if amount < min_part_msat:
            break

        path = find_path(graph, source, destination, amount)
        if path:
            parts.append(PaymentPart(
                payment_hash=payment_hash,
                payment_secret=payment_secret,
                amount_msat=amount,
                path=path
            ))
            remaining_msat -= amount
        else:
            part_amount = part_amount // 2

    if remaining_msat > 0:
        raise ValueError(f"Could not find paths for full amount. Remaining: {remaining_msat} msat")

    return parts

MPP parts use the same payment hash and payment secret. The TLV onion payload for the final hop includes:

payment_data: {payment_secret, total_amount_msat} — signals this is an MPP part
amt_to_forward: the amount in this specific part

The recipient checks that total_amount_msat is consistent across all parts and waits until received parts sum to at least total_amount_msat before releasing the preimage.

Trampoline Routing

Standard Lightning routing requires the sender to know the full path to the destination. This requires the sender to maintain a copy of the gossip graph, which is hundreds of megabytes for a full node and impractical for mobile wallets.

Trampoline routing delegates pathfinding to intermediary nodes. The sender only needs to find a path to a trampoline node. The trampoline node handles pathfinding to the destination (or to the next trampoline).

Mobile Wallet ──── Trampoline Node A ──── (pathfinding) ──── Recipient
                  (finds path itself)

The onion structure for trampoline is nested:

def build_trampoline_onion(
    hops: list[dict],    # trampoline hops
    payload: dict        # final recipient payload
) -> bytes:
    """
    Trampoline uses a nested onion:
    Outer onion: source → trampoline nodes (known path)
    Inner trampoline onion: trampoline → destination (unknown path, delegate)

    Each trampoline hop includes the inner onion in its payload.
    The trampoline node unwraps one layer of the inner onion.
    """
    # Inner onion: for the trampoline nodes to forward
    inner_onion = build_onion(hops, payload)

    # Outer onion: source to first trampoline
    outer_payload = {
        'trampoline_onion': inner_onion,
        'total_amount_msat': payload['total_amount_msat'],
        'payment_secret': payload['payment_secret']
    }
    return outer_payload

Trampoline is defined in bLIP-25 (formerly a CLN-specific feature). LND added experimental trampoline support. The main tradeoff is privacy: the trampoline node learns the payment destination if it is the only trampoline in the path. Using two trampoline nodes mitigates this.

How Failures Feed Back

When a payment fails, the failure message propagates back along the route to the sender. BOLT 4 defines the failure codes and how they are encrypted for each hop.

The failure tells the sender two things:

Which hop failed (if the failure message is attributable)
Why it failed (routing codes: TEMPORARY_CHANNEL_FAILURE, UNKNOWN_NEXT_PEER, AMOUNT_BELOW_MINIMUM, etc.)

FAILURE_CODES = {
    0x2002: 'TEMPORARY_CHANNEL_FAILURE',   # insufficient balance, retry later
    0x400F: 'TEMPORARY_NODE_FAILURE',      # node issue, route around it
    0x100E: 'UNKNOWN_NEXT_PEER',           # channel does not exist, update graph
    0x2006: 'AMOUNT_BELOW_MINIMUM',        # part too small for this hop
    0x2007: 'FEE_INSUFFICIENT',            # fee too low, update channel params
    0x100A: 'CHANNEL_DISABLED',            # channel flagged disabled in gossip
    0x4006: 'EXPIRY_TOO_FAR',             # CLTV too high, reject
}

def process_failure(failure_code: int, failed_channel: str, amount_msat: int, liquidity_db) -> None:
    if failure_code == 0x2002:  # TEMPORARY_CHANNEL_FAILURE
        # Update upper liquidity bound — channel could not forward this amount
        channel = liquidity_db.get(failed_channel)
        channel.record_failure(amount_msat, current_time())

    elif failure_code == 0x100E:  # UNKNOWN_NEXT_PEER
        # Channel no longer exists — remove from graph
        liquidity_db.mark_channel_dead(failed_channel)

    elif failure_code == 0x2007:  # FEE_INSUFFICIENT
        # Our fee estimate was stale — update from gossip
        liquidity_db.refresh_channel_fees(failed_channel)

This feedback loop is what makes probabilistic pathfinding improve over time. Failed routes update the liquidity model. Successful routes confirm liquidity exists. With enough payment history, the estimates become significantly better than the naive uniform distribution.

What LND Does in Practice

LND's pathfinding lives in routing/pathfind.go. The key parameters you can configure:

# In lnd.conf
[routing]
# Time to keep mission control data (liquidity observations)
routerrpc.mcsessiontimeout=60m

# Probability that a randomly balanced channel can forward
routerrpc.minrtprob=0.01

# How aggressively to penalize uncertain channels
routerrpc.apriorihopprob=0.6

# Weight of CLTV vs fee in path selection
routerrpc.attemptcost=100

# Via the RPC, you can query mission control state
lncli querymc  # shows all channel probability estimates

The querymc command is particularly useful for debugging — it shows you exactly what probability your node assigns to every channel it has observed.