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の説明 パート4: 多項式の盲目評価を検証可能にする方法

Ariel Gabizon | Apr 11, 2017

<< パート III

このパートでは、パートIIとパートIIIに基づいて、多項式の証明可能で盲目な評価のためのプロトコルを開発する。 プロトコルはこの直後に定義する予定だ。 パートVでは、そうしたプロトコルをどのようにSNARKsの構築のために使用し得るかについて検討を始めるので、SNARKsとの関連に行きつくまでもう少しばかりお付き合いいただきたい(笑)。

パートII におけるのと同様に、アリスは \(d\) 次のある多項式 \(P\) を持っており、 ボブはランダムに選んだ点 \(s\in\mathbb{F}_p\) を持っていると仮定する。 私たちは、ボブに \(E(P(s))\) を知ることを可能とするプロトコルを構築したい、すなわち、2つの属性を追加した \(s\) で評価された \(P\) の秘匿である:

  1. 盲目性:アリスは \(s\) について知ることは ない (そしてボブは \(P\) について知ることはない)。
  2. 証明可能性:アリスが既知である \(d\) 次の \(P\) について、\(E(P(s))\) の形の値を送るが、それでもボブが受託する可能性は、無視して良い程度である。

これは、私たちが多項式の 証明可能な 盲目評価と呼ぶものである。 パートIIのプロトコルは、最初の属性を与えてくれたが、二番目は与えてくれなかった。 証明可能性を得るためには、パートIIIで提示した係数仮定の知識(KCA)の拡張バージョンが必要とされる。

立証可能性と盲目性の属性は、アリスが \(s\) を「見ることなく」、彼女が使うことになる多項式 \(P\) を決めさせるので、そろえば有用です。[1] これは、ある意味では、アリスを「挑戦点」 \(s\) を見ることなく「答えの多項式」にコミットさせるということです。この直観は、このシリーズの次の部分でより明確になる事でしょう。

拡張版KCA

パートIIIで定義したようなKCAは、本質的には次のようなことを言っていた: ボブがアリスに何らかの \(\alpha\)-pair \((a,b = \alpha\cdot a)\) を与え、それからアリスが別の \(\alpha\)-pair \((a',b')\) を生成する場合、 彼女は \(a'=c\cdot a\) となるように \(c\) を知ることになる。言い換えれば、アリスは \(a'\)\(a\) の間の関係を知っている。

いま、1の代わりに、ボブはアリスにいくつかの \(\alpha\)-pairs \((a_1,b_1),\ldots,(a_d,b_d)\) (同じ \(\alpha\) に対するもの)を送ると仮定する; そしてさらに再度、これらのペアを受け取った後、アリスはいくつか違う \(\alpha\)-pair \((a',b')\) を生成するよう挑戦を受ける。 主要なのは、アリスは \(\alpha\)知らない にもかかわらずこれを行わなければならない点だということを想起しよう。

パートIIIで見たように、アリスにとってそうした \(\alpha\)-pair を生成する自然な方法は、ボブから受け取ったペア \((a_i,b_i)\) のうち1つを選び、両方の要素を何らかの \(c\in\mathbb{F}^*_p\) で掛けることであろう;\((a_i,b_i)\)\(\alpha\)-pair であった場合、すなわち \((c\cdot a_i,c\cdot b_i)\) も同様にそうなる。 しかし、アリスが 複数の \(\alpha\)-pairs を受け取った今、アリスは \(\alpha\)-pairs をもっと多くの方法で生成できるだろうか? たとえば、受領した \(\alpha\)-pairs のいくつかを*同時に*使用して新しいものを得ることなどはできたりしないだろうか?

答えは、イエスです:例えば、アリスは「2つの」値 \(c_1,c_2\in \mathbb{F}_p\) を選び、ペアの \((a',b')=(c_1\cdot a_1 + c_2\cdot a_2, c_1\cdot b_1 + c_2\cdot b_2)\) を計算できます。簡単な計算により、\(a'\) がゼロでない限り、これも \(\alpha\)-pair であることが示されます:

\(b' = c_1\cdot b_1 + c_2 \cdot b_2 = c_1 \alpha \cdot a_1 + c_2\alpha\cdot a_2 = \alpha (c_1\cdot a_1 + c_2\cdot a_2) = \alpha\cdot a'.\)

より一般的には、アリスは付与の \(d\) のペアの任意の 線形組み合わせ をとることができる―すなわち、任意の \(c_1,\ldots,c_d\in\mathbb{F}_p\) を選んで、\((a',b')=(\sum_{i=1}^d c_i a_i,\sum_{i=1}^d c_ib_i)\) を定義する。

彼女の \(\alpha\)-pair を生成するのにアリスがこの戦略をする場合、彼女は \(a'\)\(a_1,\ldots,a_d\) の間の何らかの線形関係を知ることになることに留意する; つまり、彼女は \(a'=\sum_{i=1}^d c_i\cdot a_i\) となるように|c1-d|を知る。

拡張版KCAは、本質的には、これがアリスが \(\alpha\)-pair を生成できる唯一の方法であると宣言する;つまり、成功する時はいつでも、彼女はそのような \(a'\)\(a_1,\ldots,a_d\) の間の線形関係を知ることになる。より形式的には、\(G\) がサイズ \(p\) で生成ファクターがパートIIIで追加的に記したように \(g\) であるあるグループだと仮定する。
\(G\) における*係数のdべき乗知識仮定*( d-KCA )[2]_ は以下のようになる:

d-KCA: ボブがランダムな \(\alpha\in\mathbb{F}_p^*\) \(s\in\mathbb{F}_p\) を選び、アリスにその \(\alpha\)-pairs \((g,\alpha\cdot g), (s\cdot g,\alpha s\cdot g),\ldots,(s^d\cdot g,\alpha s^d\cdot g)\) を送ると仮定しよう。 次にアリスは、もう一つの \(\alpha\)-pair \((a',b')\) を出力すると仮定する。すると、無視して良い程度の可能性を除き、 アリスは \(\sum_{i=0}^d c_i s^i\cdot g = a'\) となるように* \(c_1,\ldots,c_d\in\mathbb{F}_p\) を知る。

d-KCA では、ボブは任意の \(\alpha\)-pairs の群を送るのではなく、特定の「多項式構造」を持ったものを送ることに留意する。これは、以下のプロトコルにおいて役に立つことになる。

証明可能な盲目評価プロトコル

私たちの HH は、上記のように \(G\) の生成ファクター|g|についての関数 \(E(x)=x\cdot g\) であると仮定します。

簡単にするために、とりわけこの \(E\): のプロトコルを示します。

  1. ボブはランダムな \(\alpha\in\mathbb{F}_p^*\) を選び、アリスに( \(1,s,\ldots,s^d\) からの)隠匿数 \(g,s\cdot g,\ldots,s^d\cdot g\) を送り、( \(\alpha,\alpha s,\ldots,\alpha s^d\) からの)隠匿数 \(\alpha\cdot g,\alpha s \cdot g,\ldots,\alpha s^d\cdot g\) も送る。
  2. アリスは、最初のステップで送られた要素を使用して \(a=P(s)\cdot g\)\(b=\alpha P(s)\cdot g\) を計算し、両方をボブに送る。
  3. ボブは \(b=\alpha \cdot a\) であることを確認し、この等式が成立する場合のみ受諾する。

最初に、付与の|P|の係数|P(s)g|が|1s-dg|の線形の組み合わせであること;そして|alpP(s)g|が|alpha1s-dg|の線形の組み合わせであることに注意する。 そのため、パートIIのプロトコルと同様に、アリスは彼女にとって既知のボブの多項式|P|についてのメッセージから、実際にこれらの値を計算することができる。

二番目に、d-KCA により、アリスが \(b=\alpha \cdot a\) となるように \(a\)\(b\) を送る場合、ほぼ確実に彼女は \(a=\sum_{i=0}^d c_is^i\cdot g\) となるように \(c_1,\ldots,c_d\in\mathbb{F}_p\) が分かります。 その場合、多項式 \(P(X)=\sum_{i=0}^d c_i\cdot X^i\)\(a=P(s)\cdot g\) はアリスにとって既知となります。 言い換えれば、ボブがステップ3で受諾し同時にアリスがその \(P\) を知らないという確率は、無視して良い程度だということです。

まとめると、d-KCA を使用することで、私たちは多項式の証明可能な盲目評価のためのプロトコルを開発した。次の投稿では、私たちはこの基礎がSNARKの構築でどのような役割を果たすのか検討していく。

[1]形式的に完全な証明では、諸々はいくぶんかより微妙である。というのも、アリスは彼女の \(P\) を決定する前に、確かに \(s\) についての情報をいくらか見るからである―例えば、\(s,\ldots,s^d\) の隠匿である。
[2]d-KCA は、ジェンズ・グロースの`論文 <http://www0.cs.ucl.ac.uk/staff/J.Groth/ShortNIZK.pdf>`_ 内で導入された。g

cryptography, zkSNARKs, explainers | 全てのタグを見る