ZK Hack Puzzle Zero Sum Game.md

ZK Hack Puzzle Zero Sum Game

(Not sure if I have the correct solution but here we go 🙂)

Introduction

The puzzle asks us to construct a sumcheck prover that can prove the wrong sum (in this case 0) and successfully get verified.

After checking the proof that the prover need to generate, we realised that the sumcheck protocol used in the puzzle is univariate, based on polynomial commitments (in this case KZG) and low degree testing instead of a multiple round multilinear sumcheck protocol.

pub struct Proof<F: Field, PC: PolynomialCommitment<F, DensePolynomial<F>>> {
    pub f_opening: F,
    pub s: PC::Commitment,
    pub s_opening: F,
    pub g: PC::Commitment,
    pub g_opening: F,
    pub h: PC::Commitment,
    pub h_opening: F,
    pub pc_proof: PC::BatchProof,
}

The former is used in protocols such as Aurora and Marlin. For information about the later, I would recommend checking chapter 4 of Professor Justin Thaler's book or the implementation of arkworks.

Some Preparation Work

The randomness used by the verifier should be the same as the prover so we can just copy paste it to the prover

let mut fs_rng = FS::initialize(&to_bytes![&PROTOCOL_NAME, statement].unwrap());
fs_rng.absorb(&to_bytes![s, h, g].unwrap());
let xi = F::rand(&mut fs_rng);
let opening_challenge = F::rand(&mut fs_rng);

Getting Polynomial $g$ and $h$

After reading how the scheme works in the Aurora paper, we've found that (on page 11)

we observe that we can split any polynomial $f$ into two polynomials g and h such that $f (x) ≡ g(x) + ∏ _{α∈H} (x − α) · h(x)$ with $deg(g) < |H|$ and $deg(h) < d − |H|$; in particular, f and g agree on H, and thus so do their sums on H.

It can be coded up like this with the helps of arkworks:

let (h_poly, g_poly) = f
        .polynomial()
        .clone()
        .divide_by_vanishing_poly(statement.domain)
        .unwrap();
let g_poly = DensePolynomial::from_coefficients_slice(&g_poly.coeffs[1..]);

This is the same as code used as the Marlin Implementation

Getting Polynomial $s$

Now that we have polynomail $g$ and $h$ we only have polynomial $s$ left.

Inspecting how verifier checking is done, we found that

let card_inverse = statement.domain.size_as_field_element().inverse().unwrap();
let lhs = proof.s_opening + proof.f_opening;
let rhs = {
    let x_gx = xi * proof.g_opening;
    let zh_eval = statement.domain.evaluate_vanishing_polynomial(xi);

    x_gx + proof.h_opening * zh_eval + statement.sum * card_inverse
};

In this case $statement.sum = 0$ so we can ignore the last term (statement.sum $*$ card_inverse). We have $f (x) ≡ g(x) + ∏ _{α∈H} (x − α) · h(x)$ and lower the degree of $g(x)$ by $1$ through this line of code

let g_poly = DensePolynomial::from_coefficients_slice(&g_poly.coeffs[1..]);

This effectively got rid of the $x^0$ term of the original polynomial $g$ so the f_opening != x_gx + h_opening * zh_eval here. All we need is to subtract the $x^0$ term of polynomial $g$ from f_opening through polynomial $s$ then we got a matching equation.

let coeffs = vec![
        -g_poly.coeffs[0].clone(),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
    ];

    let s_poly = DensePolynomial::from_coefficients_slice(&coeffs);

Done

Now that we have all three polynomials $h$ $g$ and $s$, we have all we need to generate the proof. The puzzle is solved 🎉.

use ark_ff::{to_bytes, FftField};
use ark_poly::{univariate::DensePolynomial, EvaluationDomain, Polynomial, UVPolynomial};
use ark_poly_commit::{LabeledCommitment, LabeledPolynomial, PolynomialCommitment, QuerySet};
use ark_std::rand::RngCore;

use crate::{
    data_structures::{Proof, Statement},
    error::Error,
    rng::FiatShamirRng,
    PROTOCOL_NAME,
};

use ark_bls12_381::{Bls12_381, Fr as F};
use ark_poly_commit::marlin_pc::MarlinKZG10;
pub type PCM = MarlinKZG10<Bls12_381, DensePolynomial<F>>;

pub fn prove<
    F: FftField,
    PC: PolynomialCommitment<F, DensePolynomial<F>>,
    FS: FiatShamirRng,
    R: RngCore,
>(
    ck: &PC::CommitterKey,
    statement: &Statement<F, PC>,
    f: &LabeledPolynomial<F, DensePolynomial<F>>,
    f_rand: &PC::Randomness,
    rng: &mut R,
) -> Result<Proof<F, PC>, Error<PC::Error>> {
    /*
        ADD YOUR CODE HERE
    */
    /*
    In the rest of protocol that is not described here, the masking polynomial is opened twice. Therefore, the masking polynomial cannot be a constant polynomial.
    */

    let (h_poly, g_poly) = f
        .polynomial()
        .clone()
        .divide_by_vanishing_poly(statement.domain)
        .unwrap();

    let xi = F::rand(rng);

    let eval_f = f.polynomial().evaluate(&xi);
    let eval_g = g_poly.evaluate(&xi);
    let eval_h = h_poly.evaluate(&xi);

    assert_eq!(
        eval_f,
        eval_g + eval_h * statement.domain.evaluate_vanishing_polynomial(xi)
    );

    let coeffs = vec![
        -g_poly.coeffs[0].clone(),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
        F::from(0u64),
    ];

    let s_poly = DensePolynomial::from_coefficients_slice(&coeffs);

    let g_poly = DensePolynomial::from_coefficients_slice(&g_poly.coeffs[1..]);

    let xi = F::rand(rng);

    let eval_f = f.polynomial().evaluate(&xi);
    let eval_s = s_poly.evaluate(&xi);
    let eval_g = g_poly.evaluate(&xi);
    let eval_h = h_poly.evaluate(&xi);

    assert_eq!(
        eval_f + eval_s,
        eval_g * xi + eval_h * statement.domain.evaluate_vanishing_polynomial(xi)
    );

    let s_poly = LabeledPolynomial::new("s".into(), s_poly.clone(), None, Some(1));
    let g_poly = LabeledPolynomial::new(
        "g".into(),
        g_poly.clone(),
        Some(statement.domain.size() - 2),
        Some(1),
    );
    let h_poly = LabeledPolynomial::new("h".into(), h_poly.clone(), None, Some(1));

    let (s, s_rand) = PC::commit(&ck, &[s_poly.clone()], Some(rng)).unwrap();
    let (h, h_rand) = PC::commit(&ck, &[h_poly.clone()], Some(rng)).unwrap();
    let (g, g_rand) = PC::commit(&ck, &[g_poly.clone()], Some(rng)).unwrap();

    let s = s[0].commitment().clone();
    let h = h[0].commitment().clone();
    let g = g[0].commitment().clone();

    let mut fs_rng = FS::initialize(&to_bytes![&PROTOCOL_NAME, statement].unwrap());
    fs_rng.absorb(&to_bytes![s, h, g].unwrap());

    let xi = F::rand(&mut fs_rng);
    let opening_challenge = F::rand(&mut fs_rng);

    let eval_f = f.evaluate(&xi);
    let eval_s = s_poly.evaluate(&xi);
    let eval_g = g_poly.evaluate(&xi);
    let eval_h = h_poly.evaluate(&xi);

    let point_label = String::from("xi");
    let query_set = QuerySet::from([
        ("f".into(), (point_label.clone(), xi)),
        ("h".into(), (point_label.clone(), xi)),
        ("g".into(), (point_label.clone(), xi)),
        ("s".into(), (point_label, xi)),
    ]);

    let f_comm = LabeledCommitment::new("f".into(), statement.f.clone(), None);
    let s_comm = LabeledCommitment::new("s".into(), s.clone(), None);
    let h_comm = LabeledCommitment::new("h".into(), h.clone(), None);
    let g_comm = LabeledCommitment::new("g".into(), g.clone(), Some(statement.domain.size() - 2));

    let proof = PC::batch_open(
        ck,
        vec![f, &s_poly, &h_poly, &g_poly],
        vec![&f_comm, &s_comm, &h_comm, &g_comm],
        &query_set,
        opening_challenge,
        vec![f_rand, &s_rand[0], &h_rand[0], &g_rand[0]],
        Some(rng),
    )
    .unwrap();

    Ok(Proof {
        f_opening: eval_f,
        s,
        s_opening: eval_s,
        g,
        g_opening: eval_g,
        h,
        h_opening: eval_h,
        pc_proof: proof,
    })
}