Poseidon duplex gadget

[therealyingtong]

(issue to make gadget generic over permutation: #79)

Functions:

• absorb:
  • The first time absorb is called after a squeeze, it performs the necessary internal transformations to transition to absorb mode.
  • Applies a permutation every time the caller absorbs more than the rate.
• squeeze:
  • The first time squeeze is called after an absorb, it internally applies a padding before switching to squeeze mode.
  • Applies a permutation every time the caller squeezes more than the rate.

This should be almost all gadget logic that just uses the existing permutation circuit. However, the padding logic specific to a duplex may require new circuit work.

Considerations:

• If we can fix the number and pattern of required absorbs and squeezes in the protocol, then we can load padding in from Fixed columns (assign_advice_from_constant). This constrains the prover to follow the pre-defined pattern.
• To enable truly variable-length inputs to the Poseidon duplex, we would need to specify some maximum length and allow padding to be witnessed in Advice columns, and constrain the padding with reference to the previous iteration; however, this is out of scope in the context of recursion in halo 2.