データはいつこの世界から消えるのか

鷹見虎男氏:「Challenges to Blockchain Consistency in P2P Network」。今、あなたの手元のスマートフォン、その写真やメール、LINEのトーク履歴は、いつこの世界から消えるんでしょう。

記録メディアは、磁気や反射のような物理的な特徴が失われた時に、データを喪失します。我々がよく使っている記録メディアでは、数年から数十年。最近は耐用年数1000年を謳う光学メディアも普及してきましたが、やはり物理破壊という状況がなくなったわけではありません。

商用のクラウドストレージを利用するのもよい方法ですが、しかし、その利便性の対価に支払いがあります。つまり、クレジットカードが停止したら、結局そのすべてのデータはアクセスできなくなるのです。

あなたやあなたの家族のクレジットカード機能が停止するのは、どういう時なのでしょう。家のすべての記録メディアが物理的に破壊されるのは、どういう状況なのでしょう。

考えてください。その時あなたの家族は、機転を利かせてデータを救えるのでしょうか。それとも、あなたは家族だった人の写真に、永久にアクセスできなくなるのでしょうか。これは10年前の日本で起きたことです。そして、今日もきっと世界のどこかで起きていることです。

戦禍を生き延びた100年以上前の古文書や資料を調べながら、そんなことを考えることがよくあります。個人データの持続可能な保存、この問題に対して、まだ我々の情報技術は答えを出せていません。

趣味で実家のある地方の郷土史などを調べていると、今スライドに出ているのは手元にある資料なんですが、古い家だと江戸時代の日記や芝居の台本のようなものが、わりとカジュアルに残っていることがあります。

意外と多く見つかるのが、江戸時代の藩の触れ書きだったり、何かの通達のような書面なんです。まあ中身は「どこそこに橋を架けるから、なんとか村は何人出せ」といったようなものなのですが。つまり、たくさんコピーして広域に配布したものが、なにかの拍子に個人宅の蔵の中に残っている、というのが、データが生き残るモデルの1つなのです。

社会対立が進んだP2Pファイル共有とBitcoinの登場

2000年頃に話題になったP2Pファイル共有は、まさに広域にファイルを拡散することで、データを消すほうが難しい、という特徴を持っていました。

しかし残念ながら、あの時のブームは社会倫理と対立する方向に向かったゆえに、今に至るさまざまなわだかまりを残して、終焉に至りました。我々はあの時代の間違いと、真摯に向き合う必要があります。

一方で、都市が1つ消失したとしても、なんなら国家ごと消滅したとしても、その記録や歴史を残せる。当時のP2Pはその可能性を見せてくれた技術の1つでした。

2010年代、P2Pの世界に突如としてBitcoinが現れました。当時みんながBitcoinの何に驚いたかと言えば、それまでゴシッピングのような緩やかなレプリケーションしかできないと思われていたP2Pネットワークに、一貫性、Consistencyが持ち込まれたという点だったのです。

一貫性は、並行処理や分散システムでデータの整合性を保証するための重要な特性です。そして分散システムとして見るブロックチェーンも、根本は一貫性のあるレプリケーションを達成するという点で共通しています。

ただ、今ブロックチェーンに関する文書は、論文などもそうなのですが、暗号通貨や何やら新しい技術のような、わりと世俗的な印象が先行していて、システムや分散技術として説明できていないものが多いのです。

一方で、2021年に入ってから、Bitcoinの高値更新、NFTの大盛りあがり。今日は何かを察してブロックチェーンにアンテナを張っている人も多いと思いますが、今までのRDBや分散システムを超えて、ブロックチェーンを使ったさまざまなサービスやビジネスアイデア、それにあなた自身のスキルを拡げる時です。もう一歩の差別化を図るために、根本の分散技術の原理・原則に沿った正しい知識を着ける時がきています。

分散システムの一貫性

分散システムの一貫性は、レプリケーションをどのように行うかと強く関係しています。可用性、つまり障害耐性を持つ分散システムでは、データを複数のレプリカに分散して保存することで、あるレプリカが故障しても、残ったレプリカでサービスを継続できるように設計します。

ここで言う分散システムの一貫性とは、自分の書き込んだデータを読み出せること。それに接続先やタイミングによって、異なるデータを読み出さないことです。

レプリケーションベースのシステムでは、そんなごく当たり前のことが非常に難しくてですね。分散システムでは一貫性を達成するために、今スライドに出ているようないくつかのよく知られたメカニズムがあり、それぞれ一貫性モデルと呼ばれる分類がされています。

P2Pネットワークではどうでしょうか。これは私の観点ですが、一貫性においてクラウドやオンプレ環境にはない、P2P環境特有の難しい点が2つあります。1つは、ビザンチン故障が存在すること。ビザンチン故障とは、つまり悪意的な行動を採るノードが存在するということです。

ビザンチン故障耐性というのは、暗号理論や設計を駆使して全体の何パーセント、あるいは何台のノードまでなら耐えられるという、定量的な指標を出せる設計のことです。この点は、対象とする障害モデルが異なるだけで、分散データベースの可用性と同じ考え方です。

もう1つの大きな違いは、合意に関わるノードがシステム全体の合意を得ることなく、つまり自分の好きな時に参加・離脱するということです。

これはある瞬間のコンセンサスに関わるノードの集合を観測する術がない、という意味でもあって、これがP2Pネットワークに非決定論的な性質をもたらしている、最も大きな理由です。少し飛躍した言い方をすると、ネットワーク全体を有限状態機械と見なせなくなる、見なすのが非常に困難になるということです。

それによる具体的な問題は、ある時点の参加者がわからなければ「過半数」がわからない。つまり、投票ベースの合意アルゴリズム全般が使えなくなるということでもあります。

ブロックチェーンのコンセンサスメカニズム

そのような制約がある中で、ブロックチェーンのコンセンサスメカニズムも、分散データベースと同様に、そのレプリケーションの方法から一貫性モデルをあてはめることができます。

まず、Sequential Consistencyを達成できる代表的なメカニズムとして、BFT(Byzantine Fault Tolerance)があります。これはビザンチン障害を含んでいても、決定論的なアトミックブロードキャストを行うことができます。これは後でもう1度出てきます。

また、非巡回有向グラフのDAG構造を持つ一風変わったブロックチェーンもあります。これは既存の一貫性モデルに当てはめるなら、クライアントセントリックなCausal Consistencyに分類されるだろうと考えています。つまり、クライアントの責任で一貫性を保証するように、イベントを因果関係付けるという一貫性です。そしてDAGといえば、いつもみなさんが使っているであろうあのGitのブランチ管理も、DAGの構造に基づいています。

ここでいうクライアント中心の因果一貫性モデルは、Gitのブランチやマージ作業でもたらされる一貫性と、非常によく似ています。そして数学的構造としてのDAGは、トポロジカルソートを使って線形化、リニアライゼーションできるという特徴があるのです。

これは、ジョブ管理システムやMakefileでも行われていますが、DAGベースのブロックチェーンには、そのトポロジカルソートを行うためのコーディネーターと呼ばれるリーダー役がいて、結果的にSequential Consistencyと同等の強さの一貫性を保証できる、という特徴を持っています。

もちろん、リーダーがいるということは、すなわち暗に可用性を捨てているということを意味していますし、詳細は省略しますが、DAGは構造上のさまざまな制約を持っています。

さて、ブロックチェーンといえば多くの人が最初に思いつくであろうBitcoinのプルーフ・オブ・ワークなのですが、よく知られた一貫性のモデルには該当するものがありません。ここでは、インフォーマルな言い方ですが、プルーフ・オブ・ワークは十分に時間が経てば十分に無視できる程度に状態が収束するという意味で、確率的な、ProbabilisticなConsistencyと分類することにします。

これらの一貫性モデルは、いずれもある量のビザンチン障害が含まれていても、セイフティやライブネス特性を損なうことなく、レプリケーションを達成できています。つまり、ビザンチン障害耐性を持っています。

非決定論的なネットワーク

一方で、もう1つの大きな課題であった非決定論的なネットワークに対しては、すべてのメカニズムが解決できているわけではありません。特にSequential Consistency。これに属するメカニズムは、ほぼ投票やそれに類する決定論的な仕組みで成り立っています。

レプリケーションベースの分散システムでは、さらによく知られたCAP Theoremとも関連しています。必ずしもこの矢印の対応となるわけではないんですけども、グレーの矢印が分散データベース。緑の矢印がブロックチェーン。P2P環境やブロックチェーンでは、非決定論的なネットワークというのは、パーティショニングを暗に含んでいます。

Cを捨てて非決定論的なネットワークでのAを取るか、それとも非決定論的なネットワークの前提そのものを捨ててCを取るか。そういった選択肢として表れます。

分散データベースでもブロックチェーンでも、どのようなメカニズムがよいかという判断には、サービスにとって必要なのはCの整合性なのか、それともAの可用性なのかといった判断があります。

整合性と可用性のどちらが重要か

LINEがブロックチェーン事業を開始する時、我々が目的とするサービスにとって整合性と可用性のどちらが重要か。また、どのような一貫性が必要かという点は、とても根本的な選択でした。

我々はプラットフォーム提供者として、サービス全体のパフォーマンスやスケーラビリティ、また、コストについての責任を持つために、つまり、運用面での不透明さを排除しなければいけないという理由で、Ethereumのようなパブリックなブロックチェーンではなく、LINEとして独自のブロックチェーンプラットフォームを構築する必要があるという判断がありました。

2018年に発足したBlockchain Labは、まず暗号資産LINKを開発し、日本では2020年よりLINE BITMAXを通じて取引できるようになっています。同年、LINE Blockchainを基盤にブロックチェーンサービスを簡単かつ効率的に構築することができる開発プラットフォーム「LINE Blockchain Developers」をリリースしました。これにより既存のサービスに手軽にブロックチェーン技術を導入することができ、独自のトークンエコノミーを構築することができるようになりました。

一貫性制御とネットワーキングに関する責務を持つ「Ostracon」

Ostraconは、そのLINE Blockchain Mainnetのコンセンサス、一貫性制御とネットワーキングに関する責務を持つコアコンポーネントです。

Ostraconのコンセンサスメカニズムは、Sequential Consistency、逐次一貫性を実装しています。LINE Blockchain Mainnetのすべての処理はOstraconで強く順序付けされ、上位レイヤーのWASM VMを経由してSmart Contract、これがステートマシンに相当するアプリケーションコードで、WebAssemblyとしてコンパイルされたSmart Contractで実行されます。

WASM VMについては、別のセッションで紹介しているので、興味のある方はそちらも参照してみてください。

そしてネットワーク処理に関しても、LINE Blockchain Mainnet内の他のノードやクライアント、さらにLINE以外のブロックチェーンと相互にやり取りが可能となるように構成しています。特に今はEthereumと接続するブリッジの開発をLBBチームで邁進しています。

Ostraconの一貫性制御はBFTを使用しています。これは先のとおり、BFTはビザンチン障害耐性と、いわゆる強い整合性を持つ合意アルゴリズムです。これは、投票によってお互いが同じ値に合意していることを確認し、ビザンチン障害が全体の3分の1未満であれば、セーフティおよびライブネス特性を損なうことなく進行できます。

有名なところでは、旧来のpBFT、また、分散システムやブロックチェーン向けに最適化された設計のBFT-SMaRt、Tendermint-BFT、HotStuff BFTなどがあります。

おおむねすべてのBFTはpBFTから発生していて、図にあるように3フェーズのメッセージ交換を経て合意を形成するという構造が共通しています。何が違うかというと、合意に失敗した時に回復が早いだとか、特定の状況下でメッセージを省略できるといった改良点にあります。

その中で我々のOstraconでは、合意失敗時の回復や、投票の検証効率、駆動実績、それに再利用のしやすさ、つまり特定のブロックチェーンにガチガチに組み込まれていない、という点で、Tendermint-BFTを使用しています。

さらにOstraconでは、Tendermint-BFT以外にも新しい技術を取り入れています。1つの大きな特徴は、これはリーダー選挙に関わる部分なんですけども、リーダーが変わる時、つまりビューチェンジが発生する時に、Tendermint-BFTでは決まった順序で交代するラウンドロビン方式なのですが、将来誰がリーダーになるか予測可能ということもあって、リーダーが標的にされたり、何か共謀して悪いことを企てやすいということでもあります。

これは「改良できる点だな」と考えていて、Ostraconでは暗号理論的に偽造できない乱数、VRFという技術を使って合意に関わるノードを選出しています。つまり、固定の順序から予測不可能なランダムな選出に改良したわけです。

もう1つの特徴は、BFTベースの合意は大量の電子署名がやり取りされるのですが、それがパフォーマンスを落とす要因の1つになっています。そこでBLS署名というアルゴリズムの署名集約という特性を使って、時間計算量および空間計算量を、O(n)からO(1)にする改良を加えています。

BLSもVRFも暗号理論の範疇なので、このプレゼンでは扱いませんでしたが、いずれも興味深い技術なので、ぜひ調べてみてください。

もっと良い方法があればその方法を採用する

現在のOstraconでは、この3本柱を機能的な特徴として開発しています。我々はTendermint-BFTの強い整合性によって、NFTや権利の証明など、強い一貫性が重要視される業務をLINE Blockchainに取り入れることができました。

世の中の多くのブロックチェーンは、その目的自体に特定の技術や理論の検証実験を欠けています。しかし、我々のゴールはこれら技術の検証実験ではありません。事実として、暗号通貨のLINKを保存している初期のブロックチェーンではpBFTでした。

一方、今みなさんが利用できるLINE Blockchain Developersのバックエンドに配備されているブロックチェーンは、すでにTendermint-BFTが使われています。もし、今よりも先の時代のユーザーにとって、もっと良い方法があれば、我々は常にその方法を採用する準備をしています。

以上、このプレゼンがみなさんの未来にとって何か新しい視点やアクションを起こすきっかけとなれば幸いです。LINE Blockchain Engineering Teamの鷹見がお届けしました。