非対話零知識証明 zk-SNARKs の解説良記事を数学的ハードルを下げつつ日本語で解説していく Part-6/7 #認証

概要

zk-SNARKs に関する ELECTRIC COIN CO. の解説記事に簡単に補足をしながら紹介するシリーズ Part 6 です。

Part 5 では、アリスがボブに証明したいステートメントを二次算術プログラム(QAP)と呼ばれる形式に変換できることを見てきました。

このパートでは、アリスはボブに非常に短い証拠を送信することで、QAP を構成する割り当て(Part 5 の例における $c_1,c_2,c_3,c_4,c_5$)を持っていることを証明できる、ということを説明します。

そのために Parno、Howell、Gentry、Raykova のピノキオプロトコル¹を使います。

The Pinocchio Protocol

対応する記事

Explaining SNARKs Part VI: The Pinocchio Protocol

一言でいうと

これまで見てきた Homomorphic Hidings（HH: 準同型隠蔽）や検証可能な多項式の盲検や二次算術プログラム(QAP)を使うと、アリスとボブは互いの秘密の情報について知ることなく、アリスが条件を満たす割り当て $(c_1,...,c_m)$ を持っていることをボブが検証できます。

二次算術プログラム(QAP) のおさらい

まずは QAP の定義を思い出してみましょう。

多項式: $L_1,...,L_m, R_1,...,R_m, O_1,...,O_m$
割り当て $(c_1,...,c_m)$

を使って、以下のように $P$ を定義します。

$L := c_1 \cdot L_1 + ... + c_m \cdot L_m = \sum_{i=1}^{m} c_i \cdot L_i$
$R := c_1 \cdot R_1 + ... + c_m \cdot R_m = \sum_{i=1}^{m} c_i \cdot R_i$
$O := c_1 \cdot O_1 + ... + c_m \cdot O_m = \sum_{i=1}^{m} c_i \cdot O_i$
$P := L \cdot R - O$

この $P$ がターゲット多項式 $T$ で割り切れる場合、割り当て $(c_1,...,c_m)$ は次数 $d$ でサイズ $m$ の二次算術プログラム(QAP) である $Q$ を満たします。

$T$ というのは、ターゲットポイントで 0 となるように定義された多項式です。Part 5 の例においてはターゲットポイントは $1,2$ であったため、

$T := (X - 1)(X - 2)$

と定義されていました。

さて、Part 5 の例では $c_m = 7$ という問題を扱ってきましたが、このパートでは簡単のためそのような条件は無視して、アリスが適切な割り当て $(c_1,...,c_m)$ を持っていることをどのように証明するか、だけを見ていきます。

アリスが条件を満たす割り当てを使っている場合、次数 $d$ のターゲット多項式 $T$ は $P$ を割り切ることができるため、$P = H \cdot T$ という多項式 $H$ が存在し、どんな $s \in \mathbb{ F_p }$ においても $P(s) = H(s) \cdot T(s)$ が成り立ちます。

アリスが条件を満たす割り当てを持っていない場合、条件を満たさない割り当て $(c\prime_1,...,c\prime_m)$ を用いて $L\prime, R\prime, O\prime, P\prime$ を構築することはできますが、その場合 $T$ は $P\prime$ を割れないことが保証されます。

もしアリスがいい加減に選んだ割り当てが偶然 "条件を満たす割り当て" だった場合でも、それはそれで困ることはありません。アリスが "条件を満たす割り当て" を持っており、そしてその割り当てを用いて多項式を構築していればよく、その場合は $T$ は必ず $P$ を割り切ることができます。

上記の内容は、どんな多項式 $H$ に対しても $P$ と $L, R, O, H$ は異なる多項式になるということを意味します。²

Part 2 でも出てきた、「異なる多項式は大体の点で異なる」ことを述べた Schwartz-Zippelの補題³を使うと、異なる 2 つのたかだか $2d$ 次の多項式は、最大でも $2d$ 個の点でしか交わらないことが分かります。したがって、もし $p$ が $2d$ よりも遥かに大きい場合、 $p$ 個の要素を持つ $\mathbb{F_p}$ から $s$ をランダムに選んだ場合($s \in \mathbb{F_p}$)、$P(s) = H(s) \cdot T(s)$ が成り立つ確率はとても小さくなります。

アリスが条件を満たす割り当てを持っているかどうかをテストする手順のスケッチ

前項までに見てきたことを用いて、以下のような手順を考えることができます。

アリスはたかだか $2d$ 次の $L, R, O, H$ を選択
ボブはランダムな $s \in \mathbb{F_p}$ を選択し、$E(T(s))$ を計算
アリスはボブに $E(L(s)), E(R(s)), E(O(s)), E(H(s))$ を計算して送付
ボブは $s$ において、$E(L(s) \cdot R(s) - O(s)) = E(T(s) \cdot H(s))$ が成立するかをチェック

繰り返しになりますが、もし条件を満たす割り当てを持っていない場合、ランダムに選択された $s$ において上記の 4 の等式が成り立つ多項式をアリスは構築することは困難です。したがって、ボブは不適切な多項式を高い確率で拒絶することができます。

この手順を実現するにあたって最も重要なポイントは、アリスは $s$ についての知識を使わずに上記 3 の各値を算出しなければならないということです。
ただ、これはまさに Part 2 から 4 で見てきた検証可能な多項式の盲検で解決した問題でした。

さて、この手順を zk-SNARKs に変換するにはまだ取り組まなければならない 4 つのポイントがあります。このパートではそのうち 2 つを扱い、次のパートで残りの 2 つを扱います。

ポイント1. アリスが割り当てに従って自分の多項式を選択することを確認する

ここで重要なポイントがあります。アリスが条件を満たす割り当てを持っていない場合、それは彼女が $L \cdot R - O = T \cdot H$ となるどんな多項式も見つけることができないということを意味するのではなく、"ある割り当てから生成された" 多項式 $L, R, O$ を見つけることができないということを意味します。

Part 5 のプロトコルは単にアリスが適切な次数の $L, R, O$ を用いることを保証するだけであり、ある割り当てから生成されていることを保証するものではありませんでした。これは、正式な証明が少し微妙になるポイントです。ここでは、ソリューションを不正確にスケッチします。

次のように $L, R, O$ を組み合わせて多項式 $F$ を導出しましょう。

$F = L + X^{d+1} \cdot R + X^{2(d+1)} \cdot O$

$R$ に $X^{d+1}$を掛け、$O$ に $X^{2(d+1)}$ を掛けるのは、$F$ において $L, R, O$ の係数を混ぜないようにするためです。$F$ において $1,X,...,X^d$ の係数は厳密に $L$ の係数であり、$X^{d+1},...,X^{2d+1}$ の係数は厳密に $R$ の係数であり、最後の $d+1$ 個の項の係数は $O$ の係数となります。

同様の方法で QAP の定義に出てきた $L_i, R_i, O_i$ を組み合わせて、$i \in {1,...,m}$ に対して $F_i$ を定義します。

$F_i = L_i + X^{d+1} \cdot R_i + X^{2(d+1)} \cdot O_i$

このように定義すると 2 つの $F_i$ について $L_i, R_i, O_i$ を別々に合計できることに注意してください。例えば以下のように合計できます。

$F_1 + F_2 = (L_1 + L_2) + X^{d+1} \cdot (R_1 + R_2) + X^{2(d+1)} \cdot (O_1 + O_2)$

より一般的には、$(c_1,...,c_m)$ に対して $F = \sum_{i=1}^{m} c_i \cdot F_i$ を考えると、同じ $(c_1,...,c_m)$ に対して、$L = \sum_{i=1}^{m} c_i \cdot L_i$ $R = \sum_{i=1}^{m} c_i \cdot R_i$ $O = \sum_{i=1}^{m} c_i \cdot O_i$ となる $L, R, O$ が存在します。

言い替えると、もし $F$ が $F_i$ の線形結合である場合、$L,R,O$は実際に割り当てから生成されたことを意味します。

したがって、ボブはアリスに $F$ が $F_i$ の線形結合であることを証明するように依頼し、証明は検証可能な評価のプロトコルと同様の方法で以下のように実施します。

ボブはランダムな $\beta \in \mathbb{F^*_p}$ を選択し、アリスに $E(\beta \cdot F_1(s)),...,E(\beta \cdot F_m(s))$ を送ります⁴。そしてボブはアリスに $E(\beta \cdot F(s))$ を送るよう依頼します。もしアリスが値を送ることができれば、拡張 KCAによって彼女が $F_i$ の線形結合である $F$ を知っていることになります。

ポイント2. 零知識パートの追加 - 割り当ての隠蔽

zk-SNARKs においては、アリスは彼女の割り当てについての一切の情報を隠蔽したいのですが、$E(L(s)), E(R(s)), E(O(s))$ は割り当てについていくらかの情報を提供してしまいます。

例えば、条件を満たす他の割り当て $(c\prime_1,...,c\prime_m)$ が与えられると、ボブは $L\prime, R\prime, O\prime, H\prime$ そして $E(L\prime(s)), E(R\prime(s)), E(O\prime(s)), E(H\prime(s))$ を計算でき、これらの値がアリスから受け取った値と異なる場合、$(c\prime_1,...,c\prime_m)$ はアリスの割り当てではないことを推測できてしまいます。

割り当てに関する上記のような情報漏えいを避けるために、アリスは各多項式に "ランダム T-シフト" を加えることで彼女の割り当てを隠します。

つまり、ランダムな値 $\delta_1, \delta_2, \delta_3 \in \mathbb{F^*_p}$ を選択し、以下のような多項式を定義します。

$L_z := L + \delta_1 \cdot T$
$R_z := R + \delta_2 \cdot T$
$O_z := O + \delta_3 \cdot T$

これらの多項式は $L_z \cdot R_z - O_z = T \cdot H_z$ を満たすため、アリスが $L, R, O, H$ の代わりに用いることができます。

上記の等式が満たされることは、以下のように確かめられます。

$$
L_z \cdot R_z - O_z = (L + \delta_1 \cdot T)(R + \delta_2 \cdot T) - (O + \delta_3 \cdot T)
\= L \cdot R - O + T \cdot (L \cdot \delta_2 \cdot + R \cdot \delta_1 + \delta_1 \cdot \delta_2 \cdot T - \delta_3)\= T \cdot (H + L \cdot \delta_2 \cdot + R \cdot \delta_1 + \delta_1 \cdot \delta_2 \cdot T - \delta_3)
$$

したがって $H_z = H + L \cdot \delta_2 \cdot + R \cdot \delta_1 + \delta_1 \cdot \delta_2 \cdot T - \delta_3$ と定義すると、$L_z \cdot R_z - O_z = T \cdot H_z$ と表すことができ、アリスは $L, R, O, H$ の代わりに $L_z, R_z, O_z, H_z$ を使っても、常にボブに受け入れられます。

一方で、これらの多項式が $s \in \mathbb{F_p}$ で評価されても割り当てについての情報を明らかにしません。
例えば、$L_z := L + \delta_1 \cdot T$ について、$\delta_1$ がランダムな値であるため $\delta_1 \cdot T(s)$ もランダムな値となり、したがって $L_z(s) := L(s) + \delta_1 \cdot T(s)$ は $L(s)$ についての情報を明らかにしません。

まとめ

アリスがボブに条件を満たす割り当てを持っていることを、その割り当てに関する情報を明らかにすることなく納得させることができるピノキオプロトコル¹のスケッチを提示しました。zk-SNARKsを実現するには、まだ解決する必要のある2つのポイントがあります。

スケッチではボブは「乗算をサポートする HH」を必要としています。例えば彼は $E(H(s))$ と $E(T(s))$ から $E(H(s) \cdot T(s))$ を計算する必要がありますが、これを可能にする HH の例はこれまで見ていません(加算と線形結合をサポートする HH のみ見てきました)。
このシリーズ全体を通して、アリスとボブの間の対話型プロトコルについて見てきました。ただし、私たちの最終的な目標は、アリスがパブリックに検証可能な単一メッセージの非対話型証明を送信できるようにすることです。つまり、この単一メッセージの証明を見た人は、ボブ（アリスと以前に連絡を取り合っていた）に限らず、その有効性を確信できるようにします。

これらの問題は、次回最後の Part7(楕円曲線のペアリング) で説明する楕円曲線のペアを使用することで解決できます。

https://eprint.iacr.org/2013/279.pdf ↩
このことが言える理由が理解できなかったため、もしわかる方いたらコメントください。原文では次数についても記載があり、「たかだか $d-2$ 次のどんな多項式 $H$ に対しても $P$ と $L, R, O, H$ は異なる多項式になるということを意味します。ここでの $P$ は最大で $2（d-1）$ の次数であり、ここでの $L, R, O$ は最大で $d-1$ の次数であり、ここでの $H$ は最大で $d-2$ の次数であることに注意してください。」と記載されています ↩
https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma ↩
ボブは $L_i, R_i, O_i$ については知っているので $F_i(s)$ を算出することができます。"条件を満たす割り当て" は知らないので、割り当てを用いて構築される $L, R, O$ については知りません。 ↩