0
$\begingroup$

I am reading this explanation of zkSnarks written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

My question is about Section 4.6.1

Setup

  • construct the respective operand polynomial $l(x)$ with corresponding coefficients
  • sample random $\alpha$ and $s$
  • set proving key with encrypted $l(s)$ and it's "shifted" pair: $(g^{l(s)}, g^{{\alpha}l(s)})$
  • set verification key: $(g^{\alpha})$

1) I'll take the first step of the above setup.

construct the respective operand polynomial $l(x)$ with corresponding coefficients

We are still in that part of the text where all $l(x)$ are $a$. We haven't still reached 4.6.2 where they explore the case where out of 3 $l(x)$, 2 are $a$ and the 3rd one is $d$.

So if I create 3 points with same a's, it will look something like this

$a * x = r1$
$a * y = r2$
$a * z = r2$

With actual numbers, it can be

$2 * 2 = 4$
$2 * 3 = 6$
$2 * 4 = 8$

So the 3 $l$ points are $[(1, 2), (2, 2), (3,2)]$

If I do a Lagrange's interpolation on these 3 points, it will give me $l(x) = 2$.

If instead, I use $a = 1$, then $l(x)$ obtained from langrange's will always be $l(x) = 1$, i.e. lagrange's will always give me $l(x) = a$

So I am unable to understand how to get to a $l$ polynomial which looks like the one in 4.6.1 with $a=1$ & the $l$ polynomial is $x^2 - 3x + 3$. I am not saying $x^2 - 3x + 3$ doesn't fit the case - $l = 1$ at $x \in {1,2}$ - it does fit the case, but I am never going to get a $l$ polynomial which looks like that from lagrange's - I will always end up with $l(x) = a$.

2) Next is the 3rd step of the setup - i.e.

set proving key with encrypted $l(s)$ and it's "shifted" pair: $(g^{l(s)}, g^{{\alpha}l(s)})$

In all our protocols till now, we have always used $l(x)$ as an intermediate step - i.e. the prover never calculates $E(l(x=s))$ & hands it to verifier. He always uses $l(x)$ to construct $h(x)$ - i.e $h(x) = \frac {l(x) * r(x) - o(x)}{t(x)}$

So I am a little confused by this setup step here? Is the prover now handing Encryption of intermediate stuff ($l(x)$) to verifier instead of $E(h)$? - the verifier just needs $E(h)$ & $E(p)$ & he verifiers the proof by checking $E(p) = E(h)^t$ - so I am not clear as how providing $(g^{l(s)}, g^{{\alpha}l(s)})$ fits into reaching this final step?

$\endgroup$

1 Answer 1

1
+50
$\begingroup$

For the polynomial construction, instead of using Lagrange, start by considering a non-trivial polynomial that is 0 at the given points e.g. $x=1$, $x=2$ and $x=3$. The natural choice is $(x-1)(x-2)(x-3)=x^3-6x^2+11x-6$. We convert this to a polynomial that evaluates to 1 at the three points by adding 1 i.e. $x^3-6x^2+11x-5$. We can then multiply this to get any value $a$. We could of course simply add $a$ to our original polynomial.

As for the passing of information, multiple facts need to be verified in a proof of operation such as described in section 4.4 and so multiple values are needed. As we see in section 4.4 in four checks must be made and a total of seven inputs to these checks must be provided in addition to the values $g$and $g^\alpha$.

$\endgroup$
1
  • $\begingroup$ Thank you very much $\endgroup$
    – user93353
    Feb 25, 2022 at 1:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.