snarkjs vulnerability report

snarkjs_vulnerability_report.md

[DRAFT] Forging proofs by exploiting a flawed Fiat-Shamir transformation in the PLONK implementation of SnarkJS

Contributors: Nguyễn Duy Hiếu, Hồ Huỳnh Thanh Uyên

Introduction

In this post, we release an unreported critical attack on SnarkJS's PLONK implementation that enables us to forge proof for any false statement. The attack leverages an incorrect implementation of the Fiat-Shamir transformation. Although the recent refactor of SnarkJS in version 0.7.0 has eliminated this vulnerability and rendered the attack irrelevant, we still decide to publish all the details here since we believe that it can still serve as a useful case study for future implementations of zero-knowledge proofs where the Fiat-Shamir transformation plays an important role in achieving non-interactivity.

Background

SNARKs, SnarkJS and PLONK

Succinct Non-interactive ARguments of Knowledge (SNARKs) have gained significant attention in the field of cryptography in recent years as they open up a wide range of applications in the real world, including preservation of privacy, delegation of computation, construction of secure multi-party protocols, ... to name a few. On the other hand, SnarkJS is a core component of the well-known Circom-SnarkJS framework developed by team Iden3 that offers a comprehensive toolkit for working with SNARKs.

PLONK [1] (Permutations over Lagrange-bases for Oecumenical Non-interactive arguments of Knowledge) is a SNARK released in 2019 by Ariel Gabizon, Zachary J. Williamson and Oana Ciobotaru. Since then, PLONK has been widely adopted due to its extensibility nature to support beyond-arithmetic polynomial constraints such as permutation (polynomials' evaluations over a domain is the same as others' under an optionally predefined permutation) or lookup (each evaluation of a polynomial over a domain is contained in a table possibly made up from the evaluations of another polynomial). PLONK has been supported by SnarkJS since version 0.4.0.

Basics of PLONK

This section gives only some of the main points on the technical side of PLONK that are required for understanding our attack. Additional details will be provided on the fly when needed. For the full specification, please refer to [1].

First of all, PLONK makes use of a polynomial commitment scheme that allows a prover to commit to a polynomial and later on, prove to a verifier the correctness of the committed polynomial's evaluations at certain points chosen by the verifier.

Regarding the Fiat-Shamir transformation, we let $H$ denote a cryptographic hash function and $transcript$ denote a tuple consisting of the statement being proved and proof elements output by the prover in all previous rounds. The goal is to assure that any minor change made by the prover during proof execution must result in the rerandomization of all subsequent challenges derived from $H(transcript)$ in an unpredictable way.

PLONK is originally designed to prove the correctness of computation over arithmetic circuits that support only addition and multiplication gates. The prover algorithm is as follows:

• Round 1: Compute 3 wire polynomials $a(X), b(X), c(X)$ and output their commitments.

• Round 2: Derive permutation challenges $\beta, \gamma$ from $H(transcript)$, compute permutation polynomial $z(X)$ and output its commitment.

• Round 3: Derive quotient challenge $\alpha$ from $H(transcript)$, compute quotient polynomial $t(X)$ and output its commitment.

• Round 4 & Round 5: Derive evaluation challenge $\xi$ from $H(transcript)$, evaluate the committed polynomials at desired points ($\xi$ and others) and output the evaluations together with their proofs of correctness.

Finally, the PLONK verifier verifies that:

• All polynomial evaluation proofs are correct.

• All polynomial constraints are satisfied at $\xi$.

The vulnerability

The following code snippet is extracted from the source code of SnarkJS at version 0.6.11. If we pay close attention, it won't be hard to notice that each of the challenges is computed from the output of only ONE last round.

const transcript1 = new Uint8Array(zkey.nPublic*n8r + G1.F.n8*2*3);
for (let i=0; i<zkey.nPublic; i++) {
    Fr.toRprBE(transcript1, i*n8r, A.slice((i)*n8r, (i+1)*n8r));
}
G1.toRprUncompressed(transcript1, zkey.nPublic*n8r + 0, proof.A);
G1.toRprUncompressed(transcript1, zkey.nPublic*n8r + G1.F.n8*2, proof.B);
G1.toRprUncompressed(transcript1, zkey.nPublic*n8r + G1.F.n8*4, proof.C);

ch.beta = hashToFr(transcript1);

const transcript2 = new Uint8Array(n8r);
Fr.toRprBE(transcript2, 0, ch.beta);
ch.gamma = hashToFr(transcript2);

...

const transcript3 = new Uint8Array(G1.F.n8*2);
G1.toRprUncompressed(transcript3, 0, proof.Z);
ch.alpha = hashToFr(transcript3);

...

const transcript4 = new Uint8Array(G1.F.n8*2*3);
G1.toRprUncompressed(transcript4, 0, proof.T1);
G1.toRprUncompressed(transcript4, G1.F.n8*2, proof.T2);
G1.toRprUncompressed(transcript4, G1.F.n8*4, proof.T3);
ch.xi = hashToFr(transcript4);

...

const transcript5 = new Uint8Array(n8r*7);
Fr.toRprBE(transcript5, 0, proof.eval_a);
Fr.toRprBE(transcript5, n8r, proof.eval_b);
Fr.toRprBE(transcript5, n8r*2, proof.eval_c);
Fr.toRprBE(transcript5, n8r*3, proof.eval_s1);
Fr.toRprBE(transcript5, n8r*4, proof.eval_s2);
Fr.toRprBE(transcript5, n8r*5, proof.eval_zw);
Fr.toRprBE(transcript5, n8r*6, proof.eval_r);
ch.v = [];
ch.v[1] = hashToFr(transcript5);

...

const transcript6 = new Uint8Array(G1.F.n8*2*2);
G1.toRprUncompressed(transcript6, 0, proof.Wxi);
G1.toRprUncompressed(transcript6, G1.F.n8*2, proof.Wxiw);
res.u = hashToFr(curve, transcript6);

Here we have:

• $\beta$ = $H(\text{public inputs, commitments of } a(X), b(X), c(X))$
• $\gamma$ = $H(\beta)$
• $\alpha$ = $H(\text{commitment of } z(X))$
• $\xi$ = $H(\text{commitment of } t(X))$
• $v$ = $H(\text{polynomial evaluations})$
• $u$ = $H(\text{polynomial evaluation proofs})$

Certainly, this Fiat-Shamir transformation is insecure.

Exploit

PLONK defines the quotient polynomial $t(X)$ as:

$$ \begin{align*}\tag{1} t(X) &= \frac{1}{Z_{H}(X)}(a(X)b(X)q_{M}(X) + a(X)q_{L}(X) + b(X)q_{R}(X) + c(X)q_{O}(X) + P(X) + q_{C}(X)) \newline &+ \frac{\alpha}{Z_{H}(X)}((a(X) + \beta X + \gamma)(b(X)+\beta k_{1}X + \gamma)(c(X)+\beta k_{2}X +\gamma)z(X)) \newline &+ \frac{-\alpha}{Z_{H}(X)}((a(X) + \beta S_{\sigma 1}(X) + \gamma)(b(X)+\beta S_{\sigma 2}(X) + \gamma)(c(X)+\beta S_{\sigma 3}(X) +\gamma)z(X\omega))\newline &+ \frac{\alpha^2}{Z_{H}(X)}((z(X) - 1)L_{1}(X)) \end{align*} $$

As one might notice, (1) is actually the result of aggregating 3 different sub-constraints via the powers of $\alpha$ and hence, our only polynomial constraint in this case. Also note that:

• $P(X)$ is a polynomial constructed from the public inputs and outputs of the circuit.

• Other terms that have not been mentioned: $q_M(X), q_L(X), q_R(X), q_O(X), q_C(X), Z_{H}(X), k_1, k_2, L_1(X), S_{\sigma 1}(X), S_{\sigma 2}(X), S_{\sigma 3}(X)$ are agreed beforehand and/or derived from the computational logic of the circuit. They (or their commitments) are all known to the verifier.

Now, the goal is to make (1) satisfied when $X = \xi$ for arbitrary $P(X)$. Because of the flawed Fiat-Shamir transformation we have already pointed out, it is possible to do so:

1. Pick arbitrary $t(X)$ and compute the evaluation challenge $\xi$ which only depends on $t(X)$.

2. Choose $z(X)$ such that it is evaluated to $0$ at $\xi$ and $\xi\omega$ . This will eliminate $\beta, \gamma$ from (1). Now $\alpha$, which only depends on $z(X)$, is also determined.

3. Finally, pick suitable $a(X), b(X), c(X)$ such that $a(\xi), b(\xi), c(\xi)$ satisfy (1). The rest of the prover algorithm (round 4 & 5) can then be processed normally.

Impact

An attacker can forge a valid proof for an incorrect computational statement. This can lead to severe consequences depending on the actual application.

Suggestion

We suggest computing the challenges as follows:

• $\beta$ = $H(\text{public inputs, commitments of } a(X), b(X), c(X))$
• $\gamma$ = $H(\beta)$
• $\alpha$ = $H(\boldsymbol{\gamma}, \text{commitment of } z(X))$
• $\xi$ = $H(\boldsymbol{\alpha}, \text{commitment of } t(X))$
• $v$ = $H(\boldsymbol{\xi}, \text{opening evaluations})$
• $u$ = $H(\boldsymbol{v}, \text{opening proofs})$

The difference here is that we also feed the last generated challenge into $H$. This makes the outputs from all previous rounds recursively involved in the computation of the current challenge, thus eliminating the vulnerability.

References

[1] Ariel Gabizon, Zachary J. Williamson, Oana Ciobotaru. PlonK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge.