👩🏽‍🚀 💇🏻 👨🏽‍⚕️ SNARKの説明。楕円曲線のペアリング（翻訳） 🥅 ☃️ 👩‍👩‍👧

こんにちは、Habr！ ZCashのブログ記事の翻訳を紹介します。この記事では、ZCash暗号通貨で使用されるゼロ開示証拠システムSNARKの動作メカニズムについて説明しています（これだけではありません）。

出所

前の記事：

パート1： SNARKの説明。準同型隠蔽とブラインド多項式計算（翻訳）

パート2： SNARKの説明。採用された係数の知識と信頼できる多項式のブラインド計算（翻訳）

パート3： SNARKの説明。計算から多項式、Pinocchioプロトコルおよび楕円曲線のペアリング（翻訳）

前の記事で、zk-SNARKのPinocchioプロトコルが検討されました。検証に必要な加算と乗算の両方をサポートする準同型隠蔽（HS）、および対話型プロトコルから非対話型証拠システムへの移行をサポートする2つのことを分析します。

この記事では、楕円曲線を使用することで、乗算をサポートするHSの形式を、目的の目的には十分であるが取得できることを示します。この限定された形式のHSは、プロトコルを必要な非対話型システムに変換するのにも十分であることを以下に示します。

まず、楕円曲線に導入し、必要なHSの形状を取得する方法を説明します。

楕円曲線とそのペアリング

pが3より大きい素数であり、

u 、 v \in F_{p}

$u、v∈F_p$ そのような

4 u^{3} + 27 v^{2} \neq 0

$4u ^ 3 + 27v ^ 2≠0$ 。方程式を考えてください：

Y^{2} = X^{3} + u \cdot X + v

$Y ^ 2 = X ^ 3 + u⋅X + v$

楕円曲線Cは点の集合です

（ x 、 y ）

$（x、y）$ この方程式を満たします。これらの曲線は、グループを構築する興味深い方法を提供します。グループの要素はポイントになります。

（ x 、 y ） \in F_{p}^{2}

$（x、y）∈F ^ 2_p$ 曲線上にある、つまり、技術的な理由で必要であり、「無限遠点」と呼ばれることもあり、同一性の要素、つまりグループのゼロとして機能する特別な点Oとともに方程式を満たします。

あなたは、「何に関するポイントのセット？」と尋ねるかもしれません。代数的閉包の座標を持つ点の集合を意味します $F_p$ 。さらに、曲線にはアフィン射影バージョンがあります。射影バージョンを参照する場合、曲線の要素として「無限遠点」 Oも含めます。

ここでの問題は、2つのポイントを追加する方法です

P = （ x_{1} 、 y_{1} ） 、 Q = （ x_{2} 、 y_{2} ）

$P =（x_1、y_1）、Q =（x_2、y_2）$ サードを取得するには？加算規則は、曲線除数クラスのグループと呼ばれる抽象的なオブジェクトから取得されます。私たちの目的のために、この除数クラスのグループについて知っておく必要があるのは、加算演算の定義に次の制限を課すことだけです：任意のライン上のポイントの合計はゼロでなければなりません。 O.

この制限からどの追加規則が続くかを見てみましょう。次の形式の方程式で定義される垂直線を見てください

X = c

$X = c$ 。この線が点で曲線と交差すると仮定します

P = （ x_{1} 、 y_{1} ）

$P =（x_1、y_1）$ 。曲線の方程式の形式は

Y^{2} = f （ X ）

$Y ^ 2 = f（X）$ もし

（ x 1 、 y 1 ）

$（x1、y1）$ 曲線上にある場合、ポイントがあります

Q ： = （ x_{1} 、 - y_{1} ）

$Q：=（x_1、-y_1）$ 。さらに、これは垂直線であり、2次曲線の方程式はYであるため、これらが線と曲線が交差する唯一の点であることを確認できます。

方程式があります

P + Q = O

$P + Q = O$ つまり

P = - Q

$P =-Q$ このように

Q

$Q$ とは逆です

P

$P$ グループで。

ここで、最初の座標が一致しないポイント$ inlineP $ inlineおよび$ inlineQ $ inlineを分析しましょう。

x_{1} \neq x_{2}

$x_1≠x_2$ 、それらを積み重ねる方法を参照してください。 PとQを通る線を引きます。

曲線は3次のXの多項式で定義され、すでにこの（垂直ではない）線と2点で交差しているため、3番目の点で線と交差することが保証されます。

R = （ x 、 y ）

$R =（x、y）$ 、および他のポイントでラインを横断しません。

したがって、取得します

P + Q + R = O

$P + Q + R = O$ つまり

P + Q = - R

$P + Q =-R$ 。私たちはすでにそれを知っています

- R

$-R$ から得られた

R

$R$ 2番目の座標を

y

$y$ で

- y

$-y$ 。

したがって、グループの追加規則は次のとおりです。選択されたポイントPおよびQについて、それらを通る線を引き、線の3番目の交点の「鏡」点を取る必要があります。これは加算の結果です。

P自体を追加する場合は考慮しませんでした。これは、ポイントPで曲線に接する線を使用し、この線と曲線の2番目の交点としてRを取得することによって行われます。

このグループは通常と呼ばれます

C （ F_{p} ）

$C（F_p）$ 座標が$ inlineC $ inline曲線上の点で構成されているため、

F_{p}

$F_p$ 。しかし、さらにそれを

G_{1}

$G_1$ 。便宜上、要素の数は

G_{1}

$G_1$ p以外の素数rです。これは、Zcashが使用する曲線など、多くのソリューションで使用されます。この場合、任意のアイテム

g \in G_{1}

$g∈G_1$ Oとは異なります

G_{1}

$G_1$ 。

rが除算する最小の整数k

p^{k} - 1

$p ^ k-1$ 曲線のネスト度と呼ばれます。 kが十分に大きい場合、たとえば少なくとも6である場合、離散対数問題は

G_{1}

$G_1$ 、つまり発見

α

$α$ そして

g

$g$ から

α \cdot g

$α⋅g$ かなり複雑です。（現在Zcashで使用されているBNカーブでは、

k = 12

$k = 12$ ）

乗法群

F_{p^{k}}

$F_ {p ^ k}$ で示される次数rのサブグループを含む

G_{t}

$G_t$ 。座標で曲線の点を見ることができます

F_{p^{k}}

$F_ {p ^ k}$ だけでなく

F_{p}

$F_p$ 。同じ追加規則に従って、これらの点はOと一緒にグループを形成します。

C （ F_{p^{k}} ）

$C（F_ {p ^ k}）$ 。に注意してください

C （ F_{p^{k}} ）

$C（F_ {p ^ k}）$ 明示的に含む

G_{1}

$G_1$ 。ほかに

G_{1} 、 C （ F_{p^{k}} ）

$G_1、C（F_ {p ^ k}）$ 追加のサブグループが含まれます

G_{2}

$G_2$ 順序r （実際、

r - 1

$r-1$ 順序rの追加のサブグループ）。

ジェネレーターを修正します

g \in G_{1} 、 h \in G_{2}

$g∈G_1、h∈G_2$ 。 Tate還元ペアリングと呼ばれる効果的なマップがあり、それが要素のペアを

G_{1}

$G_1$ そして

G_{2}

$G_2$ から要素へ

G_{t}

$G_t$ そのような

$Tate（g、h）=ξ$ ジェネレータξから $G_t$
与えられた要素のペアに対して $a、b∈F_r$ 行った $テート（a⋅g、b⋅h）=ξ^ {ab}$

Tateの定義は、これらの記事の範囲をわずかに超えており、代数幾何学の概念、より多くの因子に依存しています。

実際、ZcashのペアリングではOptimal Ateペアリングが使用されます。これは、簡略化されたTateペアリングに基づいており、 Tateよりも効率的に計算できます。

のために

a \in F_{p}

$a∈F_p$ 多項式

（ X - a ）^{r}

$（X- a）^ r$ 度でゼロの値を取ります

r

$r$ ポイントaで、他のどこにもありません。ポイントについて

P \in G_{1}

$P∈G_1$ 、除数により、関数が存在することを証明できます

f_{P}

$f_P$ 曲線から

F_{p}

$F_p$ 、これは特定の正確な意味でPの次数rがゼロで、他のどこにもありません。

テ ー ト （ P 、 Q ）

$テート（P、Q）$ 次に定義される

f_{P} （ Q ）^{（ p^{k} - 1 ） / r}

$f_P（Q）^ {（p ^ k- 1）/ r}$ 。

この定義が示されたプロパティにどのように関連するかは完全には理解されていない場合があります。実際には、 Tateがこれらのプロパティに関連付けられているという証拠は非常に複雑です。

定義する

$インライン$ E_1（x）：= x⋅g、E_2（x）：= x⋅h、E（x）：= x⋅ξ$ inline $ 加算と乗算の両方をサポートするHSの弱いバージョンを取得します。

E_{1} 、 E_{2} 、 E

$E_1、E_2、E$ 追加をサポートし、非表示を知るHS

E_{1} （ x ） 、 E_{2} （ y ）

$E_1（x）、E_2（y）$ 計算できます

E （ x y ）

$E（xy）$ 。つまり、 xとyの「正しい」非表示があれば、 xyの （他の）非表示を取得できます。しかし、たとえば、

x 、 y 、 z

$x、y、z$ 私たちは非表示にすることはできません

x y z

$xyz$ 。

次に、非インタラクティブな証拠システムについて説明します。「非インタラクティブ」の意味を説明することから始めましょう。

汎用リンクモデルの非インタラクティブな証拠

非対話型証拠の最も強力で最も直感的な定義は、おそらく次のとおりです。特定のステートメントを証明するために、証明者は事前のメッセージングなしですべての関係者に利用可能な単一のメッセージを送信し、このメッセージを読んだ人はステートメントの真実を確信します。ほとんどの場合、これは実装できない可能性があります。

計算の複雑性の理論に関しては、 BPP複雑性クラスの言語のみが、非開示の非対話型証明を完全に実装していることを示すことができます。 Zcashトランザクションで証明する必要があるステートメントのタイプ、たとえば、「この行のハッシュのオリジナルを知っています」は、 NP複雑度クラスに対応し、これはBPPよりもはるかに大きいことがわかっています。

一般的な参照文字列-OSS（英語CRSから）の概念を導入するために、非インタラクティブな証拠の定義を弱めます。 OSSモデルでは、証拠が構築される前に、特定のランダムプロセスに従って文字列が作成され、すべての関係者に送信されるインストールフェーズがあります。この行はOSSと呼ばれ、証拠の作成と検証に使用されます。 OSSを作成するために使用されるランダムデータは、これらのデータの知識が誤った証拠の構築を可能にするため、どちらの側にも不明であると想定されます。

OSSモデルで、信頼できるブラインド計算のプロトコルを非インタラクティブな証拠システムに変換する方法を見てみましょう。このプロトコルはいくつかの同様のサブプロトコルで構成されているため、同様の方法で非対話型の証拠システムに変えることができます。

非インタラクティブな計算プロトコル

計算プロトコルの非インタラクティブバージョンは、最初に、ボブの最初のメッセージをOSSとして公開することにあります。プロトコルの目的は準同型の非表示を取得することであることを思い出してください

E （ P （ s ） ）

$E（P（s））$ 多項式アリスの

P

$P$ ランダムに選択された

s \in F_{p}

$s∈F_p$ 。

インストール ：ランダムに選択

α \in F_{r}^{*} 、 s \in F_{r}

$α∈F ^ * _ r、s∈F_r$ OSSによって公開されました。

（ E_{1} （ 1 ） 、 E_{1} （ s ） 、 . . . 、 E_{1} （ s^{d} ） 、 E_{2} （ α ） 、 E_{2} （ α s ） 、 . . . 、 E_{2} （ α s^{d} ） ）

$（E_1（1）、E_1（s）、...、E_1（s ^ d）、E_2（α）、E_2（αs）、...、E_2（αs^ d））$ 。

証明。アリス計算

a = E_{1} （ P （ s ） ）

$a = E_1（P（s））$ そして

b = E_{2} （ α P （ s ） ）

$b = E_2（αP（s））$ OSSの要素を使用して、

E_{1}

$E_1$ そして

E_{2}

$E_2$ 線形結合をサポートします。

チェック ：受け入れています

x 、 y \in F_{p}

$x、y∈F_p$ のために

a = E_{1} （ x ）

$a = E_1（x）$ そして

b = E_{2} （ y ）

$b = E_2（y）$ ボブ計算

E （ α x ） = テ ー ト （ E_{1} （ x ） 、 E_{2} （ α ） ）

$E（αx）=テート（E_1（x）、E_2（α））$ そして

E （ y ） = テ イ ト （ E_{1} （ 1 ） 、 E_{2} （ y ） ）

$E（y）=テイト（E_1（1）、E_2（y））$ 、およびそれらの同等性をチェックします。（それらが等しい場合、これはつまり

α x = y

$αx= y$ ）

前のパートで示したように、アリスはそのようなもののみを作成できます

a 、 b

$a、b$ それがテストされます

a

$a$ 隠れている

P （ s ）

$P（s）$ 多項式の

P

$P$ 彼女に知られている順序d 。ここでの主な違いは、ボブが知る必要がないことです

α

$α$ 検証のために、ペアリング関数を使用して計算できるため

E （ α x ）

$E（αx）$ からのみ

E_{1} （ x ）

$E_1（x）$ そして

E_{2} （ α ）

$E_2（α）$ 。したがって、彼は最初のメッセージを自分で作成して送信する必要はなく、このメッセージはOSSで簡単に修正できます。

使用されている画像はこの記事から取られたものであり、Creative Commonsライセンスの下で使用されています。

SNARKの説明。 楕円曲線のペアリング（翻訳）

楕円曲線とそのペアリング

汎用リンクモデルの非インタラクティブな証拠

非インタラクティブな計算プロトコル

More articles:

SNARKの説明。楕円曲線のペアリング（翻訳）