Write-up of ZK Hack III Puzzle 1: Zero-Sum Game

puzzle-zero-sum-game-writeup.md

Write-up of ZK Hack III Puzzle 1: Zero-Sum Game

The puzzle repository is here, and this is the puzzle description for reference:

    ______ _   __  _   _            _
    |___  /| | / / | | | |          | |
       / / | |/ /  | |_| | __ _  ___| | __
      / /  |    \  |  _  |/ _` |/ __| |/ /
    ./ /___| |\  \ | | | | (_| | (__|   <
    \_____/\_| \_/ \_| |_/\__,_|\___|_|\_\

Bob has designed a new private payments protocol design, where every note comes with a secret 
polynomial f whose sum over a specific set is zero. This is enforced using a sumcheck protocol.
Once a note is spent, f is modified to a different polynomial whose sum isn't zero. One day, 
after an interesting conversation with her friends, Alice got an idea for an attack that can 
potentially allow her to double spend notes.

Alice successfully double spent a note. Can you figure out how she did it?

Be very careful, if the verifier somehow learns the sum of the modified f, 
they can deanonymize you.

In the rest of protocol that is not described here, the masking polynomial used by 
the prover is opened twice. Therefore, the masking polynomial cannot be a 
constant polynomial.

To see examples of sumcheck, you can review the protocol described in 
https://github.com/arkworks-rs/marlin/blob/master/diagram/diagram.pdf.

The univariate sum-check protocol

The univariate sum-check condition is

$$ \sum_{H}f(X) = 0 $$

where $f(X)$ is a polynomial of degree $D$ and $H$ is the domain set.

The univariate sum-check protocol relies on the fact that proving the above condition is equivalent to proving that there exist two polynomials $h(X)$ and $g(X)$ such that:

$$ \begin{align*} f(X) = X\cdot g(X) &+ h(X)\cdot \mathbb{Z}_H(X) \quad \text{and}\ deg(h) &\le D - N\ deg(g) &< N - 1 \end{align*} $$ where $\mathbb{Z}_H(X)$ is the vanishing polynomial over the domain $H$.

See Thaler 10.3.1 for the proof of the above.

In order to make this protocol zero-knowledge (i.e. not leak information about $f(X)$), the Aurora team added a masking step where the polynomial $f(X)$ is masked with a randomly sampled polynomial $q(X)$. The polynomial $q(X)$ is chosen such that its sum over $H$ is also 0 (i.e. $\sum_H q(X) = 0$).

This masking is done in an interactive way as shown below:

The prover first commits to a randomly sampled masking polynomial $q(X)$. The verifier then randomly samples a point $c$. A masked polynomial is constructed as a linear combination of $f(X)$ and $q(X)$ using $c$. The prover and verifier then operate on this masked polynomial to generate the sum-check proof and to verify.

Bob's version

Bob's version of the sum-check protocol is similar to the one described above except for how masking is done. In Bob's version, the verifier doesn't sample a random point and the masked polynomial is simply $f(X) + q(X)$. Polynomial $q(X)$ is denoted as $s(X)$ in the code. The verifying condition is:

$$ \begin{align*} f(X) + s(X) = X\cdot &g(X) + h(X)\cdot \mathbb{Z}_H(X) \quad \text{and}\\ deg(h) &\le D - N\\ deg(g) &< N - 1 \end{align*} $$

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
};

if lhs != rhs {
    return Err(Error::IncorrectSum);
}

After Alice spends a note, the polynomial $f(X)$ corresponding to that note would no longer sum to 0 over $H$. If $s(X)$ is randomly sampled as described above then it's impossible for Alice to come up with a valid proof for the statement $\sum_{H}f(X) = 0$.

Cheating proof

We exploit the improper masking in Bob's protocol and forge a proof by setting the masking polynomial $s(X)$ to be $-f(X)$. This makes the masked polynomial identically zero. The zero polynomial also satisfies the univariate sum-check condition $\sum_{H}f(X) = 0$ and thus we can create a valid proof:

$$ s(X) = -f(X)\\ h(X) = 0\\ g(X) = 0 $$

Prover code

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>> {
    /*
    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.
    */

    // Initialize Fiat-Shamir RNG for non-interactive proofs
    let mut fs_rng = FS::initialize(&to_bytes![&PROTOCOL_NAME, statement].unwrap());

    // Define the masking polynomial s as the negation (additive inverse) of the polynomial f over the field F
    let s = -f.polynomial().clone();
    let s = LabeledPolynomial::new("s".into(), s, None, Some(1));

    // The masked polynomial as defined in the verifier is the sum of the polynomial f and the masking polynomial s
    let masked = f.polynomial() + s.polynomial();
    // Since s is the additive inverse of f, the masked polynomial is identically 0
    assert_eq!(masked, DensePolynomial::from_coefficients_slice(&[F::zero()]));
    // This also implies that the masked polynomial satisfies the sumcheck property i.e. its sum over the domain is 0

    // Decompose the masked polynomial into polynomials h (degree < D - N) and g (degree < N) through dividing it by the vanishing polynomial of the domain
    // Since the masked polynomial satisfies the sumcheck property, the degree of g is < N - 1
    let (h, g) = masked.divide_by_vanishing_poly(statement.domain).unwrap();
    let h = LabeledPolynomial::new("h".into(), h, None, Some(1));
    let g = LabeledPolynomial::new("g".into(), g, Some(statement.domain.size() - 2), Some(1));

    // In this proof, since the masked polynomial is identically 0, both h and g would also be identically 0
    assert_eq!(h.polynomial().clone(), DensePolynomial::from_coefficients_slice(&[F::zero()]));
    assert_eq!(g.polynomial().clone(), DensePolynomial::from_coefficients_slice(&[F::zero()]));

    // Generate polynomial commitments for the polynomials s, h, g
    let (commitments, rands) = PC::commit(&ck, &[s.clone(), h.clone(), g.clone()], Some(rng)).unwrap();

    let f_commitment = LabeledCommitment::new("f".into(), statement.f.clone(), None);
    let s_commitment = commitments[0].clone();
    let h_commitment = commitments[1].clone();
    let g_commitment = commitments[2].clone();

    // Progress RNG state
    fs_rng.absorb(&to_bytes![s_commitment.commitment().clone(), h_commitment.commitment().clone(), g_commitment.commitment().clone()].unwrap());

    // Generate the polynomial commitment proof and the openings
    let xi = F::rand(&mut fs_rng);
    let opening_challenge = F::rand(&mut fs_rng);

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

    let polynomials = vec![f, &s, &h, &g];
    let commitments = vec![&f_commitment, &s_commitment, &h_commitment, &g_commitment];
    let rands = vec![f_rand, &rands[0], &rands[1], &rands[2]];

    let pc_proof = PC::batch_open(
        &ck,
        polynomials,
        commitments,
        &query_set,
        opening_challenge,
        rands,
        Some(rng),
    ).unwrap();

    let f_opening = f.evaluate(&xi);
    let s_opening = s.evaluate(&xi);
    let h_opening = h.evaluate(&xi);
    let g_opening = g.evaluate(&xi);

    // Sanity checks for the openings
    assert_eq!(f_opening, -s_opening);
    assert_eq!(h_opening, F::zero());
    assert_eq!(g_opening, F::zero());

    // Return the zk proof
    Ok(Proof {
        f_opening,
        s: s_commitment.commitment().clone(),
        s_opening,
        h: h_commitment.commitment().clone(),
        h_opening,
        g: g_commitment.commitment().clone(),
        g_opening,
        pc_proof,
    })

}