はじめに
エンジニアの光田(@34ro)です。
先日CoinDeckでこのような記事が公開されました。
Lingtning NetworkのテストによってBitcoinのスケールアップが射程圏内に入った
Lightning Test Moves Bitcoin Scaling Into Striking Distance
AWSで2500台のインスタンスを立ててLightning Networkのルーティングアルゴリズムの検証を行ったとのこと。少なくとも数十万ノードにスケールできると結論付けています。運営主体のないビットコインでここまで研究を進めるのはすごい熱量です。
ここで紹介されているFlareというルーティングアルゴリズムに関するホワイトペーパーを読み進めると、ビットコインの技術界隈はこんなに進歩しているのかと驚くばかりです。大変興味深いものだったので前半部分を翻訳してみました。前半部分だけでもこれまでのLightning Networkの研究がまとめられて勉強になりました。
これまであまりLightning Networkを追ってなかったという方の参考になればと思います。
Lightning Networkが生まれた背景
ビットコインのスケール問題
ビットコインには1つのブロックに詰め込めるトランザクションのデータ量に限りがあり、多くの人が同時に送金しようとすると市場の原理によって手数料が高くなるという課題があります。
そもそも価値を移動するだけなら必ずしもブロックチェーンに書き込む必要はありません。送金を時間でロックした上で、「いつでもブロックチェーンに書き込んで送金を確定できる」というだけで十分ではないでしょうか。そのような発想の元、ブロックチェーンに書き込むことなく送金(価値の移動といったほうが正確かもしれまんせん)を行うためにいろいろな手法が考えられてきました。
payment channel
その1つがpayment channelです。古くは2011年頃から議論されていたようです。ビットコインアドレスを持っている者同士でパーティーを作り、パーティー内の送金はブロックチェーンに書き込まずにトランザクションだけ作ることで送金手数料を浮かせるという手法です。
パーティーの管理者への信頼が必要なのでビットコインの思想を一部妥協したものでした。payment channelのようにブロックを介さないことはoff-chainと呼ばれます。payment channelだけでブログ1つ分の分量になりそうなので詳細はまたの機会に。
payment channelからLightning Networkへ
Lightning Networkでは中央機関を挟まず、誰でも参加可能なネットワークでoff-chainな送金を実現しようとしています。Lightning Networkは多数のpaymant channelが集まることで機能します。
送信者と受信者の間をpayment channelで繋いで送金する点はRippleの送金に似ています。経路を見つけるためにネットワークの情報を集めるのですが、そこでもまたビザンチン将軍問題の登場です。
中央機関が無く、誰でも参加できるとなると悪意のあるノードや消滅するノードの存在を考慮しなくてはいけません。ビザンチン将軍問題なので完全な解決策はおそらく存在しないのですが、ここでも「実用的な」解なら存在するはずです。
さらにLightning NetworkはVISA並の大規模な送金プラットフォームを目指しています。参加するノード数は膨大で一台のノード内に全体のネットワーク情報を保持することは現実的ではありません。
このホワイトペーパーでは実用的な方法でより効率的に経路を見つける手法を提案しています。
これまでいくつかのルーティングアルゴリズムが考えられてきましたが、実運用には不安のあるものでした。そんな中今回Bitfuryによって考案されたルーティングアルゴリズムがFlareです。2500台のノードで実験を行ったとのことなので大いに期待できます。
以下Flare: An Approach to Routingin Lightning Networkの翻訳
Flare: Lightning Networkへのアプローチ
要約
このホワイトペーパーでは決済のルーティングを行うためのハイブリットなルーティングアルゴリズムであるFlareについて説明する。このアルゴリズムはルートをより早く発見することを目的としている。これはそれぞれのノードがLightning Networkのトポロジーの情報を積極的に集めることで達成される。ここで集められた情報はノードのアドレス空間に存在するホップ数が近いノードのへpayment channelだけでなく、beaconノードへの経路の情報を含んでいる。beaconノードの用途はランダムに選ばれたfeeler(触覚)ノードの局所的な視点を補助することである。localノード, beaconノードの連携により、経路を見つけるときに高確率で経路の状態数を最小化できる。我々は経路アルゴリズムのシミュレーションを行い、少なくとも10万ノードまでスケールすることを発見した。
本文
ビットコインは世界で最も広く使われ、価値のある仮想通貨であり、仲介者や保管場所を信用することなく誰もが価値を送ることができる。ビットコインはスクリプトを用いてプログラムで資金移動を指示するシステムを備えている。
ビットコインは10分の間隔でトランザクションをブロックに集約する。ビットコインによる決済が実質的に取り消せなくなるのは6つの承認(5つのブロックが後ろに作られるか)、1時間経つかである。送金手数料のため、2,3セントのようなマイクロペイメントは承認まで長い時間がかかる。この制約に対してビットコインの利点(セキュリティ、抵抗勢力の検閲)を保ち、瞬時に行われる決済処理や手頃な価格のマイクロペイメントを保証する上位のレイヤーの解決策が必要である。
Lightning Network(以下LN)はこの問題に対する１つの有望な解決策である。LNはブロックチェーンにトランザクションを記録すること双方向のpayment channelのとして動作する。LNはディセントライズド(少数の管理者によって操作されていない)でトラストレス(信用のあるサードパーティに資産の保管を委ねる必要がない)のために設計されている。個人のトランザクションをブロックチェーン上に作成すること無く、ネットワークのセキュリティはビットコインに組み込まれているスマートコントラクトのスクリプトによって保証される。LNはUTXOを用いるような他のブロックチェーン上にも展開可能である。それだけでなくLNはinter-ledger paymentsにも利用可能だ。他のpayment channelネットワークのコンセプトが浮かび上がってくるが、ここではトラストレスでディセントライズドな世界というビットコインの精神を含んだコンセプトに向ける。
LNの決済はブロックの承認を必要としない。したがって通常ほぼ一瞬で完結する。LN上の1つの決済はいくつかのpayment channelを通る。しかしながら、これらの決済はアトミック(全て成功か全て失敗)になるようにデザインされている。そのため、LNはマシン対マシンのトランザクションや瞬時の決済が要求される小売業のPOS端末でも使うことができる。LNはビットコインのマイクロペイメント(ソーシャルサイトのチップ)、マイクロペイメントのストリーム(オンラインゲームでの支払い)に拡張させ、ビットコインの経済圏を拡張するだろう。
LNを特徴づける点は仲介者を信用することなくネットワーク越しにpayment channelをルーティングできることである。決済を完結させるためにpayment channelを管理する運営者を必要としない。そのため決済のルーティング(送信者から受信者への経路が時間や費用のような適切な基準によって最適化されること)がLN特有の問題である。決済のルーティングに対する完全な解決策がないとLNを成立させることはできない。
これまでの研究
これまで発表されたホワイトペーパーではchannelを開いたり閉じたりする方法、決済の輸送、中継ノードが非協力的な場合にロールバックする方法について説明していた。これらではルーティングに関する問題はカバーされていなかった。
Hashplexによる実装には全てのノードがネットワーク全体のノードの情報を持つというシンプルなルーティングメカニズムが組み込まれていた。しかしこれではスケールの問題がでてきてしまう。加えて、初期の実装では完全にテストされていない。
The Bitcoin Lightning Network: scalable off-chain instant payments
A fast and scalable payment network with Bitcoin duplex mi-cropayment channels.
Reaching the ground with Lightning
我々の結論
我々にとってはまず経路を見つけることが最初のステップだ。我々がFlareと呼んでいるアルゴリズムは信用のない情報源を元にルーティングし、少なくとも数十万ノードにスケールできる。我々は妥当性をシミュレーションした結果についても記述する。最後に我々はpaymant channelの検証手続きを楕円曲線Schnorr署名で行うことを提案する。
1 Lightning Network
前述の通り、Lightning Networkはビットコインのようなスクリプトを用いたブロックチェーンならどのようなものの上にも構築できる。このホワイトペーパーではビットコインのブロックチェーン上に構築することを検討するが、このほとんどの結果はあまり苦労すること無く他のブロックチェーン上にも適用出来るはずだ。
LNのホワイトペーパーのように図1のようなノードを構成するとする。それぞれのノードを識別する公開鍵は長期的に使用する。ここではビットコインの主な暗号システムであるsecp256k1楕円曲線暗号を使うことを想定する。これはもしLN上の決済の経路が確立しなかった場合、受け取りての公開鍵から一意に決められたビットコインアドレスに送れるといったフォールバックメカニズムを用意するためである。
ライトニングノードはSPVノードまたはフルノードの上で運用する。それぞれのライトニングノードは他のライトニングノードに対し双方向のpayment channelを開き、特定の形式のトランザクションを送ることで通信する。このトランザクションはそれぞれのノードがchannel内にロックしている金額や、参加ノードを特定するための情報を含んでいる。channelのキャパシティの合計は一定で、channelに接続している各ノードが投じたトランザクションの合計金額に等しい。その一方で、お互いの合意があればノード間の価値の分配はoff chainに変えることができる。接続は一方的に閉じることができるので、協調しているパーティー内で接続を閉じる必要はない。
各ノードはchannelの経路を通じて値を送ることでLN上の他のパーティーに送金することができる。お金をロストするリスクやサードパーティーを信用することなく資金移動を実現するために、LNはhashed time-locked contracts(HTLC)の仕組みを導入する。各ノードはchannelを通じて送金のためにごく僅かな手数料を支払う。
オリジナルのホワイトペーパーや、開発者コミュニティの一般的な見解の通り、LNに対していくつかの要求がある。
図1
要件(P2Pネットワーク)
全てのノードは送信者、受信者、ルートを決めるハブという役割を同時に満たす。現在のところ、小さなノードによって作られたチャネルはLNが効率的に動作するための十分な流動性を生み出せないという理由から、コミュニティの一部のメンバーはLNはhub-and-spokeネットワークとしてのみ実現できると考えている。しかし、LNがローンチされたときに高スループットなノードがネットワークにいた場合、LNは最初からhub-and-spokeでなくとも維持できると考えている。もしディセントライズドなネットワークをベースにしたルーティングが実際に稼働することができたら、ディセントライズなこと、敏捷性、一部の障害が全体に影響を与えないという安定性の観点からネットワークに利益をもたらす。
LNをP2Pネットワークとしてデザインしたとしても、我々は他のトポロジーがよりよく機能していることを確かめ、支えていきたい。
要件(ソースルーティング)
(※ソースルーティングとは中継地点を送信者が予め指定する経路制御方式)
我々は以下のような理由からLNではソースルーティングが用いられると考える
・ユーザのプライバシー：torのようなデータ輸送で用いられるソースルーティングは仲介ノードが送り主と送り先を知ることがないのでユーザのプライバシーが守られる。
・抵抗勢力の検閲：ユーザプライバシーによって仲介ノードは送信者、受信者のアイデンティティにもとづいて検閲できない。
・手数料の予測：それぞれのchannelのオーナーによって運営されるLNノードは決済を通じていくらかの手数料を要求するだろう。これはルートが異なれば費用も変わってくるということだ。そのため送金者は料金を最適化し、ルート選びの最終的な決定を下すことに関心があるだろう。さもなければ送金者は料金を予測できないということになり、他のノードは最も低コストな経路に最適化する理由がなくなる)
・時間を固定した予測可能性：もし、非協力的な仲介ノードの存在により決済がその時点の状態でルーティングされない場合、送信者のノードはさらに時間を使って送金を補うことを必要とする(この可能性についてはLNのホワイトペーパーで紹介されているHTLCメカニズムで説明されている)
ソースルーティングでは送信者が最適なルートを決めるために、料金と利用可能なchannelの許容量の情報を得なくてはいけない(どのノードがオンラインか等)。そのため、チャネルのオーナーのいずれかにchannelの情報を要求するための上位レイヤーのメカニズムが存在する。
これによりビットコインユーザーの期待を満たせるため、LNによってビットコインの主な思想は保たれるだろう。
要件(トラストレス)
LNはトラストレスな環境にある。お金の安全性をサードパーティーに委ねていないということだ。
この目的はLNのホワイトペーパーで紹介されているHTLCメカニズムによって大部分は達成されている。
要件(高速な決済処理)
送金完了に1時間近くかかるようなビットコインの送金に対し、LNの１つの目的は高速なマイクロペイメントである。リアルタイムなマイクロペイメントやIoTアプリケーションに適合するため、1分以内か理想的には数秒で決済が完了することが必要である。
このホワイトペーパーでは各ノードが先を見越してネットワークの情報を集めることで高速な決済を達成した(詳細はsection 3)
要件(セキュリティ)
ルーティングアルゴリズムは安定してルートを見つけることを可能にする。
ランダムな要素を含んだルーティングはフォールバックメカニズムが組み込まれていることが前提である。グラフ的に遠すぎたり、経路が存在しない等の理由からもし送信者が受信者までのルートを見つけられなかった場合、いつでもブロックチェーン上で直接送金することもできる必要がある。新しいchannelを開くことはトランザクションの承認時間や手数料の観点から高価であるが、ネットワークのグラフを時間とともに改善していくためには価値のあることだ。
要件(運用コスト削減)
ビットコインウォレットは一部SPVが使われている。高いセキュリティを保ちつつ、ストレージ容量やコンピュータリソースを削減するためである。ライトニングノードもSPV上で動作させ、運用コストを下げることが必要がある。
要件(拡張性)
LNは少なくとも数百万ユーザが使えるよう適切にスケールしなくてはいけない。
要件(自動化)
ルーティングアルゴリズムはLNノードの操作性を保つため、トランザクション手数料などに対し、ある程度高いレベルの選択の自由が必要である。ユーザは望まない限りアルゴリズムの技術的なパラメータを調整したり、手動でルーティングを行う必要がないようにすべきだ。
これらの要求によれば、ルーティングの問題は以下のように定式化される。
問題1
送信者Sが受信者Rへのpayment channelを見つけるうえで以下のような制約がある
・ルーティングは送信者Sがアクセスできる情報にもとづいて行われるべき。ルーティングの決定はSによって行われる。(トラストレスな環境では信頼できる第三者に委託できない)
・アルゴリズムは送信者のネットワークの情報がメモリ不足等により不完全だったり、古くなっていることも考慮しなくてはいけない
・ルートを発見する処理は時間、お金をあまり使わずに実行されなくてはいけない。
・ルートの発見は明確なコストの機能と送信者のネットワークの情報によって行われなくてはいけない。(ルーティングアルゴリズムはルート上の累積手数料の最小化を目指す等)
2 ルーティングアルゴリズムの概要
この章では我々が提案する1やそれに類似したpayment channelのルーティングアルゴリズムの概要を提示する。
2.1 以前のアイデア
2.1.1 hub-and-spoke network
ビットコインコミュニティはいくつかのルーティングアルゴリズムの可能性を提案してきた。最も古いアイデアはノードを2つのクラス(決済を行うウォレットノードと経路を作って手数料を受け取るルーティングノード)に分割することだった。全てのハブを把握することであらゆるノードへの経路を見つけることを高い確率で保証するので、このスキームではルーティングを最初から効率化できる。同時にこのスキームは中央集権化する傾向がある。それゆえウォレットノードがオンラインになっておくことによるインセンティブがない。(とあるウォレットに決済情報が送られたとき、送金処理が完結するまでそのノードをハブにつなぎとめなくてはいけない)。もう一つの不都合な点としてハブは障害耐性を欠いていることである。もしネットワーク上のハブが2,3しかないときにその2つが障害に見舞われたとき、ネットワーク自体におそらく障害がおこる。
2.1.2 グローバルビーコン
もう一つ別のアイデアはグローバルビーコンによってランダムにいくつかのノードを選択する方法だ。ビーコンノードは決まったスケジュールでローテーションする。全てのノードはビーコンへの経路を見つけることを試み、経路情報を修復し、送金に使用する。このスキームは一部のグループに支配されることがないので前のより、よりディセントライズに感じられる。しかしながら、グローバルビーコンのノードは他に比べてより収益性が高く、Sybil attack(ビーコンノードになるためにニセのノードを増加させる)に通じる。さらにビーコンの情報が公開されるため、ネットワークを混乱させるためにDoS攻撃のターゲットにされかねない。グローバルビーコンは処理できるだけのネットワーク帯域、計算力、payment channelにストアされている価値が十分でなくてはならない。それゆえ、ビーコンノードの候補者はかなり限られる。最後に、ビーコンノードは選ばれている間、多くのchannelを作らなくてはいけないが、次のビーコンサーバが現れると無駄になってしまう。
2.1.3 ローカルビーコン
ビーコンのアイデアが進化し、個々のノードがビーコンノードのリストを持つという提案がなされた。決済情報が送られるとき、送信者と受信者はお互いのビーコンリストを比較し、交差を見つけることでルーティングを行う。ローカルビーコンはネットワーク内のトラフィックをより均一化させる。加えて、このスキームは全てのノードは他のだれかのためのビーコンになる機会がある。そのためトランザクション手数料はグローバルビーコンに比べより平等に分配される。このことがノードにオンラインにしておくインセンティブとして働き、ルーティングが送れる金額の許容量を改善した。
2.2 同様の問題を解決するためのルーティングアルゴリズム
モバイルアドホックネットワーク(MANET)の紹介なので省略
3 ハイブリットなルーティングアルゴリズムの提案
1章の要件を満たすために、proactiveとreactiveの状態を含んだハイブリットなルーティングアルゴリズムを定義した。Flareと呼んでいる。このアイデアはLNに関する情報を以下の2つに分けることができることを前提としている。
– ゆっくり変わるか、不変な情報(payment channel)
– 急速に変化する情報(ノードの状態や資金の分配、手数料など)
それゆえ、新しく開いたpayment channelや閉じたpayment channelの情報はproactiveに集める価値がある。一方で、変化は予測できないことはproactiveに変化の情報を掴むことにはあまり意味がない。
図2はルーティングアルゴリズムである。
図2：LNノードのビジネスロジックを含んでいるのはrouting moduleの部分。このモジュールの目的は意図した送信相手に特定の送金額を送るための決済のルートを提供すること。これを達成するため、ノードはproactive(隣接しているかビーコンによって得る)またはreactive(ランク付けされた候補者を選ぶ)に得たネットワークの情報を活用する。集められた情報はルーティングテーブルに置かれ、ノードの管理者のリクエストや他のノードからのリクエストを処理する。
ルートの発見(proactive part)
それぞれのノードはスケジュールに従いルーティングテーブルの情報をアップデートする。ルーティングテーブルはネットワーク上に存在する幾つかの経路のサブセットだ。ルーティングテーブルは受信者までの経路があるかないか判定することと、経路を見つけるためのビーコンノードを決定するために構築する。
最初にルート発見したあとにはそれぞれのノードは隣接したノードの非常に明確な情報を持っている。ビーコンの目的は隣接ノードを超え、ランダムにノードと接合することでネットワークの見通しを良くすることにある。
結果として、近くは良く見通すことができ、ランダムに触覚で遠くと繋がり、ノードから見たネットワークはfog of war(戦雲?)のようになる。このことが高い確率で全てのノードに到達できることを維持しながら、ネットワークのサイズが増えたとしても経路の状態数を空間の複雑さの対数に維持することを可能にする。
経路の選択(reactive part)
ノードがLNを通じて決済すると決定したとき、自身と受信者のルーティングテーブルの組み合わせから、可能なルートを見つける。もし2つのルーティングテーブルを使って適切な経路を見つけることができなかったら、受信者のビーコンか注意深く選ばれた別のノードのルーティングテーブルが使われる。ルートを見つけようとすることでこれらのノードは受信者への経路を他のノードへの経路よりたくさん知ることができる。見つかった経路は事前に定義されたコスト関数(部分的にルートのような静的な情報やfeeや使うchannelといった動的なに基づく)によって順位付けされる。この順位付けは1つの独立したステップを順番に踏むのではと考えている。
– 静的な順位：ルーティングテーブルのみによる静的な情報に基づき、相対的に小さなサンプルでルートの候補を導く。
– 動的な順位：動的な順位に基づき、onion wrapped polling messageを全ての候補のルートで送り、最新の経路の情報を集める(onion wrappedはオニオンルーティングの用語?)
このヒューリスティック情報を正確に保全しながらreactiveなステップを短くする。
最後に全ての情報が集まり、動的に順位付けられた後、送信者は送金のために最適なルートを選ぶ。我々は処理を短縮化するために、動的なデータを十分に集めたら時々動的なランキングを止め、瞬時に送金を行った。
障害耐性のため、reactiveなステップにいくつかの経路候補があったほうがいい。もし経路内のpayment channelつのノードが応答しなくなったら、次のパスを見つけ次第再送できる。もし他に経路が見つからなかった場合、連続してビーコンノードにルーティングテーブルを要求し、手続きを続ける。アドレスの距離によってビーコンを選ぶメソッドによって高い確率で経路が見つかることはcjdnsに似ている。
proactive stepのアルゴリズムはsection 3.2、3.3、3.4に記述。section 3.5、3.6にはreactiveなルーティングについて記述した。
ネットワークの仮定
我々はLN上のネットワークを抽象化しているがこれは別の議題である。我々はどの2点も間に経路が存在し、相互に通信できる。同様にLN上のノードはいつでもLNにいるノードかどうかを判定できる。
ノード間の通信は信頼でき、完全性を保証し、電子署名が施され、(単調に増加するシーケンスを含むなり、タイムスタンプを含むなりして)repay attackに対して脆弱でない。必要であればオニオンルーティングスキームを利用することができる。
各ノードの時計はだいたい同期され、時間差が問題になることはない。
悪意のあるノードに対して懲罰的な処理はしなかったがこれはまた別の問題。
翻訳ここまで
ざっくりした要約と感想
ルーティングに必要な情報をreactiveに貯めつつ、ビーコンでproactiveに集めるという点が新いようです。近くのネットワークは詳細に、遠くのネットワークはビーコンまでの経路を把握することでノードが増えても蓄積するデータ量を節約できます。把握しているネットワークを図にすると雲から触覚が伸びているような状態になります。いざ送金しようとしたときに、送信者と受信者が遠く離れていてもこの触覚が交差していれば経路が見つかるわけです。
payment channelを作っておいて経路に選ばれると手数料を受け取るというメリットがあり、Lightning Network全体の輸送可能な量を増やすという貢献ができるので、ここもマイニングのように金銭的モチベーションをうまく活かした手法だと感じました。