ブロックチェーンの前にあったもの：ステートマシンレプリケーション

分散システムの信頼性を支える基盤技術は、1980年代に暗号通貨を全く想定していなかった研究者たちによって開発された。本エピソードでは、a16z cryptoのリサーチ責任者であるTim Roughgardenと同パートナーのIttai Abrahamが、チューリング賞受賞者でMIT教授のBarbara Liskovを迎え、フォールトトレラント分散システムの進化を辿る。Liskovは、プログラミング言語から分散システムへの研究の転換、Viewstamped Replication（ビュースタンプ・レプリケーション）プロトコルの開発、そしてPractical Byzantine Fault Tolerance（PBFT）へと至る道筋を詳細に語る。これらの技術は、今日のブロックチェーンプロトコルの根幹を成す状態機械複製（State Machine Replication）の概念を具現化したものであり、理論と実践の橋渡しとしての重要性が浮き彫りになる。さらに、AI時代におけるコンピュータサイエンス研究の未来や、若手研究者へのアドバイスにも言及し、システム研究の永続的な価値を示唆する内容となっている。

0:00分散システム研究への転機：プログラミング言語からフォールトトレランスへ

Barbara Liskovは、1970年代にデータ抽象化を実現するプログラミング言語CLUの開発を主導した後、1980年頃に分散システム研究へと軸足を移した。この転換は、彼女自身が「研究としては十分やった」と感じたことに加え、Bob Kahnの論文で述べられた「分散コンピューティングの夢」—ネットワーク上の異なるノードで動作するプログラムが相互に通信する世界—に触発されたことに起因する。当時、そのようなシステムを構築する方法は誰も知らず、Liskovはこれを「素晴らしい問題」と捉えた。

興味深いのは、この転換が完全なピボットではなかった点である。彼女の最初の分散システムプロジェクトは、CLUを拡張したプログラミング言語Argusの開発だった。Argusでは、CLUの抽象データ型を継承しつつ、ネットワーク上の各ノードに常駐し、他のノードから呼び出し可能な操作を提供する「ガーディアン（guardian）」という新しいオブジェクトを導入した。これにより、分散プログラムは複数のガーディアンがそれぞれのノードで動作し、相互に通信する形で構築された。Liskovは、CLUで並列処理を扱わないと決断した経緯を振り返り、Argusではその並列性を「より興味深い形」で扱えるようになったと述べている。具体的には、複数のユーザーが並行してリクエストを発行する状況に対応し、さらに複数ノードをまたがる計算の原子性を保証するために、データベースシステムからトランザクションと2相コミットプロトコルを採用した。このように、ArgusはCLUの延長線上にありながら、より複雑な環境での新たな問題に取り組むものだった。

Liskovは、この研究の根底にある「モジュール性」の重要性を強調する。彼女は、大規模プログラムの構築においてモジュール性が全てであり、後にこの考え方が数学の定理の証明と類似していることに気づいたと語る。定理の証明では、全体を一つの塊として扱うのではなく、補題に分割し、それぞれの補題を独立して証明する。これは、各モジュールが仕様を持ち、他のモジュールのコードを見ることなくそのモジュールのコードの正しさを証明できるモジュラープログラミングと全く同じ構造である。Liskovは、自身が数学専攻であったことが、このような考え方を自然なものにしたと述懐している。

12:04Viewstamped Replication：実用的なレプリケーションプロトコルの誕生

1980年代半ば、Liskovは学生のBrian Okiとともに、複製ファイルシステムの研究に着手した。当時のシステムコミュニティでは、ファイルシステムの複製はロックを用いて実装するのが一般的だった。しかしLiskovは、遠隔地のユーザーにロックの解放を依存するこのアプローチは「非常に悪い解決策」だと直感した。彼女は、Argusでの原子トランザクションの経験から、処理の主体をユーザーではなくレプリカ側に移すべきだと考えた。これがViewstamped Replication（VSR）の出発点である。

VSRの核心は、プライマリ（主レプリカ）がバックアップ（副レプリカ）に指示を出すプロトコルと、プライマリが故障した際にバックアップが新たなプライマリを選出する「ビューチェンジ（view change）」プロトコルにある。従来の2相コミットプロトコルには「厄介なポーズ（embarrassing pause）」、すなわちプライマリが故障するとシステム全体が停止する脆弱性があった。VSRは、プライマリが故障したと判断された場合、バックアップが協調して新しいビュー（view）に移行し、別のレプリカを新プライマリとするプロトコルを考案した。この際、以前のビューでコミット済みの全ての操作が新しいビューに正確に引き継がれることが保証される。Liskovは、この仕組みを「台帳（ledger）」を構築するものと表現する。当時は「ログ」という用語が使われていたが、本質的には分散システム上で履歴を永続的に保存する台帳であり、このプロトコルは特定のアプリケーション（ファイルシステム）に依存しない汎用的なものだった。

VSRが想定していたのは、「良性障害（benign failures）」のみであった。これは、マシンが正常に動作するか完全に沈黙するか、メッセージが届くか届かないか、あるいは破損していても検出可能である、といった単純な障害である。1980年代当時はインターネットが普及しておらず、悪意のある攻撃は想定外だった。Liskovは、VSRが後にGoogle File Systemで採用されたPaxosと本質的に同じプロトコルであったという逸話を紹介する。彼女の元学生であったBill WeihlがGoogleでVSRとPaxosの同一性に気づいたというエピソードは、同じアイデアが異なる場所で同時期に発見されるという、研究史における興味深い事例である。

21:30Practical Byzantine Fault Tolerance（PBFT）：悪意ある障害への挑戦

1990年代後半、DARPA（国防高等研究計画局）がインターネット上の悪意ある攻撃への対策を求める研究公募（RFP）を出したことが、PBFT誕生の直接の契機となった。Liskovの学生Miguel CastroがこのRFPに興味を持ち、「悪意ある攻撃を扱うレプリケーションの方法を考えてみないか」と提案した。Liskovは、DARPAとNSF（全米科学財団）による研究資金が、今日のインターネットを支える基盤研究の「重要な背骨」であったと強調する。

PBFTの開発は、VSRを出発点とした。LiskovのグループはVSRを熟知しており、それを悪意ある障害（Byzantine failures）に対応するよう拡張するのは自然な流れだった。理論的な研究から、悪意ある障害に耐えるには2F+1ではなく3F+1のレプリカが必要であることは既に知られていた。しかし、実用的なプロトコルを目指す上での最大の課題は、レプリカ自体が嘘をつく可能性に対処することだった。Liskovは、この問題に取り組む感覚を「歪んだ鏡の館にいるようだ」と表現する。

PBFTの核心的なアイデアは、「個々のレプリカを決して信用せず、グループのみを信用する」という原則に基づく。これを実現するために、PBFTは「証明書（certificate）」を導入した。証明書とは、2F+1個の同一内容の署名付きメッセージから構成され、プロトコルがある特定の時点に達したことの証拠となる。VSRと比較して、PBFTではレプリケーションプロトコルに1フェーズが追加された。これは、プライマリが次のステップを提案するだけでは不十分で、2F+1個のレプリカが共同で次のステップを実行することに合意し、さらにそれをコミットするための別のフェーズが必要だからである。この証明書の概念は、今日の主要なブロックチェーンプロトコルにおけるトランザクションの順序付けの証明に広く応用されている。Ittai Abrahamは、PBFTが理論的な研究と実用的なシステムの間の「橋渡し」となったと評価する。理論的な論文が可能性を示すだけでなく、実際のベンチマークで優れた性能を示したことで、人々の考え方が変わったという。

29:12状態機械複製（State Machine Replication）とブロックチェーンへの応用

Liskovは、VSRの段階から、自分たちが開発していたのは特定のアプリケーション（ファイルシステム）のためではなく、汎用的なサービスを複製するための基盤であると認識していた。彼らは台帳にどのような操作が要求されたかを書き込むだけで、その操作の実行内容には関心がなかった。これは「関心事の分離（separation of concerns）」の良い例であり、モジュール性の原則の応用でもある。この考え方は、状態機械複製（State Machine Replication、SMR）として知られるパラダイムに他ならない。SMRでは、システム全体を一つの状態機械と見なし、全てのレプリカが同じ順序で同じ操作を実行することで、結果として同一の状態を維持する。この「順序付け」の部分をコンセンサスプロトコルが担当し、「実行」の部分はアプリケーションが担当するという明確な役割分担がなされる。

Tim Roughgardenは、イーサリアムやSolanaなどのチューリング完全なブロックチェーンプロトコルは、この汎用的な状態機械複製問題の「文字通りの実装」であると指摘する。これらのブロックチェーンは、特定のアプリケーションのためのSMRではなく、汎用的なSMRプロトコルを実装し、その上でスマートコントラクトという形で特定のアプリケーションを実行する。これは、Liskovらが1980年代から1990年代にかけて築いたアイデアの、最も直接的な具現化の一つと言える。

Liskovは、PBFTの完成後、「いつか人々がこれを使い始めるだろう」と考えていたが、VSRと同様に約10年のタイムラグがあった。そして「そこにブロックチェーンが登場した」と述べ、その偶然の巡り合わせを「とても面白い」と表現する。ビットコインはPBFTとは異なるコンセンサスメカニズムを採用していたが、ブロックチェーンコミュニティは後に、PBFTとその派生プロトコルが多くの問題に対して「まさに適切なツール」であることを認識した。2025年現在、PBFTはブロックチェーン実践者と研究者の間で、プロトコル設計の基盤として広く理解されている。

32:57AI時代のコンピュータサイエンス研究と若手研究者へのアドバイス

エピソードの後半では、AIの台頭がコンピュータサイエンス研究に与える影響について議論が交わされる。Liskovは、コンピュータサイエンスは「非常に奇妙な場所にある」としつつも、研究の未来に対しては楽観的な見方を示す。AIの基盤となるシステム研究には膨大な未解決問題が存在し、それらは非常に興味深い研究テーマを提供していると述べる。特に、AIが生成するコードの正しさを保証するための検証ツールの必要性を強調する。Mary Shawらがニューヨーク・タイムズに寄稿した記事を引用し、プログラマーの未来は、AIが生成したコードが正しいかどうかを判断できる能力を持つことにあり、そのためには自分自身でプログラムを書く方法を理解していることが不可欠だと指摘する。

Liskovは、自身が1970年代後半にMITでJohn Guttagとともに開発したコースを引き合いに出す。そのコースは「大規模プログラムの構築方法」をテーマとし、設計、モジュール性、仕様、検証に重点を置いていた。彼女は、これこそが将来のプログラマーに求められるスキルセット、すなわち「forループの書き方」ではなく、より高い抽象度でコードを管理する能力であると示唆する。また、テクノロジーが可能にする「悪い振る舞い」に対する懸念も表明し、それを修正または抑制する方法を研究することも重要な研究分野であると付け加える。

Ittai Abrahamは、最近5〜7年の間に発展した「アカウンタビリティ（説明責任）」に関する研究について言及する。これは、PBFTスタイルのプロトコルにおいて、障害数が閾値を超えた場合でも、一貫性違反が発生した際に、矛盾する署名を行った悪意あるノードを特定できるという概念である。Liskovはこの研究を知らなかったが、興味深いと述べている。

結びに

本エピソードは、現代のブロックチェーン技術が、1980年代の分散システム研究、特にBarbara LiskovによるViewstamped ReplicationとPractical Byzantine Fault Toleranceに深く根ざしていることを鮮やかに描き出した。単なる技術史の回顧ではなく、理論と実践の相互作用、モジュール性と抽象化の力、そして長期的な視点で基礎研究に取り組むことの重要性を、第一人者の口から直接聞くことができる貴重な機会となった。Liskovの「コンピュータサイエンスは素晴らしい分野であり、やるべきことは山ほどある」という言葉は、AIの急速な進化に不安を感じる時代にあって、システム研究の永続的な価値と未来への希望を力強く示している。この対話は、ブロックチェーン開発者だけでなく、コンピュータサイエンスの基礎を理解したい全ての者にとって、深い洞察とインスピレーションを与えるものだろう。