# zkSnark: Restricting a Polynomial

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.

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.
• 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? Oct 13, 2021 at 6:48
• 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. Oct 13, 2021 at 7:22