zk-SNARK まとめ
tanaka.icon 田中 芳治 2019/4/6
(参加者のみなさま,ありがとうございました.色々理解が深まりました.)
Papers
B. Parno, J. Howell, C. Gentry, and M. Raykova, "Pinocchio: nearly practical verifiable computation"
Microsoft と IBMの研究者が出した文献
Pinocchioと呼ばれるプロトコル.クライアントが大規模な計算をクラウドなどの外部に委託する際に,計算結果が正しいかをチェックする.
zk-SNARKの原型の理論が書かれている
E. Ben-Sasson, A. Chiesa, E. Tromer, and M. Virza, "Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture"
zk-SNARKの実装を含めた詳細が書かれている
元々は2014年に発表されているが,その後,更新されている
2019年2月5日版が現時点での最新のようだ
プロトコルについて知りたければ,appendixのBに書かれている表を参考にしてください.
Ariel Gabizon, "On the security of the BCTV Pinocchio zk-SNARK variant"
上の2014年の実装について,脆弱性があるようだと指摘している
筆者曰く,"This work was done while the author was working at the Zcash Company."
Pinocchioプロトコルの概要
keyGenerator(G)とWorker(W)とVerifier(V)の3者がいる.
Gは,ある計算Cを行いたいが,自分で行わず,Pに依頼する
Wは計算を実行するが,その計算の信頼性が低い.(計算をしていない,あるいは,計算を間違えているかも)
Gは,信頼できるVに,Wの計算が正しいかチェックしてもらう.ただし,計算Cについては教えない.
zk-SNARKではWorker(W)がProver(P)となり,Pが計算Cを知っていることを証明する.
【田中の疑問】Gは計算Cを知らなければならないのだが,問題ないだろうか.これはゼロ知識証明の枠組みからは外れているような気がする.
zk-SNARKの概要
keyGeneratorの役割
Arithmetic Circuit Cから,proverKey(pk)とverifierKey(vk)を生成し,それぞれPとVに送信する
Proverの役割
pkとCは知っているとして,さらに計算Cへの入力 xとwitness(計算の途中経過のようなもの)も知っている.
上記を元にして,proofと呼ばれる値の組を作成し,verifier に送信する.
Verifierの役割
そのほかの4式は,多項式の計算が行われているかのチェックに使われる.
チェックの計算過程で,ペアリング関数がある.一般的にはペアリングは生成群の次数が非対称でも定義されることに注意.