[M0lecon] Plonky Rust

index

Plonky Rusty

Solvers: M Mard ,
R Rec
Authors: Drago, mr96
Category: Crypto
Points: 303
Solves: 8
Flag: ptm{d0_n07_0p71m1z3_y0ur_p0lyn0m14l_c0mm17m3n75!}

Do you want to become a rich cryptobro? Start by breaking PCSs!

main.rs

use num_bigint::BigUint;
use plonkish_backend::{
    halo2_curves::bn256::{Bn256, Fr},
    pcs::{multilinear::Gemini, univariate::UnivariateKzg, PolynomialCommitmentScheme},
    poly::multilinear::MultilinearPolynomial,
    util::{
        arithmetic::{modulus, Field, PrimeField},
        transcript::{
            FieldTranscript, FieldTranscriptRead, FieldTranscriptWrite, InMemoryTranscript,
            Keccak256Transcript,
        },
    },
    Error as PlonkishError,
};
use rand::{rngs::OsRng, RngCore};
use std::io::{self, Write};
use bincode::{serialize, deserialize};
use base64;
 
 
type Transcript = Keccak256Transcript<std::io::Cursor<Vec<u8>>>;
type Pcs = Gemini<UnivariateKzg<Bn256>>;
type Commitment = <Pcs as PolynomialCommitmentScheme<Fr>>::Commitment;
type CommitmentChunk = <Pcs as PolynomialCommitmentScheme<Fr>>::CommitmentChunk;
type UniKzg = UnivariateKzg<Bn256>;
 
// #[allow(dead_code)]
#[derive(Clone, Debug)]
struct Challenge {
    point: Vec<Fr>,
    target_value: Fr,
}
 
 
struct Verifier {
    vp: <Pcs as PolynomialCommitmentScheme<Fr>>::VerifierParam,
}
 
impl Verifier {
    fn new(vp: <Pcs as PolynomialCommitmentScheme<Fr>>::VerifierParam) -> Self {
        Self { vp }
    }
 
    fn issue_challenge(&self, num_vars: usize, rng: &mut impl RngCore) -> Challenge {
        let mut point = Vec::with_capacity(num_vars);
        for _ in 0..num_vars {
            point.push(Fr::random(&mut *rng));
        }
        let target_value = Fr::random(&mut *rng);
        Challenge {
            point,
            target_value,
        }
    }
 
    fn verify(
        &self,
        encoded_commitment: &Vec<u8>,
        challenge: &Challenge,
        encoded_proof: &Vec<u8>,
    ) -> Result<(), PlonkishError> {
        let commitment = Pcs::read_commitment(&self.vp, &mut Transcript::from_proof((), encoded_commitment.as_slice()))?;
        let mut transcript = Transcript::from_proof((), encoded_proof.as_slice());
 
        Pcs::verify(
            &self.vp,
            &commitment,
            &challenge.point,
            &challenge.target_value,
            &mut transcript,
        )
    }
}
 
 
fn fr_to_decimal(fr: &Fr) -> String {
    let repr = fr.to_repr();
    BigUint::from_bytes_le(repr.as_ref()).to_string()
}
 
fn format_challenge(challenge: &Challenge) -> String {
    let point = challenge
        .point
        .iter()
        .map(fr_to_decimal)
        .collect::<Vec<_>>()
        .join(",");
    let target_value = fr_to_decimal(&challenge.target_value);
    format!("{},{}", point, target_value)
}
 
fn prompt_line(prompt: &str) -> Result<String, PlonkishError> {
    print!("{}", prompt);
    io::stdout()
        .flush()
        .map_err(|err| PlonkishError::InvalidPcsOpen(err.to_string()))?;
    let mut input = String::new();
    io::stdin()
        .read_line(&mut input)
        .map_err(|err| PlonkishError::InvalidPcsOpen(err.to_string()))?;
    let trimmed = input.trim();
    if trimmed.is_empty() {
        return Err(PlonkishError::InvalidPcsOpen(
            "Received empty input from prover".to_string(),
        ));
    }
    Ok(trimmed.to_string())
}
 
fn read_hex_line(prompt: &str) -> Result<Vec<u8>, PlonkishError> {
    let line = prompt_line(prompt)?;
    hex::decode(&line)
        .map_err(|err| PlonkishError::InvalidPcsOpen(format!("Invalid hex input: {}", err)))
}
 
fn win() {
    if let Ok(flag) = std::env::var("FLAG") {
        println!("{}", flag);
    } else {
        println!("WIN");
    }
}
 
fn main() -> Result<(), PlonkishError> {
    let num_vars = 3usize;
    let poly_size = 1 << num_vars;
    let mut rng = OsRng;
 
    let param = Pcs::setup(poly_size, 1, &mut rng)?;
    let (pp, vp) = Pcs::trim(&param, poly_size, 1)?;
 
 
    let serialized_pp = serialize(&pp).unwrap();
    println!(
        "Serialized prover parameters (base64): {}",
        base64::encode(&serialized_pp)
    );
 
     let verifier = Verifier::new(vp);
 
    let commitment_bytes = read_hex_line("Send commitment (hex): ")?;
 
    let challenge = verifier.issue_challenge(num_vars, &mut rng);
    println!("Challenge: {}", format_challenge(&challenge));
 
    let proof_bytes = read_hex_line("Send proof (hex): ")?;
    let result = verifier.verify(&commitment_bytes, &challenge, &proof_bytes);
    match result {
        Ok(()) => win(),
        Err(err) => {
            println!("Your proof did not verify :(");
        }
    }
 
 
    Ok(())
}

Introduction to Polynomial Commitment Scheme (PCS)

A polynomial commitment scheme lets a prover publish a short commitment to a polynomial and later convince a verifier that the polynomial evaluates to a stated value at a chosen point, it usually happens without revealing the entire polynomial.

A standard formalization has 6 algorithms

Setup
Commit
Open
Verify polynomial
Create Witness
Verify Evaluation

This altogether allows people to commit to a polynomial to produce an evaluation proof against the original commitment. For some general usage case, we have Kate Zaverucha Goldberg (KZG). In KZG it gives constant-size commitments and constant size evaluation proofs, which is why it’s used in modern SNARKs.

The KZG / PolyCommitDL Construction

The KZG mechanism relies on the simple algebraic fact that for any polynomial $\varphi(x)$ , point $i$ , and value $v=\varphi(i)$ , the polynomial $(x - i)$ perfectly divides $(\varphi(x) - v)$ . The scheme operates in a bilinear pairing setting.

1. Trusted Setup: A trusted party generates a secret random value $\alpha \in \mathbb{F}_q^*$ , and publishes public parameters known as a Structured Reference String (SRS). For a polynomial of maximum degree $t$ , the SRS includes:

\{g_1, g_1^{\alpha}, g_1^{\alpha^2}, \dots, g_1^{\alpha^t}\} \quad \text{and} \quad \{g_2, g_2^{\alpha}\}

2. Commit: To commit to a polynomial $\varphi(x) = \sum_{j=0}^{t} c_j x^j$ , the prover uses the SRS to compute the commitment “at $\alpha$ in the exponent”:

C = g_1^{\varphi(\alpha)} \in G_1

3. Open: To prove that $\varphi(i) = v$ for some point $i$ and value $v$ , the prover first computes the quotient polynomial:

\psi_i(x) = \frac{\varphi(x) - v}{x - i}

The evaluation proof, or witness, is the quotient polynomial evaluated at $\alpha$ in the exponent:

w_i = g_1^{\psi_i(\alpha)} \in G_1

4. Verify Evaluation: The verifier checks that the commitment, witness, and claimed value are consistent by performing a single pairing check. This check ties together the commitment $C$ , the witness $w_i$ , the SRS, and the claimed evaluation $(i,v)$ :

\boxed{ e(C, g_2) \stackrel{?}{=} e(w_i, g_2^{\alpha} \cdot g_2^{-i}) \cdot e(g_1, g_2)^{v} }

Why It Works

The verification equation holds true if and only if the prover is honest. The check is a direct consequence of the polynomial identity $\varphi(x) = \psi_i(x)(x-i) + v$ and the properties of bilinear maps. We can see this by substituting the definitions into the equation:

\begin{aligned} e(C,g_2) &= e\!\big(g_1^{\,f(\alpha)},\,g_2\big) = e(g_1,g_2)^{\,f(\alpha)} \\ &= e(g_1,g_2)^{\,\psi_i(\alpha)(\alpha-i)} \cdot e(g_1,g_2)^{\,v} \\ &= e\!\big(g_1^{\,\psi_i(\alpha)},\,g_2^{\,\alpha-i}\big)\cdot e(g_1,g_2)^{\,v} \\ &= e\!\big(w_i,\, g_2^{\,\alpha}/g_2^{\,i}\big)\cdot e(g_1,g_2)^{\,v}, \end{aligned}

Because the commitment $C$ and the witness $w_i$ are both single group elements, the scheme provides constant-size commitments and proofs, which is why it is so widely used inside modern SNARKs.

Soundness

When the claim being proved is $\psi(i) = v$ , soundness means a cheating prover should not be able to convince an honest verifier to accept a false pair $(i,v)$ except with negligible probability.

For the polynomial commitment scheme, requirement is exactly what evaluation binding formalizes, no adversary should be able to produce two different accepted evaluations at the same point for the same commitment.

In zero knowledge systems, soundness is on of the important attributes along the completeness and zero knowledge, where it checks that false statement doesn’t verify which is why a break in evlauation binding means soundness failure for any protocol that depends on that opening.

It’s only the optimized Gemini variant is vulnerable since in original Gemini, each round checks a relation at both signs of the same challenge and also opens the next polynomial at the positive power point

f^{(j+1)}(\rho^2)

Then it will check the split and fold identity which will look like

2 \rho \times f^{(j+1)}(\rho^2) \stackrel{?}{=} (1-u_j)\rho(f^{(j)}(\rho) + f^{j}(-\rho)) + u_j(f^{(j)}(\rho) - f^{(j)}(- \rho))

It’s wayyy too messy isn’t it? Like how life goes, let me arrange it easier

f^{(j+1)} (\rho^2) \stackrel{?}{=} (1-u_j) \frac{f^{(j)}(\rho) + f^{(j)}(- \rho)}{2} + u_j \frac{f^{(j)}(\rho) - f^{(j)}(- \rho)}{2 \rho}

The intuition of this is that querying at $\rho$ and $- \rho$ pins down even and odd parts of $f^{(j)}$ and the extra opening at $f^{(j+1)}(\rho^2)$ forces those parts to fold consistently into the next round. If you cheese your w ay by replacing $f^{(j)}$ with $g^{(j)} = f^{(j)} + \epsilon$ the discrepancy $\epsilon$ can’t basically “hide” because it has to satisfy all these openings and the folding equations at the same random $\rho$

Well, the optimized protocol changes the recursion so that step $j$ actually uses $\rho^{2^j}$ instead of the same $\rho$ each time. This has huge impact since after some algebraic substitution, some “positive point” checks essentially just disappear So $f^{(j)}(\rho^{2^j})$ for several $j \ge 1$ never gets enforced. This leaves the verification equation under constrained and this means under-constrained circuits in ZK audits. Where some constraints that should exist just aren’t there so a prover has degrees of freedom to tackle this intermediate values without getting caught.

Attack on Gemini Polynomial Commitment Scheme

I was thinking about Heartbleed vulnerability until @Rec suggested me looking at this paper (https://eprint.iacr.org/2025/565.pdf) which our case was $n = 3$ case

The vulnerability was related to the lack of soundess of the optimized Gemini protocol. What the fuck is soundness you say, well it is well explained in this paper (https://eprint.iacr.org/2024/514.pdf) at section 2.2. Soundness means if a dishonest prover can’t convince an honest verifier of the truthfulness of a false statement with high probability. Nonetheless, vulnerability is related to under-constrained circuits refer to instances during the design or programming Implementation of circuits where certain constraints are either not set or incompletely set. This can result in the circuit having uncertain behavior or producing unintended results.

n = 3 attack

The server fixes num_vars = 3 so we have the paper’s simplest case

Verifier samples a random point $u = (u_0, u_1, u_2)$ and a random target value $t$ . and honest prover needs to prove $f(u) = t$

Let the true evaluation be

v := f(u_0, u_1, u_2)

The optimized Gemini bug allows a malicious prover to commit to tampered intermediate folded polynomials so the verifier accepts any chosen value $t$ even if $v \ne t$

What can we do with this? we can pick free parameter $\lambda$ and patch the fold polynomials.

For $n = 3$ , the attacker sets

g^{(1)}(X) = f^{(1)}(X) + \varepsilon^{(1)}(X), \qquad g^{(2)}(X) = f^{(2)}(X) + \varepsilon^{(2)}(X)

with

\varepsilon^{(1)}(X) := 4\lambda X\big((1-u_1)X-u_1\big)

\varepsilon^{(2)}(X) := 2\lambda\big((1-u_1)^2X-u_1^2\big)

After this, the prover claims a fake evaluation $w = t$ by choosing $\lambda$ so that the verifier’s reconstructed value shifts by exactly $t-v$

\lambda = \frac{t - v}{2\Big((1-u_1)^2u_2 - u_1^2(1-u_2)\Big)}

This works whenever the denominator is non-zero (It fails with negligible probability in a large prime field)

Formulating Attack

Well it’s time to make exploits after math right?

1. Rebuilding Gemini’s fold chain (honestly)

Gemini starts from the multilinear evaluation table size of $2^n$ and treats it as coefficients of a univariate $f^{(0)}$ , then repeatedly “split-and-fold” halves using the challenge coordinates $u_j$

We can do this by

out[i] = (1-x) * prev[2i] + x * prev[2i+1]

This is fold_evals. We are building

fs[0] = f^{(0)}
fs[1] = f^{(1)}
fs[2] = f^{(2)}

2. Compute $\lambda$ to force the target $t$

let denom = 2 * ((1 - u1)^2 * u2 - u1^2 * (1 - u2));
let lam = (t - poly.evaluate(u)) * denom.invert().expect("inv");

This is translated version of

\lambda = \frac{t-v}{2\big((1-u_1)^2u_2-u_1^2(1-u_2)\big)}

So it’s quite straight forward

3. Add $\varepsilon^{(1)}$ and $\varepsilon^{(2)}$ by tweaking only a few coefficients

we can expand the perturbations

\varepsilon^{(1)}(X) = 4\lambda\big((1-u_1)X^2 - u_1X\big)

so only degree-1 and degree-2 coefficients change

fs[1][1] -= 4 * lam * u1;
fs[1][2] += 4 * lam * (1 - u1);

And

\varepsilon^{(2)}(X) = 2\lambda\big((1-u_1)^2X - u_1^2\big)

so that only constant and degree-1 coefficients change

fs[2][0] -= 2 * lam * u1 * u1;
fs[2][1] += 2 * lam * (1 - u1) * (1 - u1);

At this point we have built $g^{(1)}$ and $g^{(2)}$ that “cancel out” in the optimized verifier equations, so the final check will pass while claiming the fake target $t$

Full Exploit

exploit.rs

use base64::engine::general_purpose::{STANDARD as B64, STANDARD_NO_PAD as B64N};
use base64::Engine;
 
use bincode::deserialize;
use num_bigint::BigUint;
use rand::rngs::OsRng;
use std::io::{self, Write};
 
use plonkish_backend as pb;
use pb::{
    halo2_curves::bn256::{Bn256, Fr},
    pcs::{
        multilinear::Gemini,
        univariate::UnivariateKzg,
        Evaluation,
        PolynomialCommitmentScheme as PCS,
    },
    poly::univariate::UnivariatePolynomial as U,
    util::{
        arithmetic::{Field, PrimeField as PF},
        transcript::{
            FieldTranscript,
            FieldTranscriptWrite,
            InMemoryTranscript,
            Keccak256Transcript as Tr,
        },
    },
    Error,
};
 
type PC = Gemini<UnivariateKzg<Bn256>>;
type Tx = Tr<std::io::Cursor<Vec<u8>>>;
 
fn read_b64_block(prompt: &str) -> Vec<u8> {
    print!("{prompt}");
    io::stdout().flush().unwrap();
 
    let mut s = String::new();
    loop {
        let mut line = String::new();
        if io::stdin().read_line(&mut line).unwrap() == 0 || line.trim().is_empty() {
            break;
        }
        s.push_str(line.trim());
    }
 
    B64.decode(s.as_bytes())
        .or_else(|_| B64N.decode(s.as_bytes()))
        .unwrap()
}
 
fn fr_from_decimal(dec: &str) -> Fr {
    let n = BigUint::parse_bytes(dec.as_bytes(), 10).unwrap();
    let le = n.to_bytes_le();
 
    let mut repr = <Fr as PF>::Repr::default();
    repr.as_mut()[..le.len()].copy_from_slice(&le);
 
    Fr::from_repr(repr).into_option().unwrap()
}
 
fn fold_evals(prev: &[Fr], x: &Fr) -> Vec<Fr> {
    let mut out = Vec::with_capacity(prev.len() >> 1);
    let a = Fr::ONE - *x;
 
    let mut i = 0;
    while i < prev.len() {
        out.push(a * prev[i] + (*x) * prev[i + 1]);
        i += 2;
    }
    out
}
 
/// Construct
    pp: &<PC as PCS<Fr>>::ProverParam,
    poly: &<PC as PCS<Fr>>::Polynomial,
    comm: &<PC as PCS<Fr>>::Commitment,
    u: &[Fr],
    t: &Fr,
    tr: &mut Tx,
) -> Result<(), Error> {
    let n = u.len();
    assert!(n >= 3);
 
    // fs[0] is original univariate polynomial 
    // fs[i] for i>=1 
    let mut fs = Vec::with_capacity(n);
    fs.push(U::monomial(poly.evals().to_vec()));
    for x in &u[..n - 1] {
        let next_coeffs = fold_evals(fs.last().unwrap().coeffs(), x);
        fs.push(U::monomial(next_coeffs));
    }
 
    // Constants and aliases 
    let two = Fr::ONE.double();
    let four = two.double();
    let u1 = u[1];
    let u2 = u[2];
    let denom = two * ((Fr::ONE - u1) * (Fr::ONE - u1) * u2 - u1 * u1 * (Fr::ONE - u2));
    let lam = (*t - poly.evaluate(u)) * denom.invert().expect("inv");
 
    fs[1][1] -= four * lam * u1;
    fs[1][2] += four * lam * (Fr::ONE - u1);
 
    fs[2][0] -= two * lam * u1 * u1;
    fs[2][1] += two * lam * (Fr::ONE - u1) * (Fr::ONE - u1);
 
    // Commitments
    let mut cs = vec![comm.clone()];
    cs.extend(UnivariateKzg::<Bn256>::batch_commit_and_write(pp, &fs[1..], tr)?);
 
    // Fiat–Shamir 
    let beta: Fr = tr.squeeze_challenge();
    let mut pts = Vec::with_capacity(n + 1);
    pts.push(beta);
 
    let mut s = beta;
    for _ in 0..n {
        pts.push(-s);
        s = s.square();
    }
 
    let mut ev = Vec::with_capacity(n + 1);
    ev.push(Evaluation::new(0, 0, fs[0].evaluate(&pts[0])));
    ev.push(Evaluation::new(0, 1, fs[0].evaluate(&pts[1])));
 
    for i in 1..n {
        let j = i + 1;
        ev.push(Evaluation::new(i, j, fs[i].evaluate(&pts[j])));
    }
 
    tr.write_field_elements(ev.iter().skip(1).map(|e| e.value()))?;
    UnivariateKzg::<Bn256>::batch_open(pp, &fs, &cs, &pts, &ev, tr)
}
 
fn main() {
    let pp: <PC as PCS<Fr>>::ProverParam =
        deserialize(&read_b64_block("PP no dih:\n> ")).unwrap();
    let mut rng = OsRng;
    let p = <<PC as PCS<Fr>>::Polynomial>::rand(3, &mut rng);
    let mut tc = Tx::new(());
    let c = <PC as PCS<Fr>>::commit_and_write(&pp, &p, &mut tc).unwrap();
    println!("com: {}", hex::encode(tc.into_proof()));
 
    print!("Challenge r0,r1,r2,t:\n> ");
    io::stdout().flush().unwrap();
 
    let mut line = String::new();
    io::stdin().read_line(&mut line).unwrap();
 
    let vals: Vec<Fr> = line
        .trim()
        .trim_start_matches("Challenge:")
        .split(',')
        .map(|s| fr_from_decimal(s.trim()))
        .collect();
 
    let r = vec![vals[0], vals[1], vals[2]];
    let t = vals[3];
 
    println!("eval@r: {}", hex::encode(p.evaluate(&r).to_repr()));
    let mut tp = Tx::new(());
    open_proof(&pp, &p, &c, &r, &t, &mut tp).unwrap();
    println!("proof: {}", hex::encode(tp.into_proof()));
}

[M0lecon] Plonky Rust

Plonky Rusty

Plonky Rusty

Introduction to Polynomial Commitment Scheme (PCS)

The KZG / PolyCommitDL Construction

Why It Works

Soundness

Attack on Gemini Polynomial Commitment Scheme

n = 3 attack

Formulating Attack

1. Rebuilding Gemini’s fold chain (honestly)

2. Compute λ\lambdaλ to force the target ttt

3. Add ε(1)\varepsilon^{(1)}ε(1) and ε(2)\varepsilon^{(2)}ε(2) by tweaking only a few coefficients

Full Exploit

2. Compute $\lambda$ to force the target $t$

3. Add $\varepsilon^{(1)}$ and $\varepsilon^{(2)}$ by tweaking only a few coefficients