zkEVMの課題と現状

zkEVMの設計上の課題

1. EVMは楕円曲線のサポートが限定的

検証アルゴリズムはEVMフレンドリーである必要があるが、EVMはBN254ペアリングのみをサポートしており周期的楕円曲線は直接サポートされていないので、recrucive SNARKは無理

また、他の特殊なzkプロトコルを使用することも困難

2. EVMのワードサイズは256bit

EVMは256ビットの整数で動作する(通常のVMが32-64ビットの整数で動作するのと同じ）が、zk証明は素数体上で動作するので回路内で不一致なフィールド演算を行うにはrange proofが必要となり、EVMステップごとに〜100の制約が追加される

これは、EVMの回路サイズを2桁も増大させることになる

3. EVMには特殊なオペコードが多い

EVMは従来のVMとは異なり、CALLなどの特殊なオペコードが多く、また実行コンテキストやガスに関連したエラータイプも存在し、回路設計に新たな課題をもたらすらしい

sotreするtableのサイズが大きくなるのでストレージの話かな？と思った

4. EVMはスタックベースの仮想マシンである

SyncVM（zksync）やCairo（starkware）アーキテクチャは、レジスタベースモデルで独自のIR/AIRを定義している

彼らは、スマートコントラクトのコードを新しいzkフレンドリーなIRにコンパイルするために、専用のコンパイラを構築た

つまり彼らのアプローチは、ネイティブEVM互換ではなく、言語互換

ネイティブツールチェーンを直接サポートできるがスタックベースモデルでは証明が難しい

5. Ethereumのストレージレイアウトは大きなオーバーヘッドを伴う

Ethereumのストレージレイアウトは、Keccakと巨大なMPTに強く依存しており、どちらもzkフレンドリーではなく、証明のオーバーヘッドが大きい

しかし、Keccakを他のハッシュに置き換えると、既存のEthereumのインフラとの互換性の問題が発生する

6. 機械ベースの証明には巨大なオーバーヘッドがある

前述した問題をすべて適切に処理できたとしても、完全なEVM回路を得るためには、それらを効率的に合成する方法を見つける必要がある

前項で述べたように、addのような単純なオペコードでさえ、EVM回路全体のオーバーヘッドになりかねない

改善されているポイント

再帰的証明(Recrusive SNARK)、ルックアップテーブル、ハードウェア、多項式コミットメント

この分野における研究者の大きな進歩のおかげで、zkEVM の証明コストは最終的に実現可能なものとなった

多項式コミットメント

過去数年間、ほとんどの簡潔なゼロ知識証明プロトコルは、アプリケーション固有の信頼できる設定でエンコードされたPCPクエリを持つR1CSに固執していた。

各制約の次数は2である必要があるため（バイリニアペアリングでは指数を1つだけ乗算できる）、回路サイズは通常爆発的に大きくなり、多くのカスタマイズ最適化を行うことはできません。

多項式コミットメントスキームでは、ユニバーサルセットアップなどよって、制約を任意の次数に引き上げることができる

ユニバーサルセットアップ=PLONKのように一回のTrusted Setupで大丈夫なやつ

ルックアップテーブルの引数とカスタマイズされたガジェットの出現

この最適化は、まずAryaで提案され、その後Plookupで最適化された

これはzkに不親切なプリミティブ(すなわち、AND、XORなどのビット演算)を大幅に節約することができる

カスタマイズされたガジェットを使えば、高度な制約を効率的に行うことができます。

TurboPlonkとUltraPlonkはルックアップテーブルの使用とカスタマイズされたガジェットの定義を容易にするためにエレガントなプログラムシンタックスを定義しており、EVM回路のオーバーヘッドを減らすのに非常に有効

再帰的証明の実現性が高まっている

再帰的証明は、特殊なペアリングに適した巡回楕円曲線（＝MNT曲線ベースの構成）に依存するため、従来は大きなオーバーヘッドが発生していた

しかし、より多くの技術により、効率を犠牲にすることなく実現できるようになってきている

例えば、Haloはペアリングに適した曲線の必要性を回避し、特別な内積引数を用いて再帰のコストを償却可能

Aztecは、既存のプロトコルに対して直接証明集約ができることを示している

（ルックアップテーブルは非ネイティブフィールド演算のオーバーヘッドを削減し、検証回路を小さくすることが可能である）

これにより、サポートする回路規模のスケーラビリティを大幅に向上させることができる

ハードウェアアクセラレーションによる証明の効率化

既にチームは最速(自称)のGPUとASIC/FPGAアクセラレータを作成した

GPUによる証明は、Filecoinの実装よりも約5倍から10倍高速らしい