Reinforced Concrete Implementations
Better, more secure, than Poseidon
About
The problem it solves ## Introduction Since [Reinforced concrete](https://eprint.iacr.org/2021/1038) claims to be faster and more secure than Poseidon, any zk application making use of Poseidon can benefit from switching over to RC. ## Implementations We provide implementations in Circom (groth16) as well as o1js (Pallas curve). The API has been designed in such a way that it can be "drop-in" replaced with existing usages of Poseidon. Compared to [Poseidon](https://github.com/iden3/circomlib/blob/master/circuits/poseidon.circom), this hash function is designed with significantly fewer constraints, enhancing its security against statistical and algebraic attacks. ## Our optimization Alterations have been made to the precomputed values for the divisors in the `decompose` construct ensuring compatibility with the reference implementation, which splits `254 bit` word into `64 bit` words. However, these modifications are unnecessary in an execution environment where the word size is 254 bits and above (evm, etc). Therefore, we can do fewer divisions while achieving the same result.
How it's made
Challenges we ran into While working on RC in circom (bn254 field), we noticed that the state permutation after the `bars` layer was correct for the first two elements, but failed in the last element. Upon much further investigation, we discovered that a left shift operation within the `decompose` construct was causing the field element to overflow into an undefined state. This operation did not result in UB in the evm implementation nor the reference implementation since they have a larger word size (256 bits, or in the reference implementation, 4x64 bits). To overcome this overflow, we modified the precomputed values for the divisors used in the `decompose` construct, resulting in reduced number of operations, as well.