ライトニングネットワークにおける利己的ルーティングによる無秩序の代償

2022-07-12T21:14:28Z

キーワード：無秩序の代償、利己的ルーティング、支配戦略、ナッシュ均衡

本記事は以下の記事の内容をまとめたものである。

はじめに

上記記事の前半では、LNでのチャネル流量の枯渇(*1)率において送金の失敗率をシミュレーションしている。後半では、送金経路選択の戦略別に送金を行い、どの戦略がもっとも全体的なコストの面で非効率かをシミュレーションしている。ゲーム理論をライトニングネットワークに適用しようとする試みであり、まだまだ未開拓な領域ではあるが、面白い分野であるので以下にその内容をまとめた。

*1 チャネル流量の枯渇：A->Bへの送金時、チャネル資金がB側へ偏ってしまい送金できない状態のこと

チャネル流量の枯渇率による送金シミュレーション

図1は、チャネル流量の枯渇率を調整した5つのチャネル上でランダムに送金したシミュレーション結果である。drain:0.1はA-B間のチャネル資金が0.1対0.9であることを表しており、このチャネル上でランダムに送金をする。その結果、失敗率が80%へ収束していくことが読み取れる。チャネル流量の枯渇率が0.1と極端に偏っているのに失敗率が80%しかないのは、B→Aへの送金があることで、チャネルバランスが少しだけ改善するためである。また、drain:0.1のチャネルでは、逆方向の送金はほぼ100%成功することが直感的に分かる。この仮定の下で枯渇した方向への送金の成功率を求めると、0.1*1+0.9*x=0.2 x=11.1%となり、11%の確率で枯渇した方向への送金が成功することが分かる。

図1チャネル流量別の送金失敗率

図2は、どの色のチャネルでもチャネル流量の枯渇率が0.5である中央は失敗率が低く、反対にチャネルバランスが偏っている0または1に近い両端は失敗率が高くなっていることが分かる。ここで注目したいのは、チャネルバランスが偏っている場合、送金金額が大きいほど（緑色や赤色の線）、失敗率が低くなっていることである。これも直感的に、大きな金額を送金するにはチャネルバランスが偏っていた方が良いことが分かる。

図2送金金額別の失敗率

ここまでの図1,2は直感的にもイメージしやすいと思われる。少なくとも自分は、そうだよねといった感じ。次は利己的ルーティングのシミュレーションについて見ていく。

利己的ルーティングはチャネル流量の枯渇と送金失敗率の上昇を招く

利己的ルーティングとは、各自の利得だけを考えて行動することで、全体的に最適な状況（社会的最適解）に比べて非効率なものとなる。この非効率さの指標を「無秩序の代償」と呼ぶ。具体的な例として、PigouのパラドックスやBraessのパラドックスが有名である。

Pigouのパラドックス

以下の単純なネットワークを想定する。頂点sから頂点tまでに2通りの経路がある。上の経路は遠回りをするが道幅が広いため複数人が同時に通っても1時間で通行できる。下の経路は近道だが道幅が狭いため交通量が増えることで所要時間も増える。交通量がxの時、所要時間はx時間となる。例えば、1単位100人とし100人が同時にsからtへ移動する場合、全員が下の経路を選択しても、各人の所要時間は1時間であり平均所要時間は1時間となる。しかし、50人が上の経路を50人が下の経路を選択した場合、50*1 + 50*0.5=0.75時間となり、全体的なコストは低くなる。

このように各人が利己的な振舞を取ることで社会的な最適解とならないことがあり、このパラドックスをライトニングネットワークにも適用しようとするのが本記事の趣旨である。

戦略別チャネル流量の枯渇度合

図3は、戦略別チャネル流量の枯渇度合を表している。ここでいう戦略とは、送金時に使う経路選択アルゴリズムのことである。また下図では、曲線が急なほど枯渇度合が低く、緩やかなほど枯渇度合が高いことを表している。

図3戦略別チャネル流量の枯渇度合

以下に各曲線における経路選択の戦略を示す

青色はコスト関数（1/capacity）を使った戦略
橙色は最小手数料（ppmが最小となるよう）な経路選択を使った戦略
緑色はCLNのコスト関数（-log((c+1-amt)/(c+1))）を使った戦略
赤色はoptimally reliable payment flows（1.6*log(ppm+1)+log(uncertainty_unit_cost)）を使った戦略（これが一番利己的！）

赤色が一番緩やかな曲線を描いており、チャネル流量の枯渇度合が一番高いことが分かる。次に枯渇が高いのが最小手数料戦略である。そして、コスト関数を使った青色と緑色の曲線が枯渇度合いが低いことが分かる。そして、無秩序の代償が一番大きいのが赤色の曲線となる。

上記では複雑な数式やら関数がでてきているが、誤解を恐れず要約すると、みんなが手数料が最小となる経路選択で送金をするとすぐにチャネル流量の枯渇を招き、チャネルサイズが大きなチャネルを経路選択にとるとチャネル流量の枯渇がしにくくなるよ、ということだと思う。これも直感に合致する。