【保存版】ゼロ知識証明、しっくりきていますか？（ZK-SNARKや量子耐性まで理解しましょう。）
こんにちは、CryptoGamesの高橋です。
クリスペの会社です。
今回、CryptoButlersさんのNFTがリリースされるので、ゼロ知識証明やZK -SNARKについて説明していきたいと思います。
なお、参考にさせていただいた記事につきましては、末尾にリンクを貼らせていただきました。
では、はじめていきましょう。
１ そもそもゼロ知識証明とは？
１ー１ 定義
よく言われるのはこんな定義ですね。
自分が秘密の情報を知っていることを、その情報自体を明かさずに相手に証明する手法（e-wordsから）
まずは、これの言わんとしていることを分解してみましょう。
１ー２ 具体例で考えましょう。
例えば、私がある扉を開ける合言葉の「開けゴマ！」を知っていたとします。
これが私に取っての秘密の情報です。
王様もこの情報が欲しく、私に情報料と引き換えに教えてもらおうと思っています。
でも、私が本当に合言葉を知っているかを知りたいですね。
私も情報料をもらうまでは教えるわけにはいきません。
そのため
・自分が秘密の情報を知っている（私が合言葉を知っている）ことを、
・その情報自体（合言葉）を明かさずに相手（王様）に証明
する手法である、ゼロ知識証明が必要となってきます。
２ 「洞窟の問題」で実際に証明してみよう
では、いわゆる「洞窟の問題」を使って、実際にやってみましょう。
こちらはWikipediaにも載っている問題例です。
２ー１ 問題設定
下のように合言葉が必要な扉があります。
Pさんは合言葉を知っていて、Vさんは知りません。
Pさんは合言葉を教えずに、合言葉を知っていることを証明します。
なお、このように、P、Vがよく使われます
・Pさん ⇨ 証明する人（Prover）
・Vさん ⇨ 検証する人（Verifier）
２ー２ 準備をしよう
まずはPさんがVさんに知られずにA,Bのどちらかから入ります。
「ゼロ知識」証明なので、Vさんには全く情報を与えません。
その後、Vさんが出てきて欲しい出口を言います。
２ー３ 証明しよう
PさんはAと言われたので、合言葉を使ってAから出てきました。
Bと言われても、元の道を戻って出ればいいですね。
もし、Pさんが本当は合言葉を知らなければ、Aから出ることはできません。
この例では証明確率がたったの50％です。
でも、同じことを連続で20回行えば、確率は約0.0001％となります。
これで証明が完了しました。
３ ゼロ知識証明の種類は？
ゼロ知識証明には大きく
① ZK-SNARK
② ZK-STARK
の二つの方法があります。
このうち、ZK-SNARKは量子コンピュータに対して脆弱と言われます。
具体的な説明に前に、この量子コンピュータに対して理解しましょう。
４ ECDSA（楕円曲線署名）
ビットコインやイーサリアムなどではECDSAという暗号化方法がとられています。
ちょっと見ていきましょう。
計算式は上になりますが、イーサリアムでは、a=0,b=7の場合が使われています。
y^2 = X^3 + 7（乗は^で表します）
〜以下は私がもともとしていた勘違いです。〜
ここから
Xが１の時、y^2 = 1 + 7 = 8
Xが２の時、y^2 = 8 + 7 = 15
Xが３の時、y^2 = 27 + 7 = 34
・・・・・
のようにyが求まっていきます。
でも、逆の方向の
y^2が34になるようにxを求めよ。
は求めるのが非常に難しです。
そのため、xからyを求めるのは容易であるが、yからxを求めるのは難しい。
〜以下は私がもともとしていた勘違いです。ここまで〜
↑ 私のように、このように勘違いをされている方もいるかもしれません。
この辺りにつきましては、下の記事で丁寧に説明しておりますので、よかったらこちらも見てみてください。
５ ビットコインでのECDSA利用の流れ
では、ここでビットコインにおける秘密鍵や公開鍵の関係を見てみましょう。
なんだか難しそうですが、ポイントは少ないです。
ポイントは
・①秘密鍵 ⇨ ②公開鍵 ⇨ ③公開アドレス で作られる
・①秘密鍵 ⇨ ②公開鍵 でECDSAを使う
でしょうか。
ECDSAを使っているので、
・ ①秘密鍵 ⇨ ②公開鍵 は簡単でも、その逆の
・ ②公開鍵 ⇨ ①秘密鍵 は難しい
という性質があります。
６ 量子コンピュータのShorのアルゴリズムとは？
量子コンピュータが扱えるアルゴリズムの一つがShorのアルゴリズムです。
これは整数を因数分解することができます。
例えば、次のような計算式があったとします。
a × b = Z
aが20、bが33の時、Zは660と簡単に求まりますが、
逆方向のZが660になるような、a,bを求めるのは大変ですね。
今回は数が小さいのでなんとかできますが、数が大きくなればとても大変です。
このような逆方向の分解ができるのがShorのアルゴリズムです。
７ ECDSAと量子コンピュータの関係
こちら、私の理解に誤りがありましたので、削除いたしました。
別の記事で触れていこうと思います。
８ ZK-SNARKの仕組みを理解しよう
８ー１ 概要
ZK-SNARKは下のように大きく３つのアルゴリズムからなっています。（この図はhttps://zoom-blc.com/what-is-ethereum-zk-snarkから持ってきています。）
① Gアルゴリズム ⇨ 鍵を作る（Generate）
② Pアルゴリズム ⇨ 証明する（Prove）
③ Vアルゴリズム ⇨ 検証する（Verify）
８ー２ 鍵を作ろう！（Gアルゴリズム）
まずはGアルゴリズムを使って
①証明鍵
②承認鍵
を作りましょう。
CというプログラムとRという値を入れて鍵を作ります。
このRという値が大事な情報です！
これを秘匿することがポイントです。
８ー3 証明しよう！（Pアルゴリズム）
ここではPアルゴリズムを使って、「prf」を作ります。
Xが機密情報です。
Xと、Xをハッシュ化したhをPアルゴリズムに渡すと、prfができます。
できたらhとprfを検証する人に渡します。
機密情報のXを渡していないというのがポイントですね。
８ー４ 検証しよう！（Vアルゴリズム）
最後に検証を行いましょう。
・Gアルゴリズムで作られた承認鍵
・Pアルゴリズムで作られたprfと機密情報のハッシュ値のh
をVアルゴリズムに入れれば正誤（trueかfalse）が返ってきます。
この処理のみはスマートコントラクト内で実行され、結果に応じて処理が続いていきます。
９ ZK-SNARKの欠点は？
ZK-SNARKの欠点は鍵を作るGアルゴリズムにあります。
では、見ていきましょう。
９ー１ 鍵を作る人と証明する人がグルだったら？
もしこの２人がグルだったらどうでしょう？
今回、一番大事な情報は鍵を作るためのRという値でした。
この値を証明者に教えてしまえば、不正な「prf」を作ることができます。
これで正しくないものも承認させることができてしまいます。
９ー２ グルじゃないって言い切れる？
さて、ではこの２人、グルじゃないって言い切れるのでしょうか？
そもそも、Rは公開されていない秘密の情報でした。
ということは、そもそも証明する人がこのRを知っていたかがわかりません。
この辺りがTrusted Setup（信頼された設定）の問題です。
つまり、設定を行った際に不正は行われていないという信頼が前提にある仕組みです。
９ー３ 量子コンピュータ耐性について
仮に上の二つをクリアできたとしても、量子耐性の問題が残ります。
Gアルゴリズムによって、Rという値から①証明鍵と②承認鍵が作られました。
ZK-SNARKは証明鍵や承認鍵からはRが導かれないということが前提にあります。
そのため、量子コンピュータのShorのアルゴリズムによってRが導かれるようになれば、この前提は崩れてしまいますね。
今回は以上になります。
なお、この記事の作成にあたり、下の３つの記事を参考にいたしました。
これらもとてもわかりやすいので、ご興味があればぜひ。
サポートをしていただけたらすごく嬉しいです😄 いただけたサポートを励みに、これからもコツコツ頑張っていきます😊