###### tags: `Linea bug`, `oana's edit`

[PLONK](https://eprint.iacr.org/2019/953) is a ZK succinct argument system that given an arithmetic circuit $\mathcal{C}$ proves a party (i.e., the prover) knows a witness $w$ corresponding to a public input $x$ such that $(x,w)$ satisfies the arithmetic circuit $\mathcal{C}$. In most common variants of PLONK, the polynomial commitment is instantiated with a [KZG polynomial commitment](https://link.springer.com/chapter/10.1007/978-3-642-17373-8_11) and the resulting proof is a set of commitments (in fact, the commitments are, in turn points on a pairing-friendly elliptic curve) and field elements. The interactive version of PLONK includes several rounds of communication between the prover and the verifier.

During each round, the PLONK prover generates a set of challenges by hashing **the transcript** of the communication up to that round. The transcript up to a certain round is defined as "the concatenation of the public parameters that define the circuit, the public inputs that define the instance and the proof elements written by the PLONK prover up to that certain round". The [version of PLONK](https://eprint.iacr.org/2019/953) examined in this post is the latest one available at the time of writing (from the 17th of august 2022), in which the transcript and the corresponding challenges computed at each round are shown below:

| Round | Transcript | Output challenge |
|---|---|---|
| 1 | $T_1 = (pp,[a]_1, [b]_1, [c]_1)$ | $\beta = \mathcal{H}(T_1, 0), \gamma = \mathcal{H}(T_1, 1)$ |
| 2 | $T_2 = (T_1, [z]_1)$ | $\alpha = \mathcal{H}(T_2)$ |
| 3 | $T_3 = (T_2, [t_{lo}]_1, [t_{mi}]_1, [t_{hi}]_1)$ | $\zeta = \mathcal{H}(T_3)$ |
| 4 | $T_4 = (T_3, \bar{a}, \bar{b}, \bar{c}, \overline{\mathbf{s}}_{\sigma 1}, \overline{\mathbf{s}}_{\sigma 2}, \bar{z}_\omega)$ | $v = \mathcal{H}(T_4)$ |
| 5 | $T_5 = (T_4, [W_{\mathfrak{z}}]_1, [W_{\mathfrak{z} \omega}]_1)$ | $u = \mathcal{H}(T_5)$ |

where $pp$ contains the public parameters and the public inputs and $\mathcal{H}$ denotes a hash function.

Notice that $u$ (the last challenge) is not used in any of the PLONK prover rounds. In fact, $u$ is only used by the PLONK verifier to batch validate multiple evaluations at two different evaluation points. Hence, rightfully, the following question arises: given that the PLONK verifier only needs $u$ to be random and $u$ is not used by the PLONK prover, does one really need to follow the specified protocol and compute $u$ as the hash of the full transcript?

### The last challenge attack

The last challenge attack is applicable to implementations of the PLONK verifier in which the last challenge $u$ is not computed as the hash of the full transcript. We describe the attack for the particular scenario in which this vulnerability was found, where $u$ does not depend on the proof elements $[W_{\mathfrak{z}}]_1$ and $[W_{\mathfrak{z} \omega}]_1$ (which are part of the full transcript).

Before describing the steps of the attack, we briefly recall the relevant part of the PLONK verifier. The latter works in 12 steps, the last of which represents the verification of the following bi-linear pairing equation:

<figure>
<img src="https://hackmd.io/_uploads/rkxG-wqQp.png"/>
</figure>

Note that in the equation above $[F]_1$ and $[E]_1$ are computed by the verifier using the commitments and evaluations sent by the prover.

The Last Challenge Attack proceeds as follows:
- **Bootstrapping:** From a well-formed PLONK proof $\pi$ obtained on a circuit of its choice, a malicious prover $\mathcal{P}'$ produces $A$, $B$ such that $e(A,[x]_2) = e(B,[1]_2)$.
- $\mathcal{P}'$ sets proof components (except $\color{red}{[W_{\mathfrak{z}}]_1}$ and $\color{red}{[W_{\mathfrak{z} \omega}]_1}$) and the public input $PI$ to arbitary values of its choice in preparation to produce the false proof
$\pi' = ( \color{green}{[a]_1, [b]_1,[c]_1,[z]_1,[t_{lo}]_1, [t_{mi}]_1, [t_{hi}]_1}, \color{red}{[W_{\mathfrak{z}}]_1,[W_{\mathfrak{z} \omega}]_1}, \color{green}{\bar{a}, \bar{b}, \bar{c}, \overline{\mathbf{s}}_{\sigma 1}, \overline{\mathbf{s}}_{\sigma 2}, \bar{z}_\omega})$.
- $\mathcal{P}'$ computes $[F]_1$, $[E]_1$ from $\pi'$ using steps 9-11 of the [PLONK Verifier](https://eprint.iacr.org/2019/953) algorithm. Note that $\color{red}{[W_{\mathfrak{z}}]_1}$ and $\color{red}{[W_{\mathfrak{z} \omega}]_1}$ are not needed in order for $\mathcal{P}'$ to complete this computation.
- $\mathcal{P}'$ exploits the independence of $u$ from $[W_{\mathfrak{z}}]_1$ and $[W_{\mathfrak{z} \omega}]_1$ and solves a system of 2 linear equations with 2 unknowns:
$$\begin{cases}
X + u Y = A\\
\mathfrak{z} X + u\mathfrak{z}\omega Y + C = B
\end{cases}$$ where $X=[W_{\mathfrak{z}}]_1$, $Y=[W_{\mathfrak{z} \omega}]_1$ are unknowns and $A,B,C,u,\mathfrak{z},\omega$ are constants defined as follows:
$$e(\underbrace{\underbrace{[W_{\mathfrak{z}}]_1}_{X}+{u} \underbrace{\cdot[W_{\mathfrak{z} \omega}]_1}_{Y}}_{A},[x]_2)
\stackrel{?}{=}
e(\underbrace{\mathfrak{z} \cdot\underbrace{[W_{\mathfrak{z}}]_1}_{X} + {u} \mathfrak{z} \omega \cdot\underbrace{[W_{\mathfrak{z} \omega}]_1}_{Y}+\underbrace{[F]_1-[E]_1}_{C}}_{B},[1]_2)
$$
- $\mathcal{P}'$ adds the missing $\color{green}[W_{\mathfrak{z}}]_1$ and $\color{green}[W_{\mathfrak{z} \omega}]_1$ to the proof $\pi'$.
- The buggy verifier accepts the false proof $\pi'$ as valid.

<figure>
<img src="https://hackmd.io/_uploads/B1CQ-w5m6.gif"/>
<figcaption align="center">Figure 4: Visual walkthrough of the attack</figcaption>
</figure>

### Implications

In the case of a ZK rollup on Ethereum, the circuit simulates the Ethereum Virtual Machine (EVM). An honest prover can thus prove that blocks of transactions were executed correctly, and a certain state transition is valid. However, the last challenge attack makes it possible for a malicious prover to forge a proof for an invalid state transition, for example to set itself as the owner of all the assets sitting in the rollup.

<figure>
<img src="https://hackmd.io/_uploads/SyWr-P5Qp.png"/>
<figcaption align="center">Figure 5: Possible ZK rollup’s state after accepting a malicious proof</figcaption>
</figure>

### Conclusion

Fiat-Shamir transformations are a common source of vulnerabilities. A verifier should avoid leaving degrees of freedom to an attacker to manipulate an input without impacting the challenges. The easiest way to do so is to ensure that challenges derived using the Fiat-Shamir transformation depend on the entire transcript. Mind your Fiat-Shamir-s!