2
$\begingroup$

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

I have understood everything in the first 15 pages.

In 3.4 Restricting a Polynomial (Page 16)

We do already restrict a prover in the selection of encrypted powers of s, but such restriction is not enforced, e.g., one could use any possible means to find some arbitrary values $z_p$ and $z_h$ which satisfy equation $z_p = (z_h)^{t(s)}$ and provide them to the verifier instead of $g^p$ and $g^h$. For example, for some random r $z_h = g^r$ and $z_p = (g^{t(s)})^{r}$, where $g^{t(s)}$ can be computed from the provided encrypted powers of $s$. That is why verifier needs the proof that only supplied encryptions of powers of $s$ were used to calculate $g^p$ and $g^h$ and nothing else.

I am unable to understand how a prover can find some arbitrary values of $z_p$ and $z_h$ which satisfy $z_p = (z_h)^{t(s)}$? For example, for some random r $z_h = g^r$ and $z_p = (g^{t(s)})^{r}$

The prover doesn't know $s$ & nor does he know $g$, so how will he do this?

In short, I am unable to figure out what is the attack (to protect against) for which "restricting a polynomial" is needed.

$\endgroup$
0

1 Answer 1

3
+50
$\begingroup$

Per page 15 of the paper, the prover is provided with $E(s^0)=E(1)=g$ (I'll refer to this as $E_0$). Likewise they are provided with $$E_1:=E(s), E_1:=E(s^2),\cdots, E_d:=E(s^d).$$ Let $t(s)=\sum_{0\le i\le d}c_is^i$ (with the $c_i$ known to the prover) then $g^{t(s)}=E(t(s))=\prod_{0\le i\le d}E_i^{c_i}$.

Thus prover knows both $g$ and $g^{t(s)}$ and as in the paper they may choose a random $r$ to construct $z_h$ and $z_p$ by raising these value to the power $r$.

The point of the attack is that the above calculations do not require knowledge of $p(x)$ which is what prover is supposed to be proving knowledge of. A verifier foolish enough to believe that the random value $z_h$ does equal $g^{h(s)}$ and that $z_p$ does equal $g^{p(s)}$ will have nothing to contradict their belief.

$\endgroup$
10
  • $\begingroup$ I know I already accepted the answer. However, I tried an example & it didn't work. $\endgroup$
    – user93353
    Commented Oct 13, 2021 at 6:47
  • $\begingroup$ E(c) = g^c mod 23. Verifier samples at s = 14 & provides $E(s^0) = 5$, $E(s^1) = 13$, $E(s^2) = 12$, $E(s^3) = 3$ The 2 known roots are 3 & 4 i.e. $t(s) = (x-3)(x-4)$. Prover chooses a random r = 6. t(6) = 3 * 2 = 6. Prover calculates $z_h = 5^6 \pmod {23} = 8$ & $z_p = (5^6)^6 \pmod {23} = 13$ Sends $z_p$ and $z_h$ to verifier Verifier calculates t(14) = 11 * 10 = 110. Verifier calculates $E(h)^t = 8^{110} \pmod {23} = 1$. So $E(p) \ne E(h)^t$ What am I doing wrong? Have I misunderstood your answer? $\endgroup$
    – user93353
    Commented Oct 13, 2021 at 6:48
  • $\begingroup$ The prover does not compute $t(r)$ and then $g^{t(r)}$. Instead, they compute $g^{t(s)}=g^{s^2−7s+12}=12×13^{−7}×5^{12}$ and raise this to the power $r$. Firing up sagemath, we see that $g^{t(s)}\equiv 1\pmod{23}$, so prover sets $z_p=1^r\equiv 1\pmod{23}$ and $z_h=8$. They then compute $z_h^{110}=8^{110}\equiv 1\pmod{23}$ which is the same value. $\endgroup$
    – Daniel S
    Commented Oct 13, 2021 at 7:22
  • $\begingroup$ Ok, that checks out!! $\endgroup$
    – user93353
    Commented Oct 13, 2021 at 7:56
  • $\begingroup$ I found another problem with the protocol described in 3.3 Let the actual true 3rd root be 0 i.e. the true polynomial is (x)(x-3)(x-4). Even if the prover didn't know the true polynomial & the true root & he assumed that the 3rd root was instead 2 instead of 0 & that the polynomial was (x-2)(x-3)(x-4) & do all the steps - the steps still check out and the verifier wouldn't know that prover didn't know the right polynomial. I was wondering if this is a separate fault with the protocol explained in 3.3 or is it a variation of the same mentioned in 3.4. I think it's a diff fault $\endgroup$
    – user93353
    Commented Oct 13, 2021 at 8:01

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.