The ongoing work implementing batched Spartan introduces a lot of code duplication, and made some existing duplication more apparent.
Generalize use of SumcheckEngine
The SumcheckEngine used in ppsnark.rs makes it easier to batch multiple Sumcheck claims into one instantiation.
With the changes introduced by the batched_ppsnark module, it also efficiently handles batching instances of different sizes without padding.
Since the batched SNARK requires handling instances of different sizes, it would be nice to use a common implementation to handle batching of multiple instances.
Moreover, this would allow more code reuse by noting that we are often evaluating the same type of Sumcheck claim (for example, proving the multi-linear evaluation, or for proving $0 = \sum_x eq(x)\cdot(Az(x)*Bz(x) - u \cdot Cz(x) - E(x)$).
Implement RelaxedR1CSSNARK through BatchedR1CSSNARK
The implementations of the BatchedR1CSSNARKTrait copy a lot of code from their original non-batched versions. To minimize duplication, it should be possible to implement the non-batched variants by using a batching of 1.
The overhead would mainly consist of having vectors containing only a single element.
Avoid computing evaluations of pow(tau)
Given the well-structured nature of $pow(\tau)$, we know that its list of evaluations is $[1, \tau, \tau^2, \ldots, \tau^{2^{n}-1}]$ (or rather, given the evaluation order of the variables, each power $\tau^i$ is placed at the index corresponding to the bit-reversed $i$) .
If we are computing $\sum_x pow(\tau;x)\cdot F(P_1(x),P_2(x), \ldots)$, then we can more efficiently compute the univariate polynomial in round $j$ (given previous challenges $r0,\ldots,r{j-1}$) as
$$
S'_{j,i}(X_j) = F(r0, \ldots ,r{j-1},X_j, i0,\ldots,i{n-j-2}), \quad i = (i0, \ldots, i{n-j-2}), i = \sum_{k=0}^{n-j-2} i_k \cdot 2^k
$$
The last polynomial corresponds to one of the terms in the sum that comes up when computing the evaluation_points of the combination function in Sumcheck.
The neat property here, is that we can factor out the term $\left( (1-X_j) + X_j \cdot \tau^{2^{n-j-1}} \right)$ from the polynomial, which means we need to evaluate it at one point less.
If we are using Sumcheck to check that $e = \sum_x pow(\tau;x)P(x)$, then we can compute the evaluations using approximately half as many operations.
huitseeker
commented
9 months ago
The ongoing work implementing batched Spartan introduces a lot of code duplication, and made some existing duplication more apparent.
Generalize use of
SumcheckEngineThe
SumcheckEngineused inppsnark.rsmakes it easier to batch multiple Sumcheck claims into one instantiation. With the changes introduced by thebatched_ppsnarkmodule, it also efficiently handles batching instances of different sizes without padding.Since the batched SNARK requires handling instances of different sizes, it would be nice to use a common implementation to handle batching of multiple instances.
Moreover, this would allow more code reuse by noting that we are often evaluating the same type of Sumcheck claim (for example, proving the multi-linear evaluation, or for proving $0 = \sum_x eq(x)\cdot(Az(x)*Bz(x) - u \cdot Cz(x) - E(x)$).
Implement
RelaxedR1CSSNARKthroughBatchedR1CSSNARKThe implementations of the
BatchedR1CSSNARKTraitcopy a lot of code from their original non-batched versions. To minimize duplication, it should be possible to implement the non-batched variants by using a batching of 1.The overhead would mainly consist of having vectors containing only a single element.
Avoid computing evaluations of
pow(tau)Given the well-structured nature of $pow(\tau)$, we know that its list of evaluations is $[1, \tau, \tau^2, \ldots, \tau^{2^{n}-1}]$ (or rather, given the evaluation order of the variables, each power $\tau^i$ is placed at the index corresponding to the bit-reversed $i$) .
If we are computing $\sum_x pow(\tau;x)\cdot F(P_1(x),P_2(x), \ldots)$, then we can more efficiently compute the univariate polynomial in round $j$ (given previous challenges $r0,\ldots,r{j-1}$) as
$$ S_j(Xj) = \left[ \prod{k=0}^{j-1} \left( (1-r_k) + r_k \cdot \tau^{2^{n-k-1}} \right) \right] \left( (1-X_j) + Xj \cdot \tau^{2^{n-j-1}} \right) \left[ \sum{i=0}^{2^{n-j-1}} \tau^i \cdot S'_{j,i}(X_j) \right] $$
where
$$ S'_{j,i}(X_j) = F(r0, \ldots ,r{j-1},X_j, i0,\ldots,i{n-j-2}), \quad i = (i0, \ldots, i{n-j-2}), i = \sum_{k=0}^{n-j-2} i_k \cdot 2^k $$
The last polynomial corresponds to one of the terms in the sum that comes up when computing the
evaluation_pointsof the combination function in Sumcheck.The neat property here, is that we can factor out the term $\left( (1-X_j) + X_j \cdot \tau^{2^{n-j-1}} \right)$ from the polynomial, which means we need to evaluate it at one point less.
If we are using Sumcheck to check that $e = \sum_x pow(\tau;x)P(x)$, then we can compute the evaluations using approximately half as many operations.