なぜSHA-256とZKPは相性が悪く、Poseidonハッシュと相性が良いのか？
最初に
PSEのサマープログラムでメンターの方から教えていただいたことをまとめています。Poseidonハッシュを完全に理解しているわけではないので、間違いがあったら教えてください！
Poseidonハッシュの簡単なまとめ
Poseidonハッシュ関数はZK-SNARKなどゼロ知識証明に最適化されたハッシュ関数であり、circitを書くときに使われる。
ZKPの開発環境
非対話型の証明を生成し、検証する場合、Circomという言語を使って証明の生成と検証ができるコードを作ることができます。
具体的には、Circomで足し算と掛け算の算術回路を定義することで数学的に成り立つゼロ知識証明を作ります。
Poseidonハッシュが、Circomにフレンドリーな理由
SHA-256もPoseidon関数もどちらもハッシュ関数です。ですが、Poseidonハッシュの方がZKフレンドリー(計算効率がZKPにおいては優れている)と言われます。その理由を先に述べてしまうと、Poseidonハッシュを使うと、回路数やゲート数が少なくなる(足し算と掛け算の数が少なくなる)ためです。
その理由を以下に書きます。
Circomは有限体上での足し算と掛け算を行う
先ほどCircomでは足し算と掛け算を行うと書きました。ですが、注意点があります。それは普通の足し算・掛け算ではないということです。
Circomでは有限体上の足し算と掛け算を実行します。有限体上とは、ある素数pを用意して、{0,1,...p-1}というp個からなる四則演算が成立する整数の集合のことです。そして足し算または掛け算の結果をこのpで割った余りを求め、それを答えとします。(mod p)
例えばCircom上で2と5を掛け算するとpが7だとすると、計算結果は以下のようになります。
2 * 5 mod 7の答えは10を7で割った余りなので、3が答えになります。
SHA-256はXORやAND計算などでbit演算をしている
SHA-256は計算をbit演算で行いますが、Circomでbit演算を行う場合はCircomの算術回路用に調整してあげる必要があります。
bit演算に関しての説明は以下の記事に綺麗にまとまっています。
ここで、SHA-256でのA * BをCircom上で考えてみます。例えばAとBがどちらも32ビットの整数であるとすると、それぞれの数値を32ビットに戻してからCircom上で各1bitごとに変数を割り当てます。その上でAND計算をしてあげるので、順番にAの0ビット目とBの0ビット目を計算するのを32ビット目まで行う必要があり、32回の計算を実行します。
Poseidonハッシュの計算
一方Poseidonハッシュでは、有限体上の足し算・掛け算でも安全な計算が行えるようになっています。また、Circomでは有限体上の計算が標準で計算されます。つまり先ほどのSHA256のように一度ビット演算に戻して各bitごとに計算をするといったことをCircom上で行わなくていいわけです。
そのため、計算に無駄がなく回路の規模が小さくなるPoseidonハッシュ関数はZKPフレンドリーと言われています。
補足)ルックアップテーブル
先ほど32バイトの整数だと32回の計算が必要だと伝えました。ですが、この数値を足し算したらこの値になるといった表を用意しておけば計算は必要なくなり、そのテーブルに書かれている答えを使えば良くなります。
これはルックアップテーブルと呼ばれ、ルックアップテーブルを使うことでSHA256を使った計算を効率的に行えるように工夫されています。
また、なぜSHA256を使って計算にこだわるかというと現実世界ではPoseidonハッシュではなくSHA256が使われることが多く、SHA256とZKPを組み合わせて計算したいニーズがあるためです。
最後に
今回SHA256がZKフレンドリーでない(計算が遅くなってしまう)要因としては、ZKPだからこそ起こると言えます。また学びがあればこちらの記事を修正していきます。
Discussion