執筆：Fox Tech CTO 林彦熹、Fox Tech チーフサイエンティスト 孟铉济

前言：

zkRollupおよびzkEVMの分野で直面するほぼすべての課題は、本質的にはアルゴリズムの問題です。ZKPハードウェアアクセラレーションがしばしば言及される主な理由は、現在のアルゴリズムが一般的に遅いためです。「アルゴリズムが不十分で、ハードウェアで補う」という困難な状況に陥らないために、私たちは本質的なアルゴリズムから問題を解決する必要があります。巧妙な証明の再帰的な設計がこの問題を解決する鍵です。

スマートコントラクトの進展に伴い、ますます多くのweb3アプリケーションが登場し、Ethereumなどの従来のLayer1の取引量が急速に増加し、いつでも混雑が発生する可能性があります。Layer1が提供するセキュリティを確保しつつ、より高い効率を得る方法が急務となっています。

Ethereumにとって、zkRollupはゼロ知識証明アルゴリズムを基盤コンポーネントとして使用し、Layer1上で実行する必要がある高価な計算をオフチェーンに移し、チェーン上に実行の正当性を証明するものです。この分野には、StarkWare、zkSync、Scroll、Fox Techなどのプロジェクトがあります。

実際、zkRollupの設計では、効率に対する要求が非常に高いです：提出される証明値が十分に小さいことが望まれ、これによりLayer1の計算量を軽減できます。十分に小さな証明長を得るために、各zkRollupプロジェクトはアルゴリズムやアーキテクチャ設計を改善しています。たとえば、Foxは最新のゼロ知識証明アルゴリズムを組み合わせて独自の証明アルゴリズムFOAKSを開発し、最適な証明時間と証明長を実現しています。

さらに、証明の検証段階では、最も一般的な手段は線形に証明を生成し、順次検証することです。効率を向上させるために、最初に考えられるのは複数の証明を1つの証明にパッケージ化すること、これが通常言及される証明の集約（Proof Aggregation）です。

直感的に言えば、zkEVMが生成する証明を検証することは線形のプロセスであり、検証者（Verifier）は生成された各証明値を順次検証する必要があります。しかし、この検証方法は効率が低く、通信コストも大きく、zkRollupのシナリオでは、検証者側のコストが高くなるほどLayer1の計算が増え、結果としてGas費用が高くなります。

まず、例を見てみましょう：アリスは、今月の1日から7日までFox公園に行ったことを全世界に証明したいと考えています。そのため、彼女は1日から7日までの毎日、公園でその日の新聞を持って写真を撮ることができます。この7枚の写真が1つの証明になります。

図1：一般的な証明の集約方案

上記の例では、7枚の写真を直接1つの封筒に入れることが直感的な意味での証明の集約です。実際の状況では、異なる証明をつなげて順次線形に検証することに相当します。つまり、最初の証明を検証し、次の証明およびその後の証明を検証します。この方法では、証明の大きさや時間は変わらず、1つずつ証明して検証するのと同じ効果です。対数レベルの空間圧縮を実現するには、以下で述べる再帰的証明（Proof Recursion）を使用する必要があります。

Halo2およびSTARKで使用される証明の再帰的方案

再帰的証明とは何かをより良く説明するために、上記の例に戻ります。

アリスの7枚の写真は実際には7つの証明です。これらを統合することを考えると、アリスは1日に写真を撮り、2日目にはその写真と2日の新聞を持って写真を撮り、3日目には2日の写真と3日の新聞を持って写真を撮ります。このようにして、アリスは7日目に6日の写真と7日の新聞を持って最後の写真を撮ります。他の仲間たちは、7日のこの最後の写真を見て、アリスが1日から7日まで公園に行ったことを検証できます。以前の7枚の証明写真が1枚に圧縮されたことがわかります。このプロセスの中での重要なテクニックは「写真を含む写真」であり、以前の写真を再帰的な形で後の写真にネストしたことに相当します。これは、多くの写真を一緒に置いて再度写真を撮ることとは異なります。

zkRollupの再帰的証明のテクニックは、証明の大きさを大幅に圧縮できます。具体的には、各取引は証明を生成し、元の取引計算回路をC0、C0の正当性証明をP0、P0を検証する計算プロセスをV0とします。証明者（Prover）はV0を対応する回路に変換し、C0'とします。この時、別の取引の証明計算プロセスC1は、C0'とC1の回路を統合することができます。こうすることで、統合された回路の正当性証明P1を検証すれば、上記の2つの取引の正当性を同時に検証したことになります。つまり、圧縮を実現したことになります。

このプロセスを振り返ると、実際には証明を検証するプロセスを再び回路に変換し、「証明の証明」を生成することに基づいています。したがって、この観点から見ると、これは再帰的に下に向かって操作できるものです。これが再帰的証明と呼ばれる所以です。

図2：Halo2とStarkで使用される再帰的証明方案

Halo2およびSTARKが採用するProof Recursion方案は、証明を並行して生成し、複数の証明を統合することができ、1つの証明値を検証する際に複数の取引の実行の正当性を検証できるため、計算コストを圧縮し、システムの効率を大幅に向上させることができます。

しかし、このような最適化は依然として具体的なゼロ知識証明アルゴリズムのレベルに留まっており、さらに効率を向上させるためには、より基盤的な最適化と革新が必要です。Foxが設計したFOAKSアルゴリズムは、再帰的な考え方を証明の内部に適用することでこれを実現しました。

FOAKSで使用される証明の再帰的方案

Fox TechはzkEVMベースのzkRollupプロジェクトです。その証明システムでも再帰的証明のテクニックを使用していますが、上記の再帰的方式とは異なる内包を持っています。主な違いは、Foxが1つの証明の内部で再帰（Recursion）の考え方を使用していることです。Foxが使用する再帰的証明の核心的な考え方を表現するために、さらに別の例を挙げる必要があります。

上記の例では、アリスが写真を撮ってFox公園に行ったことを証明しましたが、ボブは異なる提案をしました。彼は、アリスが公園に行ったことを証明する問題を、アリスの携帯電話がその公園に行ったことを証明することに還元できると考えました。そして、この証明はアリスの携帯電話の位置情報が公園の範囲内にあることを証明することに還元できます。したがって、アリスがこの公園に行ったことを証明するためには、公園にいるときに携帯電話で位置情報を送信すればよいのです。

こうすることで、証明の大きさは元の1枚の写真（非常に高次元のデータ）から3次元のデータ（緯度、経度、時間）に変わり、コストを効果的に節約できます。この例は完全に適切ではありません。なぜなら、アリスの携帯電話がFox公園に行ったからといって、アリス本人が行ったことを証明するわけではないからです。しかし、実際の状況では、この還元プロセスは数学的に厳密です。

具体的には、Foxの再帰的証明の使用法は回路レベルの再帰です。ゼロ知識証明を行う際に、証明する問題を回路として記述し、次にその回路を通じて満たすべき等式を計算します。そして、これらの等式が満たされていることを示すのではなく、再びこれらの等式を回路として記述し、こうして繰り返します。最終的に証明すべき等式が十分に単純になるまで続け、私たちは簡単に直接証明できるようになります。

このプロセスから、これが「再帰」の意味により近いことがわかります。すべてのアルゴリズムがこの再帰技術を使用できるわけではないことに注意が必要です。仮に、各再帰がO(n)の複雑さの証明をO(f(n))の証明に変え、この再帰プロセス自体の計算複雑さがO(g(n))であるとすると、再帰を1回行った後の総計算複雑さはO1(n)=O(f(n))+O(g(n))、2回後はO2(n)=O(f(f(n)))+O(g(n))+O(g(f(n)))、3回後はO3(n)=O(f(f(f(n))))+O(g(n))+O(g(f(n)))+O(g(f(f(n))))、…と続きます。このように、fとgの2つの対応するアルゴリズム特性の関数が、あるkに対してOk(n)<O(n)を満たす場合にのみ、このような再帰技術が効果的に機能します。Foxでは、この再帰技術を効果的に使用して証明の複雑さを圧縮しています。

図3：ZK-FOAKSで使用される再帰的証明方案

結語

証明の複雑さは、ゼロ知識証明の応用において常に最も重要な要素の1つです。証明の複雑さは、証明すべき事柄がますます複雑になるにつれて、ますます重要になります。特に、zkEVMのような巨大なZKアプリケーションのシナリオでは、証明の複雑さが製品の性能やユーザー体験に決定的な影響を与えます。最終的な証明の複雑さを低下させるための多くの方法の中で、コアアルゴリズムの最適化が最も重要です。Foxは最前線のアルゴリズムに基づいて巧妙な再帰的証明方案を設計し、この技術を利用してzkEVMに最も適したZK-FOAKSアルゴリズムを構築しました。これは、zkRollup界の性能担当となることが期待されています。

参考文献

1. https://blog.csdn.net/weixin_44383880/article/details/126338813
2. https://blog.csdn.net/freedomhero/article/details/126727033