puzzle-zero-sum-game-writeup.md

Bob's protocol uses a sumcheck argument to prove the sum of $f$ over the evaluation domain $D = (a^0, a^1, ..., a^{15})$ where a is an element of order 16, i.e. $a^{16} = 1$ and $a^1, ..., a^{15} \neq 1$. It uses a polynomial s randomly generated by the prover to mask his polynomial f and preserve anonymity.

Here is the verifier algorithm as implemented in verifier.rs:

1. Initialize Fiat-Shamir randomness with protocol name, statement (domain D, commitment to f, claimed sum), and commitments to s, h, g.
2. Generate a random $\xi$ and an opening challenge.
3. Check the batch proof for the claimed evaluations of f, s, h, g at $\xi$.
4. Verify that $deg(g) <= |D|$ - 2 and $s(\xi) + f(\xi) = \xi * g(\xi) + h(\xi) * Z_h + sum * |D|^{-1}$ (where $Z_h$ is the vanishing polynomial of $D$).

The idea behind this check is that if $s + f = g + Z_h * h$ and $g(x) = \beta + x * g'(x)$ then $\Sigma_{d \in D} (f+s)(d) = \Sigma_{d \in D} (g(d) + Z_h(d) * h(d)) = \Sigma_{d \in D} g(d) = \beta * |D|^{-1}$. The proof of the last transition is similar to that of lemma 5.4 from the aurora paper.

There are 2 things wrong with this:

1. as is, the verifier interprets the sum of s + f as the sum of f,
2. the prover can choose s such that it cancels out with f (to avoid this, the verifier should generate a random field element c after V has committed to s, and then run sumcheck for $c * f + s$. Such approach is used in Aurora).

This leads to a following algorithm for a malicious prover (claiming sum = 0):

1. Set $s = -f$, $g = h = 0$.
2. Commit to s, g, h.
3. Initialize Fiat-Shamir randomness with Protocol name, statement, commitments to s, h, g.
4. Generate a random $\xi$ and an opening challenge.
5. Evaluate f, s, h, g at $\xi$ and generate a batch proof.

The only information that V learns is $f(\xi)$, which is not enough to deanonymize P (assuming that $deg(g) > 1$).