Fiat Shamir consistency

Implementing Fiat Shamir transformation is very subtle. There have been bugs in the past in implementations. We must be sure we add to the transcript all the prover outputs, and also we can have some optimisations regarding the sponge mode (instead of absorbing with a small state 10 elements, we could have a permutation with 10 elements directly). With customizable kimchi, we will need to be sure to add all commitments and all evaluations, which might be error-prone.

Merlin has been created in 22' (I think) as a Rust library to solve some issues. And there is a WIP to improve it called nimue. It reminded me a past project I had in mind. I suggest to implement some of the ideas of Merlin and nimue, including, but not restricted to:

type the transcript. Each round in the protocol must have a defined output which has to be added to the protocol. The transcript must keep in its type the step and the types of the output.
to go to round i + 1, we must enforce that the round i has been correctly executed, i.e. the transcript has been correctly filled.
at the round i, we must encode in a type the number of random variables we use. I suggest to add it in the sponge context type. At the end, the sponge context should be unit, and the protocol is paramatrized by the sponge context.
in a first version, the permutation used in the sponge mode should be switchable to any other. Atm we use Poseidon, but why not switching to a cheaper one later (like Monolith :slightly_smiling_face: ).
the permutation state size should not be fixed. For instance, at round i, we might need to absorb 2 commitments and 1 scalar field, i.e. 5 255 bits, but at round i + 1, only 2 elements, i.e. 2 255 bits. It is more efficient to use a bigger state sometimes.

This is the top of my mind night ideas. Most of the properties must be verifiable at compile time to forbid unsound FS transformation. The first step would be to have a look at merlin and nimue.

MinaProtocol / mina

Fiat Shamir consistency #14173