ゼロ知識証明を30行で実装——グラフ理論で暗号通貨を回避
A quick look at zero-knowledge proofs
暗号通貨とは無関係なゼロ知識証明の実装を、グラフの3色塗り分け問題を例に解説。著者はChris氏の提案で、Goldreichらによる論文のプロトコルを参考に、Pythonで30行程度のコードを書き、ネットワークデモも公開。ハッシュとノンスを使った「鍵付きボックス」で、証明者が解を明かさずに検証者を納得させる仕組みを、各ステップのコード付きで紹介する。
証明者が検証者に解を一切明かさずに、その解が正しいことを納得させることができる——それがゼロ知識証明のアイデアだ。
HNでの議論
36- _alphageek
素晴らしい記事です。他の人にZKPを説明するために保存しておきます。
小さな修正が1つあります。
random.randrange(100)は300通りのコミットメント（100個のナンスに対して3色）を生成します。いくつか開示されたエッジを見た後、検証者はパレットを把握し、300通りの組み合わせを総当たりで試して、実質的にすべてのコミットメントを開くことができます。
これは128ビットのランダム性を使えば緩和できます。例えば、secrets.token_bytes(16)です。
また、hashの代わりにsha256を使うべきです。Pythonのhashは適切な衝突耐性がないため、安全とは見なされません。
- namjh
良い記事ですね。読者に印象を与える追加のトピックを挙げたいと思います：
Fiat-Shamir変換です。証明者と検証者の間の対話プロセスは、ハッシュ関数（ランダムオラクルとしてモデル化）を使うことで非対話型に変換できます。これにより、証明プロセス全体を1回のやり取りで完了できるため、「ユーザー体験」が向上します。そのアイデアは、問題自体をハッシュ関数に入力し、元々検証者が生成していたランダム性をハッシュ関数に生成させるというものです。
- jackb4040
他のコメント投稿者の中にはZKPやプログラム可能な暗号技術は役に立たないと言う人もいますが、私はそうは思いません。しかし、その上に構築する人々の話し方から、パフォーマンスが非常に悪い（専用サーバーを除く）ため、それが修正されるまで基本的に理論上の技術であると知ったとき、確かに驚いたのを覚えています。これは最近変わったのでしょうか？修辞的な質問ではありません。
- mw888
より弱い技術である簡潔な非対話型知識の証明（SNARK）の有用性も考えてみてください。これらはゼロ知識にすることもできますが、たとえそうでなくても、数百人分のマルチシグのような高コストな検証を安価にすることができます。
- Cider9986
ZcashはZKPに大きな貢献をしましたが、彼らの技術がなければどうなっていたでしょうか？
彼らの進歩は暗号通貨以外に他の影響もありましたか？