Explore alternatives for the Poseidon hash function

[hecmas]

Monolith

I just leave it here for reference, but Bobbin was right claiming that the Monolith hash function looks like the best mid-term replacement for the Poseidon hash function due the two following characteristics:

1. The performance of pure hashing is close to the one for the SHA-2/SHA-3 family (not taking into account the precomputation of lookup tables).
2. The arithmetization cost is way way better than the rest (due to the abuse of lookups).
3. The security is "less" heuristic than the one for Poseidon1.

Finding a hash function that is the "best" in the previous three senses is meant to be the holy grail in the zk-hashing space.

Others

The Polygon Miden team conducted a series of comparisons by performing computational benchmarks on a variety of hash functions. This comprehensive evaluation included both traditional hash functions (like BLAKE3 and SHA3) and algebraic hash functions. The results of these benchmarks are available here.

Scenario 1: 2-to-1 hashing h(a,b)

Function	BLAKE3	SHA3	Poseidon	Rp64_256	RPO_256
Apple M1 Pro	80 ns	245 ns	1.5 us	9.1 us	5.4 us
Apple M2	76 ns	233 ns	1.3 us	7.9 us	5.0 us
Amazon Graviton 3	108 ns				5.3 us
AMD Ryzen 9 5950X	64 ns	273 ns	1.2 us	9.1 us	5.5 us
Intel Core i5-8279U	80 ns				8.7 us
Intel Xeon 8375C	67 ns				8.2 us

Scenario 2: Sequential hashing of 100 elements h([a_0,...,a_99])

Function	BLAKE3	SHA3	Poseidon	Rp64_256	RPO_256
Apple M1 Pro	1.0 us	1.5 us	19.4 us	118 us	70 us
Apple M2	1.0 us	1.5 us	17.4 us	103 us	65 us
Amazon Graviton 3	1.4 us				69 us
AMD Ryzen 9 5950X	0.8 us	1.7 us	15.7 us	120 us	72 us
Intel Core i5-8279U	1.0 us				116 us
Intel Xeon 8375C	0.8 ns				110 us