LNを利用したオフチェーン支払いをする際、基本的に送信者が受信者までの支払いの経路を決めるようになっている。つまり、送信者はこの経路を探索する必要がある。LNのゴシップネットワークで、LNノードやそのチャネルの情報が（更新を含めて）配信されるので、ノードはローカルでそれらの情報を保持し、チャネルグラフを構成し、その情報を元に受信者までの経路を探索/選択する。
LNDだと、lncliでdescribegraphコマンドを実行すると、ノードが保持するネットワークグラフのデータ＝ノード情報（nodes以下）とチャネル情報（edges以下）が取得できる↓
$ ./lncli describegraph { "nodes": [ { "last_update": 1632624677, "pub_key": "02ec095bfb29e486b814b61bcad294224597f7b890fd977149bdc1b2718210d088", "alias": "techmedia", "addresses": [ { "network": "tcp", "addr": "gkckd5v6gl4g4aeauttbds33r64b4loyml7kupfs3godshqpd6wtogqd.onion:9735" } ], "color": "#00aeef", "features": { ... } ], ... "edges": [ { "channel_id": "759077539161571329", "chan_point": "5cc1a55ab820619a4c3455539e576b80f8d942cc8df0050958637d7d28abdd5d:1", "last_update": 1632608086, "node1_pub": "02ec095bfb29e486b814b61bcad294224597f7b890fd977149bdc1b2718210d088", "node2_pub": "035b1ff29e8db1ba8f2a4f4f95db239b54069cb949b8cde329418e2a83da4f1b30", "capacity": "10000000", "node1_policy": { ... }, "node2_policy": { ... } }, ...
通常、Lightningの共通仕様はBOLTで定義されているが、↑の情報からどう経路探索/選択するかについては定義されていない。これは、経路探索が、外部のノードと対話する必要なく送信ノードが単独で計算できる類のものであるため。
経路探索
では、経路探索とは具体的に何をしているのか？
↑のデータのedgesのデータからもわかるように、チャネルの情報には以下のようなデータが含まれる。
capacity：チャネルキャパシティ- チャネルに参加している各ノードのポリシー：
fee_base_msat：支払いで発生する固定手数料fee_rate_milli_msat：支払いで発生する支払額に応じた手数料time_lock_delta：HTLCに設定されるタイムロックの差分min_htlc：転送可能なHTLCの最小値max_htlc_msat：転送可能なHTLCの最大値
経路探索とは、送信ノードから受信ノードまでの経路を見つけることだが、その際に送金額以上のキャパシティを持っているチャネルであり、かつ上記のノードポリシーから分かる手数料を加味した上で、安価に送金できる経路を探索する。
LNのネットワークは、グラフ理論を使って表現できる。グラフは頂点の集合とエッジの集合で構成される。LNの場合、各LNノードがグラフ上の各頂点で、チャネルを開設している２つのノード間にエッジが結ばれる。LNDでは、エッジに対して、支払いを転送するノードの以下のデータを重みとして設定する。
- ルーティング手数料
- タイムロックの差分
- 確率
手数料とタイムロックの値は↑のデータから分かるようにチャネルの各ノードポリシーに設定されている値。最後の確率は、送信ノードから見て、そのエッジの送信成功確率になる。この確率は、実際に支払いをその経路で試行して、その結果（成功/失敗）を追跡し、その経路で支払いが成功するかどうかを表す確率パラメータになる。LNDではMission Controlというサブシステムでこれらの支払いの試行結果のトラッキングを行っている。
このような重み付きの有向グラフをフローネットワークと呼ぶ。そしてこのようなネットワークにおいて、グラフ上の2つの頂点を結ぶ経路から重みが最小（＝LNの場合、手数料が最も安価）な経路を求めるのが最短経路問題で、ダイクストラ法（Dijkstra法）は、重みが非負であるグラフ*1の最短経路問題を解くアルゴリズムの１つ。
LNDはこのダイクストラ法を変形版を使って経路を探索している。具体的には、↑のルーティング手数料とタイムロックの差分の両方を最小化し、↑の確率を最大化する経路を見つけるようになっている。実装されてるコードはこちら。
支払い精度の向上
↑のように経路を探索/選択して支払いを実行しても、必ずしもその支払いが成功する保証はない。
- 経路上のノードが支払いのタイミングで反応しない（オフラインになっているなど）
- チャネル上には十分なキャパシティを持っているが、チャネルのHTLCを転送する側のノードに十分なローカルキャパシティが無い。例えば、チャネル参加者AとBについて、B→Aへの転送はB側に送金額より大きい残高があるので成功するが、A→Bの転送はA側の残高が送金額に満たず失敗する。
後者は、二者間のチャネル残高の配分はLNのゴシップネットワークに配信されないため、それを加味して経路を探索することはできない。これらの情報はプライバシーと、スケーラビリティの問題からおそらく今後も配信されることはないだろう。また、配信されたとしても支払いの瞬間に本当にその残高があると保証できるものでもない。
こういった不確実性がある中で、支払いの成功率を向上させるためには、↑のMission Controlのような試行結果によるフィードバックも精度の向上に繋がるが、このデータ自体が時間に敏感なデータなため、支払いを頻繁に多数していない状況だと効果は限定的になると思う。
他には、AMPのように小額を複数の経路で支払うことで、転送方向のキャパシティの制限を受けにくくすることで精度を向上させるというアプローチもあるけど、厳密にアトミックにするとどれか1つの経路が失敗したら、結局失敗してしまうことになるので、Boomerangのように冗長パスを含めるなど、他の改善との組み合わせも必要になるかもしれない。2017年にローンチされた直後と違い、ノードの参加数が大幅に増える中で、どう支払いの精度を上げるかは重要な課題の１つ。
*1:現状、LNではマイナスの手数料は存在しない。
