a16z: ステートレスなブロックチェーンが存在できない理由

著者: Miranda Christ (コロンビア大学コンピューター サイエンス博士課程学生/a16z 暗号化研究インターン)、Joseph Bonneau (a16zcrypto) 出典: a16z crypto、コンパイラー: Yvonne、MarsBit

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

このストレージの負担は、ほとんどの人々の実際の日常トランザクションをサポートするのに十分なアカウントまたは UTXO を備えたブロックチェーンでは管理できなくなり、バリデーターとなることが困難になり、分散化への脅威となります。解決策として暗号化に目を向けるのは魅力的ですが、マークル ツリーやゼロ知識証明などのツールは、これまで信じられなかった目標を達成するのに役立ちました。

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

ステートレス状態

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

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

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

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

これは自然な研究上の疑問につながります: 証人を更新する必要がない (または、証人をほとんど更新する必要がない) ステートレス ブロックチェーンを構築できますか? この疑問に答えるために、新しい理論的フレームワーク (失効証明システムなど) を開発します。これはステートレスなブロックチェーンを一般化します。このフレームワークを使用して、決定的に不可能な結果を示します。コンパクトなグローバル状態と頻繁な監視の更新との間のトレードオフが基本です。私たちの証明技術は情報理論です。これは、将来のコンピューターがこの問題を解決できるほど強力ではないことを意味します。つまり、ステートレスなブロックチェーン構造と実用性の間のギャップは決して埋まらないでしょう。

研究の背景

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

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

マークル ツリーのアプローチには 2 つの大きな欠点があります。まず、ユーザー監視の数は比較的多く、システム内のアカウントの総数は対数的に増加します。理想的には、それらは一定のサイズである必要があり、これは RSA アキュムレータなどのスキームを使用して実現できます (ステートレス ブロックチェーンのコンテキストにおける Boneh et al.)。

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

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

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

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

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

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

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

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

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

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

(暗号化に詳しい読者は、ここでいくつかの詳細を省略していることに気づくかもしれません。たとえば、ボブの解読は無視できる確率で失敗します。私たちの論文には完全な証明が含まれています。)

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

結果の影響

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

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

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

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

ブロックチェーン システムが発展するにつれて、ブロックチェーンの状態を管理するより効率的な方法を開発することがさらに重要になります。ステートレスブロックチェーンを除外した結果はネガティブに見えるかもしれませんが、不可能であるという結果はブロックチェーン設計者にとって有益であり、研究を他の場所に集中するよう指示され、理想的には実行可能なソリューションをより迅速に見つけるのに役立ちます。