The problem Reinforced Concrete Implementations solves

Introduction

Since Reinforced concrete 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, 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.

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.