ライトニングネットワークの経路選択に関しては研究余地が大きいと以前にも申しましたが、新しい研究内容が発表されたので紹介させていただきます。
今回は送金の成功確率を高めるアプローチとして、支払いを細かく分割してその成功・失敗から得られる情報を元に残額を再び分割して送ることを繰り返す、いわば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の最近のスナップショットを用いた簡易的なシミュレーションによって今回のアルゴリズムの効果を測定しました。