Halo2's Elegant Transcript As Proof

Today I want to showcase something really cute that zcash's halo2 implementation has designed in order to implement Fiat-Shamir in a secure way.

If you take a look at their plonk prover, you will see that a mutable transcript is passed and in the logic, you can see that the transcript absorbs things differently:

• transcript.common_point() is used to absorb instance points (points that the prover and the verifier both know)
• transcript.write_point() absorbs messages that in the interactive version of the protocol would be sent to the verifier
• transcript.write_scalar() same but for scalars
• transcript.squeeze_challenge_scalar() is used to generate verifier challenges

What is interesting are the prover-only functions write_point and write_scalar implementations. If we look at how the transcript is implemented, we can see that it does two things:

1. It hashes the values in a Blake2b state. This is the usual Fiat-Shamir stuff we're used to seeing. This is done in the common_point and common_scalar calls below.

2. It also writes the actual values in a writer buffer. This is what I want to highlight in this post, so keep that in mind.

    fn write_point(&mut self, point: C) -> io::Result<()> {
        self.common_point(point)?;
        let compressed = point.to_bytes();
        self.writer.write_all(compressed.as_ref())
    }
    fn write_scalar(&mut self, scalar: C::Scalar) -> io::Result<()> {
        self.common_scalar(scalar)?;
        let data = scalar.to_repr();
        self.writer.write_all(data.as_ref())
    }

On the other side, the verifier starts with a fresh transcript as well as the buffer created by the prover (which will act as a proof, as you will see) and uses some of the same transcript methods that the prover uses, except when it has a symmetrical equivalent. That is, instead of acting like it's sending points or scalars, it is using functions to receive them from the prover. Mind you, this is a non-interactive protocol so the implementation really emulates the receiving of prover values. Specifically, the verifier uses two types of transcript methods here:

• read_n_points(transcript, n) reads n points from the transcript
• read_n_scalars(transcript, n) does the same but for scalars

What is really cool with this abstraction, is that the absorption of the prover values with Fiat-Shamir happens automagically and is enforced by the system. The verifier literally cannot access these values without reading (and thus absorbing) them.

It is important to repeat: all values sent by the prover are magically absorbed in Fiat-Shamir, leaving no room for most Fiat-Shamir bug opportunities to arise.

We can see the magic happening in the transcript code:

    fn read_point(&mut self) -> io::Result<C> {
        let mut compressed = C::Repr::default();
        self.reader.read_exact(compressed.as_mut())?;
        let point: C = Option::from(C::from_bytes(&compressed)).ok_or_else(|| {
            io::Error::new(io::ErrorKind::Other, "invalid point encoding in proof")
        })?;
        self.common_point(point)?;

        Ok(point)
    }

    fn read_scalar(&mut self) -> io::Result<C::Scalar> {
        let mut data = <C::Scalar as PrimeField>::Repr::default();
        self.reader.read_exact(data.as_mut())?;
        let scalar: C::Scalar = Option::from(C::Scalar::from_repr(data)).ok_or_else(|| {
            io::Error::new(
                io::ErrorKind::Other,
                "invalid field element encoding in proof",
            )
        })?;
        self.common_scalar(scalar)?;

        Ok(scalar)
    }

Here the buffer is called reader, and is the buffer at the end of the proof creation. The common_point calls are the ones that mirror the absorption in the transcript that the prover did on their side.