Is there a better way to arithmetize GMiMC?

[dlubarov]

We have a GMiMCGate which evaluates a full GMiMC permutation. The current code uses a wire for each S-box, so constraints have degree 3. We could go to a higher degree, which would increase costs in some ways, but would probably be worth it if it lets us decrease the number of wires substantially.

With a permutation like MiMC, we could just have a wire for every other S-box. Instead of degree-3 constraints like wire_2 = wire_1^3 + constant_2, we'd have degree-9 constraints like wire_3 = (wire_1^3 + constant_2)^3 + constant_3 (just inlining wire_2).

With a permutation like Rescue, reducing the wire count is similarly easy. We could have wires for every other layer, resulting in constraints of degree alpha^2.

GMiMC uses a Feistel network, so its dependency graph has a different structure. I don't see an obvious way to reduce the wire count, but I might just not be seeing it; maybe a fresh pair of eyes would help.

[dlubarov]

Probably not worth investigating for now since we're leaning toward switching to Poseidon.