search

arkworks-rs / crypto-primitives

Interfaces and implementations of cryptographic primitives, along with R1CS constraints for them
https://www.arkworks.rs
Apache License 2.0
168 stars 80 forks source link

Rescue for Marlin #89

Open weikengchen opened 3 years ago

weikengchen commented 3 years ago

It might be worthwhile for us to consider Rescue, in addition to Poseidon.

The main reason is as follows:

When trying to find optimized parameters for Poseidon, the optimal point is alpha = 257 in one of the experiments. It is slightly too large.

Based on the analysis in Rescue paper, it might suggest that Rescue is a better choice than Poseidon for Marlin. More numerical analyses might be needed.

Apart from efficiency issues, it might be good to have both the implementations of Poseidon and Rescue, since they have similarities and differences, based on two different design strategies, and thus might be a good foundation for future hash functions.

weikengchen commented 3 years ago

Updated regarding the optimal alpha for Poseidon when counting constraint system weight---it seems that if one uses a circular MDS matrix (as suggested by Markus Schofnegger) would make alpha = 5 often the better choices for constraint system weight (previously alpha=257 may be suggested)

zhenfeizhang commented 2 years ago

There is a rescue implementation in jellyfish: https://github.com/EspressoSystems/jellyfish/tree/main/rescue We can use alpha = 5 for BN254 and BLS12-381; alpha = 11 for BLS12-377

weikengchen commented 2 years ago

Talking about which, @zhenfeizhang can you discuss with your team regarding full-state PRF?

zhenfeizhang commented 2 years ago

Is the idea to upstream the code to ark-crypto-primitives/PRF? I.e., as an alternative to Blake2s? I think we can do it for the clear implementation for sure, but not sure anyone of us has the cycle to write the R1CS.

weikengchen commented 2 years ago

The idea is that I may port the parameter generation. But I will avoid full-state PRF for some reasons.