Reinforced Concrete Implementations
Better, more secure, than Poseidon
Created on 12th November 2023
•
Reinforced Concrete Implementations
Better, more secure, than Poseidon
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 splits254 bit
word into64 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 thedecompose
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 thedecompose
construct, resulting in reduced number of operations, as well.Tracks Applied (4)
Polygon - Monolith Verifier
Polygon
O(1)Labs - Crypto Primitive
O(1)Labs
O(1)Labs - Open Track
O(1)Labs
Chewing Glass
Technologies used