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

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



前の記事： SNARKの説明。 準同型隠蔽とブラインド多項式計算（翻訳）



この記事では、検証可能な多項式の受け入れられた係数とブラインド計算のテストを調べます。 行こう...



前の記事で、アリスが盲目的に皮を見つけ出す方法を見ました $$$E（P（s））$ その多項式Pは、ボブに属する点sで d次です。 アリスは計算中に値sを取得しないため、この「ブラインド」計算と呼びました。



ただし、このプロトコルには何かが欠けています。 アリスが計算できるという事実 $$$E（P（s））$ 彼女が本当に送信することを保証しません $$$E（P（s））$ ボブ、他の意味ではない。



したがって、プロトコルを正しく追跡するためにアリスを「取得」する方法が必要です。 この記事では、これを実現する方法について詳しく説明します。 まず、これに必要なメインツールの動作原理を検討して説明しましょう。 これを係数の知識（KC）テストと呼びます。



前と同様に、順序GのグループGの生成元をgで示します $$$| G | = p$ ここで、離散対数は困難なタスクです。 便宜上、この場所から始めて、乗法ではなく加法的にグループで作業します。 つまり、 $$ $インライン$α∈F_p、α⋅g$インライン$ はαにgのコピーを掛けたものを示します。

係数知識テスト

のために $$$α∈F ^ * _ p$ 、要素のペアを呼び出します $$$（a、b）$ で $$$G$ 」 $$$α$ カップル $$$a、b≠0$ そして $$$b =α⋅a$ 。

$$$F ^ * _ p$ 非ゼロ要素を示します $$$F_p$ 。 これはと同じです $$$Z ^ * _ p$ 前の記事で説明されています 。

テストは次のとおりです。

1. ボブは乱数を選ぶ $$$α∈F ^ * _ p$ と数 $$$a∈G$ 。 彼は計算する $$$b =α⋅a$
2. 彼はアリスにペアで「リクエスト」を送信します $$$（a、b）$ 。 に注意してください $$$（a、b）$ αペアです。
3. アリスは別のペアでリクエストに応答するはずです $$$（a '、b'）$ 。 また、αペアです。
4. ボブは、次の場合にのみアリスの答えを受け入れます。 $$$（a '、b'）$ 本当にαペアです（αを知っているので、 $$$b '=α⋅a'$ ）
   
   

それでは、アリスがいつ電話に出られるかを考えてみましょう。 彼女がαを知っているとします。 この場合、彼女は単にGから任意の 'を選択し、計算することができます $$$b '=α⋅a'$ そして、新しいαペアを返します $$$（a '、b'）$ 。



ただし、 αに関する情報のみが式に含まれているため $$$α⋅a$ また、グループGには複雑な離散対数問題があり、アリスは見つけることができないと信じています $$$α$ 。



それで、 αを知らずにどうやってクエリにうまく答えられるのでしょうか？



これを行う簡単な方法は次のとおりです。アリスはいくつかを選ぶだけです $$$γ∈F ^ * _ p$ そしてカップルに答えます $$ $インライン$（a '、b'）=（γ⋅a、γ⋅b）$インライン$



この場合、次のものがあります。



$$ $ inline $ b '=γ⋅b =γα⋅a =α（γ⋅a）=α⋅a' $ inline $



このようにカップル $$$（a '、b'）$ 必要に応じて、 αペアです。



アリスがこのオプションを使用して回答した場合、アリスとアの比が等しいかどうか、つまりそのような係数を知っていることに注意してください $$$γ$ に $$$a '=γ⋅a$ 。



採用された係数の知識（係数仮定の知識（KCA））は、これが常に当てはまると述べています。



ZPK：アリスが正しい答えを返す場合 $$$（a '、b'）$ ボブの要請で $$$（a、b）$ その後、ボブの選択に関係なく、高い確率で $$$a、\α$ 彼女はそのような係数を知っています $$$γ$ に $$$a '=γ⋅a$ 。

文献では、伝統的に乗法群に使用されてきたため、これは通常「受け入れられた指数の知識」と呼ばれます 。

記事の次のパートでは、知識テストと合格率が重要なツールになります。

「アリスは知っている」とはどういう意味ですか？

特定の数式でZPKをどのように定式化できるのか疑問に思われるかもしれません。 特に、「アリスは知っている」という考えをどのように定式化するのでしょうか $$$γ$ 数学的定義では？



これは次のように行われます。Aliceに加えて、Alice Extractorと呼ばれるもう1つの側面があると言います。 アリスの抽出器は、アリスの内部状態にアクセスできます。



これで、ZPKを次のように定式化できます。Aliceが正常に応答するたびに $$$α$ 夫婦 $$$（a '、b'）$ アリスエクストラクターが戻る $$$γ$ そのような $$$a '=γ⋅a$ 。

PPCの完全な正式な定義は、Extractorを「やや弱い」と定義し、代わりに、出力ではなく、Aliceの成功した応答の可能性を示しています。 $$$γ$ この場合は重要ではありません

検証可能な多項式のブラインド計算を行う方法

さらに、以前の資料に基づいて、信頼性の高い多項式のブラインド計算のプロトコルを開発します。その定義を以下に示します。 以下のパート（および記事）では、このプロトコルを使用してSNARKを作成する方法を示します。



アリスが次数dの多項式Pを持ち、ボブが点を持っているとします $$$s∈F_p$ 彼が偶然選んだ。 ボブに知らせるプロトコルを作成したい $$$E（P（s））$ 、つまり Pをsで非表示にし、2つの追加プロパティを追加

1. 機密性：アリスはsを認識せず、ボブはPを認識しません。
   
   
2. 信頼性：アリスが値を送信する可能性 $$$E（P（s））$ ボブはそれを受け入れますが、彼女に知られている次数dの多項式Pについては無視できます。

これは、ブラインド多項式チェックテストと呼ばれます。 前の記事のプロトコルは、最初の段落のみを提供し、2番目の段落は提供しませんでした。 信頼性を得るには、採用された係数（ZPK）に関する知識の拡張バージョンが必要です。



有効性と機密性のプロパティは、アリスにsの値を見ずに使用する多項式Pを決定させるため、一緒に役立ちます。 ある意味では、これにより、アリスは「ポイントクエリ」を参照せずに「多項式で答える」必要があります。 このロジックはさらに明確になります。

完全な形式的証明では、いくつかのことをより微妙に説明しています。 たとえば、アリスは多項式Pを決定する前にsに関する情報を取得します。 たとえば、彼女は非表示になります $$$s、...、s_d$

高度なZPK

上記で定義した形式のZPKは、次のように聞こえます。ボブがアリスに $$$α$ 夫婦 $$$（a、b =α⋅a）$ そして、アリスは別のものを生成します $$$α$ 夫婦 $$$（a '、b'）$ 、彼女はcの値を知っているので、 $$$a '= c⋅a$ 。 つまり、アリスはa 'とaの関係を知っています。



ここで、ボブが1つではなく、アリスに複数の $$$α$ 夫婦 $$$（a_1、b_1）、...、（a_d、b_d）$ （同じ $$$α$ ） そして今、再びこれらのペアを受け取ったアリスは、他のものを生成するはずです $$$α$ -ペア $$$（a '、b'）$ 。 彼女は意味を知らないが、アリスはこれをしなければならないことが重要です $$$α$ 。



上記のように、アリスは作成できます $$$α$ 簡単な方法でカップル。 これを行うには、ペアのいずれかを取る $$$（a_i、b_i）$ ボブから取得し、両方の要素にいくつかを掛けます $$$c∈F ^ * _ p$ 。 もし $$$（a_i、b_i）$ だった $$$α$ カップル $$$（c⋅a_i、c⋅b_i）$ またになります $$$α$ カップル。 しかし、アリスは生成できます $$$α$ -より多くの受信のためのペア $$$α$ ペア？ そして、新しいを取得することは可能ですか $$$α$ 一度に複数の受信を使用するカップル $$$α$ ペア？



回答：はい。 たとえば、アリスは2つの値を選択できます $$$c_1、c_2∈F_p$ ペアを計算します $$ $インライン$（a '、b'）=（c_1⋅a_1 +c_2⋅a_2、c_1⋅b_1 +c_2⋅b_2）$インライン$ 。 単純な変換は、 $$$a '$ ゼロ以外、これも $$$α$ -ペア：



$$ $ inline $ b '=c_1⋅b_1 +c_2⋅b_2 =c_1α⋅a_1 +c_2α⋅a_2 =α（c_1⋅a_1 +c_2⋅a_2）=α⋅a' $ inline $



より一般的なケースでは、Aliceは結果のdペアの線形結合をとることができます。 これを行うには、いずれかを選択します $$$c_1、...、c_d∈F_p$ そして識別する $$$（a '、b'）=（Σ^ d_ {i = 1} c_ia_i、Σ^ d_ {i = 1} c_ib_i）$ 。



アリスがこの戦略を使用して彼女を生成する場合、 $$$α$ -ペア、彼女はいくつかの線形関係を知っているだろう $$$a '$ そして $$$a_1、...、a_d$ 。 つまり、彼女は知っている $$$c_1、...、c_d$ そのような $$$a '=Σ^ d_ {i = 1}c_i⋅a_i$ 。



拡張されたZPKは、実際、これがアリスが生成できる唯一の方法であると主張しています $$$α$ カップル。 したがって、正常に生成されると、アリスは $$$a '$ そして $$$a_1、...、a_d$ 。 より正式には、 Gがジェネレーターgを持つサイズpのグループであり、記事の冒頭で追加的に説明されているとします。 Gで受け入れられる次数dの係数（d-ZPC）の知識は、次のように記述できます。



d-ZPK：ボブがランダムを選択したとします $$$α∈F ^ * _ p$ そして $$$s∈F_p$ 、およびアリスを送信します $$$α$ -ペア $$ $ inline $（g、α⋅g）、（s⋅g、αs⋅g）、...、（s ^d⋅g、αs^d⋅g）$ inline $ 。 アリスが別の質問に答えるとします $$$α$ 夫婦 $$$（a '、b'）$ 。 次に、高い確率で、アリスは知っています $$$c_0、...、c_d∈F_p$ そのような $$$Σ^ d_ {i = 0} c_is ^i⋅g = a '$ 。

D-KCA（d-ZPK）がJens Grott 誌に掲載されました。

ことに注意してください $$$d-zpk$ ボブはランダムセットを送信しません $$$α$ -pair、ただし特定の「多項式構造」を持つセットを送信します。 この利点は、以下のプロトコルで確認できます。

信頼できるブラインド計算プロトコル

HS（準同型隠蔽）がマッピングであると仮定します $$$E（x）= x⋅g$ 上記のGからのジェネレータgについて。



簡単にするために、この特定のEのプロトコルを示します。

1. ボブはランダムに選ぶ $$$α∈F ^ * _ p$ 、およびアリスに非表示を送信します $$$g、s⋅g、...、s ^d⋅g$ （のために $$$1、s、...、s ^ d$ ）、および非表示 $$ $ inline $α⋅g、αs⋅g、...、αs ^d⋅g $ inline $ （のために $$$α、αs、...、αs^ d$ ）
2. アリス計算 $$$a = P（s）⋅g$ そして $$$b =αP（s）⋅g$ 最初のステップで送信されたアイテムを使用して、それらをボブに送信します。
3. ボブはそれをチェックします $$$b =α⋅a$ 、この平等が成り立つ場合にのみ答えを受け入れます。

まず、得られた係数に注意してください $$$P$ 、 $$$P（s）⋅g$ 線形結合です $$$g、s⋅g、...、s ^d⋅g$ そして $$$αP（s）⋅g$ 、そして $$$αP（s）⋅g$ は線形結合です $$ $ inline $α⋅g、αs⋅g、...、αs ^d⋅g $ inline $ 。 したがって、前の記事のプロトコルと同様に、アリスは、ボブのメッセージから、彼女が知っている多項式Pについてこれらの値を実際に計算できます。



次に、d-ZPCによると、Aliceが送信した場合 $$$a、b$ そのような $$$b =α⋅a$ 、ほぼ確実に彼女はそのようなことを知っています $$$c_0、...、c_d∈F_p$ あれ $$$a =Σ^ d_ {i = 0} c_is ^i⋅g$ 。 この場合 $$$a = P（s）⋅g$ 多項式の $$$P（X）=Σ^ d_ {i = 0}c_i⋅X ^ i$ 有名なアリス。 言い換えれば、ボブがステップ3で答えを受け入れ、アリスがそのような多項式Pを知らない確率は無視できます。



このすべてを要約し、d-ZPCを使用して、多項式の信頼できるブラインド計算のためのプロトコルを開発しました。 今後の記事では、このメカニズムがSNARKコンストラクトでどのように使用されるかについて説明します。



次の記事： SNARKの説明。 計算から多項式、ピノキオプロトコル、楕円曲線の共役（翻訳）まで