zkRollup および zkEVM トラックで発生するほとんどすべての問題は、本質的にアルゴリズムの問題です。 ZK-Proof ハードウェア アクセラレーションが頻繁に言及される主な理由は、現在のアルゴリズムが一般的に遅いためです。
「アルゴリズムだけでは足りない、ハードウェアで補う」という恥ずかしい状況に陥らないように、アルゴリズムの本質から問題を解決しなければなりません。絶妙な配信保証再帰の設計 この問題を解決する鍵となるのがスキームです。
スマートコントラクトの継続的な開発により、ますます多くのWeb3アプリケーションが徐々に登場しており、イーサリアムなどの従来のレイヤー1のトランザクション量は急速に増加しており、いつでも輻輳が発生する可能性があります。レイヤ 1 によるセキュリティを確保しつつ、いかに効率を高めるかが喫緊の課題となっています。
イーサリアムの場合、zkRollup は基礎となるコンポーネントとしてゼロ知識証明アルゴリズムを使用して、元々レイヤー 1 で実行する必要があった高価な計算をオフチェーンに移動し、実行の正しさの証明をチェーンに提供します。トラックには次のようなプロジェクトが含まれています。 スターウェア、zkSync、スクロール、 & フォックステック.
実際、zkRollup の設計には、効率に対する非常に高い要件があります。提出された証明値が十分に小さく、レイヤー 1 の計算量を削減できることが望まれます。十分に小さな証明長を取得するには、それぞれの証明値が十分に小さいことが望まれます。 zkRollup プロジェクトは、アルゴリズムとアーキテクチャ設計を改善しています。たとえば、Fox は、最適な証明時間と証明長を取得するために、最新のゼロ知識証明アルゴリズムと組み合わせた証明アルゴリズム FOAKS を開発しました。
また、証明を検証する段階において、最も簡単な手段は、証明を線形に生成し、それを逐次検証することである。効率を向上させるために、誰もが最初に考えるのは、複数の証明を 1 つの証明にパックすることです。これは一般に証明の集約と呼ばれます。
直感的に言えば、zkEVM によって生成されたプルーフの検証は線形プロセスであり、検証者は生成された各プルーフ値を順番に検証する必要があります。しかしながら、この検証方法は効率が比較的低く、通信オーバーヘッドが比較的大きい。 zkRollup シナリオの場合、検証者側のオーバーヘッドが高くなるとレイヤー 1 の計算が多くなり、ガス料金も高くなります。
まず例を見てみましょう。アリスは、今月 1 日から 7 日までフォックス パークに行ったことを世界に証明したいと考えています。そのため、１日から７日まで毎日、その日の新聞を持って公園内で写真を撮ることができ、この７枚の写真が証拠となる。
上記の例で 7 枚の写真を封筒に直接入れることは、直感的な意味での証明の集約です。これは、異なる証明を結合し、順番に線形に検証することに相当します。つまり、最初に最初の証明を検証し、次に 2 番目の証明を検証します。
2 つの証明とその後の証明。問題は、このアプローチでは、証明と検証を 1 つずつ行うのと同じで、証明のサイズも証明の時間も変わらないことです。対数空間圧縮を実現したい場合は、以下で説明する証明再帰を使用する必要があります。
Halo2 と STARK で使用される証明再帰スキーム
再帰的証明とは何かをよりよく説明するために、上の例に戻りましょう。
アリスの1枚の写真は2つの証拠です。ここで、アリスが 2 日に写真を撮り、2 日にこの写真を撮って 3 日に新聞を撮り、7 日に写真を撮って 6 番目の写真に新聞を撮ることができるように、これらを結合することを検討してください。類推すると、アリスは 7 日の写真と 1 日の新聞を合わせて 7 日に最後の写真を撮り、他の友人は 7 日の最後の写真を見ると、自分が XNUMX 日から XNUMX 日までであることを確認できます。
アリスはみんなで公園に行きました。これまでの7枚の証拠写真が1枚に圧縮されていることがわかります。そして、このプロセスにおける重要なスキルは「写真を含む写真」です。これは、前の写真を後続の写真に再帰的にネストすることに相当します。たくさんの写真を集めて1枚の写真を撮るのとは違います。
zkRollup の再帰的証明トリックにより、証明サイズを大幅に圧縮できます。具体的には、各トランザクションで証拠が生成されます。元のトランザクション計算回路をC0、C0の正当性証明としてP0、P0を検証する計算過程としてV0を設定します。
Prover はまた、V0 を C0' として示される対応する回路に変換します。現在、証明計算処理では、別トランザクションのC1、C0'とC1の回路をマージすることが可能です。このように、併合回路の正当性証明Ｐ１が検証されれば、上記２つの回路を同時に検証することと等価となる。トランザクションの正確性、つまり圧縮が達成されます。
上記のプロセスを振り返ると、圧縮の原理は検証と証明のプロセスを回路に変換し、「証明のための証明」を生成することであり、この観点から見ると、継続的に再帰できる操作であることがわかります。下向きなので、再帰的証明とも呼ばれます。
Halo2 と STARK で採用されている Proof Recursion スキームは、プルーフを並列に生成し、複数のプルーフを組み合わせることができるため、プルーフ値を検証しながら複数のトランザクション実行の正当性を検証することができ、計算オーバーヘッドを圧縮して、トランザクションの効率を大幅に向上させることができます。システム。
ただし、そのような最適化は依然として特定のゼロ知識証明アルゴリズムより上のレベルに留まります。効率をさらに向上させるためには、下位レベルの最適化とイノベーションが必要です。 Fox によって設計された FOAKS アルゴリズムは、この点までの証明内に再帰的なアイデアを適用することでこれを実現します。
FOAKS で使用される証明再帰スキーム
Fox Tech は、zkEVM ベースの zkRollup プロジェクトです。その証明体系には再帰的証明という手法も使われていますが、上記の再帰的手法とは意味合いが異なります。主な違いは、Fox が証明の中で再帰の考え方を使用していることです。 Fox が使用する再帰的証明の核となる概念を表現するには、還元された問題が十分に単純になるまで証明対象の問題を継続的に還元するために、別の例を示す必要があります。
上の例では、アリスは写真を撮って特定の日にフォックス パークに行ったことを証明するため、ボブは別の提案を出します。彼は、アリスが公園に行ったことを証明するという問題は、アリスの携帯電話が公園に行ったことを証明することに帰着できると考えています。そして、この問題の証明は、アリスの携帯電話の位置が公園の範囲内にあることを証明することに帰着することができます。
したがって、アリスが公園に行ったことを証明するには、公園にいる間に携帯電話で位置情報を送信するだけで済みます。このようにして、証明のサイズが写真（非常に高次元のデータ）から 3 次元データ（緯度、経度、時間）に変更され、効果的にコストが削減されます。
アリスの携帯電話がフォックス パークに行ったことがあるということは、アリスがそこに行ったことを意味しないのではないかと疑問に思う人もいるかもしれないので、この例は完全に適切というわけではありませんが、実際の状況では、この削減プロセスは厳密に数学的です。
具体的には、Fox の再帰的証明の使用は、回路レベルでの再帰です。ゼロ知識証明を行う場合、証明したい問題を回路に記述し、その回路を通して満たすべきいくつかの方程式を計算します。そして、これらの方程式が満たされていることを示す代わりに、これらの方程式を再度回路として書き、これを繰り返し、最終的には満足を証明する方程式が簡単に直接証明できるほど単純になります。
このプロセスから、これは「再帰」の意味に近いことがわかります。各再帰によって複雑さの証明 O(n) が O(f(n)) の証明と再帰プロセス自体の計算に変更されると仮定すると、すべてのアルゴリズムがこの再帰的手法を使用できるわけではないことに言及する価値があります。
計算量は O(g(n)) であり、1 回の再帰後の合計計算量は O2(n)=O(f(n))+O(g(n)) となり、3 回の再帰後には OXNUMX(n) になります。 =O(f(f(n)))+O(g(n))+O(g(f(n)))、XNUMX回後はOXNUMX(n)=O(f(f(f(n) ) )))+O(g(n))+O(g(f(n)))+O(g(f(f(n))))、…など。
したがって、このような再帰的手法は、アルゴリズムの特性に対応する f と g の 2 つの関数が Ok(n) を満たす場合にのみ有効に機能します。
まとめ
証明の複雑さは常に、ゼロ知識証明の適用において最も重要な鍵の 1 つです。特に zkEVM のような巨大な ZK アプリケーションでは、証明すべきものがますます複雑になるにつれて、証明の複雑さの性質がますます重要になります。
このシナリオでは、証明の複雑さが製品のパフォーマンスとユーザー エクスペリエンスに決定的な影響を与えます。最終的な証明の複雑さを軽減する多くの方法の中で、コア アルゴリズムの最適化が最も重要です。
Fox は、最先端のアルゴリズムに基づいた絶妙な配信証明スキームを設計し、このテクノロジーを使用して最適な zkEVM を作成します。 ZK-FOAKS アルゴリズムは、zkRollup 業界のパフォーマンス リーダーになることが期待されています。
免責事項： このウェブサイトの情報は一般的な市場解説として提供されており、投資アドバイスを構成するものではありません。 投資する前に、ご自身で調査を行うことをお勧めします。
ニュースを追跡するために私たちに参加してください： https://linktr.ee/coincu
ハロルド
コインク ニュース
著者
知識
より優れた証明再帰スキームを設計するには?
zkRollup および zkEVM トラックで発生するほとんどすべての問題は、本質的にアルゴリズムの問題です。 ZK-Proof ハードウェア アクセラレーションが頻繁に言及される主な理由は、現在のアルゴリズムが一般的に遅いためです。
「アルゴリズムだけでは足りない、ハードウェアで補う」という恥ずかしい状況に陥らないように、アルゴリズムの本質から問題を解決しなければなりません。絶妙な配信保証再帰の設計 この問題を解決する鍵となるのがスキームです。
スマートコントラクトの継続的な開発により、ますます多くのWeb3アプリケーションが徐々に登場しており、イーサリアムなどの従来のレイヤー1のトランザクション量は急速に増加しており、いつでも輻輳が発生する可能性があります。レイヤ 1 によるセキュリティを確保しつつ、いかに効率を高めるかが喫緊の課題となっています。
イーサリアムの場合、zkRollup は基礎となるコンポーネントとしてゼロ知識証明アルゴリズムを使用して、元々レイヤー 1 で実行する必要があった高価な計算をオフチェーンに移動し、実行の正しさの証明をチェーンに提供します。トラックには次のようなプロジェクトが含まれています。 スターウェア、zkSync、スクロール、 & フォックステック.
実際、zkRollup の設計には、効率に対する非常に高い要件があります。提出された証明値が十分に小さく、レイヤー 1 の計算量を削減できることが望まれます。十分に小さな証明長を取得するには、それぞれの証明値が十分に小さいことが望まれます。 zkRollup プロジェクトは、アルゴリズムとアーキテクチャ設計を改善しています。たとえば、Fox は、最適な証明時間と証明長を取得するために、最新のゼロ知識証明アルゴリズムと組み合わせた証明アルゴリズム FOAKS を開発しました。
また、証明を検証する段階において、最も簡単な手段は、証明を線形に生成し、それを逐次検証することである。効率を向上させるために、誰もが最初に考えるのは、複数の証明を 1 つの証明にパックすることです。これは一般に証明の集約と呼ばれます。
直感的に言えば、zkEVM によって生成されたプルーフの検証は線形プロセスであり、検証者は生成された各プルーフ値を順番に検証する必要があります。しかしながら、この検証方法は効率が比較的低く、通信オーバーヘッドが比較的大きい。 zkRollup シナリオの場合、検証者側のオーバーヘッドが高くなるとレイヤー 1 の計算が多くなり、ガス料金も高くなります。
まず例を見てみましょう。アリスは、今月 1 日から 7 日までフォックス パークに行ったことを世界に証明したいと考えています。そのため、１日から７日まで毎日、その日の新聞を持って公園内で写真を撮ることができ、この７枚の写真が証拠となる。
上記の例で 7 枚の写真を封筒に直接入れることは、直感的な意味での証明の集約です。これは、異なる証明を結合し、順番に線形に検証することに相当します。つまり、最初に最初の証明を検証し、次に 2 番目の証明を検証します。
2 つの証明とその後の証明。問題は、このアプローチでは、証明と検証を 1 つずつ行うのと同じで、証明のサイズも証明の時間も変わらないことです。対数空間圧縮を実現したい場合は、以下で説明する証明再帰を使用する必要があります。
Halo2 と STARK で使用される証明再帰スキーム
再帰的証明とは何かをよりよく説明するために、上の例に戻りましょう。
アリスの1枚の写真は2つの証拠です。ここで、アリスが 2 日に写真を撮り、2 日にこの写真を撮って 3 日に新聞を撮り、7 日に写真を撮って 6 番目の写真に新聞を撮ることができるように、これらを結合することを検討してください。類推すると、アリスは 7 日の写真と 1 日の新聞を合わせて 7 日に最後の写真を撮り、他の友人は 7 日の最後の写真を見ると、自分が XNUMX 日から XNUMX 日までであることを確認できます。
アリスはみんなで公園に行きました。これまでの7枚の証拠写真が1枚に圧縮されていることがわかります。そして、このプロセスにおける重要なスキルは「写真を含む写真」です。これは、前の写真を後続の写真に再帰的にネストすることに相当します。たくさんの写真を集めて1枚の写真を撮るのとは違います。
zkRollup の再帰的証明トリックにより、証明サイズを大幅に圧縮できます。具体的には、各トランザクションで証拠が生成されます。元のトランザクション計算回路をC0、C0の正当性証明としてP0、P0を検証する計算過程としてV0を設定します。
Prover はまた、V0 を C0' として示される対応する回路に変換します。現在、証明計算処理では、別トランザクションのC1、C0'とC1の回路をマージすることが可能です。このように、併合回路の正当性証明Ｐ１が検証されれば、上記２つの回路を同時に検証することと等価となる。トランザクションの正確性、つまり圧縮が達成されます。
上記のプロセスを振り返ると、圧縮の原理は検証と証明のプロセスを回路に変換し、「証明のための証明」を生成することであり、この観点から見ると、継続的に再帰できる操作であることがわかります。下向きなので、再帰的証明とも呼ばれます。
Halo2 と STARK で採用されている Proof Recursion スキームは、プルーフを並列に生成し、複数のプルーフを組み合わせることができるため、プルーフ値を検証しながら複数のトランザクション実行の正当性を検証することができ、計算オーバーヘッドを圧縮して、トランザクションの効率を大幅に向上させることができます。システム。
ただし、そのような最適化は依然として特定のゼロ知識証明アルゴリズムより上のレベルに留まります。効率をさらに向上させるためには、下位レベルの最適化とイノベーションが必要です。 Fox によって設計された FOAKS アルゴリズムは、この点までの証明内に再帰的なアイデアを適用することでこれを実現します。
FOAKS で使用される証明再帰スキーム
Fox Tech は、zkEVM ベースの zkRollup プロジェクトです。その証明体系には再帰的証明という手法も使われていますが、上記の再帰的手法とは意味合いが異なります。主な違いは、Fox が証明の中で再帰の考え方を使用していることです。 Fox が使用する再帰的証明の核となる概念を表現するには、還元された問題が十分に単純になるまで証明対象の問題を継続的に還元するために、別の例を示す必要があります。
上の例では、アリスは写真を撮って特定の日にフォックス パークに行ったことを証明するため、ボブは別の提案を出します。彼は、アリスが公園に行ったことを証明するという問題は、アリスの携帯電話が公園に行ったことを証明することに帰着できると考えています。そして、この問題の証明は、アリスの携帯電話の位置が公園の範囲内にあることを証明することに帰着することができます。
したがって、アリスが公園に行ったことを証明するには、公園にいる間に携帯電話で位置情報を送信するだけで済みます。このようにして、証明のサイズが写真（非常に高次元のデータ）から 3 次元データ（緯度、経度、時間）に変更され、効果的にコストが削減されます。
アリスの携帯電話がフォックス パークに行ったことがあるということは、アリスがそこに行ったことを意味しないのではないかと疑問に思う人もいるかもしれないので、この例は完全に適切というわけではありませんが、実際の状況では、この削減プロセスは厳密に数学的です。
具体的には、Fox の再帰的証明の使用は、回路レベルでの再帰です。ゼロ知識証明を行う場合、証明したい問題を回路に記述し、その回路を通して満たすべきいくつかの方程式を計算します。そして、これらの方程式が満たされていることを示す代わりに、これらの方程式を再度回路として書き、これを繰り返し、最終的には満足を証明する方程式が簡単に直接証明できるほど単純になります。
このプロセスから、これは「再帰」の意味に近いことがわかります。各再帰によって複雑さの証明 O(n) が O(f(n)) の証明と再帰プロセス自体の計算に変更されると仮定すると、すべてのアルゴリズムがこの再帰的手法を使用できるわけではないことに言及する価値があります。
計算量は O(g(n)) であり、1 回の再帰後の合計計算量は O2(n)=O(f(n))+O(g(n)) となり、3 回の再帰後には OXNUMX(n) になります。 =O(f(f(n)))+O(g(n))+O(g(f(n)))、XNUMX回後はOXNUMX(n)=O(f(f(f(n) ) )))+O(g(n))+O(g(f(n)))+O(g(f(f(n))))、…など。
したがって、このような再帰的手法は、アルゴリズムの特性に対応する f と g の 2 つの関数が Ok(n) を満たす場合にのみ有効に機能します。
まとめ
証明の複雑さは常に、ゼロ知識証明の適用において最も重要な鍵の 1 つです。特に zkEVM のような巨大な ZK アプリケーションでは、証明すべきものがますます複雑になるにつれて、証明の複雑さの性質がますます重要になります。
このシナリオでは、証明の複雑さが製品のパフォーマンスとユーザー エクスペリエンスに決定的な影響を与えます。最終的な証明の複雑さを軽減する多くの方法の中で、コア アルゴリズムの最適化が最も重要です。
Fox は、最先端のアルゴリズムに基づいた絶妙な配信証明スキームを設計し、このテクノロジーを使用して最適な zkEVM を作成します。 ZK-FOAKS アルゴリズムは、zkRollup 業界のパフォーマンス リーダーになることが期待されています。
免責事項： このウェブサイトの情報は一般的な市場解説として提供されており、投資アドバイスを構成するものではありません。 投資する前に、ご自身で調査を行うことをお勧めします。
ニュースを追跡するために私たちに参加してください： https://linktr.ee/coincu
ハロルド
コインク ニュース
その他の投稿
関連記事
