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

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



この分野からの私の以前の翻訳。 議論される内容をよりよく理解するために、まずそれらに精通することをお勧めします。

• 例付きzk-SNARKの概要（翻訳）
• 二次算術プログラム：ぼろから富へ（翻訳）

このパートでは、準同型隠蔽とブラインド多項式計算について見ていきます。 行こう...

準同型隠蔽

zk-SNARKの設計には、いくつかのコンポーネントの調和のとれた組み合わせが含まれています。 これらのコンポーネントがどのように連携するかを完全に理解するには、十分な時間がかかります。



その役割が最も顕著であるコンポーネントを1つだけ選択する必要がある場合、準同型隠蔽（HH）を選び出します。 記事のこの部分では、GSが何であるかを説明し、それがなぜ有用であるかの例を示し、それがどのように機能するかを分析します。

準同型隠蔽は暗号化で正式に使用される用語ではなく、ここでは教訓的な目的で紹介されています。 特性に関しては、よく似ていますが、よく知られている「 義務スキーム 」の概念よりも弱いです。 違いは、HSは引数を定義する関数であるが、義務は余分なランダム性を必要とすることです。 その結果、準同型は基本的に「xの大部分を非表示」になり、義務は「xをすべて非表示」になります。

HS $$$E（x）$ 数値xは、次の特性を満たす関数です。

• ほとんどのxで、既知の値を持つ $$$E（x）$ xを見つけるのは難しい作業です。
• 引数値が異なると、関数値も異なります。 したがって、 $$$x≠y$ それから $$$E（x）≠E（y）$
• 誰もが知っている場合 $$$E（x）$ そして $$$E（y）$ 、それからxとyの算術演算からHSを生成できます。 たとえば、計算することができます $$$E（x + y）$ 知っている $$$E（x）$ そして $$$E（y）$ 。

GSがゼロ知識証明に役立つ理由の簡単な例：アリスがボブに、x、yの数値を知っていることを証明したいとします。 $$$x + y = 7$ （もちろん、これはそのようなxとyを知るために特に興味深いものではありませんが、これは概念を説明する良い例です）。

1. アリスが送る $$$E（x）$ そして $$$E（y）$ ボブする。
2. ボブは計算しています $$$E（x + y）$ これらの値の（彼はこれを行うことができます $$$E$ HS）です。
3. ボブも計算します $$$E（7）$ そして今 $$$E（x + y）= E（7）$ 。 彼は平等が成立する場合にのみアリスの証明を受け入れます。

引数の値が異なるため $$$E$ さまざまな非表示（関数値に対応 $$$E$ 。 ご注意 翻訳者）、ボブは本当にアリスが非表示を送信した場合にのみ証拠を受け入れます $$$x、y$ そのような $$$x + y = 7$ 。 一方、ボブは値を取得しません $$$x、y$ 、彼は彼らの皮にしかアクセスできないからです。

しかし、ボブはいくつかの情報を得ました $$$x$ そして $$$y$ 。 例えば、彼はランダムに選ぶかもしれません $$$x '$ そして平等が成り立つかどうかをチェック $$$x = x '$ 計算 $$$E（x '）$ 。 このため、上記のプロトコルは実際にはゼロ知識プロトコルではなく、ここではスキームを説明するためにのみ使用されます。 実際、後で見るように、HSは最終的に証拠の秘密ではなく検証者の要求を隠すためにSNARKで使用されます。

次に、このような非表示の配置方法の例を見てみましょう。 実際、通常の加算で通常の整数に対してそれらを構築することはできません;その代わりに、 有限群を考慮する必要があります ：



nを整数にします。 いつ書かれますか $$$A \ mod \ n$ 整数Aの場合、 Aをnで割った余りを取ることを意味します。 例えば $$$9 \ mod \ 7 = 2$ そして $$$13 \ mod \ 12 = 1$ 。 使用することもできます $$$mod \ n$ セット{0、...、n-1}の加算演算を決定します。 通常の追加が最初に行われますが、その後に適用されます $$$（mod \ n）$ 結果にセット{0、...、n-1}の数を取得します。 時々 $$$（mod \ n）$ このタイプの加算が使用されることを指定する式の右側に書き込まれます。 例えば $$$2 + 3 = 1 \（mod \ 4）$ 。 要素のセット{0、...、n-1}を追加操作とともにグループと呼びます $$$Z_n$ 。



プライムpには 、次を使用できます。 $$$mod \ n$ 集合{1、...、p-1}の乗算の演算を決定するため、乗算の結果も常に集合{1、...、p-1}に入ります。 これは、通常の整数の乗算によって達成され、結果に適用されます $$$mod \ p$ 。 例えば $$$2⋅4 = 1 \（mod \ 7）$ 。

pが単純でない場合、この方法で乗算を決定するのは問題です。 問題の1つは、両方の引数がゼロに等しくなくても、乗算の結果がゼロに等しくなる可能性があることです。 たとえば、 p = 4の場合、次のようになります $$$2 * 2 = 0 \（mod \ 4）$ 。

この操作とともに要素のセットをグループと呼びます。 $$$Z ^ * _ p$ 。 このグループには、次の有用なプロパティがあります。

1. これは循環グループです。 これは、いくつかの要素gが存在することを意味します $$$Z ^ * _ p$ すべての要素が $$$Z ^ * _ p$ として書くことができます $$$g ^ a$ セット{0、...、p-2}からのa $$$g ^ 0 = 1$
2. 離散対数は難しい $$$Z ^ * _ p$ 。 これは、 pが十分に大きく、要素hが $$$Z ^ * _ p$ 、その後、セット{0、...、p-2}から整数aを見つけるのは困難です。 $$$g ^ a = h \（mod \ p）$
3. 同じ基底を持つ要素を乗算すると度が加算されるため、セット{0、...、p-2}からa、bを取得します 。 $$$g ^ a * g ^ b = g ^ {a + b \（mod \ p-1）}$

これらのプロパティを使用して、「加算をサポート」する準同型隠蔽を構築します。つまり、計算できることを意味します $$$E（x + y）$ 知っている $$$E（x）$ そして $$$E（y）$ 。 引数xが $$$E$ グループに属します $$$Z_ {p-1}$ したがって、範囲は{0、...、p-2}です。 定義する $$$E（x）= g ^ x$ そのようなxごとに、 $$$E$ GS：最初のプロパティから、異なる $$$x '$ から $$$Z_ {p-1}$ 異なる関数値が対応します。 2番目のプロパティから、 $$$E（x）= g ^ x$ xを見つけるのが難しい最後に、与えられた、3番目のプロパティを使用して $$$E（x）$ そして $$$E（y）$ 計算できます $$$E（x + y）$ どうやって $$$E（x + y）= g ^ {x + y \ mod \ p-1} = E（x）⋅E（y）$ 。

ブラインド多項式計算

ここで、多項式の概念を思い出し、多項式の「ブラインド計算」の概念を紹介し、準同型隠蔽（HS）を使用してそれを実現する方法を紹介します。 後で、「ブラインドコンピューティング」がSNARKコンストラクトの中心的なツールであることがわかります。



で示す $$$F_p$ サイズpのフィールド、つまり要素 $$$F_p$ セット{0、...、p-1}に属し、加算と乗算の演算は $$$mod \ n$ 上で説明したように。

多項式と線形結合

フィールド上のd次の多項式P $$$F_p$ 次の形式の式です。



$$$P（X）= a_0 + a_1 * X +a_2⋅X ^ 2 + ... +a_d⋅X ^ d$



いくつかのために $$$a_0、...、a_d∈F_p$ 、



P点の値を計算できます $$$s∈F_p$ sをXに置き換えて、結果の量を計算します。



$$$P（s）= a_0 +a_1⋅s +a_2⋅s ^ 2 + ... +a_d⋅s ^ d$



何を知っている人のために $$$P$ 、値 $$$P（s）$ 値の線形結合です $$$1、s、...、s ^ d$ ここで、線形結合は「加重和」として理解されます。 $$$P（s）$ 「重量」は $$$a_0、...、a_d$



上記からHSを決定しました $$$E$ どうやって $$$E（x）= g ^ x$ ここで、gは、実行が困難な離散対数問題を持つグループの生成元です。 このGSは、「追加をサポート」するという意味で、 $$$E（x + y）$ 知って計算することができます $$$E（x）$ そして $$$E（y）$ 。 また、「線形結合をサポートする」ことにも注意してください。 これは、与えられた $$$a、b、E（x）、E（y）$ 計算できます $$$E（a x + b y）$ これは簡単に表示できます：

$$$E（ax + by）= g ^ {ax + by} = g ^ {ax} * g ^ {by} =（g ^ x）^ a *（g ^ y）^ b = E（x）^ a * E（y）^ b$

ブラインド多項式計算

アリスが次数dの多項式Pを持ち、ボブが値を持っているとします $$$s∈F_p$ 彼はランダムに選択しました。 ボブは知りたい $$$E（P（s））$ 、つまり ポイントsでのHS Pの値。 これを行うには、2つの簡単な方法があります。

• アリスはPをボブに送信し、計算します $$$E（P（s））$ 私自身。
• ボブはsをアリスに送ります $$$E（P（s））$ それをボブに送信します。

ただし、ブラインドコンピューティングの場合、ボブに確認してもらいたい $$$E（P（s））$ 受け取らずに $$$P$ -最初のオプションを除外します。 そして最も重要なことは、アリスにsを認識させたくないので、2番目のオプションは除外されます。

送信したくない主な理由 $$$P$ ボブ、彼は大きいという事実だけで構成されています-彼は含まれています $$$（d + 1）$ 現在のZcashプロトコルでd〜2,000,000の要素。 本質的に、これはSNARKの「制限された」部分によるものです。

HSを使用して、次のようにブラインド計算を実行できます。

1. ボブはアリスに隠れている $$$E（1）、E（s）、...、E（s ^ d）$
2. アリス計算 $$$E（P（s））$ 最初のステップで送信されたアイテムの $$$E（P（s））$ ボブする。 （アリスができるのは、 $$$E$ 線形結合をサポートし、 $$$P（s）$ は線形結合です $$$1、s、...、s ^ d$ ）
   
   

もちろん、ボブがアリスに送信する隠蔽のシーケンスが多項式自体と同じ長さであることは事実ですが、このシーケンスはシステムパラメーターで「ハードコーディング」でき、アリスのメッセージはSNARK証明ごとに異なることがわかります

アリスはsを認識せず、ボブはPを認識せずに、非表示のみが送信されたことに注意してください。

実際、非表示のプロパティは、 sを取得できないことのみを保証します。 $$$E（s）$ 。 さらに、シーケンスがわかっているため、 sを取得できないことも必要です。 $$$E（s）、...、E（s ^ d）$ 、潜在的にsに関するより多くの情報を含みます。 この問題の解決策は、SNARKのいくつかのセキュリティプルーフで使用されるDiffie-Hellman d-orderソリューションに基づいています。 （離散対数の複雑さ。注翻訳者）

なぜこれが便利なのですか？

次のセクションでは、SNARKでブラインドコンピューティングがどのように使用されるかについて詳しく説明します。 大まかに言えば、検証者は「正しい」多項式の考えを持ち、証明者がそれを知っていることを検証したいと考えています。 証明者が両方に知られていないランダムなポイントでブラインド計算を実行する場合、これにより、証明者は、多項式が正しくない場合に高い確率で間違った答えを返すようになります。 これは、「異なる多項式はほとんどの点で異なる」 というシュワルツ・ジッペルの補題に基づいています。



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