The significance of rewinding a simulation in an ZK interactive proof

Question

I'm reading Matthew Green's blog post on ZK Interactive Proofs

I don't understand the part where he explains how using a time machine shows that the prover is leaking zero information

Specifically, assume that I (the Verifier) have some strategy that ‘extracts’ useful information about Google’s coloring after observing an execution of the honest protocol. Then my strategy should work equally well in the case where I’m being fooled with a time machine. The protocol runs are, from my perspective, statistically identical. I physically cannot tell the difference.

Thus if the amount of information I can extract is identical in the ‘real experiment’ and the ‘time machine experiment’, yet the amount of information Google puts into the ‘time machine’ experiment is exactly zero — then this implies that even in the real world the protocol must not leak any useful information.

I am not sure I am convinced about this. I assume that the transcript of the simulation doesn't contain the repeated/uncorrected iterations of each try. i.e. I think it will contain only the final correct simulation of each try i.e. if verifier chooses 2 vertices which are coloured different, then that step will be in the transcript. However, if the verifier chooses 2 vertices with the same colour, then the prover will operate a time machine & maker the prover forget about that try & redo it. I assume in this case, the transcript will only contain the redone try & not the try which failed. Am I right about this?

Assuming my assumption about the transcript is true, then the transcript contains only all the verified tries & all the tries where verifier had to use the time machines to reverse wouldn't be recorded in the transcript. And the verifier cannot extract any info from such a transcript.

So in the end, he writes

And yet it’s worth pointing out again that in the time machine version, Google has absolutely no information about how to color the graph.

But this is not true in the real world, right? There is no time machine in the real world. So the prover cannot convince the verifier without having actual knowledge. So how exactly does a transcript which was "corrected" using a time machine to convince the verifier prove that an actual transcript doesn't leak info?

Answer 1

I assume that the transcript of the simulation doesn't contain the repeated/uncorrected iterations of each try... all the tries where verifier had to use the time machines to reverse wouldn't be recorded in the transcript

The simulator rewinds at the point that the verifier decides which hat to check, but before the verifier actually picks up the hat. When the simulator rewinds time, the transcript does not retain information about any initial state that the simulator had prior to asking for a challenge by the verifier. Furthermore, the simulator will be expecting the verifier to make the same choice/challenge again immediately after time is rewound.

Depending on the scenario, it may be almost 100% certain that a rewind of time is necessary (as is the case for a simulator for the Schnorr protocol). Therefore, we are always recording "tries where verifier had to use the time machines", but we are not including the initial state that the simulator had prior to the point it asked the verifier to challenge it for the first time.

There is no time machine in the real world... So how exactly does... using a time machine to convince the verifier prove that an actual transcript doesn't leak info?

This is a thought experiment primarily so that the prover is assured they are not leaking information by providing a proof.

Let's take an example from the second part of the blog post you linked to. With the Schnorr protocol, each transcript (whether real-world or simulator) will contain a commitment value $K$ being sent by the prover, a challenge $c$ sent by the verifier, and a response $s$ sent by the prover. If, statistically, you cannot distinguish between $(K,c,s)$ tuples in the real-world transcripts and $(K,c,s)$ tuples in the simulator transcripts, then the verifier can't learn more from the real-world transcripts than from the simulator transcripts.

If the simulator transcripts required no knowledge of any secret information, then we know for sure that the simulator transcripts cannot be leaking any information. If the simulator transcripts are statistically indistinguishable from the real-world transcripts, then the real-world transcripts cannot possibly be more informative than the simulator transcripts.

Of course, we don't use statistical sampling to try to verify that we have a zero-knowledge proof. Instead, we check that a mechanism is in place that ensures that the real-world proof contains data that we know is statistically indistinguishable from the distribution produced by the simulation. The easiest way to do this is to ensure that both the real-world proofs and the simulator transcripts contain values that are uniformly randomly distributed.

In the case of the hats example, during the real-world proof, we always pick colors uniformly randomly and only allow the verifier to pick a single hat on each attempt. The simulator should also pick uniformly random colors. Therefore, both the real-world and simulated transcripts will contain statistically identical color distributions.

In the case of the Schnorr protocol, for the real-world proof: If $k$ is uniformly randomly distributed, then $K$ will also be uniformly randomly distributed within the group (where $K=G^k$). The response $s$ will be uniformly randomly distributed, because we calculate $s=(k+a\cdot c) \operatorname{mod} \ell$. Since $k$ is uniformly randomly distributed within the bounds $0\leq k \lt \ell$, then $(k+a\cdot c) \operatorname{mod} \ell$ is also uniformly randomly distributed within those bounds.

For the Schnorr simulator transcript, we know $K$ is uniformly randomly distributed, because we have chosen a $z$ value that is uniformly randomly distributed, and we have cheated by calculating $K=G^z\cdot A^{-c}$ where $A=G^a$ (i.e. Alice's public key). The group is cyclic, and so multiplying a uniformly randomly distributed group element ($G^z$) with another group element will always produce a result that is also uniformly randomly distributed within the group.