First part of Linea bug blogpost (edited by oana)

###### tags: `Linea bug`, `oana's edit` Researchers at [OpenZeppelin](https://www.openzeppelin.com/) encountered a critical issue during the course of an audit of the [Linea](https://www.openzeppelin.com/) zero-knowledge proof verifier using [PLONK](https://eprint.iacr.org/2019/953). At its core, the issue is similar in nature to previously disclosed vulnerabilities ([Frozen Heart](https://blog.trailofbits.com/2022/04/18/the-frozen-heart-vulnerability-in-plonk/), [00](https://cryptosubtlety.medium.com/00-8d4adcf4d255)), where a malicious prover can exploit a set of degrees of freedom introduced by the incorrect application of the Fiat-Shamir transformation when computing PLONK's final challenge. The issue was promptly communicated and fixed, but we believe the specifics of this issue are worth sharing more broadly so that others may learn to recognize similar patterns and protect against them accordingly. In the following, we give a brief high-level introduction to Zero-knowledge Succinct Non-Interactive ARguments of Knowledge (zkSNARKs) and the Fiat-Shamir transformation, and then we describe the issue in detail. ### A high-level walkthrough of zkSNARKs A zkSNARK system involves two parties: a **Prover** and a **Verifier**. The Prover aims to convince the Verifier that the result of some **computation** $F$ is correct, providing a **succinct** proof that is more efficient to verify than re-executing the entire computation. This is especially valuable in the context of a blockchain: instead of having to re-execute all the transactions in order to verify the validity of a state transition, it is cheaper for nodes to verify a zkSNARK proof attesting for the same property. In fact, such a zkSNARK proof provides for a Layer 2 $(L_2)$ a similar level of security as direct and full re-execution on Layer 1 $(L_1)$, at the cost of latency but with the benefit of improved blockchain scalability. <figure> <img src="https://hackmd.io/_uploads/BknEeD5QT.png"/> <figcaption style="text-align: center">A ZK rollup’s state being updated in its L1 contract (adapted from <a href="https://vitalik.ca/general/2021/01/05/rollup.html" style="color:#666; font-weight: bold">vitalik.ca)</a> </figcaption> </figure> The computation $F$ mentioned above is represented as an **arithmetic circuit**. The latter is a sequence of simple arithmetic operations, such as additions and multiplications, also called **gates**, connected by **wires**. The inputs to the circuit are of two types: public values (**public input**), known by both Prover and Verifier and private values (**witness**), known only to the Prover and representing the internal values of the computation. With a zkSNARK, the Prover proves knowledge of the witness without revealing it to the Verifier (i.e., the zero-knowledge property, protecting the honest Prover), and testifies that the computation $F$ was executed correctly (i.e., the soundness property, protecting the honest Verifier). We show below an example circuit corresponding to the function $g(x_1, x_2, w_1) = (x_1 + x_2)*(x_2 + w_1)$, where $x_1$, $x_2$ are the public inputs and $w_1$ is the witness. For this circuit, a Prover can use a zkSNARK to prove that, for some assignment of the public inputs $(x_1, x_2)$ and output $y$, it knows an assignment of the witness $w_1$ such that $g(x_1, x_2, w_1) == y$, without revealing any additional information about $w_1$. <figure> <img src="https://hackmd.io/_uploads/By2aJP5Qp.gif"/> <figcaption style="text-align: center">Figure 1: Simple example of an arithmetic circuit with two addition and one multiplication gate</figcaption> </figure> Given an arithmtic circuit as exemplified in the figure above, one would next choose an appropriate arithmetisation (e.g., R1CS, AIR, Plonkish) and, implicitly, an NP language for which one would build a (zk)SNARK scheme. All these details are valuable to any practitionar out there, however they are outside the scope of this blog. Instead, we recommend the interested reader a number of good resources covering such topics, e.g., Vitalik excellent trio of introductory blogposts starting with [this one](https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649) or [Vitalik's blogpost regarding PLONK](https://vitalik.ca/general/2019/09/22/plonk.html) or the recent [LambdaClass summary on arithmetisation](https://blog.lambdaclass.com/arithmetization-schemes-for-zk-snarks/). Going further, a zkSNARK system has two main buiding blocks: a Polynomial Interactive Oracle Proof scheme (PIOP) and a polynomial commitment scheme. Each of them, in their original form is **interactive**, meaning that they proceed as a series of communication rounds between a Prover and a Verifier. Intuitively, a Polynomial Interactive Oracle Proof (with a first version introduced in [PLONK](https://eprint.iacr.org/2019/953) and called polynomial protocol and then later generalised to PIOP in [BFS19](https://eprint.iacr.org/2019/1229.pdf)) abtracts away, in the form of a set of polynomial identities, the atomic constraints described by the arithmetic circuit. A PIOP is compiled into a (zk)SNARK system via one of various existing compilers (as described in either [PLONK](https://eprint.iacr.org/2019/953.pdf), [Marlin](https://eprint.iacr.org/2019/1047), [BFS19](https://eprint.iacr.org/2019/1229.pdf), etc.) by additionaly involving a polynomial commitment scheme. To better understand what interactivity means, we provide a high-level description of [KZG](https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf), the most common polynomial commitment scheme used in [PLONK](https://eprint.iacr.org/2019/953) (one of the recent and more efficient zkSNARK systems).  1. The Prover commits to a polynomial $f(X)$. The commitment $com_f$ is **binding** i.e., $f$ cannot be modified without also modifying $com_f$. 2. To validate $com_f$, the Verifier sends back a **challenge** $c$ chosen uniformly at random. 3. The Prover evaluates $f$ at $c$ and sends back a proof $\pi$ along with the evaluation $f(c)$. 4. The Verifier checks that $f(c)$, $\pi$ and $com_f$ are consistent and if so, accepts the proof $\pi$ as valid; otherwise it rejects. Note that the Prover sent the commitment first, without knowing the value of the challenge $c$ on which it would be tested. This is critical to ensure that the Prover cannot cheat and he indeed committed to the polynomial $f$.  <figure> <img src="https://hackmd.io/_uploads/SJmjxD5ma.png"/> <figcaption style="text-align: center">Figure 2: Interactive protocol</figcaption> </figure> The described protocol is **interactive** because the Prover and the Verifier have to wait for each other before moving on to the next step. In practice, interactivity introduces significant latency between the steps and requires a Prover to produce a new proof for each new Verifier. ### The Fiat-Shamir transformation The need for interactivity above really comes from Step 2, where the Verifier needs to produce the random challenge $c$. In addition to the aforementioned practical downside of interactivity, sampling a truly random value on a public blockchain is challenging. Randomness is important because if the Prover was able to predict the challenge before committing to the polynomial, it could spoof the commitments and fool the Verifier in accepting a false proof for a different circuit of the attacker's choice. In order to avoid the interactivity bottleneck, there exist the [Fiat-Shamir transformation](https://www.researchgate.net/publication/2572744_How_To_Prove_Yourself_Practical_Solutions_to_Identification_and_Signature_Problems) such that for every constant round argument system (i.e., secure against computationally bounded provers), one can contsruct an equivalent but [non-interactive version that is still an argument](https://www.comp.nus.edu.sg/~prashant/teaching/CS6230/files/notes/lecture11.pdf). An example of the Fiat-Shamir transformation is given in the figure below. <figure> <img src="https://hackmd.io/_uploads/B1YTgv97a.gif"/> <figcaption style="text-align: center">Figure 3: Fiat-Shamir transformation of an interactive protocol</figcaption> </figure> It has been shown the the [Fiat-Shamir transformation is secure](https://www.researchgate.net/publication/221348456_Security_Proofs_for_Signature_Schemes) in the [random oracle model](https://cseweb.ucsd.edu/~mihir/papers/ro.pdf). In practice, however, the random oracle model is instantiated by a hash function. This is called the Fiat-Shamir heuristic. Intuitivly, the Fiat-Shamir heuristic ensures that the Prover is not able to predict the challenge before committing to the polynomial $f$. Going back to our example introduced in Figure 3, both the Prover and the Verifier use a hash function to compute the challenge $c$ as the hash of the commitment $com_f$ and the public input $x$ for that instance. In this way, the Prover is no longer able to modify $com_f$ without also modifying $c$ in a way that deviates from the protocol (i.e., from what the Verifier himself is computing). In the following, we will focus on a concrete zkSNARK, namely [PLONK](https://eprint.iacr.org/2019/953) and an implementation bug for its Fiat-Shamir transformation. A more detailed description of PLONK is provided in the following section.