この記事の著者である Dongze は、Ambi テクノロジー コミュニティの小さなパートナーです。彼は現在スタンフォード大学で勉強しており、研究の方向性は暗号化です。この一連の記事は、スタンフォード大学の有名なコース「CS」に関する著者の研究ノートから来ています。 251: 暗号通貨とブロックチェーン技術」。このコースの講師は、暗号学のマスターである Dan Boneh です。
この記事の著者である Dongze は、Ambi テクノロジー コミュニティの小さなパートナーです。彼は現在スタンフォード大学で勉強しており、研究の方向性は暗号化です。この一連の記事は、スタンフォード大学の有名なコース「CS」に関する著者の研究ノートから来ています。 251: 暗号通貨とブロックチェーン技術」。このコースの講師は、暗号学のマスターである Dan Boneh です。
スタンフォード大学の先学期、私はダン・ボーネに従ってブロックチェーンとデジタル通貨関連のテクノロジーを学びました。これまでのコースとは異なり、今年のコースにはゼロ知識証明と呼ばれる新しい章が追加されました。愛らしいダンと彼のマスターであるベン・フィッシュ博士が順番に授業をしてくれましたが、知識ゼロのzkSNARKの起源、コンセプト、実現について説明し終えるのに2週間かかりました。
序文
序文
最初の草稿を書いた後、それを友人の校正者と共有したところ、多くの友人が背景知識が十分ではないと報告したことがわかりました。そこで、始める前にこの追加セクションを追加し、この記事を理解するために必要な背景知識を示しました。
序文を読んだ後、本文を始めましょう。
最初のレベルのタイトル
ビットコインの欠点
ビットコインに詳しい場合は、ビットコイン ネットワークではすべてのトランザクションが公開されていることを知っているはずです。
A が B に金額を支払いたい場合、A はスピーカーでネットワーク全体に、新しいトランザクション (Tx) を作成したいことをアナウンスします。このトランザクションの受益者は B の公開鍵 (P2PK) です。公開キーのハッシュ (P2PKH)。 B はトランザクションを確認している限り、自分の秘密鍵を使用してデジタル署名に署名し、自分が実際に公開鍵の所有者であることを証明できるため、お金を費やすことができます。
A が、ネットワーク上の傍観者 M として B に支払うトランザクションを送信すると、彼女には、文字化けしたアドレス文字列 bbbbb に x コインを支払うための文字化けしたアドレス aaaaa の文字列しか表示されません。次に、B が C に送金したとき、bbbbb が ccccc に多額の送金をしたことしかわかりませんでした。ビットコインの取引は強く結びついていることがわかります。誰が誰に送金したかは分かりませんが、蔓をたどっていくと多くの取引チェーンが見つかります。
すべてのユーザーが素直に送金するだけであれば、ビットコインは実際には比較的安全です。
ユーザーがそれを見抜き、もうプレイしたくない、取引所で現金化したいと考えた場合、チェーン全体の取引情報が公開されてしまいます。取引所にはKYC（Know Your Customer）ポリシーがあることが多く、デジタル通貨と法定通貨を交換する各ユーザーは実名認証を受ける必要があります。 Cがcccccのアドレスからお金を引き出して逃走すると、取引所はbbbbbがCに送金した事実を把握してしまいます。 C がマネーロンダリングの疑いがある場合、現時点では、B が現金化するのを静かに待って捕まえるだけで済みます。
米国ではChainaliesなど、ビットコインのトランザクションチェーン分析を行っている企業がすでに多数存在する。
最初のレベルのタイトル
匿名と仮名
私たちのプライバシーに対する理解は、実際には 2 つのタイプに分けられます。
1 つ目は匿名で、ユーザーは自分に関する情報を一切公開する必要がなく、学校の告白の壁のようなもので、誰が書いたかは決してわかりませんが、とにかく文字が書かれています。
2つ目はペンネーム（Pseudonymous）で、ユーザーがTiebaなど自分で作ったペンネームで情報を投稿することを意味しており、ユーザーのことをよく知らない場合、スクリーンネームから実名へのつながりを確立することができません。 、投稿者は誰なのかわかりません。
この分析から、ビットコインは実際には仮名メカニズムです。各ユーザーは独自の公開鍵 (仮名) をランダムに生成し、公開鍵アドレスを通じてお金を受け取ります。これは、A/B/C/D の 4 人がそれぞれ Xiaoming/Xiaohong/Ergou/Xiaogang として匿名でオンライン取引を行うのと似ています。D がリンク (取引所の現金引き出しなど) で自分の身元を明らかにしている限り、 Xiaoming/Xiaohong/ErgouとDの関係はすぐに暴露されます。
最初のレベルのタイトル
副題
CoinJoin
A から B への支払いは他の人に見られ、C から D への支払いも他の人に見られるため、ABCD の 4 人全員を 1 つのトランザクションに単純に投げ込むと誰かが考えました。ビットコイントランザクションには複数の入力と出力があるため、傍観者は、トランザクション内で aaaaa と ccccc の両方が x 個のコインを投入し、次に bbbbb と ddddd がお金を受け取ることがわかります。このように、取引所はこれらのアドレスが ABCD の 4 人に対応していることを知っていても、誰が誰からお金を受け取ったのかを知ることは困難です。
2 つのトランザクションのセットを識別するのがまだ簡単すぎる場合はどうすればよいでしょうか? 4 つには 2 つでは不十分、8 つには 4 つでは不十分などです。さまざまな人々の取引を組み合わせて一般大衆を混乱させ、追跡を不可能にします。これがコインジョインです。
CoinJoinのデメリットは何ですか?実際のところ、複数の取引を混在させても他人の摘発を完全に防ぐことはできず、摘発される可能性を完全に減らすことができるとしか言えません。そして、もう 1 つ重要な点があります。AB と CD の取引を混合したい場合、それらの取引量は同じでなければなりません。 A が B に 10,000 コインを支払い、C が D に 1 コインを支払う場合、入力と出力を見るだけでよく、CoinJoin トランザクションを 2 つの独立したトランザクションにすぐに分割できます。したがって、CoinJoinを導入する場合、同様の取引額の取引を混在させることも無視できない課題となります。
副題
機密トランザクション（プライベートトランザクション/CT）
自分が誰であるかを隠すのは非常に面倒なので、人々は、取引に関係する公開鍵を隠さなければ、取引金額も隠せるのではないかと考えるようになります。 A が B に送金した場合、たとえ B が暴露されたとしても、ネットワーク全体は A が B にいくら送金したかを知りません。
この運用が実現できれば、給料の支払いもビットコインで行うことができますが、毎月給料が入ってくることだけは見えていて、いくら稼いでいるのかはわかりません。
この方法を実現するには、まず準同型暗号という特殊な暗号化アルゴリズムを理解する必要があります。
一言で言えば、準同型暗号化は、暗号文が元の数学的特性を維持できるようにする特別な暗号化アルゴリズムです。
暗号化方式 E があり、E が加法準同型である場合、E(a) + E(b) = E(a+b) であると仮定できます。逆に、乗算が準同型の場合は、E(a) x E(b) = E(axb) となります。
この記事は zkp に関する一般的な科学記事であるため、具体的な実装方法については詳しく説明しません。 RSA の楕円暗号化方程式と大数モジュールの両方に特定の準同型特性があることを理解する必要があるだけです。
ピーダーソンの取り組み
隠しボリュームの話に移ります。 A の残高が 100 コインで、B に 10 コインを支払う場合、トランザクションは次のようになります。
前述の加法準同型暗号と組み合わせると、加法準同型暗号化方式 E がある場合、このトランザクションを次のように変換できます。
最初の数字が最後の 2 つの数字の合計と等しい限り、傍観者は最終的に取引高を確認することはできませんが、A が実際にお金の一部を B に渡し、その後、お金の一部を B に渡したことを認めなければなりません。お金はAに返されました。この方法はPederson Commitment（ピーダーソンコミットメント）と呼ばれるもので、データ自体は隠しますが、データ間の関係性は証明します。
負の数の脆弱性
これを読んだ友人の中には、大きな抜け穴を見つける人もいるでしょう。ピーダーソンは数値間の関係を証明すると約束しましたが、数値の値の範囲を制限しませんでした。つまり、A はいたずらをして、トランザクションを送信し、B に -100 コインを支払いたいと言い、その後、自分自身で 200 コインを「見つける」ことができます。このようにして、方程式は依然として成り立ちます。 A はこれを使用して無限にお金を印刷し、システム全体を破壊することができます。
負の数の存在を避けるにはどうすればよいでしょうか? Pederson の約束に加えて、すべてのトランザクションの数値が正であることを証明するには、別の一連の証明が必要です。つまり、すべてのトランザクションの数値は 0 ～ 2^256 (正の整数の最大値) の範囲 (範囲証明) に制限されます。
それは難しくないようですが、最も簡単な方法は間違いなくこれらの数字をすべて開示することです。しかし、これでは取引量を隠すという前提が崩れてしまいます。したがって、別の証明方法を見つける必要があります。つまり、元の数値を公開するのではなく、その特性 (値が 0 から 2^256 の間である) も証明する必要があります。それはポイントのように聞こえますか？心配しないで、別の質問を見てみましょう。
所有権の抜け穴
先に進む前に、このプロトコルには実際には所有権が不明であるという大きな抜け穴があることを簡単に指摘したいと思います。
ビットコインについて詳しい友人は、ビットコイン トランザクションを作成するときに、B に支払う予定の A が本当にお金を持っているかどうかをすぐに確認できるように、入力トランザクションの UTXO Txid を提供する必要があることを知っているかもしれません。
しかし今は、前のトランザクションを指すことについては何も言及していません。つまり、ネットワーク全体は A がいくら使ったかを知らないため、A は単に入力数値を数万、数万に変更し、そのすべてを自分自身に呼び出し、秘密裏に自分のためにコインを鋳造することができます。
この問題をどうやって解決すればいいでしょうか？選択肢は 2 つあります。
最初の解決策は、ビットコインのトランザクション メカニズムを導入し続け、最後のプライベート トランザクションの出力をトランザクションの入力として使用することです。この種の考え方は、問題の変換に少し似ています。前のトランザクションの結果をこのトランザクションに使用するので、前のトランザクションが OK である限り、私のトランザクションも OK です。
これは鶏が先か卵が先かの問題です。最初のプライベート トランザクションを問題なく作成するにはどうすればよいでしょうか?
特別なトランザクションを通じて、通常のコインをプライベートアウトプットに変換できます。このトランザクションの入力は既存のトランザクション ID (ビットコイン UTXO) であり、出力はプライベート出力になります。このようにして、私たちは最も初期の卵を生み出します。 (ZCashのシールド取引もこの原則です)
2 番目のスキームは、A の入力が本当に A に属していることを証明することです。イーサリアムのようなシステムには、世界状態という概念があります。世界状態とは、チェーン全体のすべてのユーザーとスマート コントラクトの現在のバランスとステータスです。一般に、完全なノードはワールド状態全体 (サイズが大きい) を保持しますが、ライト ノードはワールド状態のマークル コミットを保存するだけで済みます。
Pederson コミットメントとインターバル証明の提出に加えて、トランザクションで入力された数値が元の世界状態の A の残高と一致することを証明する追加の証明を提供します。この証明を達成するには、マークル証明を使用できます。
しかし、マークル証明を直接提出すると、傍観者全員が A のトランザクション入力を見ることができ、プライベートトランザクションの前提に違反します。繰り返しになりますが、依然として上記の謎のアルゴリズムを借用する必要があります。これは、答え自体 (A の残高) を隠すだけでなく、この数字が実際に世界の状態に属していることを証明することもできます。
ZCash: 全員匿名
CTという概念が提案されたとき、多くの人が現状に不満を抱き、「自分の名前さえ隠せたらいいのに」と感じずにはいられませんでした。
そこで、CT をベースに、トランザクション ユーザーを匿名化できる新しいメカニズムを追加した、ZeroCoin/ZeroCash の概念が提案されました。さて、メロンを食べていた傍観者Cさんは、インターネット上に文字化けの文字列が流れているのを見て、何のことだか全く分かりませんでしたが、本当だと信じるしかありませんでした。
ZCash は、ZeroCoin/ZeroCash プロトコルに基づいて実装されたデジタル通貨で、完全に匿名のトランザクションを実現できます。ここではあまり詳しく説明しませんが、私は依然として古い暗号化ツールに依存しています。ピーダーソンの約束、区間証明、マークル証明、そして私たちが話している黒魔術、つまり答え自体を明らかにしないものです。 .証明する。
最初のレベルのタイトル
ゼロ知識証明 (zkSNARK)
上記を読んだ後、誰もが私たちが解決したい問題について大まかに理解していると思います。
0 <= a <= 2^256 や SHA256(x) = y などの数値間の関係を証明したいと考えています。ただし、上記の a や x などの数値を公開したくありません。これを実現するためのシステムをどのように構築するか?
このトピックについて話す前に、考え方を変えて、このトピックをゼロ知識 (zk) と証明 (SNARK) の 2 つの部分に分割したいと思います。
副題
プルーフ (SNARK)
証明から始めましょう。
SNARK の正式名称は、Succinct Non-interactive ARgument of Knowledge です。この名詞は 3 つの側面から構成されます。
短い (簡潔な): 証明自体は十分に短くする必要があり、証明の複雑さが O(logN) または O(1) であることを検証するのが最善です。
非対話型: プロセス全体にインタラクションはありません。つまり、証明者は、文字化けしたコードの大きな文字列をテーブルに投げてから立ち去ることができ、後で文字化けしたコードの文字列を検証することで証明者が証明したことを検証できます。
知識の表現（知識の議論）: このことは比較的曖昧です。しかし、一般的な意味は、証明したいことは知識を表現できなければならないということです (知識の証明)。 PoK の証明には抽出器 (Extractor) というより抽象的な概念が含まれますが、具体的な内容については Guo Yu 氏の記事を参照してください。しかし、一言で言えば、あなたが証明するものは価値があり、他のものをいじるのではなく、計算によって得られたものです。
定義を読むと、SNARK を実装できるというだけで、特に簡潔さの点ですでに非常に強力であることがわかります。
アプリケーションとしては、サードパーティ組織が大量の (PB レベルの) データを独自のデータベースに保存している場合がすぐに思い浮かびます。政府機関がデータベースを監査して各データ ポイントに問題がないことを確認したい場合、通常の状況では、1 行ずつ読み、PB ごとにデータを読み、最後まで読み込む必要があるかもしれません。このとき、突然SNARKが現れ、O(1)やO(logN)というサイズと時間で、この巨大なデータベースの各データに問題がないことが十分に証明されました。ほとんどの人は、これは完全に不可能であると考えています。数千万の数値の精度を、わずか数個の数値でどのように検証できるのでしょうか。
副題
ゼロ知識 (zk)
ゼロナレッジ（知識ゼロ）に戻りましょう。
実際、ゼロ知識はこの SNARK 証明に基づく追加要件にすぎません。証明全体では、証明される答えに関連するデータを明らかにすることはできません。ゼロ知識の概念の公式定義は非常に曖昧であり、シミュレーター (Simulator) の概念が導入されています。詳細な紹介については、Guo Yu 氏の記事を参照してください。ここではそれについてのみ言及します。一言で言えば、どんなに賢いハッカーであっても、ゼロ知識証明をどう調べても、答えそのものに関連する情報を取り出すことはできない。
この政府監査データベースの概念に戻りますと、このデータベースは企業の納税状況であると想定できます。政府は税務データが正確であることを保証する必要がありますが、企業にとっては、商業機密に関わる可能性があるため、日々の業務フローを検査官に見られたくないのです。現時点では、単なる SNARK だけでは十分ではありません。以下を実現するには zkSNARK が必要です。
副題
ゼロ知識証明の応用
zkSNARKを使って何ができるでしょうか?
1つ目は、前述のプライベートトランザクション(Confidential Transaction)が実現できることです。 ZCash のプライベート トランザクション メカニズムは、zkSNARK に基づいて実装されています。このようにして、デジタル通貨取引はより安全になります。
2 つ目は、このテクノロジーを使用してブロックチェーンの効率性の問題をより適切に解決できることです。現在、ブロックチェーンのスケーリングにはいくつかの方法があることは間違いありません。コンセンサス強度を犠牲にしてブロック生成の速度を上げる、サイドチェーンを有効にする、または Lightning に似たオフラインのポイントツーポイント チャネルを有効にするなどです。
実は、ロールアップと呼ばれる別のアイデアもあります。ロールアップの概念は、おそらくメイン チェーンの負荷が大きすぎるため、トランザクションを受信し、トランザクション認証を実行し、一定期間にわたって蓄積されたすべてのトランザクションをバッチ処理できる小さなサーバーをさらにいくつかオープンします。メインチェーン。ただし、更新プロセスで依然として大量のトランザクション情報をメイン チェーンに送信する必要がある場合、このロールアップの意味は存在せず、メイン チェーンの負荷は軽減されません。このとき、SNARK が役に立ちます。SNARK (zk であってもなくてもよい) を通じて、ロールアップ サーバーは非常に短い証明をメイン チェーンに送信し、多数のトランザクションが正常であることを証明し、メイン チェーンのみを証明できます。最終的な結果に従う必要があります。その結果、いくつかの UTXO を追加または削除すれば完了です。 ZK Rollup を通じて、メインチェーンの負荷を大幅に軽減し、より多くの検証を他の場所に委託できます。
3つ目は、第三者との取引を実際に実現できることです。
A は機械学習の研究を行っていますが、優れたコンピューターを持っていないため、モデルのトレーニングのタスクを B に委託する予定だとします。 3 日後、B は A に、実行が終了したので、トレーニング済みのモデルを提供する前に A に先に支払いを依頼する必要があると伝えました。 A は、B が正直なトレーニング モデルを持っていないのではないかと心配していますが、ランダムに乱数を生成してパックしているため、支払う前に B が A に対してモデルを検証してほしいと考えています。 B は、A がモデルを入手した後、こっそりコピーし、お金を支払わずに直接ブロックするのではないかと心配しています。
この種の問題に直面した従来の解決策は、サードパーティに委託するか、チェーン上でスマートコントラクトを設計して、データと通貨の検証と交換を完了することです。 zkSNARK を使用すると、B はモデル トレーニング用の zkSNARK を A に直接送信でき、彼が本当に正直に 3 日間走り続け、不正行為をしていなかったことが証明されます。 A クイック認証が通過したら、安心して送金していただけます。
4 つ目は、データの所有権を完全に移転できることです。
銀行の口座残高データベースが SQL テーブルであると仮定すると、1 億人の顧客には 1 億行のレコードがあることになります。銀行は毎年、このような大規模なデータ システムを維持するために多額の費用を費やす必要があります。誰もが自分のレコード行をローカルに移動し、自分の口座データを維持できれば、銀行は一銭も費やす必要がなくなります。銀行がこれを行わない理由は、ユーザーが利益のために自分のデータを改ざんし、100元を100万元に変える可能性が非常に高いためです。
zkSNARK が保証できるのは、データ自体に問題がないことだけです。私たちは、全員の預金残高が各自のコンピューターに保存されている分散型銀行を想像できます。 A が B に送金したいときは、A が自分の残高から送金金額を正直に差し引いていることを確認するために、ネットワーク全体に zkSNARK を送信して、自分のアカウントの残高が正しく差し引かれていることを証明する必要があります。 B がアカウントに登録すると、残高の増加に対応する zkSNARK も送信します。
つづく
つづく
紙面の都合上、今回はここまでとさせていただきます。おそらくこれを見て、誰もがゼロ知識証明が必要な理由と、ゼロ知識証明がいかに強力であるかをより深く理解できるようになります。
次回の記事の冒頭では、zkSNARKの具体的な仕組みを中心に、もう少し詳しく書いていきたいと思います。
続きを読む
続きを読む
この記事で言及されている内容についてさらに詳しく知りたい場合は、リーディング リストを集めて以下に示します。興味のある友達は読んでみてください。
ゼロ知識証明に興味のある友人は、WeChat Xiaoan @SECBIT (id: secbit_xiaoanbi) をグループ ディスカッションに追加してください。
IOS
Android