Greetings! New to Zcash?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with more information about how you can get started with Zcash!

言語

Zcashのパラメータ及び生成方法について

Ariel Gabizon | Sep 22, 2016

根底において、Zcashのプライバシー技術は最新の暗号ツール、いわゆるzkSNARKに依存しています。これは安価に認証できる小規模な ゼロ知識証明 です。Zcashはこのパワフルなツールを大規模なスケールで用いる最初の試みとなる予定です。 zkSNARKsを動かすには、設定段階が必要となります。ここでは、"システムパラメータ"が生成されます。 この段階は公開鍵暗号システムの準備段階に類似していますが、違うところもあります。 公開鍵システムでは、ペア (\(\mathsf{privkey},\) \(\mathsf{pubkey}\)) が生成されますが、 \(\mathsf{privkey}\)破壊されます。 実際、設定段階の後では 誰も \(\mathsf{privkey}\) を保有していないことがシステムの一体化にとって重要となります。

\(\mathsf{pubkey}\) は要求されたシステムのパラメータに相当します。 \(\mathsf{privkey}\) は`ここで <https://z.cash/blog/snark-parameters.html>`_ 「有害廃棄物」と呼ばれるものに該当し、これを持つことで新しいコインを偽造できるようになります(ただし他ユーザーのトランザクションに関するプライバシーを侵害することはできません)。

リスク削減のため、Zcashは \(\mathsf{pubkey}\) の生成についてマルチプレーヤープロトコルを設計しました。このプロトコルは、\(\mathsf{privkey}\) は全参加者のシークレットの無作為性を連結したものに相当するという性質を持ちます。こうして \(\mathsf{privkey}\) は、すべての 参加者が不誠実であるか、もしくはダメージを受けている場合を除き、破壊されることとなります。

この投稿の目的は、\(\mathsf{pubkey}\) がどのようなものかと、これを生成するプロトコルがどのように作用するかについて簡単な解説を行うことにあります。

\(\mathsf{pubkey}\) とは

\(g\) を離散対数がハードであるグループ \(G\) のジェネレーターと推定してください。 \(G\) はある素数 \(r\) について行列 \(r\) を持つと仮定し、加法的にグループ操作を書き出していきます。すると、 \(s\in \mathbb{F}\) で、 \(\mathsf{privkey}\) はグループ要素の連なりとなります。 \(\mathsf{pubkey}=\) \((g,s\cdot g, s^2\cdot g,\ldots, s^d\cdot g)\)

上記において、\(\mathbb{F}^*\)\(\mathbb{F}\) の非ゼロ要素数のセットを指します。

\(\mathsf{pubkey}\) の生成方法

後ほど、なぜ \(\mathsf{pubkey}\) がこのような形なのか、どのように使われているのか簡単に説明します。 しかし、ここでは \(\mathsf{pubkey}\) を生成するプロトコルの設計に着目しましょう。

単純化するため、 \(d=2\) を修正してみましょう。分かりやすく生成できるので、最初の \(g\) 要素を \(\mathsf{pubkey}\) から削除します。 システムにとって妥当な公開鍵 \(\mathsf{pubkey}=\) \((s\cdot g, s^2\cdot g)\) を生成したいと考えている2人の当事者、AliceとBobがいると仮定します。 二人とも、両者ともに \(s\) を知らないということを確認できた上で実行したいと考えています。 まず、さらに単純にして考えてみましょう。 この二人が \(s\cdot g\) を生成したいと考えているとします(同様に、両者とも \(s\) を知らないとした上で)。 そこで次のプロトコルを使用します。

  1. Aliceは無作為の \(a\in \mathbb{F}^*\) を選択し、\(M_1:= a\cdot g\) をBobに送信します。
  2. Bobは無作為の \(b\in \mathbb{F}^*\) を選択し、\(b\)\(M_1\) を乗じます。Bobはメッセージ \(M:= b\cdot M_1\) を共同アウトプットとして送り返します。

プロトコルの終わりに、\(M=b\cdot a \cdot g = (a b)\cdot g\) が得られます。\(s:= a b\) を示してみましょう。

以下にご留意ください。

  • 離散対数は \(G\) においては困難であると仮定した通り、Bobはメッセージ \(M_1\) から \(a\) を読み解くことはできませんでした。Aliceも \(b\) について同様でした。特に、両者とも \(a\)\(b\) の積である \(s\) を確認できませんでした。
  • 修正済みの \(a\in \mathbb{F}^*\) では、\(a b\)\(b\) が無作為の時の \(\mathbb{F}^*\) の無作為要素です。Aliceが、前提とは異なり \(a\) を無作為に選ばなかったという意味で不正を行った(例えば、いつも \(a=4\) を選択)場合であっても、\(s\) は常に無作為になります。Bobの不正や、無作為に \(b\) を選ばなかった場合でも同じです。

その中の1つ がプロトコルに正確に従う限りにおいて \(M=s\cdot g\) は正しい形式となります。

\((s\cdot g, s^2\cdot g)\) の生成に類似したアイディアを使用してみましょう。

  1. Aliceは無作為な \(a\in \mathbb{F}^*\) を選択し、 \(A:= a\cdot g\)\(B := a^2\cdot g\) となる \((A,B)\) を送信します。
  2. Bobは無作為な \(b\in \mathbb{F}^*,\) を選択し、\(M=(b\cdot A, b^2\cdot B)\) を送信します。

もしAliceとBobがプロトコルに従うと、\(M= (b a \cdot g, b^2 a^2 \cdot g) = ( a b\cdot g, (a b)^2\cdot g)\) を得ることになり、このベクトルは次の正しい式になります。 \(s:= ab\)

では問題です。 ボブが不正を働き、\(B\) に:math:cneq b^2`を掛けたらどうなるでしょう。 結果として、:math:`(abcdot g, a^2 c cdot g), が得られます。 これは、どの \(s\) に対しても \((s\cdot g, s^2\cdot g)\) の形をとりません。 どうにかして、アウトプットベクトル \(s\) に対して \((s\cdot g, s^2\cdot g)\) の形をとるということを確認する必要が出てきます。 多くの場合、これは効率的に行うことができないと推測されます。いわゆる平方決定的Diffie-Hellman仮定と呼ばれるものです。 しかし、私たちの設定では、バイリネアー・ペアリング を持つグループと共に作動します。 これがグループ \(G_T\) への動作図 \(e:G\times G\to G_T,\) で、ジェネレーター \(\mathbf{g}\)\(r\) 値となり、次のような乗法で書かれます

\(e(a\cdot g, b\cdot g) = \mathbf{g}^{ab}\)

\(a,b\in\mathbb{F}.\) に対してこれにより、アウトプット \(M\) が正しい形であるか確認することが可能になります。 次をチェックします:

\(e(g,B) = e(A,A).\)

誰も不正を働いていないとして、この小切手がどのように譲与されるか見てみましょう。 誰も不正を働いていない場合、このような状態となります。\(A=s\cdot g,\) つまり

\(e(g,B) = e(g,s^2\cdot g) =\mathbf{g}^{s^2}\),

また

\(e(A,A) = e(s\cdot g,s\cdot g) = \mathbf{g}^{s^2}\)

同様のコンピュテーションにより、\(M\) がこの形態でない場合2つの価値は異なるものとなり、テストは失敗であることを確認することも可能です。

\(\mathsf{pubkey}\) の使用方法

\(\mathbb{F}\) 上での次数 \(d\) を持つ 多項式 \(P\) は、数式の一形態であることを思い出してください。

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

ある点 \(s\in \mathbb{F}\) を得ることができると保証されています。

\(\mathsf{pubkey}\) can now be used to test if \(P\) そして \(Q\) are equal at a point \(s\) not known by the sender. Say

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

そして

\(Q(X) = b_0 + b_1\cdot X + b_2\cdot X^2 + \ldots + b_d\cdot X^d\)

\(\mathsf{pubkey}=\) \((g,s\cdot g, s^2\cdot g,\ldots, s^d\cdot g)\) を使って、認証を計算できます

\(P(s)\cdot g = a_0\cdot g + a_1 s \cdot g + a_2s^2 \cdot g + \ldots + a_d s^d\cdot g\)

そして compute \(Q(s)\cdot g\) similarly. The verifier can then check if they are equal.

Since the sender of a non-valid transaction has to construct distinct \(P\) そして \(Q\) without knowing \(s,\) the chance that \(P(s)=Q(s)\) is very small.

免責条項

この投稿は根本的なプロトコルを非常に単純化して紹介したものです。完全な形での詳細は後に白書の形で公開予定です。

References

Our zkSNARKS use SCIPR Lab's implementation of the Pinnochio protocol, which in turn is based on the work of Gennaro, Gentry, Parno そして Raykova. Our protocol for parameter generation builds on a previous work of Ben-Sasson, Chiesa, Green, Tromer そして Virza.