はじめに

NFTのブームによって、付随する様々なデータなど、ブロックチェーン上に格納されるようになりました。
真贋情報、配布場所の座標、アセットに紐づくデータなどなど、膨大なデータを検証するユースケースにおいて、あらためて、ZK-SNARK / zkRollup の利用について注目されています。

ゼロ知識証明

ゼロ知識証明とは、証明者がある情報がただしいことを、検証者に対して、それが正しいこと以外の情報を明らかにせずに証明できる手法のことです。
FPSゲームなどにおいて、スナイパーが自身の座標を明らかにせず、弾の当たり判定を行いたいようなロジックには非常に有効に働きます。FPSにおける初期位置や弾道の通過するデータは多項式（方程式）で表現されることによって、多項式コミットメントを利用可能です。(コミットメントは何かが起こったことの数学的証明)。この証明（ハッシュの一種）を使用すると、自分の座標などの情報を明らかにすることなく、弾が敵に当たったかどうかだけの確認を行うことができます。

How to explain zero-knowledge protocols to your children
https://pages.cs.wisc.edu/~mkowalcz/628.pdf?ref=morioh.com&utm_source=morioh.com

ZK-SNARK

ZK-SNARK（Zero-Knowledge Succinct Non-Interactive Argument of Knowledge）は、ゼロ知識証明を構築するソリューションで、ゼロ知識証明がもつ3つの性質に加えて、SNARKの4つの性質を持っています。

Succinct（簡潔）
証明のサイズが小さい
Non-interactive（非対話型）
証明者と検証者の間で繰り返し対話をしなくて良い
ARgument
証明者の計算能力には限りがある
Knowledge
証明者は、知識なしでは証明を生成することは不可能

SNARKのなかで、主に、Succinct（簡潔）によって、検証プロセスのコストを削減できるため、zk-Rollupは複数のトランザクションをまとめ、そこにあるトランザクションをすべて検証することなく、veryfyすることができ、Layer1とLayer2を繋ぐスマートコントラクト技術としても活用されています。Ethereum2.0や、様々なSwapサービスでzk-Rollupは選択されている現状があります。

name	Rollup
Arbitrum	Optimistic Rollup
dYdX	ZK Rollup
Metis Andromeda	Optimistic Rollup
Optimism	Optimistic Rollup
Loopring	ZK Rollup
ZKSwapV2	ZK Rollup

barryWhiteHat / Jordi about RollUp
https://github.com/barryWhiteHat/roll_up/issues

手順

チュートリアルを参考にすすめていきます。
(参考)https://github.com/iden3/snarkjs

1.インストール

$ npm install -g circom@latest
$ npm install -g snarkjs@latest

# mkdir zkrollup_demo
# cd zkrollup_demo

2.サーキットの作成

$ touch basic_multiplier.cicom

記号	詳細
signal	シグナルを宣言する
private	private inputであることを示す。証明をつくったときに、排除する。
<==	シグナルを接続すると一緒に制約を作る
<--	信号に値を代入するが制約はない
===	制約を定義する

circuit.cicom

template Multiplier() {
 signal private input a;
 signal private input b;
 signal output c;

 c <== a*b;
}
component main = Multiplier();

//コンパイル
//jsonやsolidityに変換できる
$ circom circuit.cicom -o circuit.json
$ circom circuit.circom --r1cs --wasm --sym -v

3.MPCセレモニー

zk-SNARKのセットアップには、証明や検証につかう鍵を安全に作る必要があるため、
Multi party computation(MPC)を用いて鍵の作成を行う。
MPCに参加したすべての人が共謀しないかぎり、証明の偽造ができない。

MPCセレモニー(第一段階)

//開始
$ snarkjs powersoftau new bn128 12 POT12_0.ptau -v

//1回目
$ snarkjs powersoftau contribute POT12_0.ptau POT12_1.ptau --name="aaa" -v

//2回目
$ snarkjs powersoftau contribute POT12_1.ptau POT12_2.ptau --name="aaa" -v

//3回目
$ snarkjs powersoftau contribute POT12_2.ptau POT12_3.ptau --name="aaa" -v

//確認
$ snarkjs powersoftau verify POT12_3.ptau
>[INFO]  snarkJS: Powers of Tau Ok!

ランダムビーコンの適用

一定時間が経過すると利用できないランダム性をもつ情報源。たとえば、Loopringというプロジェクトでは、ビットコインの602168番目のブロックのハッシュ値をつかうと宣言し利用した。

$ snarkjs powersoftau beacon POT12_3.ptau POT12_beacon.ptau 53166ee0 10 -n="beacon"

$ snarkjs powersoftau prepare phase2 POT12_beacon.ptau POT12_final.ptau -v

//確認
$ snarkjs powersoftau verify pot12_final.ptau

MPCセレモニー(第二段階)

特定のサーキットに対応した証明用の鍵(proving key)と検証用の鍵(varification key)を作成する

$ snarkjs zkey new circuit.r1cs POT12_final.ptau circuit_1.zkey

$ snarkjs zkey contribute circuit_1.zkey  circuit_2.zkey --name="aaa" -v

$ snarkjs zkey contribute circuit_2.zkey  circuit_3.zkey --name="aaa" -v

$ snarkjs zkey verify circuit.r1cs POT12_final.ptau circuit_3.zkey

ランダムビーコンの適用

$ snarkjs zkey beacon circuit_3.zkey circuit_final.zkey 53166ee0 10 -n="final beacon"

//確認
$ snarkjs zkey verify circuit.r1cs pot12_final.ptau circuit_final.zkey

//verification_key
$ snarkjs zkey export verificationkey circuit_final.zkey verification_key.json

//Generate the proof
$ snarkjs groth16 prove circuit_final.zkey witness.wtns proof.json public.json

//verify
$ snarkjs groth16 verify verification_key.json public.json proof.json

Ethereumのcontractとの組み合わせる

EthereumとZkSnarksが組み合わせることでセキュリティを向上させることができます。
たとえば、よくあるwalletの残高を表現するmappingなどについて、hashで管理することで、
送信金額と残高を秘匿化します。

mapping(address => uint256) balance;

->

mapping(address => bytes32) blanaceHashes;

送信残高が送信される値よりも大きいことをハッシュ化し、このハッシュが正しいことを参加者の中で検証することが重要です。

balances[fromAddress] >= value

送信側がハッシュが一致することを確認

function senderFunction(x, w) {
  return (
    w.senderBalanceBefore > w.value &&
    sha256(w.value) == x.hashValue &&
    sha256(w.senderBalanceBefore) == x.hashSenderBalanceBefore &&
    sha256(w.senderBalanceBefore - w.value) == x.hashSenderBalanceAfter
  )
}

受信側がハッシュが一致することを確認

function receiverFunction(x, w) {
  return (
    sha256(w.value) == x.hashValue &&
    sha256(w.receiverBalanceBefore) == x.hashReceiverBalanceBefore &&
    sha256(w.receiverBalanceBefore + w.value) == x.hashReceiverBalanceAfter
  )
}

zk-SNARKの証明キーと検証キーを生成。コントラクトの一連の流れは下記のようになる。

function transfer(address _to, bytes32 hashValue, bytes32 hashSenderBalanceAfter, bytes32 hashReceiverBalanceAfter, bytes zkProofSender, bytes zkProofReceiver) {
  bytes32 hashSenderBalanceBefore = balanceHashes[msg.sender];
  bytes32 hashReceiverBalanceBefore = balanceHashes[_to];
  
  bool senderProofIsCorrect = zksnarkverify(confTxSenderVk, [hashSenderBalanceBefore, hashSenderBalanceAfter, hashValue], zkProofSender);

bool receiverProofIsCorrect = zksnarkverify(confTxReceiverVk, [hashReceiverBalanceBefore, hashReceiverBalanceAfter, hashValue], zkProofReceiver);

  if(senderProofIsCorrect && receiverProofIsCorrect) {
    balanceHashes[msg.sender] = hashSenderBalanceAfter;
    balanceHashes[_to] = hashReceiverBalanceAfter;
  }
}

文字を利用したサーキットを作る

文字を利用する場合は、Unicodeを用いてあらかじめ変換しておく必要があります。
たとえば、shibuyaという文字列について、検証するためには、

shibuya -> Unicode変換

s = 115
h = 104
i = 105
b = 98
u = 117
y = 121
a = 97

結果つなげて、input値は
1151041059811712197
と比較します。

参考

Zk Rollup Tutorial
https://keen-noyce-c29dfa.netlify.app/

ポーカー
https://medium.com/coinmonks/zk-poker-a-simple-zk-snark-circuit-8ec8d0c5ee52
(source)https://github.com/glamperd/snark-example/

戦艦ゲーム
https://kunalm.xyz/posts/zksnark-battleship.html
(source)https://github.com/kunalmodi/battlesnark

コードブレーカー
https://github.com/weijiekoh/zkmm

キノピオプロトコル
https://eprint.iacr.org/2013/279.pdf