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

想定読者

零知識証明 / zk-SNARKs について知りたい人
- 特に理論的側面を知りたい人
「zk-SNARKs って何だ？」という人

概要

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

Part 2 のテーマは Blind Evaluation of Polynomials（多項式の盲検） です。
"多項式の盲検" の解説はこの記事だけでは完結せず Part 4 まで続きます。

Part 1 の解説記事で紹介した zk-SNARKs の概要や Homomorphic Hidings（HH: 準同型隠蔽）についての知識を前提とした内容となります。まだお読みでない方は、先にそちらに目を通すことをお勧めします。

読み方

Part 1 の解説記事の読み方と同様です。

込み入った議論や数学的に細かい部分は注釈(foot note)にまとめました。そのため、注釈が多くなっていますが、注釈を読まなくても大丈夫ですので、読み飛ばしていただいて構いません。

備考

このQiita記事の筆者は Part 1 の解説記事とは異なります。Part 3 以降も交代で解説記事をアップしていく予定です。

Blind Evaluation of Polynomials

対応する記事

Explaining SNARKs Part II: Blind Evaluation of Polynomials

一言でいうと

ある多項式を知っている人が知らない人に対して、式の詳細を伝えることなく、知っているという事実を証明することができます。そして、それを 多項式の盲検(blind evaluation of polynomials) と呼びます。

「多項式の盲検」の特徴

多項式の盲検 は zk-SNARKs の特徴である「計算量的な簡潔さ」「非対話性」を実現するための中心的なツールです。多項式の盲検は、前回紹介した HH を使って実装します。

前提知識

この記事では、"多項式" とその "次数"、"線形結合"、"有限体 $\mathbb{F}_p$" といった数学用語が出てきます。

多項式は数と変数の和と積で構成される式のことで、その次数とは式に含まれる変数の指数の中で最も大きいものを指します。

例えば、

$6 + 5x + x^2$

は多項式であり、その次数は $x^2$ の指数 $2$ となります。(解説本編の多項式の表現に合わせて、次数の昇順で項を並べています)

また線形結合とは、定数倍して足し合わせる、ということを意味します。

上記の例の多項式は $x^0(=1)$ を $6$ 倍、 $x^1$ を $5$ 倍、 $x^2$ を $1$ 倍して足し合わせたものであるため、 $x^2, x^1, x^0$ の線形結合と捉えることができます。

最後に有限体 $\mathbb{F}_p$ とは、以下のように定義される集合のことを言います。¹

要素数が $p$ 個で各要素は ${ 0,1,...,p-1 }$
足し算と掛け算をした時は $p$ で割ってそのあまりを結果とする

例えば $\mathbb{F}_7$ は、

要素数は 7 個で各要素は ${ 0,1,2,3,4,5,6 }$
足し算と掛け算をした時は $7$ で割ってそのあまりを結果とする

ということになります。

ここまでで前提知識の説明はおしまいです。

多項式と線形結合

有限体 $\mathbb{F}_p$ 上の次数が $d$ の多項式 $P$ は以下のような形式となります。

$P(X) = a_0 + a_1 \cdot X + a_2 \cdot X^2 + \cdots +a_d \cdot X^d$

「$\mathbb{F}_p$ 上の」というのは多項式の各係数 $a_0, a_1, a_2,...,a_d$ が $\mathbb{F}_p$ の要素 ${ 0,1,...,p-1 }$ から選ばれているということを意味します。

この多項式 $P$ をこれまた $\mathbb{F}_p$ の要素である $s$ で評価すると、多項式上の $X$ が $s$ で置き換えられることになるので、

$P(s) = a_0 + a_1 \cdot s + a_2 \cdot s^2 + \cdots +a_d \cdot s^d$

となります。

ではなぜ $P$ の値を計算する上で、有限体 $\mathbb{F}_p$ の要素であることが重要なのでしょうか？
その理由は次回以降の記事で解説されますので、ここでは一旦そういうものだと思っておいてもらえばOKです。

$P$ を知っている人にとっては $P(s)$ の値は $1, s,s^2...,s^d$ の線形結合となります。この場合「線形結合」という言葉は $a_0,a_1,...,a_d$ を重みとみなした単純な加重合計を意味します。

前回 HH $E$ を $E(x) = g^x$ と定義し、足し算をサポートすることで構成しましたが、この HH は線形結合も同時にサポートします。

「線形結合をサポートする」とは $a,b,E(x),E(y)$ が与えられた時に $E(ax + by)$ が計算できることを意味し、以下の式が成り立つことから確認できます。

$E(ax + by) = g^{ax+by} = g^{ax} \cdot g^{by} = (g^x)^a \cdot (g^y)^b = (E(x))^a \cdot (E(y))^b$

多項式の盲検

アリスが次数が $d$ の多項式 $P$ を持ち、ボブが $\mathbb{F}_p$ から無作為に1つの要素 $s$ を選んだとします(この時点ではアリスは $s$ を知らず、ボブは $P$ を知りません)。

この状態でボブが $E(P(s))$ の結果を知るためには2つのシンプルな方法が考えられます。

アリスが多項式 $P$ をボブに送り、ボブが $E(P(s))$ を計算する
ボブが $s$ をアリスに送り、アリスが $E(P(s))$ を計算して結果をボブに送る

しかし「盲検」を実現するために、ボブは $P$ を知ることなく、同時にアリスは $s$ を知ることなく、ボブが $E(P(s))$ の結果を知ることができるようにしたいわけです。²

HH を使えば以下のように盲検をおこなうことができます。

ボブはアリスに $E(1),E(s),E(s^2),...,E(s^d)$ を送る
アリスはボブから受け取った要素を使って $E(P(s))$ を計算してボブに送る

$E$ は線形結合をサポートしており $P(x)$ は $1,s,s^2,...,s^d$ の線形結合なので、アリスは計算することができます。³

これらの隠蔽情報のみが送られることでアリスは $s$ を⁴、ボブは $P$ を知ることはありません。

なぜこれが便利なのか？

後続の投稿で SNARKs の中で盲検がどのように使われるか詳細に分け入りますが、ここでは直感的な説明をします。

検証者は証明者が「正しい」多項式を知っているかどうかを知りたい、というシーンを考えてみましょう（つまり前述の例ではボブが検証者、アリスが証明者となります）。

証明者の多項式が「正しくない」ものであった場合、証明者に無作為に選択されたポイントで盲目的に多項式を評価させると、高い確率で誤った答えが出されることになります。

これは「異なる多項式は大体の点で異なる」ことを述べた Schwartz-Zippel の補題⁵に依拠しています。

まとめ

多項式の盲検(blind evaluation of polynomials) をすることで検証時にやり取りする情報や計算量を抑えることができる
多項式の盲検 は HH や有限体上の多項式を使うことで構成できる

次回はPart3(係数知識のテストと仮設)です。まだ下準備は続きます。多項式の盲検をするためには、アリスから受け取った結果が正しい手順で計算した $E(P(s))$ であることをボブが検証できる必要があります。この問題の解決方法がPart4にかけて解説されます。

雑な書き方になっていますので、有限体についてちゃんと知りたい方は「有限体（ガロア体）の基本的な話」など、他の解説記事を確認してください。 ↩
ボブに $P$ を送信したくない主な理由は、対象の多項式の項が非常に多いからです。 zk-SNARKs を使っている暗号通貨の Zcash のプロトコルでは次数 d は最大で 2,000,000 とのことです。 $P$ を送信しないことは SNARKs の "簡潔さ"(頭文字 S: Succinct)に関係しています。ボブが送信している $E(1),E(s),E(s^2),...,E(s^d)$ も同じくらいの長さとなりますが、こちらはシステムのパラメータとして「ハードコード」できるのに対して、 $P$ は証明プロセスを実行するごとに異なる値となります。(元記事の注釈での言及) ↩
以下のように確かめることができます。
$E(P(s)) = E(a_0 + a_1 \cdot s + a_2 \cdot s^2 + \cdots +a_d \cdot s^d)$
　　　　$= g^{a_0 + a_1 \cdot s + a_2 \cdot s^2 + \cdots +a_d \cdot s^d}$
　　　　$= g^{a_0} \cdot g^{a_1 \cdot s} \cdot g^{a_2 \cdot s^2} \cdots g^{a_d \cdot s^d}$
　　　　$= g^{a_0} \cdot E(1) \cdot g^{a_1} \cdot E(s) \cdot g^{a_2} \cdot E(s^2) \cdots g^{a_d} \cdot E(s^d)$ ↩
実際には HH は $s$ は $E(s)$ から復元ができないことを保証するだけです。$s$ についての情報量が潜在的には多い $E(1),E(s),E(s^2),...,E(s^d)$ を使っても復元できないと主張できるのは、決定的 Diffie-Hellman 仮定に基づいています。決定的 Diffie-Hellman 仮定を簡単に説明すると、 HH で用いた生成子 $g$ と $\mathbb{F}_p$ からランダムに選択した要素 $a, b, c$ に対して $(g^a, g^b, g^{ab})$ と $(g^a, g^b, g^c)$ を区別できない、というものです。正確な定義はこちらを参照してください。(元記事の注釈での言及) ↩
『むしゃくしゃしてやった，今は反省している日記 - Schwartz-Zippelの補題』に正確な Statement とその証明があります。記事内で紹介されているSchwartz-Zippelの補題の歴史もなかなか興味深いです。 Schwartz よりも早い時期にこの補題と似たアイディアを論文にまとめてはいたものの、現在ほぼ言及されることがない Lipton の手記です。 ↩