Add zero knowledge

[dlubarov]

My understanding is that this requires these changes:

• Send evaluations on a coset of the subgroup, rather than a subgroup itself. Otherwise the FRI verifier might query some points on H, which would directly leak witness data. Alternatively, I think we could have the prover rewind, and retry with new randomness, until it gets a query set disjoint from H (should take just a couple hundred attempts). That might be simpler, but it's not the standard approach.
• Salt each leaf (with 2 field elements ~= 128 bits, I think?) in Merkle trees containing witness data, to make them hiding commitments. (Ideally we would not salt the Merkle tree that contains public, precomputed circuit data like sigma polynomials. But if it's simpler to salt everything, that might not be a big deal.)
• Add a bunch of random blinding factors to each witness polynomial (need to calculate how many). We also need to blind Plonk's Z polynomials; see here for one method of doing that.
• I noticed that facebook/winterfell#9 also mentioned "Combine composition polynomial with a random low-degree polynomial before running it through FRI protocol." I vaguely recall the Aurora and/or Fractal papers mentioning something similar. I'm not clear on the purpose of it though.

[wborgeaud]

• Send evaluations on a coset of the subgroup, rather than a subgroup itself. Otherwise the FRI verifier might query some points on H, which would directly leak witness data. Alternatively, I think we could have the prover rewind, and retry with new randomness, until it gets a query set disjoint from H (should take just a couple hundred attempts). That might be simpler, but it's not the standard approach.
• Salt each leaf (with 2 field elements ~= 128 bits, I think?) in Merkle trees containing witness data, to make them hiding commitments. (Ideally we would not salt the Merkle tree that contains public, precomputed circuit data like sigma polynomials. But if it's simpler to salt everything, that might not be a big deal.)

I've started working on these two in the zero-knowledge branch.

I noticed that facebook/winterfell#9 also mentioned "Combine composition polynomial with a random low-degree polynomial before running it through FRI protocol." I vaguely recall the Aurora and/or Fractal papers mentioning something similar. I'm not clear on the purpose of it though.

I'm not sure I understand what this does. What information leaks without adding this polynomial that doesn't leak with it?

[dlubarov]

I've started working on these two in the zero-knowledge branch.

Nice, will check it out!

I'm not sure I understand what this does. What information leaks without adding this polynomial that doesn't leak with it?

I'm still not sure either, but here's that bit of Aurora I was thinking of, from Section 8.1:

the honest prover in the new protocol will send, in addition to the messages of the underlying RS-encoded IOP, a random codeword r, which is added to the linear combination of messages that are tested for proximity to RS.

I guess that would be in addition to salting Merkle leaves, since this is the RS-IOP-to-IOP transformation, so we're still assuming theoretical oracles at this point, which wouldn't leak any information beyond what's queried.

I don't understand what information would be leaked if we skipped this though. Maybe Nick can clarify for us later.

[dlubarov]

So William already took care of the first two changes. The next step is adding some random blinding factors (there's a stub for it in CircuitBuilder).

As in Aurora etc., we can provide zero knowledge against a query bound b (the number of points that get queried) by adding b blinding factors to each polynomial (including Zs, using the technique in our blog).

For us, I think the query bound b for witness polynomials is

num_challenges + \sum_i (arity_i - 1) + |final_polynomial_coeffs|

But I think we need to double this for Z polys, since they are opened at two points, both in the Plonk openings and in FRI queries.

Does that sound right to you @wborgeaud? I'm happy to add it, just double checking first. We can also double check with Nick later.