puzzle-zero-sum-game.md

The write-up for puzzle-zero-sum-game

First of all if we want to open a polynomial f(x) at a set of points which are all the points on the domain H by KZG10 batch opening. $$ H = (1, \omega, \omega^2,...,\omega^{n-1}), with \ w^n=1. $$ The vanishing polynomial over H takes an concise form $v_H(x)=\prod_{i=0}^{n-1}(x - \omega^i) = x^n -1$.

The polynomial for computing witness is

$$h(x) = \frac{f(x) - p(x)}{\prod_{i=0}^{n-1}(x - \omega^i)}$$

where $p(x)$ is the remainder of the polynomial division $f(x)/\prod_{i=0}^{n-1}(x - \omega^i)$ and for $a \in H, f(a) = p(a)$.

The polynomial $p(x)$ is also a Lagrange interpolation polynomial over domain H,

$$p(x) = \sum_{i=0}^{n-1} f(\omega^i) \cdot L_i(x) \ = p_0 + p_1 \cdot x + ... + p+{n-1}\cdot x^{n-1}$$

So the grand sum of polynomial over domain H is

$$\sum_{a \in H} p(x)= f(\omega^0) + f(\omega^1) + ... + f(\omega^{n-1})$$

and

$$\sum_{a \in H} p(x)= p(\omega^0) + p(\omega^1) + ... + p(\omega^{n-1})\\ = p_0 + p_1 \cdot \omega^0 + ... + p_{n-1} \cdot \omega^{0} \\ = p_0 + p_1 \cdot \omega^1 + ... + p_{n-1} \cdot \omega^{n-1} \\ ... \\ = p_0 + p_1 \cdot \omega^{n-1} + ... + p_{n-1} \cdot \omega^{(n-1)(n-1)} \\ = n \cdot p_0 + 0 +... + 0 = n \cdot p_0$$

So we can get a conclusion, $p_0 = \frac{f(\omega^0)+ f(\omega^1) + ... + f(\omega^{n-1})}{n}$

we can rewrite $p(x)$ as

$$p(x) = x \cdot g(x) + \frac{f(\omega^0)+ f(\omega^1) + ... + f(\omega^{n-1})}{n}$$

So we can rewrite the polynomial for batch opening as

$$f(x) = h(x) \cdot (x^n-1) + x \cdot g(x) + \frac{f(\omega^0)+ f(\omega^1) + ... + f(\omega^{n-1})}{n}$$

This polynomial can be use as the univariate sumcheck protocol. The univariate sumcheck protocol enables the verifier to delegate the task of computing a grand sum to the prover.In other word, if we can get the polynomials $h(x)$ and $g(x)$, so that the equation $f(x) = h(x) \cdot (x^n-1) + x \cdot g(x) + \frac{c}{n}$ holds, we can convince $f(\omega^0)+ f(\omega^1) + ... + f(\omega^{n-1}) = c$。

Coming back to tht puzzle, $f(\omega^0)+ f(\omega^1) + ... + f(\omega^{n-1})$ is not equal to zero now. In order to verify success. we can constrcut the mask polynomial s(x), so that the sum of the grand sums of the polynomials $f(x)$ and $s(x)$ is equal to zero,i.e.

$$f(\omega^0)+ f(\omega^1) + ... + f(\omega^{n-1}) + s(\omega^0)+ s(\omega^1) + ... + s(\omega^{n-1}) = 0$$

The grand sums of the polynomials $f(x)$ is 0x36248AFF0，so we should construct $s(x)$ with the grand sum is -0x36248AFF0。

A solution is we can first copy $f(x)$ as $s(x)$, so that the sum of two grand sums is

$$f(\omega^0)+ f(\omega^1) + ... + f(\omega^{n-1}) + s(\omega^0)+ s(\omega^1) + ... + s(\omega^{n-1}) = 2 \times 0x36248AFF0$$

Then we modify constant term of $s(x)$ so that each $s(\omega^i)$ can be reduced by $2 \times 0x36248AFF$.

let mut coeffs: Vec<F>  = f.polynomial().coeffs().into_iter().map(|coeff| coeff.clone()).collect();
coeffs[0] = coeffs[0] + F::from(908364543u64).double().neg(); // 908364543u64 = 0x36248AFF

Due to n=16 in the puzzle, so all of the $s(\omega^i)$ are reduced by $2 \times 0x36248AFF \times 16 = 2 \times 0x36248AFF0$。

So that now

$$f(\omega^0)+ f(\omega^1) + ... + f(\omega^{n-1}) + s(\omega^0)+ s(\omega^1) + ... + s(\omega^{n-1}) = 0$$

Now we can construct the equation for verification successfully.

$$f(x) + s(x)= h(x) \cdot (x^n-1) + x \cdot g(x) + \frac{0}{n}$$