a16z Crypto：ステートレスブロックチェーンの実現不可能性についての考察

原文タイトル：無状態ブロックチェーンの不可能性について

著者：ミランダ・クリスト、コロンビア大学CS博士、a16z夏季インターン研究員 & ジョセフ・ボノー、a16z研究パートナー

編訳：bayemon.eth、ChainCatcher

ブロックチェーン技術のユーザーが増加し、その上での取引がますます頻繁に行われる中、検証者が取引を検証するために保存する情報量（「状態」）も増加しています。例えば、ビットコインでは、状態は未使用の取引出力（UTXO）のセットで構成されています。イーサリアムでは、状態は各アカウントの残高と各スマートコントラクトのコードおよびストレージを含みます。

十分なアカウントまたはUTXOを持つブロックチェーンにとって、このストレージの負担は、ブロックチェーンが相当数の人々の日常的な取引を実際にサポートすることを困難にし、これによりこれらのユーザーが検証者になることができず、したがって分散化に対する脅威となります。Merkle TreeやZKなどのツールがブロックチェーンに驚くべき目標を達成するのを助けているため、私たちは暗号学に訴えて相応の解決策を求めたいと考えています。

これが「無状態ブロックチェーン」の目標です。しかし、この分野で多くの作業が行われているにもかかわらず、相応の解決策はまだ実用化には程遠いのが現実です。実際、構造と実用性の間の埋められないギャップのために、この進展の遅れは本質的なものであり、この遅れはどの業界の発展過程においても自然に存在する障害のようです。私たちの最新の研究は、追加の措置を講じて「状態」を管理しない限り、どんなに賢い無状態ブロックチェーンの解決策も実行不可能であることを示しています。しかし、この記事の最後で述べるように、結果が実用的でないとしても、私たちはそれに落胆すべきではありません。

無状態とは何か

現在、状態は膨大ですが、管理は容易です。例えば、ビットコインノードは約7GBのデータを保存し、イーサリアムノードは約650GBのデータを保存しています。しかし、フルノードのストレージ負担はチェーンのスループット（毎秒取引量またはTPS）とほぼ線形に増加しますが、現在のメインチェーンのスループットは実際に非常に低いです。現在の設計では、日常的な取引（数万から数十万TPS）を実際にサポートするために必要な状態は非常に大きく、数TBまたは数PBのストレージスペースが必要です。

メインチェーンの限られた性能は、検証者が必要とする状態量を大幅に削減する技術的手法を探求する動機となっています。最良の技術的手法は無状態ブロックチェーンを構築することです。つまり、取引のスループットに関係なく、検証者は一定のサイズの状態のみを保存する必要があります。（この用語は実際には誤解を招くもので、状態は依然として一定のサイズで存在しますが、将来のどんなスループットでも正常に機能するのに十分小さいのです）。無状態ブロックチェーンはハードウェアのストレージ要件を大幅に削減し、検証者ノードを運営することを容易にし、楽観的に言えば、誰もが携帯電話でノードを運営できるようになります。そして、検証者の数が増えることでチェーンの安全性が向上するため、検証者の参入障壁を下げることは非常に重要です。

Todd、Buterin、Boneh、Srinivasanなどが無状態ブロックチェーンについて多くの研究を行っていますが、完全な実現にはまだ距離があります。私たちが現在知っている限り、成功裏にデプロイされた無状態ブロックチェーンは存在しません。すべての既知の無状態ブロックチェーンの根本的な問題は、ユーザーが追加のデータ（「証拠 Witness」と呼ばれる）を保存することを要求することです。これにより、検証者はそのアカウントに関連する取引を検証します。例えば、この証拠はMerkleの包含証明であり、ユーザーのアカウントとその残高がグローバル状態のコミットメントに含まれていることを示します。ユーザーが取引を行うとき、彼らはその証明を検証者に提出し、アカウントに十分な残高があることを示します。

変更されない秘密鍵とは異なり、これらの証拠は頻繁に変化します。積極的な取引を行っていないユーザーにとっても、これは想像を絶する負担をもたらします。想像してみてください、もしあなたが自分のクレジットカードを使用するために、世界中の他のすべてのクレジットカード取引を継続的に監視し、それに応じていくつかのローカルデータを更新しなければならないとしたら、確かに不必要なトラブルを引き起こすでしょう。したがって、ブロックチェーンを実用的にするためには、ユーザーがオフラインの状態を維持し、取引を提出する際にのみブロックチェーンと相互作用できる必要があります。これは、ハードウェアウォレットを含むさまざまな状況において、証拠が完全に更新できないことを意味します。

これにより、私たちは自然に研究の問題を考えました：更新が不要（またはほとんど不要）な無状態ブロックチェーンを構築できるでしょうか？この問題に答えるために、私たちは新しい理論的枠組み（取り消し可能な証明システム）を開発し、無状態ブロックチェーンを概念化しました。この枠組みを利用して、私たちは確固たる不可能性を証明しました：簡潔なグローバル状態と頻繁な証拠の更新の間にはほぼバランスを取ることができないのです。私たちの証明技術は情報理論的であり、これは未来のコンピュータがこの問題を解決するには強力すぎないことを意味します：無状態ブロックチェーンの構造と実用性の間のギャップは永遠に埋められないでしょう。

研究の背景

上記の「不可能性」をさらに直感的に理解するために、まずMerkle Treeを使用して無状態ブロックチェーンの自然な方法を説明します（Merkle Treeに基づく解決策は効率が高くないですが）。私たちの目標は、検証者がユーザーが提出した取引が有効かどうかを確認することです。例えば、ユーザーが取引に使用できる十分なアカウント残高を持っているかどうかです。無状態ブロックチェーンの提案では、検証者は一定のサイズの状態を保存し、ユーザーが取引を行うとき、その取引には証拠が含まれている必要があります。検証者は現在の状態とユーザーが提出した（取引、証拠）のペアを使用して、そのユーザーが取引を行うのに十分なアカウント残高を持っているかどうかを確認できます。

私たちはまずMerkle Treeを構築します。このツリーの各ペア（アカウントID、残高）のキー値ペア（a,b）はツリーの葉です。検証者が保存する一定のサイズの状態Vは、このツリーの根であり、アカウント-残高のキー値ペアのコミットメントとして機能します。各ユーザーはMerkle包含証明を通じてその（アカウントID、残高）情報を維持する必要があります。葉（a,b）のMerkle包含証明は、その葉からツリーの根へのパス上のノードの集合（v1, …, vk）で構成されます。検証者は、(a,b)の証明（v1, …, vk）を現在の状態Vと照合することで、bがアカウントaの残高であるかどうかを確認できます。Merkle Treeの特性の一つは、葉のMerkle包含証明が与えられた場合、葉が変化すると結果の根を簡単に計算できることです。言い換えれば、検証者は取引実行後のアカウントaの新しい残高をキャッチする更新された状態V'を簡単に計算できます。

しかし、Merkle Treeには2つの主要な欠点があります。まず、ユーザーの証拠は相対的に大きいことです。これは、システム内のアカウントの総数の対数に比例して増加します。理想的には、これらは一定のサイズであるべきであり、RSA累積器などのスキームを使用して実現できます（Bonehらは無状態ブロックチェーンにおいてこれを研究しました）。

第二の欠点は回避が難しいです：他のユーザーが取引を行う限り、アカウント-残高のキー値ペアの証明が変化します。思い出してください、葉の証明は葉からツリーの根へのパス上のノードの集合で構成されています。他の葉が変化すると、これらのノードの一つも変化し、実際の問題を引き起こします。ほとんどのブロックチェーンユーザーは、彼らのコインを財布に保管することを受動的に望んでおり、取引を行いたいときだけオンラインになります。しかし、この無状態ブロックチェーンの実際のアプリケーションでは、ユーザーは他の人の取引を常に監視し、自分の証拠が最新であることを保証しなければなりません。（第三者がユーザーのために監視を行うことは可能ですが、これは標準的な無状態ブロックチェーンのモデルから逸脱します。私たちはこの記事の最後でこれについて議論します）。実際、これは無状態ブロックチェーンにとって克服が難しい課題であり、ユーザーに重い負担をもたらします。

結論：無状態ブロックチェーンは実現不可能である

この現象はMerkle Treeに特有の欠陥ではありません------現在知られているすべての無状態ブロックチェーンの提案は、ユーザーが対応する証拠情報を頻繁に更新することを要求します。より正確には、証拠情報を更新する必要があるユーザーの数は、すべてのユーザーの取引総量とほぼ線形の関係にあり、単調に増加します。

これは、ユーザーのアリスが取引を行っていなくても、彼女の証拠情報が他のユーザーの取引に応じて変わる可能性があることを意味します。検証者が保存する簡潔な状態が、完全な状態（すべてのアカウント残高の集合）をキャッチできないほど小さい限り、簡潔な状態の保存規模を増やしても何の助けにもなりません。私たちはこの暗黙の関係を視覚化し、異なるスループットのブロックチェーンが毎日必要とする検証者の変更回数を出力しました。これらの図は、最適な無状態ブロックチェーンに必要な証拠の変更回数を示しています。その中で、データユニバースはアカウントモデル下のアカウント総数またはUTXOモデル下のUTXO総数を指します。

私たちが証明した核心は情報理論的な論証です。クロード・シャノンが正式に提唱した情報理論の核心原則は、アリスがサイズ2nの集合からランダムにオブジェクトを選択し、ボブに彼女の選択を知らせたい場合、少なくともnビットをボブに送信しなければならないということです。もし無状態ブロックチェーンの提案が存在し、ユーザーが証拠を更新する必要がない場合、アリスはnビット未満のコストでボブに彼女の具体的な選択を伝えることができるでしょう------しかし、シャノンはこれが不可能であることを証明しました。したがって、私たちもそのような無状態ブロックチェーンが存在することは不可能であると考えています。

簡単にするために、私たちはまず弱化された証明を行います。すなわち、ユーザーが永遠に証拠を更新する必要がない無状態ブロックチェーンは存在しないということです。証明の重要なプロセスは、アリスが無状態ブロックチェーンの提案を使用して彼女の情報をボブにエンコードして伝送することを含みます。最初に、アリスとボブがすべてのnユーザーのアカウント-残高ペアを知っていると仮定します。また、各アカウントの残高は少なくとも1であるとします。さらに、アリスとボブは無状態ブロックチェーンの簡潔な状態Vとすべてのアカウント残高ペア（ai、bi）の証拠wiを知っており、二人は情報とアカウント集合との間のマッピングを合意しています。アリスは彼女の情報に対応するアカウントのセットAを選択し、アカウント残高を使用して消費し、最終的に無状態ブロックチェーンを使用してボブに彼女が選択したアカウント集合を伝えます。ボブはこのアカウント集合から彼女の情報が何であるかを理解できます。

エンコード：アリスは無状態ブロックチェーンの提案を使用して更新された状態V'を計算し、V'をボブに送信します。

デコード：各iについて、ボブはVerify(wi,(ai,bi))をチェックします。ボブはVerify(wi, (ai, bi)) = falseとなるアカウント集合Bを出力します。

最終的に、ボブはアリスが選択したのと同じ集合を成功裏に出力します。すなわち、B = Aです。まず、アリスがアカウントaiのコインを使った場合、その古い残高の証拠はもはや受け入れられないべきです------さもなければ、アリスは重複して消費することができます。したがって、Aの各アカウントaiについて、Verify(wi, (ai, bi)) = falseとなり、ボブはこのアカウントをBに含めます。一方、ボブは残高が変わらないアカウントをBに含めないでしょう。なぜなら、これらのアカウントの残高は変わらず、（私たちが証明しようとしている「弱化」声明を思い出してください）それらの証拠は永遠に変わらないからです。したがって、BはちょうどAに等しいのです。

最後に、私たちはアリスがボブに送信すべきビット数を計算することで矛盾を導き出します。彼女が選択できるアカウントの部分集合は2n個あり、したがってシャノンの法則に従えば、彼女はボブに少なくともnビットを送信する必要があります。しかし、彼女は定数サイズの状態V'を送信しただけで、nビットよりも短いのです。

（暗号学に精通している読者は、私たちがここでいくつかの詳細を無視していることに気づくかもしれません。例えば、デコード失敗の確率は無視できるほど小さいです。私たちの論文には完全な証明が含まれています）。

私たちは無状態ブロックチェーンを使用して証明を記述しましたが、アリスとボブは他のさまざまな認証データ構造（累積器、ベクトルコミットメント、認証辞書など）を使用して同様の効率的な通信を行うこともできます。私たちはこの一連のデータ構造を新しい抽象概念として形式化し、取り消し可能な証明システム（revocable proof system）と呼びます。

結論の意味

以上の結果は、私たちが「暗号技術によって状態を完全に排除する」ことができないことを示しており、したがってユーザーが永遠に証拠を更新する必要がない無状態ブロックチェーンを実現するための簡単な解決策は存在しないことを示しています。状態は消失するのではなく、検証者からユーザーに頻繁に更新される証拠の形で移転されます。

現在、厳密な無状態ブロックチェーンモデルから逸脱した他の合理的な解決策がいくつか存在します。このモデルの自然な緩和の一つは、第三者（ユーザーでも検証者でもない）がすべての状態を保存することを許可することです。この第三者は証明サービスノードと呼ばれ（Srinivasanらが最も厳密に研究しました）、完全な状態を使用してユーザーのために最新の証拠を生成します。その後、ユーザーはこれらの証拠を使用して取引を行うことができ、通常の無状態ブロックチェーンと同様に、検証者は依然として簡潔な状態のみを保存します。このシステムのインセンティブメカニズム、特にユーザーが証明サービスノードにどのように補償するかは、興味深いオープンな研究の方向性です。

これまでの議論は主にL1ブロックチェーンに集中していましたが、私たちの結果はrollupなどのL2システムにも影響を与えるでしょう。楽観的またはzk rollupの場合、通常は大きな状態値を生成し、対応する手段を通じてL1に小さな値を提出して保存します。私たちは、これらのユーザーがL2サーバーの協力なしに、直接アカウント残高の証拠を発行し、L1で資金を引き出すことを望んでいます。私たちのモデルでは、この設定も取り消し可能な証明システムの一例です。実際、無状態ブロックチェーンは実践においてL2 rollupの形で実現されていると言えます。

しかし残念ながら、私たちの「不可能性」は直接的に応用されることはありません。ユーザーのrollup撤回証拠は常に変更され、同期される必要があり、さもなければほぼ全てのL2層の状態がL1に書き込まれなければなりません。したがって、現在のrollup解決策は通常、データ可用性委員会（時には「validium」と呼ばれる）を設定し、これはユーザーが退出する準備ができたときに新しい証拠を計算するのを助ける機能を持っています。私たちの研究結果は、取引データにアクセスできない場合、ユーザーは資金の所有権を証明し、引き出しを実行するために必要なMerkle Treeを計算できないことを示しています。これは、イーサリアムの文書においてユーザーに常に適用される警告でもあります。

ブロックチェーンシステムの発展に伴い、より効率的なブロックチェーン状態管理方法の開発がますます重要になるでしょう。私たちの研究が無状態ブロックチェーンが実用化不可能であるという結果は、否定的に見えるかもしれませんが、この結論はブロックチェーン設計者にとって意味のあるものです。なぜなら、それは私たちに研究の焦点を他の場所に移し、実行可能な解決策をより早く見つける手助けをすることを示唆しているからです。