adr1anh
commented
1 year ago ID Polynomials
Start by noting that $ID(X0,\ldots,X{d-1}) = X_0 + X1 \cdot 2 + \cdots + X{d-1} \cdot 2^{d-1}$, and that $ID_j(\vec{X}) = (j-1)n + ID(\vec{X})$. As part of indexing from 0, I suggest we relabel these with $j=0,1,2$ so that $ID_j(\vec{X}) = j \cdot n + ID(\vec{X})$.
The state required to define $ID(X0,\ldots,X{d-1})$ is only $d$, and possibly $j$ in order to define $ID{j}(X{0},\ldots,X_{d-1})$ (since $n = 2^d$).
At round $\ell$ of Sumcheck, we will have had to partially evaluate it in $u0,\ldots, u{\ell-1}$ which are the verifier Sumcheck challenges. We define this partially evaluated polynomial as
$$ \begin{align} ID^{(\ell)}j( X\ell, \ldots, X_{d-1}) &= ID_j(u0,\ldots,u{\ell-1}, X\ell, \ldots, X{d-1}) \ &= \underbrace{\left( j \cdot n + \sum_{k=0}^{\ell-1} uk \cdot 2^k \right)}{c\ell} + X\ell \cdot 2^\ell + \left( \sum_{k=\ell+1}^{d-1} Xk \cdot 2^k \right) \ &= c\ell + X\ell \cdot 2^\ell + \left( \sum{k=\ell+1}^{d-1} X_k \cdot 2^k \right) \end{align} $$
Going from $ID_j^{(\ell)}$ to $IDj^{(\ell+1)}$ by evaluating $X\ell$ in $u\ell$ means we update the constant $c{\ell+1} \gets c\ell + u\ell \cdot 2^\ell$ and increment $\ell$ to $\ell+1$. This constant is part of the polynomial's state, and we initialize $c_0 = j\cdot n$.
When we are iterating through the edge $(h{\ell+1}, \ldots, h{d-1}) \in {0,1}^{d-\ell-1}$, we let $h = h{\ell+1} + h{\ell+2}\cdot 2 + \cdots h_{d-1} \cdot 2^{d-\ell-2}$.
$$ \begin{align} ID^{(\ell)}j( X\ell, h{\ell+1} \ldots, h{d-1}) &= c\ell + X\ell \cdot 2^\ell + \left( \sum_{k=\ell+1}^{d-1} hk \cdot 2^k \right) \ &= c\ell + X\ell \cdot 2^\ell + 2^{\ell+1}\cdot \left( \sum{k=\ell+1}^{d-1} hk \cdot 2^{k-(\ell+1)} \right) \ &= c\ell + X\ell \cdot 2^\ell + 2^{\ell+1}\cdot \left( \sum{k=0}^{d-\ell-2} h{\ell+1+k} \cdot 2^{k} \right) \ &= c\ell + X_\ell \cdot 2^\ell + 2^{\ell+1}\cdot h \ \end{align} $$
The first edge univariate is $U0(X\ell) := c\ell + X\ell \cdot 2^\ell$, and if we have the edge univariate $U{h}(X\ell)$, we obtain $U{h+1}(X\ell) = U{h}(X\ell) + 2^{\ell+1}$.
template <typename FF>
struct IDUnivariate {
FF constant{0}; // c_l
FF two_pow_l{1}; // 2^l
// Equal to ID_0
IDUnivariate() = default;
// Initialize to ID_j
IDUnivariate(size_t d, size_t j)
: constant{(1 << d) * j} {}
// Partially evaluate in X_l = u_l
void fold(const FF challenge /*u_l*/) {
constant += challenge * two_pow_l;
two_pow_l.self_dbl();
}
// Returns the (not-extended) univariate edge for the edge at index h
Univariate<FF, 2> current_edge(size_t h) const {
// Compute (c_l + 2^l * (2h)) + 2^l * X_l
return {constant + two_pow_l * h, two_pow_l};
}
}Note that in sumcheck_round.hpp, we have h equal to $2 \cdot h$ (the index is incremented by 2 at every loop), so we can simplify the computation of the edge.
We also realize that we don't need to store the number of variables $d$. We also don't need technically need to store the current round number $\ell$.
During the Sumcheck, both parties must run fold with the new challenge. After the last round, the veriifer can get the result of the evaluation by querying constant.
Motivation
We currently store too many preprocessed polynomials in the proving key, like
ID_1, ID_2, ID_3, andL_FIRSTandL_LAST. All of these can be efficiently evaluatable by the verifier, so they do not need to be committed. Moreover, it may be more efficient to derive their "edge extension" directly by exploiting their structure.