Folded Zip+

[agarreta]

Small variation of Zip+ that halves proof sizes (details to follow)

[frozenspider]

Here's how folded Zip+ works:

P and V now do the folding trick, reducing the degree of binary polynomials by $N$ times (if folding factor $N$ is 4x, it will be 8 instead of 32)

• Before commitment, P does the folding of binary polynomial witness MLEs by splitting each evaluation into lower and upper half, which are then concatenated to form a MLE with twice the number of evaluations. Such action increases number of variables by one.

  • This can be done iteratively to further reduce the degree at the cost of increased number of variables.

• When proving folded wintess columns with Zip+, P uses an extended evaluation point ${r_{0}}_{ext} = r_0 \lVert \gamma$, where :

  • $r_0$ is the evaluation point for regular Zip+
  • $\gamma = (\gamma_1, \dots, \gamma_k)$ (where $k = \log_2 N$) are newly sampled random challenges

• V uses the exact same logic as P to reconstruct ${r_{0}}_{ext}$

• To verify folded Zip+ proof, V, uses alpha-projection of the column's lifted-eval polynomial down to a single scalar in $F_q$ as it does for regular Zip+, but it folds the column first.

  • It does so by splitting lifted evals into $N$ chunks (where $N$ is the folding factor), and doing chunkwise projection $P_i = \langle \alpha, \bar u^{(i)} \rangle$, where
    • $\bar{u} = \bar{u}^{(1)} \lVert \bar{u}^{(2)} \lVert \dots \lVert \bar{u}^{(N)}$ is the column's (non-folded) lifted-eval coefficients in $F_q[X]$, chunked onto $N$ chunks of equal length
    • $\alpha$ are sampled random challenges, same as in regular Zip+
  • It then MLE-evaluates $P_i$ at the folding challenges $\gamma$:
    • Viewing $(P_0, \dots, P_{N-1})$ as the values of a $k$-variable multilinear polynomial $\widetilde P$ on $\{0,1\}^k$, the final eval-claim is
      • $\widetilde{P}$ $(\gamma) = \sum_{i=0}^{N-1} \widetilde{\mathrm{eq}} (\mathrm{bin}(i), \gamma) \cdot P_i$
  • When $N = 1$ (non-folded case), it converges to the same dot product as before.