Zeromorph partial quotients as a byproduct of Sumcheck

[iakovenkos]

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:

1. 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.
2. 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.