Proof/Transcript

Please read the Fiat-Shamir documentation page before this one!

Transcript

A Remainder Transcript consists of all of the explicit sponge function operations which take place during the generation of a non-interactive (GKR) proof. As mentioned in the Fiat-Shamir documentation page, the prover can interact with the sponge function $\mathcal{H}$ in two primary ways, exactly corresponding with the interactive version of the protocol:

• When the prover would send a message $m$ to the verifier in the interactive version of the protocol, they instead invoke $\mathcal{H}.\text{absorb}(m)$.
• When the verifier would send a challenge $r_i$ to the prover in the interactive version of the protocol, the prover instead invokes $r_i\leftarrow \mathcal{H}.\text{squeeze}()$.

Remainder's TranscriptSponge captures exactly these operations. You will generally work with the TranscriptWriter and TranscriptReader structs. The TranscriptWriter is the prover's view of the transcript, and the prover can add Operations to the internal Transcript struct. When the prover is finished appending all of their messages (and squeezing challenges where appropriate) to/from the TranscriptWriter struct, they can then eject the internal Transcript and send this directly to the verifier (e.g. as bytes), as the Transcript includes all of the proof data and can be treated as the GKR proof itself (note that this is slightly different from the structured proof within Hyrax). The verifier can feed this struct into the constructor of a TranscriptReader (again, mostly a convenience wrapper around a Transcript for the verifier to read prover messages from and sample Fiat-Shamir challenges from while maintaining its own hash function's sponge state) and consume the Operations in the same order to perform verification.

Appending Input Elements

See append_input_elements() for more details. There is a special function for appending input elements (i.e. all elements which the prover needs to communicate to the verifier before the first output claim challenge is generated), ProverTranscript::append_input_elements(), which should be called. This function provides some insurance against the attack on non-interactive GKR described in this paper by creating a long hash chain (1000 iterations of SHA-256, specifically) for each input -- in general, this prevents most circuits (due to their limited depth) from being able to generate the hash chain value themselves and thus carry out the attack. In general, however, we emphasize that all circuits used in production should be audited to mitigate such attack potential.