Poseidon Hash
zk friendlyなhash(≒有限体の演算のみで計算できるhash)の一つ。Sponge型のhash。
Sponge hash function
Sponge hash functionとは、図のように内部状態の一部(図の上側のワイヤ)に入力メッセージ$ m_iを加えながら$ \mathcal{P}を繰り返し行い、入力メッセージを全て吸収したのち、所望の個数の出力ハッシュ$ h_iを得るまで$ \mathcal{P}を繰り返しながら内部状態の一部を出力するハッシュ関数である。つまり (入力の個数) + (出力の個数) - 1回だけpermutation $ \mathcal{P}を繰り返す。
https://scrapbox.io/files/6489786fcef5bc001b9f5582.png
$ \mathcal{P}を一度定義してしまえば、任意の個数の入力/出力に対応できることがSponge hash functionの強み。
sha3/keccakもsponge型のhash関数
Permutation
Poseidonは内部状態をベクトルとして保持する。poseidonのpermutationは、
定数ベクトルの足し算; ARC(AddRoundConstants)
要素のn乗; S-box
行列の掛け算; M (MixLayer)
の3つの操作の組み合わせで記述される。
full round
full roundとは、1回のARC, 各要素への1回のS-box, 1回のMによって構成されるラウンドで、permutationの最初と最後にそれぞれ$ R_f回実行される。
partial round
partial roundとは、1回のARC, 第1要素のみへの1回のS-box, 1回のMによって構成されるラウンドで、permutationの中頃に$ R_P回実行される。
https://scrapbox.io/files/64897c526f1156001b7886e6.png
partial roundは一要素のみに非線形過程のS-boxを適応するため、full roundより小さな計算コストで実行することができる。また、線形過程と非線形過程を前半と後半に分離することによる計算高速化テクニックも知られている(原論文の付録B)。
安全な$ R_fと$ R_Pの回数とS-boxのnの値は、有限体の大きさと内部状態ベクトルの要素数によって決まる。