Fiat-Shamir paradigm and the forking lemma I am reading the proof by Pointcheval and Stern and by Bellare and Neven about the forking lemma. The papers discuss the security proof of digital signatures by applying the lemma. It seems also mentioned that the same proof idea works for showing the Fiat-Shamir transformed interactive proof system is sound in the random oracle model. 

I am not sure I understand why the forking lemma implies the Fiat-Shamir transformed noninteractive protocol is sound using a random oracle, or it is essential to apply it for only the soundness. There are many papers about instantiation in the plain model, but that is beyond what I am trying to understand for now. 

It would be appreciated if anyone could explain the connection, or point some good references about that.
Let's recall important definitions. A proof system $(\mathsf{P}, \mathsf{V})$ for an NP language $\mathcal{L}$ is a pair of interactive Turing machines where the prover ($\mathsf{P}$) and the verifier ($\mathsf{V}$) receive a common input $\ell \in \{0,1\}^*$ and the prover receives an additional input $w \in \{0,1\}^*$ that is the witness for $\ell$, i.e., the relation $\mathcal{R}_\mathcal{L}$ defined by the NP language $\mathcal{L}$ satisfies $\mathcal{R}_\mathcal{L}(\ell,w) = 1$. The prover and verifier exchange a couple of messages and finally the verifier outputs a single bit denoted by $\mathsf{out}_\mathsf{V}(\langle\mathsf{P}(\ell,w)\leftrightarrow\mathsf{V}(\ell)\rangle)$, indicating whether the verifier accepts the proof (1) or rejects it (0). The proof system is public-coin if the verifier's messages consist of pure, unprocessed randomness. In this case the Fiat-Shamir heuristic says that no security is lost by replacing these randomly chosen messages by the hash of all messages up until that point. (And since there is a proof of this fact, albeit in the random oracle model, it is technically wrong to refer to it as a heuristic --- hence the more common phrase "Fiat-Shamir transform".)

The proof system is complete for a language $\mathcal{L} \in$ NP if honest provers are likely to succeed, i.e., $\forall \ell \in \mathcal{L} \, . \, \forall w \in \{0,1\}^* \, . \, \mathrm{Pr}[\mathcal{R}_\mathcal{L}(\ell,w) = 1 \, \Rightarrow \, \mathsf{out}_\mathsf{V}(\langle\mathsf{P}(\ell,w) \leftrightarrow \mathsf{V}(\ell)\rangle) = 1] \geq 1 - \mathsf{negl}(\lambda)$, for some function $\mathsf{negl}(\lambda)$ that is negligible in the security parameter.

The proof system is zero-knowledge if the transcript, i.e., the list of all exchanged messages which is denoted by $\langle\mathsf{P}(\ell,v) \leftrightarrow \mathsf{V}(\ell)\rangle$, is indistinguishable from the output of some simulator $\mathsf{S}$ that receives the string $\ell$ but not the witness $w$. Formally, $\forall \ell \in \mathcal{L} \, . \, \forall w \in \{0,1\}^* \, . \, \mathcal{R}_\mathcal{L}(\ell, w) = 1 \, \Rightarrow \, \langle\mathsf{P}(\ell,w) \leftrightarrow \mathsf{V}(\ell)\rangle \sim \mathsf{S}(\ell)$. Here $\sim$ denotes your favorite notion of indistinguishability of probability distributions, i.e., perfect, statistical, or computational.

With respect to soundness, it is important to draw a clear distinction between two related notions. First, the proof system has plain soundness if no (appropriately bounded) adversary $\mathsf{A}$ can make the verifier accept nonmembers of the language: $\forall n \not \in \mathcal{L} \, . \, \mathrm{Pr}[\mathsf{out}_\mathsf{V}(\langle \mathsf{A}(n) \leftrightarrow \mathsf{V}(n)\rangle) = 1] \leq \mathsf{negl}(\lambda)$. I call this notion plain soundness for the sake of exposition but the literature refers to it simply as soundness. Second, the proof system has knowledge-soundness if there is an (appropriately efficient) extractor machine $E$ that can extract and output a valid witness from any successful proof-forger $\mathsf{B}$, whether it receives the witness $w$ or not. Formally, $\forall \ell \in \mathcal{L} \, . \, \mathrm{Pr}[\mathsf{out}_\mathsf{V}(\langle\mathsf{B}(\ell) \leftrightarrow \mathsf{V}(\ell)\rangle) = 1 \, \Rightarrow \, \mathcal{R}_\mathcal{L}(\ell, \mathsf{E}^\mathsf{B}()) = 1] \geq \mathsf{noti}(\lambda)$, where $\mathsf{noti}(\lambda)$ is some noticeable function of the security parameter. Here $\mathsf{E}^\mathsf{B}$ means that the algorithm $\mathsf{E}$ has black-box access to $\mathsf{B}$, meaning that $\mathsf{E}$ is allowed to interact with $\mathsf{B}$ through messages that have the format of the proof system but $\mathsf{E}$ is not allowed to view or alter $\mathsf{B}$'s state. The literature also refers to this notion as witness-extractability and, confusingly, as soundess. Proof systems with this property are proofs of knowledge.

For many languages, knowledge-soundness is the relevant property and plain soundness is not. Consider for instance the standard Schnorr proof of knowledge of a discrete logarithm, whereby knowledge of an exponent $x \in \mathbb{Z}_{|\mathbb{G}|}$ is proven such that exponentiation-by-$x$ sends $g \in \mathbb{G}$ to $X = g^x \in \mathbb{G}$. When $g$ is a generator, as it usually is, plain soundness is trivial: since $X$ is a group element it must have a discrete logarithm with respect to $g$. However, for circuit-satisfiability type languages, plain soundness is usually more important than knowledge-soundness.

To prove plain soundness, it suffices to count the number of possible challenges from the verifier that expose a cheating prover; and the number of possible challenges that allow him to get away with the fraud. The ratio between the number of challenges that do not expose the cheating prover and the total number is known as the soundness error --- the fact that the verifier chooses his challenges at random makes this ratio equal the cheating prover's success probability and if it is negligible in the security parameter then plain soundness is satisfied. With the Fiat-Shamir transform, it suffices to argue from the difficulty of finding particular preimages to the random oracle. Formally, you can model the (classical) random oracle as a procedure that samples a random output only when it is needed and no sooner. Then the only way to find an input that leads to an answerable challenge is to test enough of them.

To prove knowledge-soundness, one must provide a description for the witness-extractor $\mathsf{E}$ and show that its success probability is noticeable if $\mathsf{B}$ has a noticeable success probability of convincing the verifier. The Forking Lemma provides such a description:


$\mathsf{E}$ plays the part of $\mathsf{V}$ honestly and runs the protocol with $\mathsf{B}$ thereby obtaining one transcript $T_1$.
$\mathsf{E}$ rewinds $\mathsf{B}$ to just after one of its messages, typically where it commits to something.
Once again, $\mathsf{E}$ plays the part of $\mathsf{V}$ honestly but with different randomness, thereby obtaining a second transcript $T_2$.


The language is structured in such a way that it is easy to extract a witness from two valid transcripts with the same commitments but different challenges. This description involves only one instance of rewinding; it may be necessary to rewind multiple times to obtain a set of transcripts satisfying very particular constraints.

Intuitively, the success probability of the extractor $\mathsf{E}$ should be somehow related to the success probability of the proof-forger $\mathsf{B}$. However, Bellare and Neven show that there is necessarily a square-root security degradation. In particular, if the extractor $\mathsf{E}$ splits into 2 branches, then $\mathrm{Pr}[\mathsf{B} \, \mathit{success}] \leq \sqrt{\mathrm{Pr}[\mathsf{E} \, \mathit{success}]}$, because the proof-forger $\mathsf{B}$ has to be successful in both branches. This means that even if the discrete logarithm problem takes $2^{128}$ units of work to compute, the proof shows only that the adversary as to perform at least $2^{64}$. In general, if the extraction requires $b$ branches, then the proof technique will induce a $b$th root degradation.

With the Fiat-Shamir transform, the random messages from the verifier are replaced with the response from the random oracle upon being queried with the list of protocol messages up until that point. This random oracle is simulated by the extractor $\mathsf{E}$, meaning that it can choose which responses the random oracle will provide. The trick is that by rewinding the proof-forger $\mathsf{B}$, the extractor $\mathsf{E}$ can reprogram different outputs for the random oracle. In particular, the extractor $\mathsf{E}$ proceeds as follows.


$\mathsf{E}$ runs $\mathsf{B}$ and provides it access with a random oracle $\mathsf{RO}$ whose responses are sampled uniformly at random when they are needed, and obviously conformant to the responses of previous queries. This provides the extractor $\mathsf{E}$ with the first transcript $T$.
$\mathsf{E}$ rewinds $\mathsf{B}$ to just after one of its messages, typically where it commits to something. Note that the list of all messages up until this point is fixed; denote this list by $L$.
$\mathsf{E}$ replays $\mathsf{B}$ again from this point but provides it with access to a random oracle $\mathsf{RO}'$ whose only difference is its response to $L$. In particular, this response has been sampled at random. This second execution of $\mathsf{B}$ provides $\mathsf{E}$ with the second transcript $T_2$.


With $T_1$ and $T_2$, the extractor $\mathsf{E}$ should be able to extract the witness. If more transcripts are needed then the extractor rewinds and replays the proof-forger as often as necessary.