Rescue and Poseidon

Overview

This repo contains implementations of arithmetization oriented hash functions(Rescue, Poseidon, Rescue Prime) that constructed by a sponge construction over prime field for both out-of circuits and in-circuit usages. Each algebraic hash function uses same sponge construction with different round function or permutation function. Gadgets are optimal in the constraint systems while also supporting different scalar fields which supported by bellman.

Usage

Add dependency

rescue_poseidon = 0.1

    use franklin_crypto::bellman::bn256::Fr;
    use franklin_crypto::bellman::Field;
    use rescue_poseidon::rescue_hash;

    const L: usize = 2;
    let input = [Fr::one(); L]; // dummy input

    // fixed length rescue hash
    let result = rescue_hash::<Bn256, L>(&input);
    assert_eq!(result.len(), 2);

More examples can be found in examples folder.

Testing

cargo test -- --nocapture

Benchmarks & Constraint System Costs

cargo bench -- --nocapture

CPU: 3,1 GHz Intel Core i5

hashes	1x permutation runtime (μs)	1x permutation gates	number of rounds
Poseidon	13	166	8f + 33p
Rescue	680	266	44f
Rescue Prime	300	104	9f

References

• [1] Cryprographic sponge functions
• [2] The sponge and duplex constructions
• [3] STARK Friendly Hash – Survey and Recommendation
• [4] MARVELlous: a STARK-Friendly Family of Cryptographic Primitives
• [5] POSEIDON: A New Hash Function for Zero-Knowledge Proof Systems
• [6] Rescue-Prime: a Standard Specification (SoK)