Score:2

Crypto

zkSnark: Restricting a Polynomial

user93353

2/8/23, 10:47 AM

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.

129

0 + 0

number-theory

zero-knowledge-proofs

Score:3

Crypto

Daniel S

2/10/23, 12:26 PM

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.

0 + 0

user93353

2/13/23, 6:47 AM

I know I already accepted the answer. However, I tried an example & it didn't work.

user93353

2/13/23, 6:48 AM

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?

Daniel S

2/13/23, 7:22 AM

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.

user93353

2/13/23, 7:56 AM

Ok, that checks out!!

user93353

2/13/23, 8:01 AM

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

Daniel S

2/13/23, 8:23 AM

Yes, the problem is that the sample value chosen, $s=14$ is a root of $t(x)$ modulo 22 which is the order of the group mod 23. This leads to $z_p=1$ which causes degeneracy as you have found. The verifier should check before sending that $t(s)\not\equiv 1\pmod{q}$ for a large prime $q$ dividing $p-1$. This is very likely to be the case if we use a large, strong prime.

user93353

2/13/23, 8:33 AM

Are you saying both the problems (one described in 3.4 & the one I pointed out in my last comment) are because $s=14$ is a root of $t(x) \pmod {22}$ or is only one of them because of this?

user93353

2/13/23, 9:37 AM

So, I tried both the issues with s = 16 which is not a root . And both the issues still remain. So having s as a root of t(s) mod (p-1) does cause E(p) to always be 1, but otherwise how does it cause any problems with the protocol?

Daniel S

2/13/23, 5:53 PM

I don't have an issue with $s=16$. For the polynomial $t(x)=x(x-3)(x-4)$, $t(s)=2496$. For the polynomial $(x-2)(x-3)(x-4)=x^3-9x^2+26x-24$ the prover would compute $E(s^3)E(s^2)^{-9}E(s)^{26}E(1)^{-24}=8$. Picking random $r=6$ prover sends $z_h=8$ and $z_p=13$. Verifier then has $z_h^{2496}=3$ which is not the same as $z_p$.

user93353

2/14/23, 12:46 AM

p(x) = x(x-3)(x-4), t(x) = (x-3)(x-4) - so t(16) = 156 & not 2496. $13^{156} \pmod {23} \equiv 8$ - hence matches

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: zkSnark: Restricting a Polynomial

TH: zkSnark: การจำกัดพหุนาม

RO: zkSnark: Restricționarea unui polinom

RU: zkSnark: ограничение полинома

VI: zkSnark: Hạn chế đa thức

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.