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

想定読者

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

概要

zk-SNARKs とは

　zk-SNARKs というのは、非対話零知識証明の構築方法の一つです。

零知識証明とは

　Wikipediaを見ると

ある人が他の人に、自分の持っている（通常、数学的な）命題が真であることを伝えるのに、真であること以外の何の知識も伝えることなく証明できるようなやりとりの手法である。

とあります。少しわかりにくいのでもう少し具体的に書いてみます。例として、本人確認の文脈に絞ると、以下のように言って良いと思います。

自分自身であることを他の不要な情報を送らず(知られず)に証明することができる手法

何となくわかったとしても、「実際どうするの？」という疑問が出てくると思います。初めて聞いた方はピンとこないかもしれないので、洞窟の例なども見ていただければと思います。

非対話零知識証明とは

　上記の零知識証明を"非対話"にしたバージョンです。

洞窟の例では、登場人物は何度かやりとり(対話)を行って証明を構成していました。非対話零知識証明では構成時にこういった対話が不要になります。対話が不要になるということは通信が不要になるということです。

　「じゃあ、それはどうやるの？」という話ですが、その理論的背景を zk-SNARKs を使って本記事で行っていく予定です。zk-SNARKs は非対話零知識証明の構築方法の一つです。zk-SNARKs 自体についてはZCashの解説にも詳しく書かれています。

この記事の内容

　zk-SNARKs に関する概略は日本語でも容易に見つかりますが、理論的側面に関して丁寧に書かれたものはなさそうです。英語では以下のような解説記事がありますが、より丁寧でわかりやすかった 2. の記事を簡単に補足をしていきながら紹介します。大意は同じですが、正確な翻訳にはなっていません。本家も Part 7 までありますので、全7回になります。数学的ハードルを下げつつ、解説することも目的になっているので、分量は本家より少し多くなっています。

Part 1 のテーマは Homomorphic Hidings(HH: 準同型隠蔽) です。
※ hindings は独自に和訳しただけなので、混乱を生むので以下では、HHと表記することにします。

読み方

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

Homomorphic Hidings

対応する記事

Explaining SNARKs Part I: Homomorphic Hidings

一言でいうと

こちらにある定義に基づいた関数をHomomorphic Hidings（HH: 準同型隠蔽）と呼ぶことにします。HHは以後の zk-SNARKs の中でも最重要の部分になります。

前提

　zk-SNARKs による構築には、いくつかの手法を組み合わせる必要があります。

　その中でも最も重要な役割を果たす成分を一つ選ぶとすれば、Homomorphic Hidings（HH: 準同型隠蔽）と呼ぶものです。 ¹ この記事では、HHとは何かを説明した後、それが有用である理由とそれがどのように構築されるかの例を示します。

HHの定義

HH である関数 $ E(x) $ は以下の性質を持つものです。

ほとんどの $x$ に関して²、$E(x)$から$x$を特定するのが難しい
異なる入力には異なる出力をする($x \neq y \rightarrow E(x) \neq E(y)$)
$E(x)$と$E(y)$がわかると、$x$と$y$の四則計算³した際の値も計算可能(例: $E(x)$と$E(y)$がわかると$E(x+y)$が計算可能)

HHの例(toy example)

　ここで、HHがなぜ零知識証明に有用かを体験するために、以下に(実用的でない)簡単な例を紹介します。定番のアリスとボブに登場してもらいましょう。

　アリスは彼女が$x+y=7$となる$x$,$y$を知っているということをボブに証明したいとします。
このような場合、零知識証明の文脈では、アリスを証明者(prover)、ボブを検証者(verifier)と呼びます。
※ 以下の例では、HHである関数$E(x)$が存在していると仮定

アリスが$E(x)$と$E(y)$をボブに送る
ボブが$E(x+y)$の値を計算する(HHの定義の3.よりこれは常に可能)
ボブは$E(7)$を計算し、$E(x+y)=E(7)$であるかどうかを確認し、等号が成立する場合にはアリスの証明を受け入れる

　HHの定義の2.より、$E(x+y)=E(7)$を確認するだけで$x+y=7$をアリスが知っているかどうかの証明の判定できるというわけです。大事なことは、ボブは$x$や$y$に関する情報を得ていないということです。⁴

HHの構成方法

　ここまででHHがどのような使われ方をするのかを見てきました。しかし、HHのようなそんな都合の良い関数は存在するのでしょうか？ここで、そのような隠蔽がどのようにして構築されるかの例を見てみましょう。

　通常の整数や通常の足し算では難しいことはわかります。有限群を利用する必要があります。"有限群"という用語にちょっと身構えてしまいそうですが、数学の用語に惑わされず、例を見ていただけるとどのように構成されるかは理解できると思います。⁵

mod の世界("あまり"の世界)

　HHの構成方法を考える前にいくつか準備が必要です。まず、$\bmod \ \ $について説明します。
少し見慣れない人もいるかもしれませんが、わり算の余りを表すための記号です。要するに $9 \div 4 = 2 \ あまり\ 1$ を、商に興味がなく、あまりに注目したい場合に $9 = 1 \bmod 4$ と書くというだけです。

　$\bmod \ \ $を使って、$n$以下の自然数の集合$\ \{ 0,1,...n-1 \}\ $に対して演算を定義できます。新たな演算を定義すると言っても簡単です。2つの数を足したあと、$\bmod \ \ $を作用させるだけです。

例: $n = 7$ の場合
$\ \{ 0,1,...6 \}\ $における演算(足し算)を $\bmod \ \ $ を以下のように定義できます。

$$ 4 + 6 = 10 = 3 \bmod 7$$

となります。要するに$\ \{ 0,1,...6 \}\ $における新たな足し算の世界では、"4たす6は3"と言えるわけです。(ここでの"たす"は通常の足し算とは違う点に注意が必要です。⁶)

　こうして導入された演算(足し算)と演算の対象となる集合$\ \{ 0,1,...n-1 \}\ $をあわせて(有限群)$\mathbb{Z}_n$ と呼びます。掛け算バージョンも同様に定義できます。足し算の同様に演算の後に$\bmod \ \ $を作用させるだけです。

$$ 4 \times 2 = 8 = 1 \bmod 7$$

$\ \{ 1,...p-1 \}\ $とその演算をあわせて$\mathbb{Z}^{\ast}_p$と書きます。ただし、ここでは$p$を素数とします。⁷逆算ができなくなるので、0が含まれていないことに注意してください。

この足し算バージョンと掛け算バージョンを利用して以下にHHを構成していきます。見慣れない記号も出てきましたが、「答えを $\bmod \ \ $ にとる掛け算と足し算を使うんだな」とわかればOKです。

HHの構成

$\mathbb{Z}^{\ast}_p$ の以下の数学的な性質を利用して、HHを構成します。

$\mathbb{Z}^{\ast}_p$ のすべての要素は、$\ \{ 0,...p-2 \}\ $の要素$a$を使って、$g^a$ と書けるような生成子と呼ばれる要素 $g$ が存在する。⁸(ただし、$g^0=1$ と定義します。)
$\mathbb{Z}^{\ast}_p$においては離散対数問題を解くのが(計算量上)困難である。⁹
掛け算が指数の足し算になる($g^a \cdot g^b = g^{a + b \bmod p-1}$)¹⁰

　これらの性質を用いて、"足し算"をサポートしたHHを構成します。"足し算"をサポートというのは、$E(x+y)$を$E(x)$と$E(y)$から計算できるということです。
まず、$E(x)$の入力$x$が$\mathbb{Z}_{p-1}$の要素であると仮定します。その時の範囲は$\ \{ 0,...p-2 \}\ $となっています。そして、$E(x)$を
$$E(x)=g^x$$
と定義すると、$E(x)$がHHになります。このように定義したHHがHHの定義を満たしているか確認していきましょう。

ほとんどの $x$ に関して²、$E(x)$から$x$を特定するのが難しい

$E(x)$から$x$を特定するということは、$g^x$から$x$を特定するということです。これは離散対数問題になっています。HHの構成の$\mathbb{Z}^{\ast}_p$の性質の2.より、離散対数問題を解くのが困難であるので、この性質を満たしていることがわかります。

2. 異なる入力には異なる出力をする($x \neq y \rightarrow E(x) \neq E(y)$)

HHの構成の$\mathbb{Z}^{\ast}_p$の性質の1.より、異なる入力は異なる出力になることが確認できます。

3. $E(x)$と$E(y)$がわかると、$x$と$y$の四則計算³した際の値も計算可能(例: $E(x)$と$E(y)$がわかると$E(x+y)$が計算可能)

HHの構成の$\mathbb{Z}^{\ast}_p$の性質の3.より、

$$g^x \cdot g^y = g^{x+y \bmod p-1}$$

一方で、上の定義より$E(x) = g^x, E(x+y) = g^{x + y} = g^{x + y \bmod p-1}$ですので、

$$E(x + y) = g^{x + y \bmod p-1} = g^x \cdot g^y = E(x) \cdot E(y)$$¹¹

となり、$E(x+y)$を$E(x)$と$E(y)$の掛け算で表せることがわかります。

まとめ

Homomorphic Hidings(HH: 準同型隠蔽) の定義はこちらの通りである
$\mathbb{Z}^{\ast}_p$の性質を用いることでHHを構成できる
- 具体的には$\mathbb{Z}_{p-1}$に属する$x$に対して、$E(x)=g^x$と定義することでHHを構成できる
- 上記の構成法でHHの定義を満たすことを確認できた

少々長くて大変だったと思いますが、確実な理解を少しずつ踏めた方も多いのではないでしょうか？
筆者は専門家ではないので、マサカリもぜひいただけると光栄ですし、逆に質問も歓迎していますのでコメントいただけると幸いです。
次回はPart2(多項式の盲検(blind evaluation))についてです。これまた準備になりますが、zk-SNARKsの理解に必要です。

HH自体はこれまで使われてきた専門用語ではないとのことです。"準同型隠蔽"はこのQiita記事の筆者がつけた訳語です(もっと通じません)。HHは一般的に知られている計算量的秘匿なコミットメントと似ていますが、それよりも弱い概念です。その違いは、コミットメントはランダム性を追加して出力するのに対し、HHが入力に対して決定論的な関数であるという点です。これにより、コミットメントでは"すべてのx"を隠蔽するのに対し、HHは"ほとんどのx"を隠蔽するという違いが生まれています。 ↩
数学的には測度論での a.e. くらいの意味だと思われます。とはいえ、数学的な意味は深く考えなくても「異常な例はあるが、それを除けば」くらいに理解して概ね大丈夫です。現実的にも、そのような異常なケースは事前に確認して避けることができます。 ↩
arithmetic expressions とありましたが、四則計算のことと思われます ↩
実際にはボブは$x$と$y$に関する情報を得ています。ボブはランダムに数$x'$を選び、$E(x')$を計算し、$E(x)$と比較することができます。万が一、等しいものを見つけた場合は$x=x'$がわかるので、$E(x)$から$x$を特定できてしまうことになります。そのため、これは厳密には零知識証明とは言えません。 toy example と書かれているのはそのためで、説明のための例に過ぎない点に注意してください。後ろのPartで説明されますが、実際、HHは最終的には証明者(prover)の秘密ではなく、検証者(verifier)のチャレンジ(ナンスなど)を隠すために使用されています。 ↩
ここでの目的は数学における有限群を理解することではなく、HHがどのように構成されるかを理解することです。例を見ていただけることで、「ちょっと変則的な足し算のルールを使えばHH作れそうだな」と思えるとことが目的です。 ↩
後に紹介する表現を使うと、より正確な表現として "$\mathbb{Z}_7$において6たす4は3" といえます。 ↩
pが素数でない場合、掛け算をこのように定義できません。両方の引数がゼロでない場合でも、掛け算の結果が0になることがあるということです。例えば、$p=4$ の場合、$2 \times 2=0 \bmod 4$ となってしまい、元の集合にない0が得られてしまい、演算として問題があります。 ↩
こういった概念に初めて触れる人にはわかりにくいかもしれないので、こちらに例を上げておきます。$p=7$の時を考えます。このとき、$\mathbb{Z}^{\ast}_p$ のすべての要素は$\ \{ 1,...6 \}\ $です。生成子を$g=5$とすると、$\ \{ 0,...5 \}\ $の要素$a$を使って$g^a$を考えます。すると$g^0=1, g^1=5, g^2=4, g^3=6, g^4=2, g^5=3 \bmod 7$ となり、$\ \{ 1,...6 \}\ $のすべてが一回ずつ出てくることがわかります。(どんな$g$でも成り立つわけではありませんが、他の$g$についても成り立ちます) ↩
十分$p$を大きくとると、$g^a = h \bmod p$において、$h$から$a$を求めるのが困難であるということです。($a$から$h$を求めるのは簡単なので、非対称性が著しいといえます。) ↩
これは通常の掛け算と足し算であれば成り立つことは当たり前かもしれませんが、ここでは、$\mathbb{Z}^{\ast}_p$の演算において成り立っていることに注意してください。 ↩
元記事ではしれっと使われているのですが、$\mathbb{Z}^{\ast}_p$においては、$g^a = g^{a \bmod p-1}$が成り立ちます。これはフェルマーの小定理($g^{p-1} = 1 \bmod p$)から成り立ちます。フェルマーの小定理はあまり気にしなくて大丈夫ですが、興味のある人はリンク先に飛んで証明を追いかけてみていただければと思います。 ↩

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