Remove the need to multiply by powers of x^n in verifier

[ebfull]

We will start doing this soon so that the protocol is trivially zero-knowledge, but it's expensive inside the recursive circuit. One alternative is to switch back to what we were doing before (sending openings at x for each H commitment) at the cost of increasing the proof size, but this might be difficult or impossible to prove zero-knowledge.

[daira]

Can you explain this in more detail, @ebfull?

[daira]

@ebfull wrote:

We have this large degree polynomial h(X) that the prover needs to commit to. So we split it into several polynomials h₁(X), h₂(X), … each of degree at most n - 1. Then we open them all at x and take those openings and scale them by different powers of xⁿ to get h(x). Problem is that the openings reveal info about h(X) that is difficult to blind. To get around this we instead scale the commitments themselves by powers of xⁿ and combine them together and open them at x. This reveals no additional info about h(X) and makes the zero-knowledge argument simpler.

But it’s inefficient inside the recursive circuit to scale the commitments versus scaling the openings because powers of xⁿ are arbitrary field elements. So we have to figure this out eventually, either take the performance hit or somehow blind h(X) further.