Pathfinding 路徑搜索

Lightning Network Graph Structure:

Nodes (Vertices):
  - Each Lightning node is a vertex
  - Identified by 33-byte public key
  - Announced via node_announcement message

Edges:
  - Each public channel is an edge
  - Actually bidirectional (each direction independent)
  - Announced via channel_announcement
  - Updated via channel_update

Edge Properties:
  short_channel_id: channel identifier
  capacity: total capacity (known)
  balance: each party's balance (unknown!)

  Per-direction parameters:
    - base_fee: base fee
    - fee_rate: proportional fee (ppm)
    - cltv_delta: timelock delta
    - htlc_min: minimum HTLC
    - htlc_max: maximum HTLC

Typical Network Size (2024):
  - Nodes: ~15,000
  - Channels: ~50,000
  - Total capacity: ~5,000 BTC
  - Graph size: ~10MB

Dijkstra Algorithm Variant:

Basic Idea:
Find lowest "cost" path from source to target

Cost Function Design:
cost(edge) = f(fee, probability, time_lock, ...)

LND Cost Function Example:
cost = fee
     + amount * risk_factor * cltv_delta
     + amount * (1 - success_probability) * penalty

Parameters:
  - fee: direct fee cost
  - risk_factor: time value (fund locking cost)
  - cltv_delta: timelock increase for this hop
  - success_probability: historical success estimate
  - penalty: failure penalty factor

Algorithm Flow:
  1. Search backwards from target (more efficient)
  2. Maintain priority queue (sorted by cost)
  3. Pop lowest cost node each time
  4. Update optimal path for neighbor nodes
  5. Until reaching source node

Pseudocode:
function dijkstra(source, target, amount):
  dist[target] = 0
  queue.add(target, 0)

  while queue not empty:
    node = queue.pop_min()

    for edge in node.incoming_edges:
      if can_forward(edge, amount):
        new_cost = dist[node] + edge_cost(edge, amount)
        if new_cost < dist[edge.source]:
          dist[edge.source] = new_cost
          prev[edge.source] = edge
          queue.update(edge.source, new_cost)

  return reconstruct_path(prev, source, target)

Channel Balance Uncertainty:

Problem:
  - Only know total capacity, not individual balances
  - Balances change in real-time
  - Selected path may fail due to insufficient balance

Example:
Channel capacity: 1 BTC
Possible balance distributions:
  - Alice: 0.0 BTC, Bob: 1.0 BTC
  - Alice: 0.3 BTC, Bob: 0.7 BTC
  - Alice: 0.5 BTC, Bob: 0.5 BTC
  - Alice: 1.0 BTC, Bob: 0.0 BTC
  - Any value in between...

Probability Model:
Assume balance uniformly distributed in [0, capacity]

P(can_forward amount) = (capacity - amount) / capacity

amount = 0.1 BTC, capacity = 1 BTC
P(success) = 0.9 (90%)

amount = 0.9 BTC, capacity = 1 BTC
P(success) = 0.1 (10%)

Multi-hop Success Rate:
P(path success) = P(hop1) * P(hop2) * ... * P(hopN)

3-hop path, 90% success rate each hop:
P(success) = 0.9^3 = 0.729 (73%)

This is why large payments often fail!

Mission Control (LND's Learning Mechanism):

Concept: Learn path reliability from payment history

Recording Each Attempt:

  Payment Attempt #1:
    Path: A -> B -> C -> D
    Result: Failed at B->C (TEMPORARY_CHANNEL_FAILURE)
    Learned: B->C may have insufficient balance

  Payment Attempt #2:
    Path: A -> E -> F -> D (avoiding B->C)
    Result: Success
    Learned: E->F->D path is reliable

Mission Control Data Structure:
{
  "node_pairs": {
    "B->C": {
      "last_fail_time": "2024-01-01T12:00:00Z",
      "fail_amount": 100000,
      "success_amount": 50000
    }
  }
}

Success Rate Estimation Update:
if (amount > fail_amount):
  P(success) = 0  // will definitely fail
else if (amount <= success_amount):
  P(success) = high  // likely to succeed
else:
  P(success) = interpolate(...)

Decay Mechanism:
  - Old data weight decreases (balances change)
  - Retry failed paths after some time
  - Typical decay time: 1-24 hours

MPP Path Finding:

Problem: How to find multiple paths that work together?

Method 1: Greedy Split
  1. Find best single path, allocate max possible amount
  2. Repeat on residual graph
  3. Until total amount satisfied

Method 2: Min-Cost Flow
  - Model as network flow problem
  - Capacity = estimated available balance
  - Cost = fee + risk
  - Solve minimum cost maximum flow

Method 3: Opportunistic
  1. Try single path for full amount
  2. If fails, halve amount and retry
  3. Recursively split until success or give up

LND's Approach:
  1. Compute multiple candidate paths (K shortest paths)
  2. Evaluate success probability and cost for each path
  3. Select optimal combination (lowest total cost with
     sufficient probability)
  4. Send shards in parallel
  5. Re-route failed shards

How Trampoline Routing Changes Path Finding:

Traditional Mode:
  - Sender maintains complete network graph
  - Sender computes full path
  - High computation cost, not mobile-friendly

Trampoline Mode:
  - Sender only knows a few Trampoline nodes
  - Sender computes path to Trampoline
  - Trampoline nodes compute subsequent paths
  - Greatly reduces sender's computation and storage

Path Finding Responsibility Distribution:

  Sender:
    -> Finds path to first Trampoline

  Trampoline 1:
    -> Finds path to Trampoline 2 (or destination)

  Trampoline 2:
    -> Finds path to final destination

See: /tech/lightning/trampoline