ライトニングネットワークの経路選択に関しては研究余地が大きいと以前にも申しましたが、新しい研究内容が発表されたので紹介させていただきます。

今回は送金の成功確率を高めるアプローチとして、支払いを細かく分割してその成功・失敗から得られる情報を元に残額を再び分割して送ることを繰り返す、いわばPDCAを回していくような送金方法です。

Optimally Reliable & Cheap Payment Flows on the Lightning Network - Rene Pickhardt, Stefan Richter.

https://arxiv.org/pdf/2107.05322.pdf

現在は手数料重視のあまり成功率が低いことも

ライトニングノード実装のほとんどは支払い経路の選択をする際に、手数料がなるべく安くなる経路を求めようとします。しかし、手数料が安いチャネルが安定性の高いチャネルとは限らず、手数料を重視して安定性の低いチャネルをいろいろ試した挙げ句にタイムアウトで送金失敗するというケースもあります。そのとき、もう少し高い手数料であれば成功率が非常に高い経路があったというケースもあるでしょう。

4月のはじめに確率的な経路選択アルゴリズムということでチャネルの大きさから個別のチャネルでの成功確率を、ホップ数から送金の成功確率を求めるシンプルなアプローチを紹介しました。その話からもわかるように、確実性の高い経路選択が困難な理由は各チャネルのバランス(資金の偏りの状態) や接続安定性などが外部からわからないことによります。

今回の論文は、１つの送金を複数回に分割し、各回で得た成功・失敗の情報をもとに次回の確率推定を改善するというアプローチです。

まずはできる限りの状況把握

まず、送金するノードはネットワーク全体について知っている情報を整理します。この段階では、各チャネルの残高の偏りはわからないので、ほとんどが不明です。知っているのは、自らと繋がっているチャネルの状況のみで、これらに関しては100%確実に知っています。

ここで更に宛先のノードから、宛先のノードに繋がっているチャネルの状況を聞くことにします。実は送金者・宛先の組み合わせの95%にとって、送金額を制限する一番の要因は送信者のアウトバウンドキャパシティか宛先のインバウンドキャパシティだそうです。したがって、大きな送金などはこの段階でたいてい無理かどうかわかります。

支払いを分割してPDCAを回す

次が今回のメソッドの肝となる部分です。

送金者は、金額を複数の経路に分割して送金するMPP(マルチパートペイメント) と呼ばれるものを実行します。この際、それぞれの経路は成功確率が高いと思われるものが選ばれていますが、それでもやはり失敗するものが一部出てくると考えられます。

失敗した経路、成功した経路の情報を元に送金者はネットワークについて知っている情報をアップデートすることで、それらのチャネルの状態についての予測を改善し、失敗によってまだ支払えていない金額をより確実に支払う経路を求めるのに使います。

つまり、送金が成功したチャネルはそれだけアウトバウンドキャパシティが減少しているので次回の成功確率は低下します。そして送金が失敗したチャネルに関しては「それ以前のチャネルには金額以上のアウトバウンドキャパシティがあった」「失敗したチャネルでは足りなかった」ことを成功確率の計算に利用することができるようになり、もし特定のノードがオフラインであったのならば、それは今回の支払いに関しては以後選択肢から排除してよいという情報が得られます。

MPPはAMP(アトミック・マルチパスペイメント) と呼ばれるものと混同しやすいですが、AMPは分割した送金のすべてが失敗するかすべてが成功するかという不可分性(Atomicity) を持つのに対し、MPPは一部が失敗することを許容します。この不可分性という性質が必要ない、もしくは今回のように却って邪魔になってしまう場合にMPPが好まれます。

シミュレーション結果 (実際のイメージ)

論文の著者たちは、未解決のHTLCの扱いなど現実でこの経路選択アルゴリズムを利用する場合に考慮しなければならない問題点を克服するのにはまだ時間が必要と判断し、LNの最近のスナップショットを用いた簡易的なシミュレーションによって今回のアルゴリズムの効果を測定しました。

アウトバウンドキャパシティが合計0.42BTCのノードから、3ホップ先にあるインバウンドキャパシティが合計0.4BTC以上で総キャパシティ1.5BTCのノードに対して上記の方法で送金すると、第一ラウンドで数百の経路を利用して75%ほどを送金でき、第二ラウンドではその結果を元におよそ100の経路を通して送金できなかったのはおよそ90,000satのみだったそうです。

第三ラウンドにおいて15の経路のうち14が成功し、最後のラウンドでは1つのチャネルを除いてすべてが十分なキャパシティを持つことがわかった8ホップの経路が選択され、送金が無事成功したそうです。(第四ラウンドの成功確率は99.97%と予測)

「手数料の固定部分はないほうがよい」という主張

今回の論文に関して、著者のRene Pickhardt氏の大きな主張の１つとして「ルーティングの手数料の固定部分はないほうが良い」というものがあります。

LNのルーティング手数料は固定部分(大抵は1sat)と変動部分(0.0001% = ppm単位で指定)の組み合わせによってチャネルごとに決められています。固定部分の存在理由は超定額の送金でネットワークがパンクするのを防ぐスパム対策と思われます。考案者のRusty Russellは、より複雑な提案との妥協案として選ばれた、現実世界でもよくある課金方式だと述べています。

Pickhardt氏の主張は大きく分けて2つあります。

1つ目は、固定部分(base fee) の存在によって手数料を優先したLNの経路選択問題がNP困難になっているという指摘です。このため、経路選択に必要な計算量が非常に大きいことを問題視しています。(固定部分がなければかなり単純になることは簡単に想像できますね。)

2つ目は、base feeをゼロに設定しているノードが十分にあれば、計算効率の良いアルゴリズムを実装するウォレットに選ばれやすくなるのではないかという予想と希望的観測です。これに関して、氏はbase feeをゼロに設定しているパブリックチャネルの割合を示すウェブサイトを立ち上げています。

https://basefee.ln.rene-pickhardt.de/

まとめ

・現在のLN送金経路選択は主に手数料のみを考慮している

・成功確率を考慮した経路選択方法がいろいろと研究されている

・送金を細かく分割して大量の経路に送ることで情報を取得し、その情報を元にさらなるラウンドを重ねる方法が発表された

・著者は中継手数料の固定部分であるbase feeをゼロにするメリットも主張している