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

前言

ProverとVerifierの間の計算代理の考え方は、ゼロ知識証明の核心的な内容の一つであり、証明者と検証者の作業量と複雑性のトレードオフを調整するためのツールです。異なるゼロ知識証明アルゴリズムの本質的な違いは、計算代理の程度の違いにあります；高度な代理は検証の計算を容易にしますが、証明の複雑性が高くなる可能性があり、その結果、証明にかかる時間が長くなったり、生成される証明のサイズが大きくなったりします；逆に、低い程度の代理は検証者の負担を大きくします。

図1: ゼロ知識証明の計算代理の程度の影響

計算代理とは

イーサリアム上のアプリケーションとユーザーの拡大に伴い、イーサリアムメインネットの混雑度は増しており、zkRollupを使用したLayer2の拡張が非常に魅力的な選択肢となっています。FOXはFOAKSアルゴリズムを使用したzkRollupに特化したプロジェクトです。zkRollupの実現可能性は、使用されるゼロ知識証明アルゴリズムの原理の実現可能性に本質的に依存しています。簡単に言えば、ゼロ知識証明アルゴリズムの機能は、証明者が検証者に対して何かを証明することですが、その事柄に関する情報は一切開示しません。zkRollupの構造はこの特性を利用しており、Layer2のノードが本来Layer1で行われる計算を実行し、同時にLayer1ノードに計算の正当性を証明する証明を提供します。

より広義の観点から見ると、上記のプロセスは、検証者（Layer1ノード）の計算能力が限られているため、この部分の計算を証明者（Layer2ノード）に代理させて実行させることができると理解できます。証明者がこのタスクを完了し、結果を検証者に返す必要があります。この観点から、ゼロ知識証明アルゴリズムは正当性を保証する「計算代理」を実現することを可能にします。マクロ的には、このような計算代理の例はzkRollupのような形式のアプリケーションとして表現され、具体的なゼロ知識アルゴリズムの中でもこの計算代理の考え方はさまざまな応用があります。

この記事では、FOAKSがOrionで言及したCode-Switchingを使用して、証明者が検証者のために検証計算を実行するプロセスと、FOAKSがこの技術をどのように適用して再帰を行うかについて紹介します。これにより、証明のサイズと検証者の負担を軽減しました。

なぜ計算代理が必要なのか

システムの実用性の観点から見ると、多くの場合、計算ノードの計算能力は限られているか、計算リソースが非常に貴重です。例えば、Layer1チェーン上のすべての計算（送金や契約呼び出しを含む）は、すべてのノードの合意を経る必要があり、ユーザーは高額な手数料を支払う必要があります。したがって、このような状況では、本来合意ノードが処理する計算を「代理して」オフチェーンノードに完了させることは自然な考え方であり、チェーン上のリソースの消費を避けることができます。これがFOXが特化しているオフチェーン計算サービスです。

暗号理論の観点から見ると、GMRモデルでは証明者が無限の計算能力を持ち、検証者が多項式の計算能力を持つことが制限されています。もし検証者も無限の能力を持つなら、ゼロ知識証明の基本的な性質は満たされません。したがって、自然に計算を証明者側に傾け、証明者により多くの計算を負担させることは、多くのゼロ知識証明アルゴリズムの設計で考慮される問題です。

もちろん、これを実現するためには特別な技術が必要です。

Code Switching

このセクションでは、Orionで使用されているCode Switching技術について紹介します。OrionとFOAKSは、Brakedownを多項式コミットメントスキームとして使用しており、Code SwitchingはOrionで命名された、証明者が検証者の代わりに検証計算を実行するプロセスです。

「FOAKSにおける多項式コミットメントプロトコルBrakedownを理解するための一文」において、検証者の検証計算は以下のプロセスであると紹介しました：

idxI,C0[idx]==\<0,C1[:,idx]>and EC(y0)==C0

idxI,C1[idx]==\<r0,C1[:,idx]>and EC(y1)==C1

今、証明者にこの計算を負担させると、証明者はこれらの計算を実行するだけでなく、自身の計算が正しいことを証明するために証明値を添付する必要があります。

方法は、上記の等式を同様にR1CS回路に書き換えることです：

Statement:

EC(y0)=C0, EC(y1)=C1

idxI,C0[idx]=\<0,C1[:,idx]>and EC(y0)=C0

idxI,C1[idx]=\<r0,C1[:,idx]>and EC(y1)=C1

y=\<r1, y1>

idxI, EC(C1[:,idx]) is consistent with ROOTidx, and ROOTidx's Merkle tree proof is valid.

その後、Virgoアルゴリズムを使用して検証します。

FOAKSにおける計算代理

FOAKSでも同様の技術を使用して計算代理を完了しています。特に、FOAKSはFiat-Shamirヒューリスティック技術を使用して非対話式証明を実現している点が注目に値します。詳細を知りたい方は、「対話式証明を非対話式に変換する方法？Fiat-Shamirヒューリスティック！」を参照してください。したがって、FOAKSのチャレンジ生成とOrionで使用されるCode Switchingの方法は異なり、回路には新しい等式を追加する必要があります：

0=H(C1,R, r0,r1)

I=H(C1,R, r0,r1,c1,y1,c0,y0)

これにより、FOAKSの証明者も同様に代理検証者による検証の計算証明を生成しました。証明の検証プロセスに関しては、FOAKSはアルゴリズム自体を利用して反復を行い、これがFOAKSが再帰を実現するための重要な内容です。具体的な内容は「巧妙な証明再帰スキームを設計する方法」を参照してください。

一定回数の反復を行うことで、証明のサイズを圧縮し、検証者の計算負担と通信の複雑性を大幅に低減することができます。これがFOAKSというゼロ知識証明スキームがFOXのzkRollupにとって重要な意義を持つ理由です。

結語

zkRollupで使用されるゼロ知識証明アルゴリズムの計算代理の程度は慎重に設計される必要があり、全体の効率を最適化するためには適切でなければなりません。FOAKSアルゴリズムは自身の反復による再帰を通じて調整可能な計算代理を実現しており、zkRollupのために特別に設計されたゼロ知識証明アルゴリズムです。

参考文献

1. Orion： Xie, Tiancheng, Yupeng Zhang, and Dawn Song. "Orion: Zero knowledge proof with linear prover time." Advances in Cryptology--CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15--18, 2022, Proceedings, Part IV. Cham: Springer Nature Switzerland, 2022.