search

zcash / halo2

The Halo2 zero-knowledge proving system
https://zcash.github.io/halo2/
Other
696 stars 480 forks source link

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

Open ebfull opened 3 years ago

ebfull commented 3 years ago

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 commented 3 years ago

Can you explain this in more detail, @ebfull?

daira commented 3 years ago

@ebfull wrote:

We have this large degree polynomial h(X) that the prover needs to commit to. So we split it into several polynomials h1(X), h2(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 xn 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 xn 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 xn are arbitrary field elements. So we have to figure this out eventually, either take the performance hit or somehow blind h(X) further.