Loading...
シリーズ: Zcashから第一原理 . 第5回記事: 零知識証明 対象読者: 新規ユーザー。以前の記事（有限体、曲線、コミットメント、マージェルツリー）すべてに言及しますが、必要に応じてそれぞれのアイデアを思い出します。 得られるもの: 零知識証明とは何か、それが提供する3つの保証、任意の文がどのように証明されるのか、そしてSaplingとOrchardがどのような力を持っているかについて直感的で正しい理解。
これはシリーズ全体が向かっている記事です。第0回記事以降、支払いは「カーテンの裏側」で検証されると述べてきました。正しいことを示しながら何も明らかにしないというものです。零知識証明とはそのカーテンです。これは我々が最初に提示したパラドックスを解決する最後のピースです: 公開されたネットワークが見ることを許されていない取引をどのように検証できるのか？
Zcashの中心にある矛盾を思い出してください:
これらは互いに排他的に見えます。検証には見ることが必要であり、プライバシーは見ることを禁止します。もし両方を和解できないなら、誰もが信頼できるプライベートなお金を持つことはできません。
零知識証明（ZKP）とはその和解です。それは証明者が検証者に、ある文が真であることをそれが真である以外の情報を一切明らかにせずに説得できるようにします。金額も、身分も、ノートもありません。ただ: "ここにあるものはすべてルールを守っている" だけです。機械的な仕組みよりも直感を構築しましょう。
パスワードを知っていることを示すが、それを言わない。 ウェブサイトはあなたがパスワードを知っていることを確認するために、あなたがそのパスワードでしか開けないものを使ってロック解除する様子を見ることによって行うことができます。パスワード自体は決して見られません。知識の証明は情報の開示なしに行われます。
色覚障害を持つ友人と2つのボール。 赤いボールと緑のボールを持っていて、あなたの色覚障害を持つ友人に見えるのは同じように見えています。あなたは彼にそれらが異なる色であることを説得したいですが、どちらが赤かを教えてはいけません。彼は両方を背中に隠し、任意で交換してから1つを見せます。あなたは彼が交換したかどうか言い当てます。もしボールが本当に異なっていたら、あなたは常に正解します。もし同じ色だったら、あなたは50%の確率で正解するだけです。20ラウンドを繰り返して、あなたの連勝記録は彼にそれらが異なることを説得しますが、彼はどのボールが赤かは決して学ばないでしょう。彼は事実に説得されたまま、他のことは何も学ばない。 これは零知識のミニチュアです。
洞窟。 環状の洞窟には、秘密の言葉でしか開かない魔法の扉があります。あなたはその言葉を知っていると主張します。それを明らかにすることなく証明するには: 検証者は外に待機し、あなたが中に入り、ランダムに左または右の通路を選んで進みます。検証者がどちらの側から出てきてほしいか叫びます。もし本当に言葉を知っていたら、常に応じられます（必要であれば扉を開けて通路を切り替えることができます）。もし嘘をついていたなら、たまたま正しい側から出るだけです。50%の確率で毎ラウンド。20回繰り返すと、嘘つきが生き残る確率は100万分の1未満になります。
その洞窟の物語は静かに3つの保証を示しています: すべての零知識証明が提供しなければならないものです。
| 保証 | 洞窟の物語での説明 | Zcashでの説明 |
|---|---|---|
| 完全性 | 言葉を知っているなら、常に正しい側から出る | 有効な取引は常に受け入れられる証明を生成する |
| 妥当性 | 嘘つきは圧倒的な確率で捕まる | 欺瞞的な取引（偽造されたお金、二重支払い）は受け入れられない証明を生成できない |
| 零知識 | 検証者は秘密の言葉を決して聞くことができない | ネットワークは金額、アドレス、どのノートかを学ぶことはできない |
これらの中のいずれかが失敗すればシステムは破綻します: 完全性がないと誠実なユーザーが拒否される; 妥当性がないと偽造者がお金を作れる; 零知識がないとプライバシーが消える。
洞窟は1つのかわいらしい事実を証明します。Zcashでは、より豊かな文を証明する必要があります: "私はツリー内に未使用のノートを知っている、それを支払う権限がある、そのnullifierが正しく計算されている、そして私の入力は出力と等しい。" どうやってボールや洞窟からそれへ到達するのでしょうか？
このシリーズ全体をつなぐアイデアがあります:
任意の文は計算で確認できるなら、それを算術回路として書き換えることができます: 有限体（第1回記事）上の加算と乗算のネットワーク。
回路を、文が真である限りすべて満たされる算術制約のリストと考えてください。すべてのチェックを可能にするプライベートな入力、あなたのノート、あなたの鍵、マージェルツーパスは証明者と呼ばれます。
これがなぜ第1回記事で有限体に時間を費やしたのか、そして第3回記事でZK対応ハッシュに時間を費やしたのか: 回路はフィールド算術を話すので、文内のすべての操作（ハッシュと第4回記事のマージェルツーパス含む）がそのように表現される必要があります。各操作が表現するコストが低いほど、証明は小さくて速くなります。
洞窟では多くのやり取りが必要でした。これはブロックチェーンには実用的ではありません。証明は一度投稿され、誰もが永遠にチェックしなければなりません。2つのアップグレードでこの問題を解決します。
非対話的（Fiat-Shamirのアイデア）。ライブ検証者がランダムな挑戦を叫ぶ代わりに、証明者は自分の証明までの部分をハッシュして「ランダムな挑戦」を自分で生成します。良いハッシュは予測不可能（第3回記事）なので、証明者は自分の利益のために挑戦を調整することはできません。冗長な会話は単一の自己完結型証明に縮小され、後で誰もがチェックできます。
簡潔性。最良のシステムでは、証明は非常に小さく、迅速に検証可能です。これは本当に驚くべき部分です。
Groth16証明（Saplingが使用）は約 192バイトで、証明する文が小さいか大きいかに関係なくミリ秒単位で検証されます。数百バイトの証明でも、数千の制約を含む計算に証拠を与えることができます。
これらを組み合わせると、あなたがいたるところ見かける略語を得ます:
zk-SNARK = zero-knowledge Succinct Non-interactive ARgument of Knowledge. 零知識（何も明らかにしない）、簡潔性（非常に小さく迅速）、非対話的（一発勝負）、知識の証明（証明者は本当に有効な証明者を知っている）。
無料のランチはありません。多くのSNARKは、回路に公開パラメータを生成するための一度限りのセットアップが必要です。このセットアップは秘密のランダム性を副産物として生成しますが、その秘密は破棄されなければなりません。誰かがそれを保持していたら、証明を偽造でき、つまりお金の偽造ができてしまいます（ただし、重要なのはプライバシーを壊すことはできないということです）。
この残った秘密は毒廃棄物と呼ばれています。これを安全に処分するために、Zcashでは多くの独立した参加者がランダム性をそれぞれ寄付する複雑な多当事者式儀礼を行いました; たとえ1人でも 自分の部分を正直に破棄すれば、毒廃棄物は回復不可能になります。
新しいシステムではこの要件を完全に取り除くことができるので、これはZcashが証明システムを進化させてきた最大の理由の一つです。
| デザイン | 証明システム | 信頼設定？ | 建設基盤 |
|---|---|---|---|
| Sprout（最も古い） | 初期のzk-SNARK | はい | 元の儀礼 |
| Sapling | Groth16 | はい（多当事者式「Powers of Tau」+ Sapling儀礼） | BLS12-381（第2回記事） |
| Orchard（現在） | Halo 2 | 信頼設定なし | Pallas / Vesta（第2回記事） |
SproutからSaplingへ、そしてOrchardへの進化は主に証明が小さく、速くなり、信頼設定を排除するという話です。Halo 2を使用しているOrchardは儀礼を一切必要とせず、再帰（他の証明を検証する証明）をサポートするために設計されています。そのため、Orchardは第2回記事のPallas/Vestaの曲線のサイクルを使用しています: 各曲線は他方の曲線上で書かれた証明を検証するように調整されています。
これは第0回記事からの最大のループを閉じます。「カーテンの裏側」の魔法とはzk-SNARKです: それはあなたの取引がすべてのルールをエンコードした算術回路に満たされていることを証明しながら、**ただ1つのビット「有効」**以外は何も明らかにしません。
零知識証明は深く専門的な分野であり、我々は意図的に直感レベルに留めました。妥当性における正確な確率の境界や算術回路（R1CS、PLONKishなど）の正確な形式、多項式とコミットメントが回路を短い証明に変換する方法、Groth16およびHalo 2の実際の内部構造については定義しませんでした。洞窟は対話的証明です; 実用システムは非対話的でずっと複雑です。これらすべてが変わることはありません: 回路が秘密の証明者によって満たされていることを完全に、妥当的に、何も明らかにせずに証明するというコアです。機械的な仕組みは独自のシリーズになります。
| 項目 | 平易な意味 |
|---|---|
| Zero-knowledge proof | 他の情報を一切明らかにせずに誰かに文が真であることを説得する |
| Prover / Verifier | 証明を作成する人 / 証明をチェックする人 |
| Completeness | 真の文は常に受け入れられる（誠実な証明者から） |
| Soundness | 偽の文は拒否される（不正行為者はたまたま成功する以外は勝てない） |
| Witness | 文が真になる秘密の入力 |
| Arithmetic circuit | 有限体上の加算と乗算として再構成された文 |
| Non-interactive (Fiat-Shamir) | ライブなやり取りを必要としない一発勝負の証明 |
| Succinct | 文のサイズに関係なく、証明は非常に小さく迅速に検証可能 |
| zk-SNARK | 零知識 Succinct Non-interactive ARgument of Knowledge |
| Trusted setup / toxic waste | 一度限りのパラメータ生成で残った秘密を破棄しなければならないもの |
証明が何も明らかにしないなら、チェックすることには意味がないのか？ 数学は本当に有効な証明者だけが通過する証明を作成できるように配置されているからです。チェックを通すことはそれ自体が証拠であり、開示は必要ありません。
誰かが証明を偽造できるのか？ 妥当性によりこれは不可能です。唯一の例外は信頼設定の毒廃棄物を保持しているSNARKです; そのために儀礼でそれを破棄することが重要です。
壊れた信頼設定は私のプライベートデータを漏らすのか？ いいえ。それは攻撃者が新しいお金を作成できるようにするだけで、金額、アドレス、ノートを明らかにすることはできません。プライバシーと妥当性は別々の保証です。
Zcashが証明システムを変更したのはなぜか？ より小さく、速い証明を得るためであり、Halo 2により信頼設定を完全に排除し、再帰を可能にするためです。
洞窟では、検証者が証明者がすでに中に入っている後に出口の側を選択することがなぜ必須なのか？（下記に答えがあります。）
もし検証者が最初に側を発表したなら、言葉を知らない嘘つきはその側から入り始め、戻って出ればいいだけです。扉を使う必要がないので、証明者を選択する前に選ぶことはできません。証明者が通路を選んだ後に検証者が選ぶことで、嘘つきはたまたま成功する（50/50）ことになり、それが繰り返しのラウンドが説得力を持つ理由です。この「まずコミットしてから挑戦される」順序はFiat-Shamirにより証明者がすでにコミットした証明のハッシュから挑戦を導出することで保持されます。
第6回記事 . シールドされたプロトコル、端から端まで: 終章。すべてのピース、ノート、コミットメント、ノートコミットメントツリー、nullifier、価値バランス、そして零知識証明を取り出し、完全なZcashシールド取引を構築し、第0回記事で開いたすべてのループを閉じます。
ZecHub向けの Zcash from First Principles シリーズの一部。CC BY-SA 4.0ライセンス。