LNDのrouting
-----------------------------
LNでの送金時のルーティングの計算はBOLTで決まっているものではなく、各ノード実装に委ねられている。
LNDの場合はダイクストラ法が用いられている。
ダイクストラ法について
ダイクストラ法(だいくすとらほう、英: Dijkstra's algorithm)はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。
各点が線(経路)で繋がっていて、その各経路に重み付けがされている。
その場合にある点からある点までの最小のコストの経路を探索するアルゴリズム。
以下で点1から点5を目指す場合、1→3→6→5 が最小のコストの経路となる。
https://scrapbox.io/files/66a76f9b8c11d7001dab64bf.png
この記事がわかりやすかった
簡単にまとめると始点の最小のものから探索し、終点までのコストを算出する。始点で次の最小のものを探索し、最初に求めた終点のコストより高くなった時点で切り捨てる。
LNDの経路探索について
手数料が一番安く送金できるルートを求めたい
以下の3項目で計算される
ルーティング手数料
タイムロックの差分
確率
https://scrapbox.io/files/66a7756659b4b6001c82e76c.png
各ノードでこのようなグラフを作り計算している。
LNのゴシップネットワークで配信されるチャネル情報を元にチャネルグラフを作成する。
code:チャネルグラフの情報
capacity:チャネルキャパシティ
チャネルに参加している各ノードのポリシー:
fee_base_msat:支払いで発生する固定手数料
fee_rate_milli_msat:支払いで発生する支払額に応じた手数料
time_lock_delta:HTLCに設定されるタイムロックの差分
min_htlc:転送可能なHTLCの最小値
max_htlc_msat:転送可能なHTLCの最大値
チャネルグラフではキャパシティを見ることはできるが、チャネル間のローカルとリモートキャパシティは見ることができない。
そのためキャパシティを満たしていても希望の額すべて送金できるルートがない場合がある。
プライバシーの問題で細かいローカル・リモートキャパシティを公開するようにはなっていないため、経路探索は少し難しい。
LND(Lightning Network Daemon)のルーティングにおける重み付け計算は、経路選択の際に手数料、タイムロック、チャネルの成功確率などを総合的に評価する仕組みです。
重み付けの基本要素
手数料(Fee): 経路上の各ノードで発生する手数料です。LNDは通常、この手数料の二乗を使用して重みを計算しますが、これがサブ最適なルート選択を引き起こす可能性があります。改良された重み付け関数では、リスクファクターを使用して、手数料とタイムロックのバランスを調整します。
タイムロック(Time Lock): 支払いが完了するまでの最大時間で、これも重み付けに影響します。特に高額な支払いでは、タイムロックが与えるペナルティが大きくなるように設計されています。
成功確率(Probability): 過去の送金の成功・失敗履歴に基づいて、各チャネルの成功確率が計算されます。LNDの「Mission Control」という機能が、この情報を管理し、経路選択に反映します。
重み付けについて
code:lnd
// edgeWeight は、エッジ(チャネル)の重みを計算します。この値は、チャネルグラフ内で
// 2つのノード間の最短経路を探索する際に使用されます。重みは、手数料そのものに
// タイムロックペナルティを加えたものです。これにより、タイムロックデルタが短い
// チャネルや、一般的にホップ数が少ないルートが有利になります。
// RiskFactor は、タイムロックがルート選択に与える影響を制御します。
// これは現在固定値ですが、将来的には設定可能になるかもしれません。
func edgeWeight(lockedAmt lnwire.MilliSatoshi, fee lnwire.MilliSatoshi,
timeLockDelta uint16) int64 {
// timeLockPenalty は、このチャネルのタイムロックデルタに対するペナルティです。
// これは RiskFactorBillionths によって制御され、チャネルを通過する金額に比例して
// スケールします。これは、2倍の金額がロックされると、2倍悪いという理論に基づいています。
timeLockPenalty := int64(lockedAmt) * int64(timeLockDelta) *
RiskFactorBillionths / 1000000000
return int64(fee) + timeLockPenalty
}
code:findPath
// findPath は、ネットワーク上で支払いを行うためにソースノードからターゲットノードまでの
// 有効な経路を検索します。検索は Dijkstra アルゴリズムに基づいており、最短経路を見つける
// ことを目的としています。この関数は、最大試行回数を持つ設定に応じて複数の経路を
// 検索できます。見つかった経路は、送信する支払いのために利用されます。
//
// 経路の探索は、以下の要素に基づいて行われます:
// - 手数料: 経路上の各ノードが課す手数料。
// - タイムロック: 経路上の各チャネルに関連するタイムロックペナルティ。
// - 容量: 支払いを完了するために、各チャネルが十分な容量を持っているかどうか。
// - ホップ数: 経路上のノードの数。少ない方が好ましい。
//
// 経路が見つからない場合、この関数はエラーを返します。エラーには、経路が見つからない
// ことや、ネットワークに有効なチャネルが存在しない場合が含まれます。
コードの解説
findPath関数は、Lightning Network内で支払いのための最適な経路を見つける非常に重要な関数です。この関数は、与えられたソースノードからターゲットノードまでの経路を見つけ、最適な経路を選択します。
1. アルゴリズム
findPath関数は、最短経路を見つけるためにDijkstraアルゴリズムを使用します。Dijkstraアルゴリズムは、グラフ内のノード間の最短パスを計算するための有名なアルゴリズムです。これにより、Lightning Network内での支払い経路を効率的に探索できます。
2. 手数料とタイムロック
この関数は、経路のコストを計算する際に、各ホップ(ノード)で発生する手数料とタイムロックペナルティを考慮します。手数料が低く、タイムロックが短い経路が優先されます。
3. 容量の確認
支払いを実行するためには、各チャネルが十分な容量を持っている必要があります。findPath関数は、各チャネルの容量をチェックし、支払いが成功する可能性のある経路を選択します。
4. ホップ数の最小化
経路上のホップ数(経由するノードの数)も重要な要素です。ホップ数が少ないほど、支払いの成功率が高くなり、手数料やタイムロックのリスクが減少します。そのため、findPath関数は、ホップ数が少ない経路を優先します。
5. エラー処理
経路が見つからない場合、または有効なチャネルがない場合、この関数はエラーを返します。これにより、支払いが失敗する可能性のある状況が適切に処理されます。
このfindPath関数は、Lightning Network内での支払い経路を選択するための中核的な機能を提供しており、ネットワークの効率的な運用に不可欠です。経路の探索におけるこれらの要素を適切に処理することで、支払いが迅速かつ低コストで行われるように設計されています。
Mission Control
missioncontrol.goは、Lightning Networkのルーティングにおいて、過去のHTLC(Hashed Time-Locked Contract)送信の成功および失敗の履歴を管理し、将来の送信の成功確率を推定するためのロジックを提供します。具体的には、以下のような機能を持っています:
1. Mission Controlの初期化:
NewMissionControl関数は、Mission Controlの新しいインスタンスを作成し、設定を検証し、データベースストアを初期化します。
2. 履歴の管理:
ResetHistory関数は、Mission Controlの履歴をリセットし、過去の送信試行をすべてクリアします。
ImportHistory関数は、外部から提供された履歴をMission Controlにインポートします。
3. 成功確率の推定:
GetProbability関数は、特定のノードペアに対する支払いの成功確率を返します。これは、過去の履歴と現在の状態に基づいて計算されます。
4. 支払い結果の報告:
ReportPaymentFail関数は、失敗した支払いをMission Controlに報告し、将来の確率推定の入力として使用します。
ReportPaymentSuccess関数は、成功した支払いをMission Controlに報告します。
5. 内部状態の更新:
applyPaymentResult関数は、支払い結果をMission Controlの内部状態に適用し、将来の確率推定に反映させます。
6. スナップショットの取得:
GetHistorySnapshot関数は、現在のMission Controlの状態のスナップショットを取得します。
GetPairHistorySnapshot関数は、特定のノードペアに対する履歴を取得します。
主な構造体と関数の説明
構造体:
MissionControl: Mission Controlのメイン構造体で、内部状態、現在の時間、自己ノード、データベースストア、確率推定器などを保持します。
MissionControlConfig: Mission Controlの設定を定義する構造体です。
MissionControlSnapshot: 現在のMission Controlの状態のスナップショットを保持します。
MissionControlPairSnapshot: 特定のノードペアの状態のスナップショットを保持します。
paymentResult: 支払い試行の結果を保持する構造体です。
関数:
NewMissionControl: Mission Controlの新しいインスタンスを作成します。
ResetHistory: Mission Controlの履歴をリセットします。
ImportHistory: 履歴をインポートします。
GetProbability: 支払いの成功確率を返します。
ReportPaymentFail: 失敗した支払いを報告します。
ReportPaymentSuccess: 成功した支払いを報告します。
applyPaymentResult: 支払い結果を内部状態に適用します。
GetHistorySnapshot: 現在の状態のスナップショットを取得します。
GetPairHistorySnapshot: 特定のノードペアの履歴を取得します。
これらの機能を通じて、missioncontrol.goはLightning Networkのルーティング効率を向上させるための重要な役割を果たしています。
/lnd/routing/probability_bimodal.go について
LNDの手数料計算のまとめ
上に書いてあるのをまとめると
weightと成功確率で経路を求める
weightの求め方
手数料とタイムロックが影響するため、タイムロックデルタが短いチャンネルや、ホップ数が少ないルートが優先
code:weight
# /lnd/routing/pathfind.go
func edgeWeight(lockedAmt lnwire.MilliSatoshi, fee lnwire.MilliSatoshi,
timeLockDelta uint16) int64 {
// timeLockPenalty is the penalty for the time lock delta of this channel.
// It is controlled by RiskFactorBillionths and scales proportional
// to the amount that will pass through channel. Rationale is that it if
// a twice as large amount gets locked up, it is twice as bad.
timeLockPenalty := int64(lockedAmt) * int64(timeLockDelta) *
RiskFactorBillionths / 1000000000
return int64(fee) + timeLockPenalty
}
timeLockPenaltyの計算:
- lockedAmt(通過する金額)にtimeLockDelta(タイムロックデルタ)を掛け、RiskFactorBillionthsでスケールします。
- RiskFactorBillionthsは、タイムロックデルタの影響を制御するための定数です。
- timeLockPenaltyは、lockedAmtとtimeLockDeltaに比例して増加します。
weightの計算:
- weightは、fee(手数料)とtimeLockPenaltyの合計です。
成功確率は /lnd/routing/missioncontrol.go で計算・管理している
内部のアルゴリズムは /lnd/routing/probability_bimodal.go と /lnd/routing/probability_apriori.go
/lnd/routing/probability_bimodal.go
二峰性モデルに基づく成功確率の計算。二峰性モデルは、チャネルの流動性が二つの異なる状態に分布していると仮定し、それに基づいて確率を計算。
/lnd/routing/probability_apriori.go
アプリオリモデルに基づく成功確率の計算。アプリオリモデルは、過去の支払い結果に基づいて確率を計算し、特定の期間を設定して過去のデータの影響を減衰。
hide & seek について
プライバシーに配慮した形でリバランシングを行える hide and seek