Poseidon is a cheap hash function for ZK(and possibly MPC), to avoid using too many boolean functions like SHA256 and SHA3-keccak .
The main techniques: sponge hash + Hades strategy + Round function in Fp
Sponge hash: starting with full zero initial state(I), (add r-bit message every round then permutation) for all messages, then (output r-bit h_i) for a number rounds (such as 128/r) to get a 128-bit hash result. If the permutation is a randomly chosen one, the sponge function is indifferentiable from a random oracle for up to a number of calls (2^(c/2)).
Hades strategy: interleave partial rounds(only one sbox) and full ones, to reduce the use of expensive sbox(), while still maintaining protection against statistical attacks(possibly some in the future? why not use more partial rounds? how to quantize the ratio of partial/full?). But (t partial round ->one full round) has a similar cost, but severely decreased security(not surprising: you reduced overall full rounds).
Round function: AddRoundConstants+SubWords(sbox)+MixLayer(mul with a square t*t MDS matrix)
Sbox (operations in Fp, p~=2^n, ceil(log(p))=n), two ways:
- x^a- poseidon^\pi: sbox(x)=x^a, given gcd(a, p-1)=1, such as a=3 or a=5. x⁵ is suitable for BLS12–381 and BN254.
- x^-1-poseidon^\pi:sbox(x)=x^(-1), sbox(0)=0
MDS matrix exits, if 2t+1≤p
Implementation:
The fact that the non-linear layer is partial in RP rounds can be used to reduce the size of the round constants required in each partial round…..reducing the number of constant multiplications in each round with a partial S-box layer from t2 to 2t, which is particu- larly useful for large t and R_p….Sage performance improves by a factor of about 5.
Next: poseidon gate in Plonky2.