Trying to make sense of the split accumulation (folding) scheme in ProtoStar.

The big scary formula in Figure 3 is trying to show how to calculate vectors $\mathbf{e}$ and $\mathbf{e}_{j\in[1,d-1]}$. To understand how it’s constructed, we take the “relaxed” verifier check function

$$ \mathsf{V_{NARK}}^{relaxed}(\mathsf{acc}) = \sum_{j=0}^d \mu^{d-j}·f_j^\mathsf{V_{SPS}}(\mathsf{acc}) = \mathbf{e} $$

and apply it to the linear combination of the “fresh proof” $\pi$ and accumulator $\mathsf{acc}$ (vs just to $\mathsf{acc}$) with coefficients $(X, 1)$: $X·\pi + 1·\mathsf{acc}$, where $X$ is a free scalar variable (which we’ll see in a moment why we need it).

The whole expression we’re looking at, could be written down as

$$ \mathsf{V_{NARK}}^{relaxed}(X·\pi + \mathsf{acc}) = \sum_{j=0}^d (X+\mu)^{d-j}·f_j^\mathsf{V_{SPS}}(X·\pi + \mathsf{acc}) = \mathbf{e} + \sum_{j=1}^{d-1}X^j·\mathbf{e}_j $$

Note: in our linear combination, $\mu$ (coming from $\mathsf{acc}$) becomes $X+\mu$, because for “fresh proofs” $\mu_\pi=1$

Now, because $f_j^\mathsf{V_{SPS}}$ is a degree $j$ polynomial, and we’re multiplying it by $(X+\mu)^{d-j}$ — of degree $(d-j)$, we end up with maximum degree $d$ in $X$.

Everything else beside $X$ are just numbers (constants). So, we expand the formula and collect things around powers of $X$. Each power of $X$ will now have a coefficient in the form of a vector of size $\ell$.

$$ (X^0)·\sum_{j=0}^d \mu^{d-j}·f_j^\mathsf{V_{SPS}}(\mathsf{acc}) + X^d·\sum_{j=0}^d f_j^\mathsf{V_{SPS}}(\pi) + \sum_{j=1}^{d-1}X^j·\mathbf{e}_j $$

Here:

• The constant part (the coefficient of $X^0$) looks exactly like the definition of the vector $\mathbf{e}$ (this is also why we don’t need to pass $\mathbf{e}$ in the accumulator).
• The coefficient of $X^d$ should equal $\mathbf{0}^\ell$ — it’s the $\mathsf{V_{NARK}}$ expression to verify proof $\pi$.
• The coefficients of $X^j$, for $j \in [1, d-1]$, are vectors $\mathbf{e}_j$.

Each $\mathbf{e}_j$ will be a vector of polynomials (“cross-products”) of $\mu$ and various parts of $\pi$ and $\mathsf{acc}$ (parts of the witnesses and random challenges). The structure of these polynomials does not matter. We only need to calculate the numerical values.