a16z：「ステートレスブロックチェーン」の不可能性について
TechFlow厳選深潮セレクト
a16z：「ステートレスブロックチェーン」の不可能性について
状態は消え去ったわけではなく、検証者からユーザーへと移管され、頻繁なワitness更新という形でプッシュされる。
Web3業界の深掘り報道に専念し潮流を洞察執筆：Miranda Christ、Joseph Bonneau
編集：TechFlow
ブロックチェーンがより多くのユーザーとより頻繁な取引をサポートするにつれて、検証者が取引の正当性を確認するために保存する情報（いわゆる「状態」）の量も増加している。たとえば、ビットコインでは、この状態は未使用トランザクション出力（UTXO）の集合から構成される。イーサリアムでは、各アカウントの残高および各スマートコントラクトのコードとストレージから構成される。
アカウントやUTXOが人口の相当部分にとって日常的な取引を実際に支えるに足る規模まで成長した場合、このストレージ負荷は制御不能になり、検証者になることを困難にし、分散化に対して脅威となるだろう。魅力的な解決策として、Merkle木やゼロ知識証明といった道具によって以前には想像もできなかったことが可能になる暗号技術への移行がある。
まさにこれが「ステートレス・ブロックチェーン」の目標である。しかし、これに関する研究は多く行われているものの、まだ実用にはほど遠い。そして事実は、この進展の遅れは本質的なものであり――すなわち、これらの構築と実用性との間のギャップは永久に埋められないということだ。我々の最近の研究は、追加的な状態管理措置なしでは、いかに巧妙なステートレス・ブロックチェーン方式であっても実現不可能であることを示している。ただし、本文の末尾で示すように、この不可能性の結果が落胆を招くべきではないことも明らかにする。
ステートレスとは
今日、状態は膨大だが管理可能である。たとえば、ビットコインノードは約7GBのデータを、イーサリアムノードは約650GBのデータを保存している。しかし、フルノードのストレージ負荷はチェーンのスループット（秒あたりの取引数、TPS）とおおよそ線形に比例して増加する。現在のスループットは依然として受け入れがたい低さだが、将来的に日常的な取引を真に支えるために必要なレベル（秒あたり数万から数十万件の取引）になると、状態はギガバイト、あるいはペタバイト単位のストレージを必要とするほど制御不能になる。
これは、検証者の必要とする状態量を大幅に削減する技術的手段を探求する動機となる。特に重要なのは、検証者が取引スループットに関係なく一定サイズの状態のみを保存すればよい「ステートレス・ブロックチェーン」の実現である（実際にはこの用語は誤称である：完全に状態がないわけではなく、未来のあらゆるスループット下でも実用可能なほど十分に小さい、通常は定数サイズの状態が存在する）。このような軽量なストレージ要件により、検証者ノードの運用がはるかに容易になる。楽観的に言えば、誰もが自分のスマホ上でノードを走らせることができるようになる。検証者の数を増やすことはチェーンの安全性を高めるため、検証者参加のハードルを下げることは極めて重要である。
ステートレス・ブロックチェーンについては多大な研究が注がれている（例：Todd、Buterin、Bonehら、Srinivasanらによる研究）が、実用化まではまだ遠く、我々の知る限り、実際に導入されたものは存在しない。すべての既知のステートレス・ブロックチェーンの根本的な問題は、ユーザーが自身のアカウントに関連する取引を検証者に検証してもらうために、いわゆる「ワitness（証人情報）」と呼ばれる追加データを保持しなければならない点にある。たとえば、このワitnessは、ユーザーのアカウントと残高がグローバルな状態コミットメントに含まれていることを示すMerkle包含証明である可能性がある。ユーザーが取引を行うとき、彼らはこのワitnessを検証者に提出し、自身のアカウントに十分な残高があることを示す。
秘密鍵の保存とは異なり、それは一度設定すれば変更不要だが、これらのワitnessは、非アクティブなユーザーであっても頻繁に変化するため、ユーザーに非現実的な負担を強いる。別の例えとして、自らのクレジットカードを使うために、世界中の他のすべてのクレジットカード取引を常に監視し、それに応じてローカルデータを更新せねばならない状況を想像してほしい。ブロックチェーンを実用化するには、ユーザーがオフラインのままにしておき、取引を提出するときだけブロックチェーンと相互作用できる必要がある。ハードウェアウォレットなど多くのケースでは、ワitnessの更新は不便なだけでなく不可能である。
こうした状況から自然な研究課題が生じる：頻繁なワitness更新を必要としない（あるいは極めて少ない更新しか必要としない）ステートレス・ブロックチェーンを構築することは可能か？ この問いに答えるため、我々はステートレス・ブロックチェーンを一般化する新規の理論的枠組み（取り消し可能な証明システム）を開発した。この枠組みを用いて、簡潔なグローバル状態と頻繁なワitness更新の間のトレードオフが本質的に調和困難であるという不可能性の結果を証明した。我々の証明手法は情報理論に基づくものであり、つまり将来のコンピュータ能力をもってしてもこの問題を解決できないことを意味する：ステートレス・ブロックチェーンの構築と実用性の間のギャップは永久に埋められない。
研究の背景
我々の不可能性の結果を理解しやすくするために、まずMerkle木を用いた自然だが効率の悪いステートレス・ブロックチェーン構築法を説明する。目的は、ユーザーが提出した取引が有効かどうか（たとえば、ユーザーに取引を行うのに十分なアカウント残高があるか）を検証者が判断できるようにすることである。ステートレス・ブロックチェーン方式では、検証者は一定サイズの状態を保存する。ユーザーが取引を行うとき、取引とともにワitnessを含める必要がある。検証者は、現在の状態とユーザーが提出した（取引、ワitness）の対を使って、そのユーザーが取引に必要な残高を持っているかどうかを検証できる。
まず、各（アカウントID、残高）の対 (a, b) を葉とするMerkle木を構築する。検証者が保存する一定サイズの状態Vは、この木のルートであり、一組のアカウント残高対へのコミットメントとして機能する。各ユーザーは、自身のワitnessとしてMerkle包含証明を保持する。(a, b) のMerkle包含証明とは、その葉からルートに至るパス上の「パートナー」ノード (v₁,…,vₖ) からなる。アカウントaが残高bを主張して取引を行う場合、検証者はその証明 (v₁,…,vₖ) と現在の状態Vを照合することで、bが本当にaの残高であるかを検証できる。もし正当であれば、検証者は取引を実行し、アカウントの残高を適切に更新する。Merkle木の便利な特性として、ある葉の包含証明が与えられれば、その葉が変更されたときに新しいルートを簡単に計算できる。つまり、検証者は、アカウントaの新たな残高を反映した更新済みの状態V'を容易に計算できる。
このMerkle木方式には2つの主要な欠点がある。第一に、ユーザーのワitnessは比較的大きく、システム内の総アカウント数の対数に比例して増加する。理想は定数サイズだが、RSAアキュムレータなどの方式でこれを達成できる。
第二の欠点はさらに避けがたい：他のユーザーが取引を行うたびに、アカウント残高対の証明が変化してしまう。葉の証明は、その葉からルートまでのパス上のパートナーノードから構成されることを思い出そう。他の葉が変化すれば、そのうちの一つのノードも変化し、実用上大きな問題となる。ほとんどのブロックチェーンユーザーは、硬貨をウォレットに静かに保管しておき、取引を行いたいときだけネットに接続することを望んでいる。しかし、このステートレス・ブロックチェーンでは、ユーザーは他人の取引を常に監視して、自身のワitnessを最新に保つ必要がある。第三者がユーザーに代わってこの監視を行うことも可能だが、これは標準的なステートレス・ブロックチェーンモデルからの逸脱である。実際上、これはステートレス・ブロックチェーンにとって克服不能な課題であり、ユーザーに重い負担を課す。
結論：ステートレスは不可能である
この現象はMerkle木構造に限ったものではない。既知のすべてのステートレス・ブロックチェーン方式は、ユーザーが頻繁にワitnessを更新しなければならず、ここにその証明を示す。より正確には、ワitnessを更新せざるを得ないユーザーの数は、全ユーザーによる取引総数とほぼ線形に比例して増加する。
つまり、ユーザーAliceがまったく取引を行わなくても、他のユーザーの取引に応じて彼女のワitnessが変更を要することがある。検証者が保存する簡潔な状態が、完全な状態（すべてのアカウント残高の集合）を捉えるには小さすぎる限り、そのサイズをいくら大きくしてもほとんど助けにならない。我々の定理に基づき、以下にその関係をグラフで示すとともに、異なるスループットを持つブロックチェーンにおいて1日に必要なワitness変更回数も示す。これらの図は、最良のステートレス・ブロックチェーンでも必要なワitness変更回数を示している。「データ宇宙」とは、アカウントモデルにおける総アカウント数またはUTXOモデルにおける総UTXO数を指す。
我々の証明の核心は情報理論的議論にある。クロード・シャノンが形式化した情報理論の基本原理の一つは、「Aliceがサイズ2ⁿの集合からランダムに一つの対象を選ぶとき、Bobにそれが何かを伝えるには、少なくともnビットの情報を送らなければならない」というものである。もしユーザーがほとんどワitnessを更新しないステートレス・ブロックチェーン方式が存在すれば、Aliceはnビット未満でBobに選んだ対象を伝えられることになり、これはShannonが証明した通り不可能である。したがって、そのようなステートレス・ブロックチェーンは存在しえない。
簡単化のため、ここでわずかに弱い主張の証明を述べる：ユーザーが決してワitnessを更新する必要がないステートレス・ブロックチェーンは存在しない。鍵となるのは、Aliceがステートレス・ブロックチェーン方式を用いてメッセージを符号化し、Bobに送信するというアイデアである。初期状態で、AliceとBobはn人のユーザー全員の完全なアカウント残高対の集合を共有している。各アカウントは少なくとも1コインを持っているとする。AliceとBobはまた、ステートレス・ブロックチェーンの簡潔な状態Vおよびすべてのアカウント残高対(ai, bi)に対するワitness wiを共有している。さらに、メッセージとアカウント集合の間のマッピングも合意している。Aliceは、自分のメッセージに対応するアカウント集合Aを選択し、それらのアカウントからコインを消費する。彼女はステートレス・ブロックチェーンを通じてBobに選択した集合を伝え、Bobはその集合からメッセージを復元できる。
符号化：Aliceは集合Aに属する各アカウントから1コインを消費する。ステートレス・ブロックチェーン方式を用いて、更新後の状態V'を計算し、それをBobに送信する。
復号：各iについて、BobはVerify(wi, (ai, bi))が真かどうかをチェックする。BobはVerify(wi, (ai, bi)) = falseとなるアカウント集合Bを出力する。
Bobは正しくAliceが選んだ集合を出力する：B = A。まず、Aliceがアカウントaiからコインを消費した場合、その古い残高に対するワitnessはもはや受理されてはならない――さもなくば、Aliceは二重払いを可能にするからである。したがって、Aに含まれる各アカウントaiについて、Verify(wi, (ai, bi)) = falseとなり、BobはそのアカウントをBに含める。一方、Aliceがコインを消費していないアカウントは、その残高が変わらず（今考えている緩めた主張によれば）ワitnessも決して変化しないため、BobはそれらをBに含めることはない。よって、BはちょうどAに等しい。
最後に、矛盾を導くために、AliceがBobに送るべきビット数を考察する。彼女が選べる部分集合は全部で2ⁿ個あるため、シャノンの定理により、少なくともnビットを送らなければならない。しかし、彼女が送るのは定数サイズの状態V'だけであり、これはnビットよりもはるかに短い。
証明の説明ではステートレス・ブロックチェーンを使用したが、AliceとBobは累積器、ベクターコミットメント、認証付き辞書など、さまざまな他の認証付きデータ構造を用いて同様の効率的通信が可能である。我々は「取り消し可能な証明システム」と呼ぶ新しい抽象化によって、こうしたデータ構造を形式化した。
結果の影響
我々の結果は、「暗号技術で状態を消せる」ことはできないことを示している。ユーザーが決してワitnessを更新する必要のないステートレス・ブロックチェーンを構築できる魔法のようなスキームは存在しない。状態は消えたわけではなく、検証者からユーザーへと、頻繁なワitness更新という形で押し付けられているのだ。
厳密なステートレス・ブロックチェーンモデルから外れるが有望な他の解決策も存在する。その自然な緩和案の一つは、ユーザーでも検証者でもない第三者が完全な状態を保存する役割を担うことを許容するというものである。この「証明サービサー」と呼ばれる第三者は、完全な状態を使ってユーザーに最新のワitnessを生成する。その後、ユーザーは通常のステートレス・ブロックチェーンのようにそのワitnessを使って取引を行い、検証者は依然として簡潔な状態のみを保存する。このシステムのインセンティブ設計、特にユーザーが証明サービサーにどのように報酬を支払うかは、興味深い未解決の研究課題である。
これまでの議論はL1ブロックチェーンに焦点を当ててきたが、我々の結果はRollupサーバーなどのL2システムにも影響を与える。Rollup（OptimisticでもZKでも）は通常、L1上に大きな状態のコミットメントを小さな値で保存する。この状態にはL2上の各ユーザーのアカウントが含まれる。我々は、ユーザーがL2サーバーの協力を得ずに直接L1上で資金を引き出せることを望む。そのためには、現在のアカウント残高に対するワitnessを提示する。この設定も、我々のモデルにおける「取り消し可能な証明システム」の一つの実例である。実際、ステートレス・ブロックチェーンはすでにL2 Rollupの形で実践的に実装されているといえる。
しかし残念ながら、これは我々の不可能性の結果が直接適用されることを意味する。ユーザーのRollup引き出し用ワitnessは頻繁に変更されなければならない。そうでなければ、L2のほぼすべての状態をL1に書き込む必要が生じる。そのため、今日のRollupは通常、「データ可用性委員会（時として“validium”と呼ばれる）」が存在すると仮定しており、これは「証明サービサー」と類似した存在であり、ユーザーが引き出し準備をする際に新しいワitnessを計算するのを助ける。我々の結果は、イーサリアムのドキュメントにあるユーザーへの警告――「トランザクションデータがなければ、ユーザーは資金の所有権を証明し引き出しを実行するためのMerkle証明を計算できない」――が常に妥当し続けることを示している。
TechFlow公式コミュニティへようこそ
Telegram購読グループ：https://t.me/TechFlowDaily
Twitter公式アカウント：https://x.com/TechFlowPost
Twitter英語アカウント：https://x.com/BlockFlow_News
a16z
