Greetings! New to Zcash?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with monthly highlights on ecosystem growth, network development and how to get started with Zcash!

言語

SNARKs の説明 パート1:同形秘匿

Ariel Gabizon | Feb 28, 2017

zk-SNARKsを構築するには様々な要素を慎重に組み合わせなければなりません。ですが、これらの要素を完全に理解しようとすると時間がかかってしまいます。

あえて 一番重要な要素 を選ぶとすれば、それは 同形秘匿 (HH) [1]_です。この記事ではHHとは何なのかを具体的な事例とともに、これが便利な理由、どのように構築されるのか説明したいと思います。

あるHH \(E(x)\) の数字|x|は以下の要素を満たす役割があります。

ではなぜHHがゼロ知識証明で使われるのか例を見てみましょう。アリスがボブに \(x+y=7\) のように \(x,y\) の値を知っていることを証明したいと思っています。( xとyの値が分かったところでワクワクしないとは思いますが、コンセプトの説明には便利なのでこのような例を用いています。)

  1. アリスは \(E(x)\)\(E(y)\) をボブに知らせます。
  2. ボブはこの値から \(E(x+y)\) を計算します ( \(E\) がHHなのでこれが可能)
  3. ボブは \(E(7)\) も計算し、\(E(x+y)=E(7).\) となっているかも確認します。これが合っていると確認できればボブはアリスの証明を受け入れます。

\(E\) によって異なるインプットが異なる隠された値になるため、 ボブはアリスが \(x+y=7\) のように \(x,y\) の隠された値を送った場合のみアリスの証明を受け入れます。 ですがボブには隠された値 [2] しかわからないため \(x\)\(y\) がなんなのかわかりません。

ではどのように隠された値が構築されているのか例を見てみましょう。実は整数と普通の足し算で構築することはできないのですが、有限群 で見てみましょう。

まず、\(n\) は整数とします。 整数 \(A\)\(A\;\mathrm{mod}\;n\) と書く時は、\(n\) で割った後 \(A\) の余りをとるという意味です。 \(9\;\mathrm{mod}\; 7 = 2\)\(13\; \mathrm{mod}\;12 = 1.\) のような例があげられます。 \(\mathrm{mod}\; n\) の作業は \(\{0,\ldots,n-1\}\) の数値の加法演算を定義するために使います。また 普通の足し算もできますが \(\{0,\ldots,n-1\}\) の間の数字に戻ってくるために答えに \((\mathrm{mod}\; n)\) を適応します。 \(2+3 = 1\; (\mathrm{mod} \;4).\) のように、このタイプの足し算を使っていると明確にするために \((\mathrm{mod}\; n)\) を右側に書くこともあります。

\(\{0,\ldots,n-1\}\) のような要素を加法演算のグループと合わせて \(\mathbb{Z}_n\) と呼んでいます。

素数 \(p\) の場合、 整数の普通の掛け算をして \(\mathrm{mod}\;p\) の結果をとり、掛け算の結果が常に \(\{1,\ldots,p-1\}\) となるようにすることで、\(\mathrm{mod}\;p\) を使って \(\{1,\ldots,p-1\}\) のような数字の 掛け算 をすることができます [3]。例を挙げると \(2\cdot 4=1\; (\mathrm{mod}\; 7).\) となります。

これらの計算を含めた要素は \(\mathbb{Z}_p^*\) グループと言われます。\(\mathbb{Z}_p^*\) には以下のような便利な特徴があります。

  1. これは*巡回* 群です。 which means that there is some element \(g\) in \(\mathbb{Z}_p^*\) called a ジェネラータ such that all elements of \(\mathbb{Z}_p^*\) can be written as \(g^a\) for some \(a\) in \(\{0,..,p-2\}\), where we define \(g^0=1.\)
  2. The discrete logarithm problem is believed to be hard in \(\mathbb{Z}_p^*\). This means that, when p is large, given an element \(h\) in \(\mathbb{Z}_p^*\) it is difficult to find the integer \(a\) in \(\{0,..,p-2\}\) such that \(g^a=h\;(\mathrm{mod}\;p).\)
  3. As ''exponents add up when elements are multiplied'', we have for \(a,b\) in \(\{0,..,p-2\}\) \(g^a\cdot g^b = g^{a+b\;(\mathrm{mod}\;p-1)}.\)

これらの特徴を使って''足し算を立証する''HHを構築する、つまり \(E(x+y)\)\(E(x)\)\(E(y)\) とから計算可能ということです。 \(E\) のインプット \(x\) は from \(\mathbb{Z}_{p-1}\) からくるものだと仮定するため、\(\{0,..,p-2\}\) の範囲内です。 そのような各 \(x\)\(E(x)=g^x\) だと定義し、\(E\) はHHだとします: 1つ目の特徴は \(x\)\(\mathbb{Z}_{p-1}\) は異なるアウトプットに繋がることを示唆しています。 二つ目の特徴は \(E(x)=g^x\) の場合 \(x\) を特定することが難しいことを示唆します。 最後に3つ目のプロパティでは \(E(x)\)\(E(y)\) から|E(x+y)| を \(E(x+y) = g^{x+y\;\mathrm{mod}\; p-1} = g^x\cdot g^y = E(x)\cdot E(y).\) として計算可能だということがわかります。

[1]同形秘匿という言葉は暗号学で正式に使われる言葉ではなく、説明のために便宜的に使用しています。これはよく知られているcomputationally hiding commitmentの概念に似ていて、それより少し弱いものです。違いはHHはインプットの決定性の機能でコミットメントはさらにランダムさが加わっています。結果として、HHは基本的に「ほとんどのxを隠す」ものでコミットメントは「全てのxを隠す」ものとなっています。
[2]ボブはxとy について いくつかの 情報は得ています。例えばxの値を予想してE(x')を計算することで x=x' であるか確かめることができます。ですので上記のプロトコルはゼロ知識プロトコルだとは言えず、ここでは説明の為に使われているだけです。今後の記事の中で出てきますがHHはsnarksの中で証明する側の秘密よりも証明を確認する側のチャレンジを隠すために使われています。
[3]pが素数でない場合はこのように掛け算を定義するのは難しくなります。問題のひとつには二つの独立変数の値がゼロではないのに掛け算の結果がゼロになってしまう可能性があることです。 例えば p=4の場合、2*2=0 (mod 4)となってしまいます。