Anbi Lab の Guo Yu: ディープ ニューラル ネットワークがゼロ知識証明に遭遇するとき

編集者注: この記事は以下から引用しました万祥ブロックチェーン (ID: gh_1b8639a25429)、許可を得てOdailyによって転載されました。

編集者注: この記事は以下から引用しました

万祥ブロックチェーン (ID: gh_1b8639a25429)

ゼロ知識証明

、許可を得てOdailyによって転載されました。

この記事は、Wanxiang Blockchain Hive Academy の第 29 回オンライン公開コースの共有コンテンツです。この号では、SECBIT Lab の創設者である Guo Yu 氏に「ディープ ニューラル ネットワークがゼロ知識証明と出会うとき」を紹介してもらいます。

今日は「ディープニューラルネットワークがゼロ知識証明に出会うとき」を紹介します。

ゼロ知識証明

「ゼロ知識証明」の概念は、ブロックチェーンの基礎となる技術アーキテクチャに馴染みがあり、1985 年に Goldwasser、Micali、Rackoff によって提案されました (図を参照)。 「ゼロ知識証明」は長い間、計算理論研究の狭い領域に限定されてきましたが、その影響は広範囲に及んでいます。

ゼロ知識証明に「証明」という言葉がありますが、この概念は人類の文明発展の歴史の中で何度もパラダイムシフトを繰り返してきました。古代ギリシャにおいて「証明」は独創的な数学的手法であったが、20世紀初頭までに第三次数学的危機の中で数学的証明が再解釈され、形式論理が導入されて形式化され、コンピューティング理論とコンピュータが誕生した。

1970 年代までに、プログラムと証明の間の素晴らしい関係が発見され、現代の関数型プログラミングと自動定理証明の多くの概念が導入され、1980 年代までに、「証明」の概念は対話型システムに拡張されました。 1980 年代以降、対話型証明システムは、哲学的な意味と理論的および技術的な側面の両方で革命的な新しい洞察をもたらしました。

ゼロ知識証明の概念を初めて見たとき、私の最初の反応は、これは非常に直感に反するものであるということでした。なぜ「直感に反する」のでしょうか?まずゼロ知識証明の基本的な枠組みを簡単に紹介します。

ゼロ知識証明では、右側のような人物 (ボブと呼びます) が存在する必要があり、左側は信頼できないマシンである可能性があります。この時点で、ボブには左側のマシンに実行するコンピューティング タスクが渡されますが、マシン自体は人間によって制御される可能性があるとします。ボブは、計算タスクとして「F ()」関数を使用し、入力「X」を取得し、それを左側のマシンに渡して計算タスクを完了させる必要があります。この計算プロセスは左側のマシンで行われたため、ボブは計算プロセス全体を目撃していないのに、なぜボブは計算結果 Y=F (X, W) の式が成り立つと信じているのでしょうか。また、計算過程には左の機械だけが知っている秘密のデータ（W）が混ざっていますが、ボブはWを持っていないため、ボブは計算過程を繰り返しても計算結果が正しいかどうかを知ることができません。このような状況でも、ボブは計算結果が正しいと信じられるでしょうか?

一言で言えば、ゼロ知識証明は魔法のようにボブに計算結果が正しいことを納得させることができます。これは少し信じられないように聞こえますが、信頼計算結果 Y は、左のマシンに対する不信感、つまり、何もないところから信頼を生み出すというゼロ知識証明に基づいており、まさに直感に反しています。二人の人がお互いをまったく信頼していないときでも、何か信頼を築くことができるものがあると想像するのは、とてもとても興味深いです。

直観に反するゼロ知識証明 要約すると、次のように理解できます。リモート コンピューティング プロセスの完全性と機密性は保証されます。

1. 誠実さ。私は計算プロセスがリモートで行われているのを見たことはありませんが、そのプロセスを目撃したことはありませんが、計算プロセスが現実の世界で起こったに違いないことは知っています、そして計算結果は正しい、つまり計算プロセスは行われていないことを意味します悪意を持って改造または偽造されたもの。

2. 機密保持。私は計算プロセスを目撃することはできませんが、計算プロセスの一部の中間結果を知ることは不可能であり、その内部の情報を知ることも不可能であるため、いくつかの秘密の入力を含む計算プロセス全体は私にとって秘密であり、秘密です。 。

これが、直観に反するゼロ知識証明が達成できることです。ゼロ知識証明は何に役立ちますか?最も直接的な用途は、いわゆる「データプライバシー保護」だと思います。個人データ、健康データ、銀行取引明細書、旅行手配、通信記録などのいくつかを簡単にリストしました。実際、私たちは心拍数、医療記録、毎日の支出額などの健康状態を誰にも知られたくないのです。しかし、タクシーに乗りに出かけるなどのサードパーティのサービスも楽しみたいです。自分の場所を一部の人には知ってもらいたいが、他の人には知られたくない、または大まかな場所だけを知ってもらいたいそして、私たちは彼に詳細を知らせたくありません。

企業データ: 人事ファイル、倉庫保管と物流、財務台帳、顧客情報。伝統的にこれらは非常に機密性の高いデータですが、企業間コラボレーションの効果を最大化するには、一部のデータを共有する必要があります。ゼロ知識証明は、データ プライバシーを確​​保し、同時にデータを共有する方法を提供するため、私たちの将来の生活や仕事に最も大きな影響を与えるのは、非常に効果的なデータ プライバシー保護テクノロジーを提供することです。

ゼロ知識証明は、ブロックチェーンの基礎技術として今でも興味深い用途が数多くありますが、ゼロ知識証明は 1985 年に提案されて以来、ブロックチェーン技術が実用化されるまで、長い間理論的結果のレベルにとどまっていました。おそらく 2015 年から大規模。2020 年、ゼロ知識証明がブロックチェーンで広く使用されています。ブロック圧縮、トランザクションの匿名性の保護、アイデンティティのプライバシー、共有データ、オフチェーンのデータストレージの整合性などを含め、ブロックチェーン業界の技術者の友人はこれらに精通している必要があります。

zkSNARK

次に、2 つの非常に基本的な概念を紹介します。

非インタラクティブなゼロ知識証明

前述したように、ゼロ知識証明が提案されたとき、「証明」パラダイムに新たな革新が加えられました。これまでは、証明は紙に書かれていました。たとえば、教師が試験で質問するなどです。外。ゼロ知識証明は対話型の証明であり、教師に証明のプロセスを話さなくても、教師と話すことで私の言うことを信じてもらうことができます。

なぜ非インタラクティブなゼロ知識証明が再び存在するのでしょうか?非インタラクティブなゼロ知識証明では、いくつかの特別な技術を使用して、インタラクティブな証明プロセスを非インタラクティブなゼロ知識証明に折り畳むことができます。非インタラクティブなゼロ知識証明は、ブロックチェーン分野でより広く使用されています。

これも非常に一般的な単語ですが、学術分野ではあまり一貫性のない解釈が多数あります。厳密に言えば、zkSNARK は特別な種類の NIZK、つまり特別な非対話型ゼロ知識証明です。

ポイントとしては以下の3つが挙げられます。

1. 簡潔。それが生成する証拠は非常に小さいですが、どれほど小さいのでしょうか?通常は KB 程度で、200 バイト以下の場合もあります。わずか数百バイトですが、表現できる計算プロセスは非常に大規模になる可能性があり、保護できるデータはテラバイト単位になることもあります。

2. 議論。これはゼロ知識証明の一種ですが、後で簡単に説明します。

3. zkSNARKの最後に「K」があり、知識を意味します。意味は、証明とは「知識」についての証明であり、この「知識」には数学的な定義があるということです。

プライバシー保護、ブロックチェーン、ゼロ知識証明

この概念について説明する前に、まず暗号化コミットメントという非常に重要な概念について説明する必要があります。図に示すように、左側にデータベースがあることがわかります。このデータベースは非常に大きく、おそらく 1TB 以上の大きさです。暗号化によって非常に小さなバイトのセグメントに変換できます。おそらく 100 バイト未満です。データベースがどれほど大きくても、最終コミットメントは 100 バイトを超えないデータに圧縮できます。

わずか 100 バイト強ですが、データベースとの一意のバインディング関係を確立できるため、データベースに変更が発生した場合は、それに合わせて Promise も変更する必要があります。約束は「鍵」のようなもので、誰かが約束を書き留める限り、データベースに変更がある限り、約束は劇的に変化します。

Promise には 2 つのプロパティがあります。

性質 1: バインド。Promise は元のデータ セットをバインドします (改ざんできません)。このデータ セットは非常に大きくなる可能性がありますが、非常に小さなコミットメントでバインドできます。

性質２：隠蔽し、元データの情報を漏洩しないことを約束する。 100バイト程度しかないため、情報量が大幅に失われており、元データの情報が漏洩することはありません。

旅行記録や銀行などのデータベースが多数ある場合、2 つのコミットメントを生成し、そのコミットメントをチェーン上に置くことができます。コミットメントをブロックチェーン上に置くと、次のような効果が得られます。もう約束を戻すことはできません。データベースは変更されましたが、Promise をチェーンに追加した後は、全員に表示できます。Promise を通じてデータベースにアクセスすることはもちろん、選択的に開くことも、開くこともできますデータベース データを何らかの処理した後です。しかし、このコミットメントが鎖でロックされているため、不正行為は不可能です。データを他の人に引き渡す前に、非常に複雑な処理を行ったり、その中の機密データを削除したりすることができますが、約束は連鎖しているため、これは非常に正直であり、偽りではない必要があります。

コミットメントというとすごいように聞こえますが、これは非常に伝統的で一般的に使用されている暗号化ツールであり、専門家以外の人にはほとんど知られていません。実際には Promise を実装する方法はたくさんありますが、最も簡単な方法は Hash などの操作を使用することです。また、マークル ツリー、ペダーセン コミットメントまたは多項式コミットメント、エルガマル暗号化などもあり、これらはすべて約束を果たすことができます。

コミットメントには 2 つの主要なタイプがあり、暗号理論の観点から分析されます。1 つ目のタイプは、計算結合と完全隠蔽です。 2 番目のカテゴリ: 完全結合と計算による隠蔽。

いわゆる完璧な隠蔽とは、1 ビットも漏洩することは絶対に不可能であり、元のデータは完全に隠蔽されるという約束ですが、その結合関係は計算上のものです。現在の計算能力をはるかに超えており、元のデータに関係のない偽の約束を偽造して偽造する可能性があります。

もう 1 つはその逆で、その結合関係は完全結合です。超量子コンピューターがあっても偽造は不可能ですが、その隠蔽は計算可能です。つまり、100 年後に超量子コンピューターが登場したら、現在の Generate a Promise を解読して、そこから有用な情報を抽出できる可能性があります。

Binding と Hiding の両方において完璧なコミットメント スキームが存在することは不可能であることが理論的に証明されています。しかし、プライバシー保護のためのゼロ知識証明の観点からは、通常、最初のタイプのコミットメント (完全隠蔽) が使用されますが、そのコミットメントは計算結合です。約束を連鎖させたいので、100 年後も誰もが見ることができることを意味しますが、この情報は 100 年後に本当に他人に解読されるのではないかと心配する必要はありません。さらに、このタイプのコミットメントは、非常に簡潔なゼロ知識証明を生み出すことができます。これが、先ほど述べた議論です。

zkSNARK原則

データベースが 100 バイトであると約束しながら、同時にデータが特定の特性を満たしていることを証明できるのは、なぜ信じられないことなのでしょうか。

まず、「ゼロ知識証明」とは何なのかをおさらいしてみましょう。計算をして、その計算結果を彼が信じていないリモート マシンに送信するように言ったのは右側のボブです。このマシンはハッカーによって制御されているか、この人物が問題を起こしている可能性がありますが、それは問題ではありません、関数を指定して X を入力し、しばらくしてから Y を入力してください。私はその機械を信じませんが、Yを見たので、Yを疑っていますが、追加のゼロ知識証明を確認したため、ゼロ知識証明はYが真実であると教えてくれたので、信じました。これはどのように機能しましたか?

まず最も単純なアイデアに戻りましょう。プログラムを実行するマシンがあれば、プログラムが見えなくても心配しません。最も簡単な方法は、計算プロセス全体をカメラで最初から最後まで記録することです。ビデオを取得した後、計算の各ステップが正しいかどうかをフレームごとにチェックできます。これはばかげていますが、理論的にはうまくいくかもしれません。

しかし、明らかにこの解決策は非常に非現実的です。マシンの実行中、マシンのメモリ状態は 4G メモリなど非常に大きく、ビデオ ファイルはプロセス全体を記録した後で検証できないほど大きくなります。

改善する方法はありますか？ CPU とメモリのモデルではなく、計算回路の計算モデルを使用します。演算回路の計算モデルとコンピュータCPUが動作するプログラムの表現能力はほぼ同等であり、基本的に一般的な計算を表現することができます。

演算回路は、「乗算ゲート」や「加算ゲート」などの「ゲート」が相互に接続されて構成されています。回路の左側から入力が入力され、演算後の右側の出力線に演算結果が出力されますが、全体の処理は「＋」と「×」を計算することになります。 、ほとんどの操作を表現できます。

演算回路の利点は、計算過程を撮影できることです。このとき、カメラがシャッターを押して写真を撮り、回路を一望できれば、計算過程をすべて記録したことになる。このように、検証計算は検証ビデオではなく、ビデオはフレームごとに見られますが、写真は、写真の細部まで検証されている限り、単なる写真です。

回路計算を検証するにはどうすればよいですか?各ゲートの動作を検証するには、各加算ゲートについて、左右の入力の加算が出力と等しくないことを確認します。乗算ゲートの場合は、左右の入力の乗算が出力と等しくないことを確認します。一つ一つのドアを根気よくチェックしていれば大丈夫です。

ゲート数が数百億の場合、検証には 1 年以上かかる場合があります。非常に多くのゲートの検証プロセスを簡素化する方法はあるでしょうか?これは、数学ツール「多項式エンコーディング」を使用して実行できます。

たとえば、y0、y1、y2 という数値があり、それらを XY 軸平面上に置き、それらを 1 つずつ点に変換し、それらの点を通過する曲線を見つけます。これは、すべての値をエンコードするのと同じです。 y0 から yn までの 1 つの曲線値。

曲線としてエンコードする利点は何ですか?利点は、値 yk の 1 つを変更したい場合、たとえ少し変更したとしても、曲線全体が明らかに乱れることです。摂動された曲線は、n 個の点でのみ元の曲線と同じですが、他の点は逸脱しています。多項式エンコーディングは、たとえ小さな変更であっても増幅する可能性があります。したがって、点をランダムに検証することで、曲線によってエンコードされた点が変更されているかどうかを確認できます。

次に、先ほどの算術回路内のすべての乗算ゲートの左側の入力ゲート、右側の入力ゲート、および出力ゲートに対して 3 つの異なる多項式エンコードを実行して、3 つの曲線を形成できます。ここで、曲線が 3 つある限り、3 つの曲線 (3 つの多項式) 間の乗法関係が満たされていることを検証するだけで十分です。乗算関係を検証するには、X 軸上の点をランダムにサンプリングするだけでよく、100 億ゲートを検証する必要はありません。 3 つの曲線は検証されていますが、検証者が見た秘密が多すぎることは明らかであり、ゼロ知識証明では計算プロセスの秘密が漏洩しないようにする必要があります。どうやってするの？多項式演算は、楕円曲線グループに準同型的にマッピングできます。

整数の有限体に対する加算演算は、楕円曲線グループに対する二項演算にマップされます。整数乗算演算は楕円曲線群上の双一次ペア演算に準同型写像でき、乗算は単乗のみですが、演算回路の演算関係を検証するには十分です。

このプロセスは単純に見えますが、zkSNARK の研究は多くの暗号学者の努力に基づいています。そのルートは IKO07 (2007) まで遡ることができます。2010 年に Groth は予備的なアイデアを持ち、重要なブレークスルーは 2013 年でした。 Groth16 の改良されたソリューションは、業界で最も人気のあるゼロ知識証明アルゴリズムです。 Marlin、Aurora、Spartan、Fractal などの非常に新しい改善スキームもいくつかあり、これらはすべて GGPR13 アルゴリズムの継続的な改善から開発されました。

2013 年の GGPR13 論文は比較的大きな進歩であり、そこから多くの素晴らしいアイデアが生まれました。この論文の著者は、Rosario Gennaro、Craig Gentry、Bryan Parno、Mariana Raylova の 4 人です。

GGPR13/Pinocchio/Groth16 フレームワークを見てください。何か計算を表現したいとき、まず高級言語でコードを書き、それをコンパイラで演算回路にコンパイルし、行列表現でR1CS行列を生成し、多項式エンコードでQAPを生成し、最後にTrusted-Setup 経由: キーの証明、キーの検証。証明キーは計算プロセスを証明するために使用でき、検証キーは証明 π が正しいことを知るために使用できます。

ゼロ知識証明 + ディープ ニューラル ネットワーク

ゼロ知識証明を使用すると、データベースのコミットメントを計算し、チェーン上で公開できます。コミットメントを通じてデータベースをチェーン上に置いた後、多くのことができるようになります。データベースを使用して、多くの有用な情報を生成できます。個人のプライバシーを暴露することなく、友人、企業、社会全体と情報を共有する機能。次に、私たちのチームがディープネットワークで段階的に行った結果を紹介します。

画像認識は広く使用されています。これは標準的な画像分類モデルです。標準的なテスト ケースには飛行機、車、鳥、犬などが含まれ、解像度は 224×224 です。次のステップは、プライバシー保護 + 機械学習 (ゼロ知識証明 + ディープ ニューラル ネットワーク) です。

左側には個人情報が多く含まれるデータベースがあり、機械学習（トレーニング）を経て人工知能モデルが生成されます。モデルには個人のプライバシーが反映される可能性があるため、アリスはモデルを公開したくありません。

しかし、アリスはモデルがボブに貴重な情報を提供できると考えており、ボブはアリスに写真を提供して、その写真を特定するのを手伝ってくれると言いますが、私はあなたの訓練セットの詳細を知りません。アリスは写真を撮り、それを認識用のモデルに入力し、ゼロ知識証明とともに結果を生成できます。モデルの結果が猫を認識した場合、その結果が秘密のモデルによって実際に認識されたことを証明するゼロ知識証明も教えます。もちろん、猫や犬は証明なしで見えますが、機械学習のシナリオでは、予測結果が信頼できるかどうかを判断する方法がありません。

たとえば、医療診断フィルムにがんの初期兆候があるかどうか、この結果はフィルムを見ただけではわかりませんが、モデルからはあなたが非常に健康であることがわかります。信じなくても問題ありません。ゼロ知識証明により、これが確かに信頼性の高い X 線フィルム データベースから推定された結果であることがわかります。

モデルは鎖に乗っていると約束できるので、アリスがボブをだますことは絶対に不可能になります。重要な点は、アリスが善人か悪人かを信じる必要がなくなるということです。証明結果を出せれば、あなたが気にするのは結果だけであり、誰がそれを提供したかは気にしません。

次に、VGG16のニューラルネットワークモデルである画像認識実験を行いました。 16層のディープニューラルネットワークです。 14 の畳み込み層、2 つの全結合層、Relu 活性化関数、Max-pooling プーリングなど、多数のパラメータがあります。

これを行うのは非常に挑戦的ですが、まず、参考にする先行研究がありません。

課題 1: 算術回路で科学計算を実行する方法。

科学技術計算では、10 進数と浮動小数点の演算が数多く行われます。有限体上の固定小数点数をエンコードすることを選択し、VGG16 モデルのすべてのデータを正規化して、すべての数値が 256 を超えないようにします。 6 つの 10 進固定小数点数を考えます。8 ビットは整数部分を表し、6 ビットは小数部分を表し、24 ビットは特定の点を表します。デジタル回路を使用して、固定小数点数（二乗、平方根、対数など）のさまざまな演算を実現します。

課題 2: R1CS マトリックスは巨大であり、PB レベルのメモリを必要とします。

一般的なコンピュータのメモリは GB ですが、サーバーのメモリは数百 G に達し、すでに非常に大きいと考えられています。 R1CS 行列演算回路を実際にエンコードする場合は、PB レベルのメモリが必要です。通常のマシンではほとんど耐えられません。 VGG16 画像認識を行うには 146 億の乗算ゲートが必要であると計算されました。私たちの知る限り、これはこのような大規模で実用的なアルゴリズムのゼロ知識証明としては世界初となります。乗算回数の分布は畳み込み層が多く、ディープニューラルネットワークを行う場合は畳み込み演算が多く、90%以上を占めます。

回路マトリックスが大きすぎるため、画像認識プロセスを証明するために、新しいゼロ知識証明スキーム - CLINK を発明する必要がありました。他のゼロ知識証明スキームと比較して、CLINK は大規模回路に対処するためにいくつかの特別な技術を採用しています。

技術 1: 巨大な回路には多数の回路が重なっています。画像認識に関して言えば、畳み込み層はたくさんありますが、多くの畳み込み層の回路部分は似ており、似たものを組み合わせて処理することができます。

技術 2: 巨大な回路を多数の小さな回路に分解し、小さな回路を 1 つずつメモリに保持し、完成後にリンクすることができます。回路が分解された後でも、複数の回路間の接続を保護する必要があるため、これらの値は依然として秘密であり、公開することはできません。私たちは依然として、中間のすべてのサブ回路間の露出した配線を約束によって保護しています。そうすれば、回路の分解が実現できます。

同一のサブ回路を組み合わせて証明することができます。最終的に、巨大な回路に対して多数のゼロ知識証明が生成され、中間値コミットメントが追加されて完全なゼロ知識証明が形成されました。このプロセスでは、サブ回路と中間の公開ライン計算コミットメントに対してゼロ知識証明が生成され、中間値はパブリック入出力として使用されず、結果はパッケージ化されて圧縮されます。

私たちは 2 つの実験を行いました。

解決策 1 (並列): マルチコア CPU を最大限に活用し、VGG16 を同時に並列計算し、16 層の回路すべてを並列に証明し、すべてのコミットメント層間のリンク証明を同じ時間です。

解決策 2 (シリアル): レイヤーごとにシリアル化し、最初に 1 番目のレイヤーと 2 番目のレイヤーを作成し、次に 1 番目のレイヤーと 2 番目のレイヤーの間のリンク証明を実行します。

1TB メモリと高性能 SSD を搭載したスーパーサーバーを提供してくれた QTUM チームに非常に感謝しています。並列ソリューションにはまだ大量のメモリが必要なので、最初の並列ソリューションを最初に使用しましょう。PB レベルは必要ありませんが、並列ソリューションの実行には約 5 TB のメモリが必要で、そのうち 4 TB はスワップ パーティションで実行されます。プロセス全体で SSD スワップ パーティションが使用されるため、パフォーマンスが大きく影響されます。

並列解法: 画像が 224×224 の解像度で子猫を認識することを証明します。証明時間は 25 時間かかります。 4TB メモリを搭載したマシンが与えられた場合は 5 時間しかかからないかもしれませんが、4TB メモリを搭載したマシンを見つけるのは難しく、検証時間は 1 時間かかります。証明長は 80KB、ピーク時のメモリ使用量は 5TB です。

シリアル スキーム: 遅く見えますが、マシン上での実行速度が速いため、500 GB のメモリのみが使用され、スワップ パーティションが使用されないため、全体的に高速です。証明時間は 20 時間、検証時間は 1 時間です。 、証明長は 110KB です。

私たちの実験の過程で、韓国の学者も草稿を送ってきて、私たちと同様の研究をしました。最大の違いは、特に回路内で最大プーリングを実行することが非常に難しい場合に、VGG16 に妥協的な修正を加えていることです。そのため、平均値を使用してプーリングを実行します。その中には非常に大容量の83GB CRSが導入されました。私たちのスキームでは、CRS は非常に小さく、実用性はより優れています。これは私たちが知ることができる最新の国際的な研究結果です。

ビッグデータゼロ知識証明の応用展望

ゼロ知識証明は理論から工学へと移り、徐々に応用へと進んでおり、将来的にはより多くのデータを扱えるようになるでしょう。探索プロセス中に開発した CLINK アルゴリズムは、ディープ ニューラル ネットワークの推論プロセスを含む、ビッグ データの統計、クエリ、その他の複雑な操作をサポートできます。将来的には、これらのテクノロジーは次の用途に使用できるようになります。