zkSNARKのプロトコルではどのように公開入力をパラメータ化しているのか？

Table of Contents

はじめに

今回は小ネタです。zkSNARK（¹など）の記事を読むと「回路を数式に落とし込んでいるんだな」ということは分かると思いますが、単純なアルゴリズムでは「予め決められた形式の回路に対して出力が1になる何らかの非公開入力（private input）が存在する」ということの証明しかできません。

例えばZeroSyncなど（ZeroSyncはSTARKを使っていますが）一度だけ証明を検証すればいいケースではこれだけで役に立つ場合もあるのですが、スマートコントラクトやその他の大部分のケースでは、検証用の回路は一度だけ用意（＝スマートコントラクトをデプロイ）したいのです。そして、その検証用の回路に対して「公開入力(public input)」と「証明」を渡すことにより、公開入力の元でパラメータ化された様々な条件の回路に対して、渡した証明が正しいかどうかを繰り返し検証したいです。

これは、スマートコントラクトのデプロイに手数料がかかること、そしてデプロイが毎回手動であるよりもパラメータを取る形の回路の方が自律的に動作するスマートコントラクトを記述できるためです。

例として、トルネードキャッシュ（Tornado Cash）²³の場合を考えます。
トルネードキャッシュの基本的な仕組みの説明は参考文献²³に譲るとして、これらの仕組みの説明の中では「現在のコントラクトの状態（マークルルートの状態）」をzkSNARK検証器に渡しています。つまり、純粋な証明だけを受け取る回路の検証器ではなくコントラクトの状態によってパラメータ化された回路の検証をしているといえます。

今回この記事で説明するのは、Groth16⁴系のzkSNARK証明システムにおける具体的な公開入力値のパラメータ化方法になります。

パラメータ化

公開入力値と非公開入力値は、回路の内部的には同じカテゴリの変数aを使って表現されています。論文⁴ の 2.3 Quadratic arithmetic programsに書いてあります。

しかし論文⁴ の 2.2 Non-interactive zero-knowledge arguments of knowledge で定義されているとおり、公開入力値はステートメント(φ)、非公開入力値は証拠(w)としてプロトコル上では区別して記述しています。

すなわち、 $\phi = (a_1, ..., a_l) \in \mathbb{F}^l, w = (a_{l+1}, ..., a_m) \in \mathbb{F}^{m-l}$ としています。

具体的なパラメータ化の手順については 3.1 Non-interactive linear proofs for quadratic arithmetic programs に書かれています。

証明したい、パラメータ化されていない式が以下の式であるとします。(ただし全部が0にならないように $a_0 = 1$ であるとします)

$a_i \in \mathbb{F}, u_i, v_i, w_i, h, t \in \mathbb{F}[X]$ に対して $\sum_{i=0}^{m} a_i u_i(X) \cdot \sum_{i=0}^{m} a_i v_i(X) = \sum_{i=0}^{m} a_i w_i(X) + h(X)t(X)$ ... (※)

なぜこのような式を証明することになるのかという具体的な経緯については省略しますが、各 $a_i$ が回路への入力になっています。このうち、ステートメント $\phi$ にあたる $(a_1, ..., a_l)$ だけを公開して、 $w$ にあたる $(a_{l+1}, ..., a_m)$ は公開しないまま、(※)の式の関係を証明したいということになります。

もしもパラメータ化をせずにこの式(※)を証明するということになれば、入力変数aは全て非公開になります。パラメータ化をする場合、証明者は以下のように間接的に変数A,B,Cを用意して検証者に対し証明する式とします。なお、ここで作成した値を直接検証者に送信するわけではないです。

証明者の作成する証明

乱数 $\alpha, \beta, \gamma, \delta, x, r, s \in \mathbb{F}^*$ に対して、以下の共通参照可能な式は検証者に共有されているとします。

$(\sigma, \tau) = ((\alpha, \beta, \gamma, \delta, \{x^i\}_{i=0}^{n-1}, \{ \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma}\}_{i=0}^{l}, \{ \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta}\}_{i=l+1}^{m}), \{\frac{x^i t(x)}{\delta} \}_{i=0}^{n-2} ), (\alpha, \beta, \gamma, \delta, x))$

以下のA,B,Cを計算し、証明したい式とします。

$A = \alpha + \sum_{i=0}^{m} a_i u_i(x) + r\delta$
$B = \beta + \sum_{i=0}^{m} a_i v_i(x) + s\delta$
$C = \frac{ \sum_{i=l+1}^{m} a_i (\beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x)t(x) } {\delta} + As + rB -rs\delta$

検証

$A\cdot B = \alpha \cdot \beta + \frac{ \sum_{i=0}^{l} a_i (\beta u_i(x) + \alpha v_i(x) + w_i(x)) } {\gamma} \cdot \gamma + C \delta$

であることを検証します。この検証の式を変形すると(※)の式と同値であることがわかります（完全性）。

解説

証明者は $\phi$ にあたる $(a_1, ..., a_l)$ と、 $w$ にあたる $(a_{l+1}, ..., a_m)$ を使って制約(※)を満たすA, B, Cを作成することができ、検証者は参照可能な式 $(\sigma, \tau)$ と、与えられたA,B,Cと $\phi$ にあたる $(a_1, ..., a_l)$ だけを使って手元で式を組み立てることが可能、というのが大まかな説明です。
繰り返しになりますが、上記でやりとりされる数字は全てそのまま送信されるわけではなく、楕円曲線ペアリングで計算・検証可能になるように楕円曲線上の点として送信されるため、検証者は限られた値しか実際には知ることができないということに注意してください。楕円曲線ペアリングでの計算については¹を参照してください。

また、この式の安全性に関する詳しい解説は他のブログ⁵を参考にしてみてください。