2017年4月14日にユナイテッド・ビットコイナーズ株式会社のブログに載せたものを移動しました。
今井です。
Lightning Networkの中でも重要なルーティングアルゴリズムの部分を説明したいと思います。
ホワイトペーパーを勉強される方は、coincheck光田さんの翻訳(全５章中の第２章まで)もこちらにありますので、そちらも参考にしてみてください。
論文情報
- Title: Flare: An Approach to Routingin Lightning Network
- Author: Pavel Prihodko, Slava Zhigulin, Mykola Sahno, Aleksei Ostrovskiy, Olaoluwa Osuntokun
- Year: 2016
- URL: http://bitfury.com/content/5-white-papers-research/whitepaper_flare_an_approach_to_routing_in_lightning_network_7_7_2016.pdf
背景
Bitcoinの問題点やその背景については、TumbleBit論文輪読会資料を公開の「Bitcoinの問題点」に書いてあるため、こちらを参照してください。
Lightning Networkとは？
Bitcoinのスケーリングの問題を解決する方法の一つとして開発されているものです。
通常、BitcoinはProof of Workを使ってブロックチェーンにトランザクションを格納していきつつ進んでいきます。ご存知の通り、この格納していくことを承認(confirmation)といい、平均して１０分間に１回行われていきます。
しかし、大きな金額を送る場合であればよいですが、毎回毎回トランザクション手数料がかかる(2017年4月現在、50円程度)のはイヤですし、レジで１０分も待つのはイヤです。
居酒屋のツケのように、毎回毎回払うのは面倒なのである程度まとまって払うということはよく行います。Lightning Networkでは、毎回毎回ブロックチェーンにトランザクションを送っていくのではなく、このまとまって払うということを行うことで送金１回あたりのトランザクション手数料を安くし、１０分間も待たなくてもよいということを実現しています。これをオフチェーンでの取引といいます。
ただ、居酒屋の店主は見ず知らずの人からツケを受け付けたいとは思いません。あとで払ってもらえるかわからないからです。なので、ツケをできるようにするにはある程度居酒屋に通う、またはデポジットを払うなど最初は手間がかかります。
では、この手間を省くにはどうすればいいかですが、例えば、長い付き合いがある親友がよく行っている居酒屋に一緒に行き、親友にツケをしてもらいます。自分は、すでに信頼関係がある親友に対してツケをします。このようにすると、すでにある信頼関係を使って行ったことのない居酒屋でツケをすることができます。
Lightning Networkでは、このようにすでにあるツケをできる関係(チャネルといいます)を利用して、新しくチャネルを作るコストを最小にしつつ、取引を高速化しています。
親友を間に挟むだけであればうまくいきそうです。では、間に２人挟んだらどうでしょうか？
２人でも同じことができますが、間に入る人が増えてくると友達の友達が悪人ということもあり得ます。すると、自分が払ったツケ分のお金をその悪人が持ち逃げしてしまい、居酒屋に払われないということも起こります。
これを避けるために、HTLC(Hashed Time Lock Contract、資金ロック時間があるハッシュを伴う契約)を使って持ち逃げできないようにしています。上図のHがこのハッシュに対応するものです。HTLCの話は、Flareの話から離れていってしまうので別の機会に説明できればと思います。
現在の主要なプロダクトはlnd, lit, lightningdの３つあり、http://www.unitedbitcoiners.com/blog/ae89f52fcd6 にまとめたものがあります。
Flare概要
Lightning Networkはとても魅力的なものですが、「自分から払いたい相手までのルートがある」というのが重要になります。
Flareは、このルートをネットワーク全体から効率的に発見し、しかも使いやすい有用なルートを見つけるためのルーティングアルゴリズムの１つです。
なぜルーティングアルゴリズムが重要なのか？
Lightning Networkの意味として処理の高速化とトランザクション手数料が下がる点を挙げましたが、これはルーティングアルゴリズムの性能次第で以下のようなものも実現できます。
- １取引あたり0.1円未満
- 全世界で１秒間に1000万取引以上
- トランザクション手数料が0.000001%未満
これは、ある特定団体のサーバ群を使うのではなく、P2Pネットワークを使うことで達成できると思っています。ある人からある人にお金を送る際に、DBへの書き込みとレプリケーションを行うかと思います。必ずあるDBにはリクエストを送る必要があり、取引数はそのDBの性能に依るわけです。
しかし、P2Pネットワークで賢いルーティングアルゴリズムが正常に稼働すると、アクセスが集中するノードを避けて送金でき、P2Pネットワークノードは誰の許可を取ることなく立ち上げることができるため、全世界での秒間取引数を大きくできるのではと思います。
ただ、例えば、クレジットカードVisaの場合、平均的な１秒あたり取引数が１０万件程度、瞬間最大風速が１００万件程度のようです。これと比べると、秒間１０００万件という性能は不要な気がします。
個人的に、このような性能はマシン間での取引に使えるのではないかと思っています。交通渋滞の緩和や広告費を直接個人に払うなどといった現時点で存在しない行動インセンティブモデルのよる社会モデルに使えるのではないかと思っています。
このため、ルーティングアルゴリズムがどれだけ賢いかというのはとても重要です。
Flareの仕組み
Flareでは、ルート発見プロセスを以下の４つに分けています。
- ホップ数近傍ノードの状況把握 -> Neighbor discovery
- ビーコン(ノードアドレス近傍ノード)の状況把握 -> Beacon discovery
- 送金先ノードの近傍状況把握 -> Route selection
- ルートのランク計算 -> Route ranking
P2Pネットワーク全体の状況を各ノードが逐一把握でき、無限の計算リソースを使って最適ルートを計算できれば何の問題もないのですが、それはできません。あるノードは近傍のノード情報しか把握できず、最適ルートもある有限時間内に計算を終わらさなければいけません。
このため、どのノードとどのノードがチャネルを張っているかというルーティングテーブル情報をいかに効率的に分散し、そして分散しつつも必要な情報に基づき最適ルートを計算するかがカギとなります。
ルーティングテーブルは以下のようなものです。
ルーティングテーブルはある限られた範囲の情報だけでは意味がありません。なぜなら、それだと新しくチャネルを張らないと送金できないノードが発生しやすくなるためです。
できるだけP2Pネットワーク全体に手を伸ばせるようにするために、ホップ数近傍ノードとビーコンとに分けてルーティングテーブルを管理します。ビーコンはノードアドレス近傍なのでP2Pネットワーク全体にランダムに分散しており、ホップ数で言った時にとても遠くのノードになる可能性が高いのです。
ホップ数近傍ノードの状況把握
ノードは、新しくチャネルを開いた時にすでに接続しているノードにルーティングテーブルを送ります。
このときに送られるメッセージが「NEIGHBOR_HELLO」です。
使われるメッセージは以下の４つです。
- NEIGHBOR_HELLO
- NEIGHBOR_UPD
- NEIGHBOR_AKC
- NEIGHBOR_RST
ビーコン(ノードアドレス近傍ノード)の状況把握
ホップ数は、自身が１ホップ目(場合によっては０ホップ目)、自身に接続しているノードが２ホップ目、その先にさらに接続しているノードが３ホップ目と続いていきます。
ノードアドレス近傍は、XOR距離で測った距離です。ノードアドレスは256bitの整数で、例えば、3bitノードアドレス空間でいうと、110との距離は
- 000 -> 2
- 001 -> 3
- 010 -> 1
- 011 -> 2
- 100 -> 1
- 101 -> 2
- 110 -> 0
- 111 -> 1
のようになります。bitをいくつ変えたら一致するかですね。これは、Kademliaやcjdnsと同じような形をしています。
ただ、ノードアドレスとIPアドレスとの紐付けをどのようにしておくのかはホワイトメーパーにありませんでした(見つけた方がいたら教えてください)。
ビーコン探索時はまず「BEACON_REQ」メッセージをアドレス近傍ノードに送り目印をつけます。最終的に、ビーコンに定めたノードに対して「BEACON_SET」を送ります。
メッセージは以下の３つです。
- BEACON_REQ
- BEACON_ACK
- BEACON_SET
送金先ノードの近傍状況把握
ここまでは、静的情報であるチャネル開閉だけを使ってきました。P2Pネットワーク全体を把握するときには、チャネルのbitcoinキャパシティーなど動きやすいものは捕まえにくいので無視しておきます。
ただ、具体的にルートを見つけるためにはチャネルのbitcoinキャパシティーは不可欠です。このため、送金元は送金先にルーティングテーブルを要求し、まずルート候補を１０個ほど見つけます。このとき、送金元と送金先のルーティングテーブルだけを使ってもルートが見つからないことが多いため、ビーコンのルーティングテーブルも加味してルート候補を探します。
- TABLE_REQ
- TABLE_RESP
ルートのランク計算
ルート候補が１０個ほど見つかると、この時点で初めて以下の動的情報を用いてランク計算を始めることになります。
- チャネルbitcoinキャパシティー
- 転送手数料
送金者はすべてのルート候補に対して以下のメッセージを送ります。
- RANK_POLL
送金先までの間にある各ノードはこのメッセージに上記の動的情報を載せて次に送ります。このとき、オニオンルーティングを用いておき、どこからメッセージが届いたかは秘匿してプライバシーにも配慮しておきます。
最後に送金先は届いたメッセージを送金元に送り、ホップ数も含めランク計算に必要な情報が送金元に集まることになります。
最短経路アルゴリズムとしては、ダイクストラ法が使われます。
有用だと判断されたルートはキャッシュに記録しておき、同じ送金先が生じた場合にはまずこのルートの状況を調べることでルート候補を絞り込む処理を省くことができます。
実験結果
以下のWatts - Strogatz グラフで実験(http://gc.sfc.keio.ac.jp/class/2006_19872/slides/07/60.htmlから引用)
このホワイトペーパーとは別に、2016年9月に行われたAcinqによる実験。 http://www.coindesk.com/bitcoins-lightning-network-milestone-acinq-routing/
数十万ノードに対してFlareは適用でき、0.5秒以内に80%のルート選択ができたとのこと。
最近の動き
BOLT
- https://github.com/lightningnetwork/lightning-rfc/blob/master/04-onion-routing.md
- https://github.com/lightningnetwork/lightning-rfc/blob/master/06-irc-announcements.md
- https://github.com/lightningnetwork/lightning-rfc/blob/master/07-routing-gossip.md
presentation of roasbeef(Olaoluwa Osuntokun), lightning lab
