一文でわかるStarkNetのゼロ知識再帰証明—STARK

StarkNet中国コミュニティ

2022-08-16 19:07:26

コレクション

再帰は、コストとパフォーマンスをさらに拡張したいプラットフォームやアプリケーションに、より多くの機会を提供します。

共有する

WeChatでQRコードをスキャン

原題：《Recursive STARKs》

著者：StarkWare コアエンジニア Gidi Kaempfer

翻訳：StarkNet 中国コミュニティ

概要

再帰証明がメインネットに導入され、1つの証明で StarkEx アプリケーションと StarkNet を拡張
再帰証明はスケーラビリティを向上させ、コストと遅延を削減（スケーラビリティと遅延の同時発展が可能）
再帰証明は L3 やその他の応用の条件を創出
再帰証明に関するブログを見てみましょう、超クールです ?

倍数拡張！

Cairo の汎用計算に支えられた再帰証明が生産に投入されました。これは STARK の L2 スケーリング能力の大幅な向上を示しています。単一の証明で Ethereum に書き込まれる取引の数は急速に倍増します。

これまで、STARK 証明は数万、さらには数十万の取引を「集約」して単一の証明として Ethereum に書き込むことでスケーリングを実現してきました。再帰を通じて、多くのそのような証明を「集約」して単一の証明にすることができます。

この方法は、StarkWare の SaaS スケーリングエンジン StarkEx や許可不要の Rollup StarkNet 上で動作する多くの Cairo ベースのアプリケーションに適用されています。

これまでの発展の歴史

2020 年 3 月にメインネットで最初の証明が生成されて以来、STARK 証明はさまざまな発展段階を経てきました。

STARK スケーリング

2020 年 6 月、最初の STARK スケーリングソリューション StarkEx が Ethereum メインネットに展開されました。StarkEx には、オフチェーンで大規模な計算を実行し、取引の正確性を示す STARK 証明を生成する証明器と、証明の正確性をオンチェーンで検証する検証器があります。最初の展開は StarkWare のエンジニアによってゼロから手がけられたため、StarkEx の機能は大きく制限されていました。最終的に、証明の汎用計算をサポートするプログラミング言語が必要であると判断しました。こうして、Cairo が誕生しました。

Cairo プログラミング言語

2020 年夏、Cairo が初めて Ethereum メインネットに登場しました。Cairo は CPU 代数中間コード (CPU Algebraic Intermediate Representation [AIR]) であり、対応する「CPU」命令セットを検証するための単一の AIR を含んでいます。Cairo は、より複雑なビジネスロジックや任意の計算命題をコーディングするための扉を開き、より迅速かつ安全にします。Cairo プログラムは、対応するアプリケーションの実行ロジックを証明できます。しかし、Cairo プログラムは複数のそのようなアプリケーションを集約することもでき、これが SHARP です。

SHARP

SHARP は共有証明器 (SHARed ProSver) であり、いくつかの独立したアプリケーションの取引を集約し、単一の STARK 証明で証明します。アプリケーションは異なるバッチ取引を組み合わせ、STARK 証明の容量をより早く満たすことができます。取引処理速度と遅延が向上します。再帰証明は次世代の最先端技術であり、ハードコーディングされたロジックだけでなく、汎用計算にも適用されます。

再帰証明のすべての利点を理解するためには、SHARP がこれまでどのように（非再帰的）証明を実行してきたかをさらに理解する必要があります。図 1 は典型的な非再帰プロセスを描いています：

このプロセスでは、命題が徐々に到達します。容量（または時間）が一定の閾値に達すると、大規模な組合せ命題 (Train) が生成されます。すべての個別命題を受け取った後でのみ、この組合せ命題を証明できます。この証明には長い時間がかかります（個別の命題ごとの証明に必要な時間の合計に相当します）。

非常に大規模な命題の証明は、最終的にメモリなどの利用可能な計算リソースの制限を受けます。再帰の前には、これは実際に STARK 証明のスケーラビリティを制限する大きな障害でした。

再帰証明とは？

STARK 証明を通じて、命題を証明するのにかかる時間は、命題を実行するのにかかる時間とおおよそ線形の関係にあります。さらに、命題を証明するのにかかる時間が T である場合、証明を検証するのにかかる時間はおおよそ log(T) であり、これは通常「対数圧縮」と呼ばれます。言い換えれば、STARK を使用することで、ユーザーが命題を検証するのにかかる時間は、命題を計算するのにかかる時間よりもはるかに少なくなります。

Cairo は汎用計算命題を表現でき、これらの命題は STARK 証明によって証明され、対応する STARK 検証器によって検証されます。

これが再帰を実行する機会です：何千もの取引の正確性を証明するための Cairo プログラムを書くことができるように、複数の STARK 証明を検証するための Cairo プログラムを書くこともできます。複数の「上流」証明の有効性を検証するための証明を生成できます。これが私たちが言う再帰証明です。

対数圧縮と証明時間がおおよそ線形の関係にあるため、STARK 証明を証明するのに必要な時間は比較的短いです（近い将来には数分で済むと予想されています）。

再帰を実現する際、SHARP は命題を受け取るとすぐにそれを検証できます。証明はさまざまなパターンで繰り返し結合され、ある時点で生成された証明がオンチェーンの検証者コントラクトに提出されます。図 2 は典型的な再帰証明のパターンです：

この例では、4 つの命題が SHARP に送信されます（おそらく 4 つの異なるアプリケーションから）。これらの命題はそれぞれ並行して証明されます。次に、各ペアの証明は再帰検証器命題（STARK 証明を検証する Cairo プログラム）によって検証され、証明が生成されます。この命題は、2 つの証明が検証されたことを証明します。次に、再帰検証器命題によって再度この 2 つの証明が結合されます。これにより、すべての 4 つの元の命題を証明する証明が生成されます。この証明は最終的にチェーンに提出され、Solidity 検証器スマートコントラクトによって検証されます。

再帰証明の直接的な利点

オンチェーンコストの削減

間違いなく、私たちは複数の証明を「圧縮」して 1 つにすることを実現しました。これは、各取引のオンチェーン検証コストが大幅に低下することを意味します（各命題には多くの取引が含まれている可能性があります）。

再帰証明を使用することで、これまで証明のサイズを制限していた計算リソースの障害（メモリなど）を排除できます。各命題の容量は限られており、個別に証明できます。したがって、再帰を使用する場合、再帰の有効な組合せ命題 (Train) の容量はほぼ無限であり、各取引のコストを数桁削減できます。

実際の操作では、コストの削減は許容される遅延（および取引の到達速度）に依存します。さらに、各証明には通常、対応するオンチェーンデータ出力が伴うため、単一の証明とともに書き込まれるオンチェーンのデータ量も限られます。それにもかかわらず、コストを 1 桁削減し、さらなる性能向上を簡単に実現できます。

遅延の削減

再帰証明パターンは、大規模な組合せ命題の証明遅延を削減できます。2 つの要因が作用します：

受信した命題は並行して証明できます（巨大な組合せ命題を証明するのではなく）。
Train の最後の命題が到達するのを待つ必要はありません。代わりに、新しい命題が追加されると、いつでも証明と結合できます。つまり、Train に最後の命題が追加される遅延は、証明の最後の命題に必要な時間と、再帰検証器命題（この特定の Train に「追加された」命題をすべて証明する）に必要な時間の合計にほぼ相当します。

私たちは、証明の再帰検証器命題の遅延問題を積極的に開発および最適化しています。数ヶ月以内に、証明の再帰検証器命題は数分のオーダーに達する見込みです。したがって、高効率の SHARP 遅延は数分から数時間に制御でき、遅延の長さは各取引のオンチェーンコストのトレードオフに依存します。これは SHARP 遅延の大幅な改善です。

L3 アプリケーションの促進

Cairo で開発された再帰検証器命題は、StarkNet に証明を提出する可能性も開きます。なぜなら、この命題は StarkNet スマートコントラクトに書き込むことができるからです。これにより、StarkNet L2 公共ネットワーク上に L3 を展開することが可能になります。

再帰パターンは、L3 からの集約証明にも適用され、L2 上の単一の証明によって検証されます。したがって、L3 も超大規模なスケーリングを実現できます。

さらなる応用

再帰の応用

再帰は、コストと性能をさらに拡張したいプラットフォームやアプリケーションに新たな機会を開きます。

各 STARK 証明は、特定の「公開入力」（または Cairo 用語で「プログラム出力」）に対する命題の有効性を証明します。概念的には、STARK 再帰は 2 つの入力を持つ 2 つの証明を 1 つの 2 つの入力を持つ証明に圧縮します。言い換えれば、証明の数は減少しますが、入力の数は変わりません。次に、入力は通常、アプリケーションによって L1 上の特定の状態を更新するために使用されます（たとえば、状態ルートの更新やチェーン上の引き出しの実行）。

再帰命題がアプリケーション層で認識できる場合、つまりアプリケーション自体の意味を識別できる場合、再帰命題は 2 つの証明を圧縮するだけでなく、2 つの入力を 1 つに組み合わせることもできます。最終的な命題は、アプリケーションの意味に基づく入力の組み合わせの有効性を証明します。これが応用再帰（Applicative Recursion、図 3 の例を参照）です。

命題 1 は A から B への状態更新を証明し、命題 2 は B から C へのさらなる更新を検証します。命題 1 と命題 2 の証明は、A から C への更新を直接証明するための第 3 の命題に統合できます。類似の再帰ロジックを適用することで、状態更新のコストを非常に大幅に削減し、最終的な遅延要件を満たすことができます。

応用再帰のもう 1 つの重要な例は、複数の証明からの集約データを圧縮することです。たとえば、StarkNet のような有効性証明 Rollup に対して、L2 は各更新を L1 更新の伝送データとしても保存し、データの可用性を確保します。しかし、同じストレージユニットに対して複数回の更新を送信する必要はありません。なぜなら、証明によって検証された取引のみが最終的にデータの可用性を満たすからです。この最適化は、単一の StarkNet ブロック内で実行されています。しかし、各ブロックに対して証明を生成することで、応用再帰は複数の L2 ブロックの集約データを圧縮できます。これにより、コストを大幅に削減し、L2 のブロック生成時間を短縮し、L1 更新のスケーラビリティを犠牲にすることなく実現できます。

注意すべき点は、応用再帰は前述の応用汎用再帰と組み合わせて使用できることです。しかし、この 2 つの最適化は互いに無関係です。

オンチェーン検証器の複雑性の削減

STARK 検証器の複雑性は、検証に使用される命題の種類に依存します。特に Cairo 命題に関しては、検証器の複雑性は Cairo 言語で許可される特定の要素、より具体的にはサポートされる組み込み項目に依存します（Cairo を CPU に例えるなら、組み込み項目は CPU 内のマイクロサーキットに相当します：計算の実行が非常に頻繁であるため、自己計算を最適化する必要があります）。

Cairo 言語は進化し続け、ますます多くの有用な組み込み項目を提供しています。一方で、再帰検証器はごく一部の組み込み項目を使用するだけで済みます。したがって、再帰 SHARP は再帰検証器内の完全な言語をサポートすることで、Cairo 内の任意の命題を成功裏にサポートできます。具体的には、L1 上の Solidity 検証器は再帰証明のみを検証する必要があるため、検証器は Cairo 言語のより安定したサブセットの検証に限定できます。L1 検証器は最新の安定した組み込み項目に更新する必要はありません。言い換えれば、命題は進化し続け、複雑な検証は L2 に任せ、L1 検証器は単純で安定した命題を検証するだけで済みます。

計算フットプリントの削減

再帰の前には、複数の命題を 1 つの証明に集約することは、利用可能な計算インスタンス上で証明できる命題のサイズ（およびそのような証明を生成するのに必要な時間）の制限を受けていました。

再帰があれば、これほど大規模な命題を証明する必要はありません。なぜなら、より小さく安価な計算インスタンスが利用可能だからです（ただし、大型の単一証明器を使用する場合よりも多くの計算インスタンスが必要な場合があります）。これにより、より多くの物理的および仮想的な環境で証明器インスタンスを展開することが可能になります。