More flexible folding factor.

[yczhangsjtu]

Is it possible to set a separate folding factor for different rounds?

Motivation: for each round, the prover needs to open 1 << folding_factor evaluations for each shift query. For a folding factor of 4, that means 16 evaluations for each query. This doesn't incur a large proof size for the intermediate rounds. However, for the first round, the leaf size can easily become large when multiple polynomials are opened in batch. In that case, it may be beneficial to start with a small folding factor in the first round, and switch to a larger one later.

[WizardOfMenlo]

Sure, changing folding parameter every round is relatively easy. To do so, one can replace folding_factor in params with an array (each for round). The parameter estimation is relatively easy to change accordingly.

An alternative that you might also want to explore, suppose that you want to batch evaluate f_1, ..., f_n at z.

1. Verifier sends alpha
2. Prover sends g = f_1 + alpha * f_2 + ... + alpha^{n-1} * f_n (you can actually send this at an higher rate and get an improvement! In this case, I think you also need an OOD sample).
3. Verifier samples z_1,...,z_t, queries f_j(z_i) and sets y_i = f_1(z_i) + alpha * f_2(z_i) + ... + alpha^{n-1} * f_n(z_i)
4. Run WHIR on g with as input the claim that g(z) = sum of evals of f_js and g(z_i) = y_i

This way, you are free to use whatever folding factor in WHIR, and you don't pay a num_fun * (1<<folding_factor) factor.

[yczhangsjtu]

Thank you. I will try that.