The book by Wigderson includes this quote on page 39, following the statement of the Cook-Levin theorem that $SAT$ is $\mathsf{NP}$-complete:
The proof of this theorem (namely, the construction of the reduction algorithm $f$ ) gives an extra bonus that turns out to be extremely useful: It maps witnesses to witnesses. More precisely, for any witness $y$ certifying that $z \in C$ (via some verifier $VC$ ), the same reduction $f$ converts the witness $y$ to a Boolean assignment of the variables of the formula $f(z)$ that satisfy it. In other words, this reduction translates not only between the decision problems, but also between the associated search problems.
The Arora-Barak book makes a similar remark, on page 50 under "More Thoughts on the Cook-Levin Theorem":
The reduction $f$ from an $\mathsf{NP}$-language $L$ to $SAT$ presented in Lemma 2.11 not only satisfied that $x \in L \iff f(x) \in SAT$ but actually the proof yields an efficient way to transform a certificate for $x$ to a satisfying assignment for $f(x)$ and vice versa. We call a reduction with this property a Levin reduction. One can also modify the proof slightly (see Exercise 2.13) so that it actually supplies us with a one-to-one and onto map between the set of certificates for $x$ and the set of satisfying assignments for $f(x)$, implying that they are of the same size.
There are other references to this fact of the Cook-Levin theorem. Recall that the proof of the Cook-Levin theorem takes a computation history of a Turing machine, a polytime verifier, and produces a polysized CNF formula which is satisfiable if and only if the verifier accepted.
I do not see how the Cook-Levin theorem implies this transformation from witnesses to witnesses, as it does from problems to problems. I would appreciate any directions or pointers, I feel like I may be missing something obvious.
