You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
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^d mults 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 to q[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 text was updated successfully, but these errors were encountered:
The evaluations of multilinear quotients in Zeromorph
compute_multilinear_quotients
could be computed as a byproduct of Sumcheckpartially_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^d
mults and10*2^{d+1}
adds, whered
is the circuit size (~ 19, 20).It requires minor changes:
partially_evaluted_polynomials
containingpoly_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_evaluations
with2^d
rows 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_0
as a first challenge, in Zm, the first required challenge isu_{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 skipscompute_multilinear_quotients
.The text was updated successfully, but these errors were encountered: