ゼロ知識証明
zero-knowledge proof; ZKP
何かを証明したい人が、「自分はある事柄を知っている」という事実を、それを確かめたい人にその事実以外の知識を何も与えることなく証明する技術
近年、プライバシー強化技術として注目されている
以下の実用例がある
匿名認証
年齢や国籍などの個人情報を明かさずに、「成人であること」や「特定の国籍であること」を証明する
プライベート取引
取引の送金者、受取人、金額を隠したまま、その取引が正当なものであることを証明する
スケーラビリティ向上
大量の計算や取引をオフチェーン（ブロックチェーンの外）で実行し、その計算が「正しく行われたこと」の証明だけをブロックチェーンに記録する これにより、ブロックチェーン本体の負担を大幅に減らすことができる
処理フロー
https://scrapbox.io/files/697237d5bbc6e69c5a754c46.png
証明者（Prover）
証明したい計算プログラム（e.g. 「100個の取引をすべて処理しました」）を、数学的な「算術回路」という形式に変換する
この算術回路と秘密の情報をインプットとして、非常に小さな「証明」を生成する
検証者（Verifier）
証明者から受け取った「証明」と、公開されている情報（プログラムの内容など）を使って、証明が正しいかどうかを検証する
検証が成功すれば、証明者は「計算を正しく実行した」と認められる
この検証プロセスは、元の計算をすべて再実行するよりもはるかに高速
証明者は「私はこの秘密の条件を満たす多項式を知っています」ということを、検証者に証明しなくてはならない
しかし、多項式そのものを渡してしまってはいけないので、コミットメントスキーム（Commitment Scheme）が使われる 情報を 「固く封印して相手に渡す技術」
コミット
証明者は、秘密の多項式から非常に短い 「コミットメント」 というデータ（指紋のようなもの）を計算する
計算したコミットメントを検証者に渡す
このコミットメントから元の多項式を復元することはできない
オープン
検証者は、後から証明者に「その多項式の“ある一点”だけ教えて」と要求する
証明者がその点を教えると、検証者は受け取ったコミットメントと照合する
そのコミットメントが本当に正しい多項式から作られたものかを確認する
ZKの証明生成、特にPLONKやGroth16のようなスキームでは、主に以下の2つの暗号学的処理が計算のボトルネックとなる MSM (Multi-Scalar Multiplication)
多数の楕円曲線上の点を、それぞれのスカラー値で掛け合わせて一斉に足し合わせる計算
FFT (Fast Fourier Transform)
計算の表現を、評価が容易な多項式の形に変換するための計算
これらの処理は、無数の小さな独立した計算に分割できるため、並列処理との相性が良い
しかし、これを実際にCUDAやOpenMPのような技術で手動で実装するには、ハードウェアを熟知した専門家の多大な労力が必要
cf.