The evaluations of multilinear quotients in Zeromorph compute_multilinear_quotients could be computed as a byproduct of Sumcheck partially_evaluate method.
How it affects the efficiency: If we use Zeromorph to prove evaluations of 10 multilinear polynomials passed through Sumcheck, it would save us 10*2^dmults and 10*2^{d+1} adds, where d is the circuit size (~ 19, 20).
It requires minor changes:
instead of updating top rows in partially_evaluated_polynomials as we currently do, we set up two tables:
partially_evaluted_polynomials containing poly_view[j][i] + round_challenge * (poly_view[j][i + 1] - poly_view[j][i]) where we release memory instead of rewriting top rows once the prover gets next challenge, they are equal to f_k[l] = g[l] + u_challenge[log_N - k] * q[l] in Zm
zeromorph_quotients_evaluations with 2^d rows containing differences poly_view[j][i + 1] - poly_view[j][i] as currently computed in partially_evaluate, they are equal toq[l] = f_k[size_q + l] - f_k[l] in Zm.
re-indexing of challenges: in Sumcheck we get u_0 as a first challenge, in Zm, the first required challenge is u_{d-1}
At the end of Sumcheck, zeromorph_quotients_evaluations would contain the coefficents of the univariates the prover is committing to when proving the evaluations and skips compute_multilinear_quotients.
The evaluations of multilinear quotients in Zeromorph
compute_multilinear_quotientscould be computed as a byproduct of Sumcheckpartially_evaluatemethod.How it affects the efficiency: If we use Zeromorph to prove evaluations of 10 multilinear polynomials passed through Sumcheck, it would save us
10*2^dmults and10*2^{d+1}adds, wheredis the circuit size (~ 19, 20).It requires minor changes:
partially_evaluted_polynomialscontainingpoly_view[j][i] + round_challenge * (poly_view[j][i + 1] - poly_view[j][i])where we release memory instead of rewriting top rows once the prover gets next challenge, they are equal to f_k[l] = g[l] + u_challenge[log_N - k] * q[l] in Zmzeromorph_quotients_evaluationswith2^drows containing differencespoly_view[j][i + 1] - poly_view[j][i]as currently computed in partially_evaluate, they are equal toq[l] = f_k[size_q + l] - f_k[l]in Zm.u_0as a first challenge, in Zm, the first required challenge isu_{d-1}At the end of Sumcheck,
zeromorph_quotients_evaluationswould contain the coefficents of the univariates the prover is committing to when proving the evaluations and skipscompute_multilinear_quotients.