some errors

[mimoo]

Since you created this, here are some errors I picked up:

missing comma:

should be \bf{x}_j here:

^ shoud be the inverse no? range checks -> point checks reduction

[mimoo]

I believe that's another one, missing -1

[mimoo]

[mimoo]

I don't think the division by Z_H(x) should occur in the two permutation polynomials at the middle, I think it should divide the two middle polynomials after subtraction.

[mimoo]

^ I think here the reconstruction of t should use X^n and X^{2n}, not zeta

[arielgabizon]

Thanks for these comments! I will work through them - for one thing: reduce point checks to range checks is correct. The idea is that range checks are what is easy/what we already have, when using ranged protocols/proving things by dividing by Z_H; so that's what we need to reduce to. (That's in the ranged protocol, it is true that ultimately in the "compiled protocol" using KZG all checks are reduced to a point check by randomly sampling a challenge point)

[arielgabizon]

^ I think here the reconstruction of t should use X^n and X^{2n}, not zeta

I think not, cause we're deriving the value of t using the three partial polys' values (The point of splitting t into several polys is to only have to work with degree n and not higher)

[arielgabizon]

I don't think the division by Z_H(x) should occur in the two permutation polynomials at the middle, I think it should divide the two middle polynomials after subtraction.

I guess that would be equivalent. Not sure what's better typographically

[arielgabizon]

I believe that's another one, missing -1

I don't think so, the verifier adds that -1 in step 8

[mimoo]

I guess I'm learning about the protocol by submitting false corrections then :P thanks!

[arielgabizon]

There were several true corrections :)

[mimoo]

^ I think here the reconstruction of t should use X^n and X^{2n}, not zeta

I think not, cause we're deriving the value of t using the three partial polys' values (The point of splitting t into several polys is to only have to work with degree n and not higher)

Oh right, so if I understand correctly this is using Maller's optimization!

[arielgabizon]

Umm you could perhaps call it a special case of that optimization...not sure.. Btw if you look at the recently updated paper t doesn't appear at all in the opening proof polynomial, cause now it's all encorporated in r using Maller's optimizaiton. In any case, nice writeup on that!

[mimoo]

I don't think the division by Z_H(x) should occur in the two permutation polynomials at the middle, I think it should divide the two middle polynomials after subtraction.

I guess that would be equivalent. Not sure what's better typographically

the polynomials are not individually divisible by Z_H no? It's the subtraction that is (otherwise you'd get a result in the rational numbers)

[mimoo]

btw this is still an error right?

[mimoo]

same here, it looks like the permutation stuff is missing from c?

[mimoo]

Umm you could perhaps call it a special case of that optimization...not sure.. Btw if you look at the recently updated paper t doesn't appear at all in the opening proof polynomial, cause now it's all encorporated in r using Maller's optimizaiton. In any case, nice writeup on that!

oh I see! So it's not really a KZG opening anymore!

You reduced the problem of showing that f(z) = Z_H(z) t(z)

to showing that z is a root of f(x, z) - Z_H(z) t(x) (thus f(z, z) = Z_H(z) t(z).

EDIT: nevermind, I think we're opening f(x, z) - Z_H(z)t(x) at z, which is 0

EDIT2: oh I see, so that's where Maller's optimization is used

[arielgabizon]

same here, it looks like the permutation stuff is missing from c?

So the idea is to split the terms between r' and r_0. I think all the terms appear in them together

[mimoo]

OK, so I think I finally got it, and I wrote a note to explain how we go from "send the evaluations of f(z), t(z) and have the verifier check f(z) = t(z) Z_H(z)" to "send the evaluations and have the verifier check the opening proofs".

The thing that finally clicked for me was that instead of having the verifier check that identity by themselves, we have them check the polynomial (which is where Maller optimization is used).

[mimoo]

same here, it looks like the permutation stuff is missing from c?

So the idea is to split the terms between r' and r_0. I think all the terms appear in them together

but where is the third permutation poly (S_sigma3) from the original circuit equation?

[arielgabizon]

The factor of the third perm poly is in r', it doesn't need to be made constant like first two, cause r is already linear after fixing those.

[mimoo]

I guess I'm confused as to where does the line I pointed out here goes?

(I wrote this, to try to find out how this was transformed in the PLONK paper)

[mimoo]

nevermind, I figured it out :D I should write a note somewhere. I guess the optimization with r_0 through me off a bit.