a16z: 「ステートレスブロックチェーン」の不可能性について

オリジナルはミランダ・クライストとジョゼフ・ボノーによって書かれました。

原文編集：Deep Tide TechFlow

ブロックチェーンがより多くのユーザーとより頻繁なトランザクションをサポートするにつれて、トランザクションを検証するためにバリデーターによって保存される情報 (または「状態」) の量が増加します。たとえば、ビットコインでは、状態は一連の未使用のトランザクション出力 (UTXO) で構成されます。イーサリアムでは、状態は各アカウントのアカウント残高と、各スマート コントラクトのコードとストレージで構成されます。

ブロックチェーンが人口のかなりの部分の実際の日常トランザクションをサポートするのに十分なアカウントまたは UTXO で成長するにつれて、このストレージの負担は管理できなくなり、バリデータになることが困難になり、分散化への脅威になります。魅力的な解決策は、暗号化に目を向けることです。マークル ツリーやゼロ知識証明などのツールを使用すると、以前は想像もできなかったことを実現できます。

これはまさに「ステートレスブロックチェーン」の目標です。しかし、それらについて多くの研究が行われているにもかかわらず、実用化にはまだ程遠いです。しかし、この進歩の遅れは本質的なものであり、これらの構築と実用性との間のギャップは決して埋まらないことが判明しました。私たちの最近の研究は、ステートレスなブロックチェーンの提案は、どんなに賢くても、ステートを管理する追加の手段がなければ実現不可能であることを示しています。ただし、この記事の最後で示すように、このありそうもない結果に落胆する必要はありません。

＃＃ ステタスはありません

今日、州は巨大ですが管理可能です。たとえば、ビットコイン ノードは約 7 GB のデータを保存し、イーサリアム ノードは約 650 GB のデータを保存します。ただし、フルノードのストレージ負荷はチェーンのスループット (1 秒あたりのトランザクション数 (TPS)) にほぼ直線的に増加しますが、これは現在でもまだ受け入れられません。現在の設計では、日々のトランザクション (1 秒あたり数万から数十万のトランザクション) を真にサポートするために必要な状態は管理できなくなり、ギガバイト、さらにはペタバイトのストレージが必要になります。

これにより、人々はバリデーターが必要とする状態の量を大幅に削減する技術的な方法を見つけるようになりました。重要なのは、ステートレスなブロックチェーンの実装であり、バリデーターは、トランザクションのスループットに関係なく、一定サイズの状態のみを保存する必要があります (実際には、この用語は誤った呼び方です。将来的に実用になる程度に十分小さい状態がまだ存在します)。スループット - 通常は一定のサイズ）。この軽量なストレージ要件により、検証ノードの実行が容易になり、楽観的に言えば、誰もが自分の携帯電話でノードを実行できるようになります。バリデーターの数を増やすとチェーンのセキュリティが高まるため、バリデーターの参入障壁を下げることが重要です。

ステートレス ブロックチェーンに関する多くの研究（Todd、Buterin、Boneh et al.、Srinivasan et al.など）にもかかわらず、それらは実用には程遠く、私たちの知る限り、まだ導入されていません。既知のすべてのステートレス ブロックチェーンの根本的な問題は、ユーザーが自分のアカウントに関係するトランザクションを検証するバリデーターを支援するために、証人と呼ばれる追加データを保存する必要があることです。たとえば、この証人は、ユーザーのアカウントと残高が世界的な国家コミットメントに含まれていることを示すマークルの包含証明である可能性があります。ユーザーが取引を行うとき、アカウントに十分な残高があることを示すために、この証人をバリデーターに提出します。

変更する必要のない秘密鍵の保管とは異なり、これらの証人は、積極的に取引を行っていないユーザーであっても頻繁に変更されるため、ユーザーに非現実的な負担がかかります。同様に、他のすべてのクレジット カード取引をグローバルに常に監視し、それに応じてローカル データを更新して自分のクレジット カードを使用している場合を想像してください。ブロックチェーンが実用的であるためには、ユーザーはトランザクションを送信するときのみ、オフラインでブロックチェーンを操作できる必要があります。ハードウェアウォレットなどの多くの場合、証人の更新は不便であるだけでなく、不可能です。

これは、当然の研究上の疑問につながります。頻繁な監視者の更新を必要としないステートレス ブロックチェーン (または、頻繁に更新することだけを必要とするブロックチェーン) を構築できるか?この質問に答えるために、私たちはステートレスなブロックチェーンを一般化する新しい理論的フレームワーク (Revocable Proof System) を開発します。このフレームワークを使用すると、ありそうもない結果が示されます。つまり、コンパクトなグローバル状態と頻繁な監視の更新との間のトレードオフは、本質的に調整が難しいということです。私たちの証明技術は情報理論です。これは、将来のコンピューターがこの問題を解決できるほど強力ではないことを意味します。ステートレスなブロックチェーンの構築と実用性の間のギャップは決して埋まりません。

研究の背景

不可能な結果を理解するために、まずマークル ツリーを使用してステートレス ブロックチェーンを構築する自然だが非効率的な方法について説明します。私たちの目標は、ユーザーが送信したトランザクションが有効かどうか、たとえば、ユーザーがトランザクションを実行するのに十分な口座残高を持っているかどうかなど、バリデーターが判断できるようにすることです。ステートレス ブロックチェーン スキームでは、バリデーターは一定サイズの状態を保存します。ユーザーが取引を行うときは、取引に証人を含める必要があります。バリデーターは、ユーザーが送信した現在の状態と (トランザクション、監視) のペアを使用して、ユーザーがトランザクションを実行するのに十分なアカウント残高を持っているかどうかを検証できます。

まず、各 (アカウント ID、残高) ペア (a、b) がリーフ ノードとして含まれるマークル ツリーを構築します。バリデーターによって保存される一定サイズの状態 V はこのツリーのルートであり、一連の口座残高ペアに対するコミットメントとして機能します。各ユーザーは、マークルの包含証明として証人を維持します。リーフ (a、b) のマークル包含証明は、そのリーフからツリーのルートまでのパスに沿ったパートナー ノード (v1、...、vk) で構成されます。アカウント a によるトランザクションと要求された残高 b が与えられた場合、検証者は、(a,b) の証拠 (v1,...,vk) を現在の状態 V と照合することで、b が実際にアカウント a の残高であることを検証できます。そうである場合、バリデーターはトランザクションを実行し、それに応じてアカウントの残高を更新する必要があります。マークル ツリーの便利な特性は、リーフの包含のマークル証明があれば、そのリーフが変更されたときに結果の根を計算するのが簡単であることです。言い換えれば、検証者は、トランザクションの実行後に新しい口座残高 a を取得する更新された状態 V' を簡単に計算できます。

このマークル ツリー スキームには 2 つの大きな欠点があります。まず、ユーザーの証人は比較的大きく、システム内のアカウントの総数に応じて対数的に増加します。理想的には、それらのサイズは一定である必要があり、RSA アキュムレータなどのスキームを使用してこれを実現できます。

2 番目の欠点は、回避するのがより困難です。別のユーザーが取引を行うたびに、口座残高ペアの証明が変化します。リーフ ノードの証明は、そのリーフ ノードからツリーのルートまでのパス上のパートナー ノードで構成されていることを思い出してください。他のリーフ ノードが変更されると、ノードの 1 つが変更され、実際の問題が発生します。ほとんどのブロックチェーン ユーザーは、コインをウォレットに受動的に保管し、取引を行う場合にのみオンラインにアクセスしたいと考えています。ただし、このようなステートレスなブロックチェーンでは、ユーザーは他の人のトランザクションを常に監視して、目撃情報を最新の状態に保つ必要があります。サードパーティがユーザーに代わってこの監視を実行することもできますが、これは標準のステートレス ブロックチェーン モデルから逸脱します。実際には、これはステートレス ブロックチェーンにとって克服できない課題であり、ユーザーに大きな負担を強いることになります。

私たちの結論: 無国籍は不可能

この現象は、この種のマークル ツリー構造にのみ当てはまるわけではありません。すべての既知のステートレス ブロックチェーン スキームでは、ユーザーが証人情報を頻繁に更新する必要があります。これについては、ここで説明します。より正確には、証人情報を更新する必要があるユーザーの数が、すべてのユーザーによって行われたトランザクションの合計数にほぼ直線的に増加することを示します。

これは、ユーザーのアリスが取引を行わなかったとしても、彼女の証人情報は他のユーザーの取引に応じて変更する必要がある可能性があることを意味します。バリデーターによって保存されたコンパクトな状態が小さすぎて完全な状態 (つまり、すべての口座残高のセット) をキャプチャできない限り、コンパクトな状態のサイズを増やしてもほとんど役に立ちません。定理に基づいて、以下に示すこの関係を、さまざまなスループットのブロックチェーンで 1 日に必要な監視変更の数とともにプロットします。これらのグラフは、最適なステートレス ブロックチェーンが証人情報を変更する必要がある回数を示しています。ここで、データ ユニバースとは、アカウント モデル内のアカウントの合計数、または UTXO モデル内の UTXO の合計数を指します。

私たちの証明の中心となるのは情報理論的な議論です。クロード・シャノンによって形式化された情報理論の中心的な教義は、アリスがサイズ 2n のセットからオブジェクトをランダムに選択し、どのオブジェクトを選択したかをボブに伝えたい場合、アリスは少なくとも n ビットを彼に送信しなければならないというものです。ユーザーが証人情報をほとんど更新しないステートレスなブロックチェーンスキームが存在する場合、アリスはボブにどのオブジェクトを選択したかを n ビット未満で伝えることができますが、シャノンが証明したように、これは不可能です。したがって、そのようなステートレスなブロックチェーンは存在しません。

わかりやすくするために、ここでは少し弱いステートメントの証明を説明します。ユーザーが証人情報を更新する必要がないステートレスなブロックチェーンは存在しません。重要なのは、アリスがステートレス ブロックチェーン スキームを使用してボブへのメッセージをエンコードしているということです。最初は、アリスとボブの両方が、n 人のユーザー全員の口座残高ペアの完全なセットを知っています。各アカウントには少なくとも 1 つのコインがあると仮定します。アリスとボブは両方とも、ステートレス ブロックチェーンの簡潔な状態 V と、すべての口座残高ペア (ai、bi) の証人 wi を知っています。アリスとボブは、メッセージとアカウントのセットの間のマッピングについても同意します。アリスは、メッセージに対応するアカウントのセット A を選択し、それらのアカウントからコインを支払います。彼女はステートレス ブロックチェーンを使用して、ボブが彼女について知ることができる、彼女が選択したセットをボブに通信します。

エンコーディング: アリスは A の各アカウントから 1 コインを使います。ステートレス ブロックチェーン スキームを使用して、アリスは更新された状態 V' を計算し、それをボブに送信します。

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

ボブは、アリスが選択したのと同じセット、B = A を正常に出力します。まず、アリスがアカウント ai からコインを使った場合、その古い残高の証人はもはや受け入れられるべきではないことに注目してください。そうでないと、アリスは二重に使うことができてしまいます。したがって、A の各アカウント ai について、Verify(wi, (ai, bi)) = false となり、Bob はこのアカウントを B に含めます。一方、ボブは、アリスがコインを使用しなかった口座を B 口座に含めることは決してありません。これらの口座の残高は同じままであり、(証明したいリラックスした声明を思い出してください) 彼らの証人は決して変更されないからです。したがって、B は A とまったく同じです。

最後に、アリスがボブに送信するビット数を計算することで矛盾を解決します。彼女が選択できるサブセットは 2^n 個あるため、シャノンの法則によれば、彼女は少なくとも n ビットをボブに送信する必要があります。ただし、彼女は、n ビットよりもはるかに短い、一定サイズの状態 V' のみを送信します。

証明を説明するときにステートレス ブロックチェーンを使用しましたが、アリスとボブは、アキュムレータ、ベクトル コミットメント、認証済み辞書など、他のさまざまな認証済みデータ構造を使用して同様の効率的な通信を実行できます。私たちは、可逆証明システムと呼ばれる新しい抽象化を使用して、そのようなデータ構造を形式化します。

結果の影響

私たちの結果は、「暗号的に状態を排除する」ことはできないこと、そしてユーザーが証人を更新する必要がないステートレスなブロックチェーンを構築できるコミットメントスキームに特効薬はないことを示しています。状態は消えることはありませんが、バリデーターから転送され、頻繁な監視更新の形でユーザーにプッシュされます。

厳密にステートレスなブロックチェーン モデルから逸脱する、他にも有望なソリューションがいくつか存在します。このモデルの自然な緩和は、サードパーティ (ユーザーでも検証者でもない) が完全な状態を保存する責任を負えるようにすることです。このサードパーティはプルーフ サービス ノードと呼ばれ、完全な状態を使用してユーザーの最新の証人情報を生成します。その後、ユーザーは通常のステートレス ブロックチェーンと同様に、これらの監視を使用してトランザクションを実行できます。バリデーターは依然としてコンパクトな状態のみを保存します。このシステムのインセンティブメカニズム、特にユーザーがサービス実証ノードを補償する方法は、興味深いオープン研究の方向性です。

これまでの議論は L1 ブロックチェーンに焦点を当ててきましたが、結果はロールアップ サーバーなどの L2 システムにも影響を及ぼします。ロールアップ (オプティミスティックまたは ZK) は通常、L1 上の大きな状態へのコミットメントを小さな値で保存します。この状態には、L2 上のすべてのユーザーのアカウントが含まれます。私たちは、これらのユーザーが、現在の口座残高の証人を公開することにより、(L2 サーバーの協力なしで) L1 で直接資金を引き出すことができるようにしたいと考えています。このセットアップは、モデルにおける可逆証明システムのインスタンスでもあります。実際、ステートレス ブロックチェーンは L2 ロールアップの形ですでに実際に実装されていると主張できます。

しかし残念なことに、これは私たちの不可能性の結果がそのまま当てはまることを意味します。ユーザーのロールアップ フェッチ監視は頻繁に変更する必要があります。変更しない場合は、L2 状態のほぼ全体を L1 に書き込む必要があります。その結果、今日のロールアップは通常、ユーザーがプルする準備ができたときに新しい証人を計算するのを支援する「プルーフ サービス ノード」に似た、データ可用性委員会 (「検証」と呼ばれることもあります) の存在を前提としています。私たちの結果は、イーサリアムのドキュメントにあるユーザーへの警告「トランザクション データがなければ、ユーザーはマークル証明を計算して資金の所有権を証明し、出金を実行することはできません。」が常に適用されることを示しています。