Hi maintainers (cc @ivokub @Tabaie) — I'd like to contribute an Anemoi in-circuit hash gadget to std/hash, and want to confirm scope and interest before writing it so I don't build something out of scope.
What: an in-circuit Anemoi permutation plus the Jive 2-to-1 compression mode (and a sponge FieldHasher), mirroring the structure of std/hash/poseidon2 + std/permutation/poseidon2. Since no out-of-circuit Anemoi exists in gnark-crypto, I'd also add the out-of-circuit reference under ecc/<curve>/fr/anemoi first and have the gadget mirror it, exactly as Poseidon2 did.
Why: std/hash has MiMC, SHA2, SHA3, RIPEMD-160 and Poseidon2, but no Anemoi. Anemoi is an AO hash designed so the S-box (the closed Flystel) is verified by a low-degree relation, so in-circuit it needs no inversion hint (you witness the Flystel output and check two degree-α equations). Its Jive mode is purpose-built for Merkle trees (2-to-1 compression with no capacity waste). Reference: New Design Techniques for Efficient Arithmetization-Oriented Hash Functions: Anemoi and Jive, ePrint 2022/840 (CRYPTO 2023): https://eprint.iacr.org/2022/840
Target: BN254 first (Linea-relevant, α=5, 21 rounds at state width 2 for 128-bit), generalizable to BLS12-381/377.
Rough cost: the closed-Flystel verification is ~5 R1CS multiplication constraints per S-box, so ≈ 105 R1CS for the width-2 permutation / Jive 2-to-1 compression (to be confirmed by compiling), versus gnark's Poseidon2 at ~241 R1CS for the t=3 compression. I'll report exact R1CS + PLONKish counts vs Poseidon2 in the PR.
Security disclosure: I want to be upfront — the post-2024 algebraic cryptanalysis line (Algebraic FreeLunch, CRYPTO 2024, and follow-ups) reduced Anemoi's claimed margin; the 128-bit instantiations remain secure but with a thinner margin than originally advertised. I'd ship the conservative round count and document this. Happy to hear if this changes your appetite.
Questions:
- Would you accept Anemoi into
std/hash (+ the out-of-circuit primitive in gnark-crypto), or do you prefer to keep new AO hashes out of the stdlib?
- Plain gadget first with a GKR variant as a follow-on, or both together?
- Any preference on curve coverage, and on exposing Jive-compression vs a sponge (or both)?
I have gnark experience and have already written + cross-validated an out-of-circuit reference against the authors' anemoi-rust known-answer tests. I'll mirror the Poseidon2 PR structure (tests against the reference via the test engine, constraint benchmarks in the PR). Happy to adjust scope.
Hi maintainers (cc @ivokub @Tabaie) — I'd like to contribute an Anemoi in-circuit hash gadget to
std/hash, and want to confirm scope and interest before writing it so I don't build something out of scope.What: an in-circuit Anemoi permutation plus the Jive 2-to-1 compression mode (and a sponge
FieldHasher), mirroring the structure ofstd/hash/poseidon2+std/permutation/poseidon2. Since no out-of-circuit Anemoi exists ingnark-crypto, I'd also add the out-of-circuit reference underecc/<curve>/fr/anemoifirst and have the gadget mirror it, exactly as Poseidon2 did.Why:
std/hashhas MiMC, SHA2, SHA3, RIPEMD-160 and Poseidon2, but no Anemoi. Anemoi is an AO hash designed so the S-box (the closed Flystel) is verified by a low-degree relation, so in-circuit it needs no inversion hint (you witness the Flystel output and check two degree-α equations). Its Jive mode is purpose-built for Merkle trees (2-to-1 compression with no capacity waste). Reference: New Design Techniques for Efficient Arithmetization-Oriented Hash Functions: Anemoi and Jive, ePrint 2022/840 (CRYPTO 2023): https://eprint.iacr.org/2022/840Target: BN254 first (Linea-relevant, α=5, 21 rounds at state width 2 for 128-bit), generalizable to BLS12-381/377.
Rough cost: the closed-Flystel verification is ~5 R1CS multiplication constraints per S-box, so ≈ 105 R1CS for the width-2 permutation / Jive 2-to-1 compression (to be confirmed by compiling), versus gnark's Poseidon2 at ~241 R1CS for the t=3 compression. I'll report exact R1CS + PLONKish counts vs Poseidon2 in the PR.
Security disclosure: I want to be upfront — the post-2024 algebraic cryptanalysis line (Algebraic FreeLunch, CRYPTO 2024, and follow-ups) reduced Anemoi's claimed margin; the 128-bit instantiations remain secure but with a thinner margin than originally advertised. I'd ship the conservative round count and document this. Happy to hear if this changes your appetite.
Questions:
std/hash(+ the out-of-circuit primitive ingnark-crypto), or do you prefer to keep new AO hashes out of the stdlib?I have gnark experience and have already written + cross-validated an out-of-circuit reference against the authors'
anemoi-rustknown-answer tests. I'll mirror the Poseidon2 PR structure (tests against the reference via the test engine, constraint benchmarks in the PR). Happy to adjust scope.