zk-SNARKs：簡潔な非対話型証明

zk-SNARK（Zero-Knowledge Succinct Non-interactive ARgument of Knowledge）とは、(1) ゼロ知識性を持ち、(2) 簡潔であり（証明が非常に小さく、計算量に関係なく検証が高速）、(3) 非対話型である（単一の証明文字列で構成される）証明です。

Σプロトコルは、離散対数の知識のような単純な命題に適しています。しかし、「秘密の入力に対してこの関数を正しく実行した」のような複雑な計算には、汎用的な証明システムが必要です。SNARKは、任意の計算をO(1)の検証時間で証明します。

まず、計算を算術回路として表現します。算術回路は、有限体上の加算ゲートと乗算ゲートからなる有向非巡回グラフです。例として、x=3を明かさずに、x^3 + x + 5 = 35を満たすxを知っていることを証明します。この回路は約5ゲートで構成されます。

算術回路はR1CSに変換されます。R1CSは、zをすべてのワイヤ値のベクトルとしたときの、(A*z)*(B*z) = C*zという制約の集合です。各乗算ゲートは1つの制約になります。証明者は、秘密のワイヤを明かさずに、すべての制約を満たすzを見つける必要があります。

R1CSはQAPに変換されます。QAPは、A(x)*B(x)-C(x)が目標多項式t(x)で割り切れることと、制約が満たされることが同値になるような多項式A(x)、B(x)、C(x)で構成されます。証明者は、witnessを明かさずに、多項式商H(x)を知っていることを示します。

Groth16（2016）は、最も効率的な汎用SNARKです。信頼済みセットアップ（CRS生成）の後、証明者は3つの群要素からなる証明を出力します（BLS12-381では約192バイト）。検証には3回のペアリング演算を使います。回路のサイズに関係なく、証明サイズは一定です。

Groth16では回路ごとに信頼済みセットアップが必要です。トキシック・ウェイスト（ランダムな秘密情報）を生成してCommon Reference Stringを計算し、その後トキシック・ウェイストを破棄します。これが残っていると、攻撃者は偽の証明を作成できます。複数当事者によるセレモニー（Powers of Tau）によって、信頼を分散できます。

PLONK（2019）はユニバーサルな信頼済みセットアップを使用します。1回のセレモニーで、サイズ上限までのすべての回路に対応できます。回路ごとのセットアップは必要ありません。トレードオフとして、Groth16より証明がやや大きくなります。Polygon HermezやzkSync EraなどのZK-EVM実装で使用されています。

STARK（Scalable Transparent ARguments of Knowledge）は信頼済みセットアップを必要とせず、ハッシュ関数を使用します（耐量子安全です）。トレードオフとして、証明が大きくなります（200バイトに対して数十KB）。StarkWare、StarkNet、Cairo言語で使用されています。SNARKは小さく、STARKは耐量子性を備えています。

Groth16は双線形ペアリングを使用します。e: G1 × G2 → GTであり、e(a*P, b*Q) = e(P,Q)^{ab}を満たします。これにより、値を明かさずに指数上の多項式恒等式を検証できます。BLS12-381曲線は、効率的なGroth16のペアリング向けに最適化されています。

10^6ゲートの回路に対するGroth16の証明生成時間は、最新のCPUで約10秒です。検証は約1ミリ秒です。この非対称性は意図されたものです。重い計算を行った証明者が処理を担当し、検証者（ブロックチェーンノード）はほぼゼロの処理で済みます。

PLONKと比較した場合、Groth16の主な欠点は何ですか？

zk-SNARKは、任意の計算を一定サイズの証明で証明します。処理の流れは、計算 → 算術回路 → R1CS → QAP → SNARK証明です。Groth16は最も効率的ですが、回路ごとに信頼済みセットアップが必要です。PLONKはユニバーサルセットアップを使用します。次は、ブロックチェーンにおけるZKPの応用です。