UlrichHaboeck75
commented
3 years ago I spent another thought on it: in joint arithmetics, the size m' of the indexer domain K' at most 3 times larger than the size m of the standard indexer domain K. The concrete factor depends on the circuit, and I'd expect |K'| ≈2*|K|.
In terms of the most dominant operations needed for the inner sumcheck, i.e. fast Fourier transforms (FFT) and multi-scalar multiplications (MSM), we have the following counts assuming m'=2*m:
normal arithm.: 1 FFT(m)+ 1 FFT(4m) ≈ 3 FFT(m), 1 MSM(m)+1 MSM(3m)≈ 4 MSM(m), joint arithm.: 1 FFT(m') + 1 FFT(2 m')≈ 4 FFT(m), 2 MSM(m') ≈ 4 MSM(m).
Hence in terms of performance the joint arithmetics is expected to be as good as the standard one, with the benefit of a smaller prover and verifier key.
However, if one uses the domain extended dlog commitment scheme (which is just another name for segmentation),
then the verifier key might not benefit from a joint arithmetization: In our recursive setting where we always choose the segment size at factor (and often even below) of the size of the outer sumcheck domain H, the degree of the indexer polynomials matter. Although we have half the number of polynomials, their sizes and therefore their number of segment commitments increase by the factor m'/m, yielding the same number of segment commitments as before. Again this is under assumption of m'=2*m.
In this light, I consider a change to joint arithmetization as questionable.
Arkworks does a better way to handle the arithmetization for Marlin's inner sumcheck, see their PR. In short, instead of indexing the matrices A,B,C separately, each having their own row_M, col_M and row.col_M polynomial, they index the joint matrix which has the tripes (a_ij, b_ij,c_ij) as entries. The indexer domain is now large enought to host the number of entries != (0,0,0), and the polynomials are row,col, row.col, and val=(val_A,val_B,val_C). Overall it halves the number of indexer polynomials in the prover and verifier key. Moreover, the number of auxiliary precomputed polynomials for the arithmetic operation in the inner sumcheck are reduced, too.