ライトニングネットワークでの支払い時には、目的となるノードまでどのチャネルを利用するか、経路の選択が必要です。現在、

ユーザーが何もしなくてもノードが自動的に手数料が安くなるように選択してくれますが、選択した経路での送金が失敗すると自動的に次の経路を試せるまで数秒から十数秒ほどかかることがあり、待ち時間がUXを損ないます。その問題を軽減するために現在の簡単な経路選択アルゴリズムより優れたアルゴリズムが色々考えられ、最近その１つである確率的な経路選択アルゴリズムを試してみた論文が出ました。

今回の記事では双方のアルゴリズムを紹介し、比較してみます。

論文："Security and Privacy of Lightning Network Payments with Uncertain Channel Balances." Rene Pickhardt, Sergei Tikhomirov, Alex Biryukov, and Mariusz Nowostawski (2021)

手数料に基づくアルゴリズム

ライトニングノードが支払い経路を選択するアルゴリズム自体はライトニングの仕様ではないため、ウォレットによって異なる実装になる可能性があります。一番メジャーなライトニングノード実装であるLndでは、手数料が一番安く済む経路から順に成功するまで試行します。

手数料最優先ではない経路選択をするウォレットがあれば教えて下さい。

しかし、手数料による経路選択では他のノードも優先的に手数料が安いチャネルを経由するため、ある時点での使用状況によっては手数料の安いチャネルのバランスが崩れている可能性があります。もし残高が相手方に偏っていた場合、ここで送金が失敗してしまう確率が高くなります。

このとき、そのチャネルは必要以上に安売りしていると言えるので、手数料を引き上げたり別のチャネルの手数料を引き下げてバランスを保ち、より多くの支払いを取り次ぐことで手数料を得るのがノードで稼ぎたい人の戦略となります。ライトニングノードの運用に関してはSpotlightにいい記事がたくさんあるので、興味がある方は読んでみてください。

送金手数料が最安となる経路は理想的でありますが、厄介なことにLNではプライバシー面からリアルタイムなチャネルバランスの状態が当事者にしかわからないため、このような問題に直面することがあります。逆に言えば、安価さより成功確率・速度を優先する経路選択アルゴリズムにも利用価値があるシナリオもあるかもしれません。

確率的な経路選択アルゴリズム

今回紹介するアルゴリズムでは、すべてのチャネルの状態を連続一様分布 (自分方の残高として存在しうるすべての場合の確率が等しい)と推定し、各チャネルの大きさに対する送金額とホップ数 (経路上のチャネル数)によって送金が成功する確率を事前に試算します。

送金額が大きいほどいずれかのチャネルで自分方の残高が不足する可能性が高まり、経由するチャネル数が多いほど途中でそのようなチャネルに遭遇する可能性が高まる、ということですね。

この試算結果を成功確率が最も高い経路を選び、最初の支払いを試行することによって、一時期のLNのスナップショットを利用したシミュレーションにおいて支払いの試行回数を通常と比べて20%削減することに成功したそうです。論文の筆者が提案している、隣合うノードがお互いの持つチャネルのバランス情報を共有できるようにする仕様BOLT14が採択されればこれが48%削減になるとも主張しています。実際のチャネルバランスの推定によってより支払いの成功確率が高そうな経路を選択しているわけですが、すべてのチャネルバランスの状態を連続一様分布という非常に単純な確率で推定をしているので、頻繁にバランシングしている既知のチャネルを優先したりして更に改善できるでしょう。

更に今回紹介したような経路選択方法では金額が大きいほど各チャネルで失敗する確率が上がると推定していますが、マルチパスペイメント(MPP)を利用して１つの支払いを複数に分割し、それぞれ別の経路に流すことで成功確率を大幅に向上させるアプローチもあります。MPP自体は始点・終点のノードが対応していれば既に使えるので、ルーティングに積極的に活用するアプローチも有望だと思います。

まとめ

手数料最優先でライトニングネットワークの支払い経路を選択すると、途中のチャネルの状態によっては送金が失敗しやすくなり、そのたびに別の経路を試していくため送金が成功するまで数秒から数十秒ほど時間がかかってしまいます。それに対して、手数料の安さではなく成功確率を最優先する経路選択アルゴリズムを提案する論文を紹介しました。ライトニングネットワークのスナップショットを利用したテストにおいて、手数料最優先のルーティングと比較して20%少ない試行回数で送金が完了したとしています。

最近はライトニングノードの運用戦略やルーティングのアルゴリズムなど、プロトコル自体に定義されていないプログラマブルな部分に関する静かな盛り上がりを感じます。マニアな領域ですが、Defiが好きな人やグラフ理論で実験したい人にはとても刺激的な環境だと思います。