zk Friendlyなハッシュ関数
大雑把な説明
zk-SNARKは任意のプログラムをzk-circuitと呼ばれる回路に入力し、それを多項式に変換することで成り立っている。
gateに複数のinput wireが入り、output wireとして出力される。
この一連の関係をconstraint(制約)と呼ぶ。
最終的に複数のconstraintがcommitmentとして集約される。
https://scrapbox.io/files/63ccf56a34e3af001e918b4a.png
この一連の処理は証明者に多大な計算を強いることになる。
zk-Rollupの中身
https://scrapbox.io/files/63cd00c701a5d6001e7e5423.png
zk-RollupではSMT(Sparse Merkle Tree)にTxなどの情報を格納し、Rootを計算したものをL1のMerkle TreeにLeafとして入力する
SMTの中では、Rootまでの計算過程もゼロ知識証明によって保証される。
...つまりハッシュ計算が必要 = ハッシュ計算のゼロ知識証明が必要
計算コストを減らすには？
ゼロ知識証明向けのハッシュ関数によって計算コストを下げることが可能
SNARKに適したハッシュ関数を使用すると、回路制約の数と証明生成時間が大幅に短縮されるが、オンチェーンではより多くのgasが必要となる。
SHA256, Poseidon Hash, MiMCのそれぞれに定数を入れて実験してみた。
/?gist=8c112274f39985c7883a3c838c08a04b
いずれもcircomlibに実装されています。Kechakは用意されていませんでした。
code:SHA256
STDOUT:
template instances: 100
non-linear constraints: 28953
linear constraints: 0
public inputs: 0
public outputs: 0
private inputs: 0
private outputs: 0
wires: 28645
labels: 204268
Written successfully: ./main.r1cs
Written successfully: ./main.sym
Written successfully: ./main_js/main.wasm
Everything went okay, circom safe
Compiled in 4.61s
ARTIFACTS:
main.wasm (298.60KB)
main.js (7.67KB)
main.wtns (916.72KB)
main.r1cs (8034.68KB)
main.sym (13919.06KB)
DONE:
Finished in 4.90s
code:Poseidon
STDOUT:
template instances: 68
non-linear constraints: 261
linear constraints: 0
public inputs: 0
public outputs: 0
private inputs: 0
private outputs: 0
wires: 265
labels: 1381
Written successfully: ./main.r1cs
Written successfully: ./main.sym
Written successfully: ./main_js/main.wasm
Everything went okay, circom safe
Compiled in 1.05s
ARTIFACTS:
main.wasm (1077.21KB)
main.js (7.67KB)
main.wtns (8.56KB)
main.r1cs (121.03KB)
main.sym (49.99KB)
DONE:
Finished in 1.33s
code:MiMC
STDOUT:
template instances: 2
non-linear constraints: 12
linear constraints: 0
public inputs: 0
public outputs: 0
private inputs: 0
private outputs: 0
wires: 15
labels: 15
Written successfully: ./main.r1cs
Written successfully: ./main.sym
Written successfully: ./main_js/main.wasm
Everything went okay, circom safe
Compiled in 0.35s
ARTIFACTS:
main.wasm (42.37KB)
main.js (7.67KB)
main.wtns (0.56KB)
main.r1cs (2.25KB)
main.sym (0.34KB)
DONE:
Finished in 0.61s
容量
constraintsの数が少ないほど優位。
mimc>poseidon>sha256
証明スピード
ユースケースやzkスキーム(CircomではGroth16, Plonkをサポートしている)によって数値に乖離がでる。
mimc>poseidon>sha256
証明サイズ
constraintsの数に比例して大きくなる。
mimc>poseidon>sha256
厳密にはMiMCはハッシュ関数ではなく、Poseidonが広く使われている。
https://scrapbox.io/files/63ccf9e6f515aa001e0beb9f.png
まとめ
ゼロ知識証明の世界ではハッシュ関数の最適化が求められる。
どんな回路を設計するかによって、容量、証明速度、証明サイズ、検証用コントラクトを検討・比較することになる。
デファクトスタンダードなのはPoseidon Hash