Arrabbiata: Poseidon gate - use 12 different gadgets instead of one with many public inputs

[dannywillems]

The current design of the Poseidon gadget is to have a single set of polynomials for 5 rounds, and the round constants are given as "public inputs". This design does not make sense, and the round constants should simply be constants in the polynomial.
We have something like:

q_pos P_pos(X1, ..., X15, cst1, ..., cst1) = q_pos [(X3 + cst1)^5 ...]

By supposing we have 60 full rounds, I suggest to have the following design:

• We split the unique gadget in 12 gadgets, each having a different selector.
• Each gadget has its own set of 15 round constants encoded in the polynomials describing the gadget (15 because we have 5 rounds, and 3 elements in the permutation state).
• We add one gadget for absorbing inputs.
  We end up with 13 gadgets, and the following constraints:

q_pos_1 * P_pos1(X1, ..., X15) // compute rounds from 1 to 5
q_pos_2 * P_pos2(X1, ..., X15) // compute rounds from 6 to 10
...
q_pos_12 * P_pos12(X1, ..., X15) // compute rounds from 55 to 60
q_absorb * P_absorb(X1, ..., X15) // Computes X3 = X1 + X2, X6 = X4 + X5, simulating the absorbtion of two values (X5 and X2), that would be public inputs.

We would end up with the constraint:

q_pos1    * P_pos1(X1, ..., X15)   + \
q_pos2    * P_pos2(X1, ..., X15)   + \
... + \
q_pos12  * P_pos12(X1, ..., X15)   + \
q_absorb * P_absorb(X1, ..., X15)

The degree stays the same.

[dannywillems]

Another design would have been to have 15 "selectors" (like the q_c in vanilla PlonK), and it would be fixed at setup time.
Instead of having 15 selectors that every gadget could use, we go with the solutions that 13 selectors are available.

[dannywillems]

I would close this as 3055 has been merged.