Low Degree Testing in zk-STARK: Part 2

1. The finite field

Here we assume some knowledge of finite field (the fancy version of modular arithmetic).

2. The magic

Here comes the magic.

3. The Merkle proofs

Now here is a strategy for Bob to prove deg_a(g) < 4 to Alice.

3.1 Bob’s task

(1) Bob computes f(a) for all a in Fₚ.

3.2 Alice’s task

Alice verifies all Merkle proofs: 40 proofs of g in M2, and 160 proofs of f in M.

4. Verifying the next variable

Bob has proven deg_a(g) < 4 to Alice.

4.1 Bob’s task

(1) Bob uses the root hash of M2 to pick a pseudo-random B in [0, (p-1)/4–1]. Therefore Bob cannot cheat by cherry-picking a special B.

  • {A, 4c, 16c, 64c}
  • {A, 4(c+(p-1)/16), 16c, 64c} which equals {A, 4(c+(p-1)/16), 16(c+(p-1)/16), 64(c+(p-1)/16)} and thus already computed.
  • {A, 4(c+2(p-1)/16), 16c, 64c} which equals {A, 4(c+2(p-1)/16), 16(c+2(p-1)/16), 64(c+2(p-1)/16)} and thus already computed.
  • {A, 4(c+3(p-1)/16), 16c, 64c} which equals {A, 4(c+3(p-1)/16), 16(c+3(p-1)/16), 64(c+3(p-1)/16)} and thus already computed.

4.2 Alice’s task

Alice verifies all Merkle proofs: 40 proofs of {A, 4B, 16c, 64c} in M3, and 160 proofs of {A, 4b, 16b, 64b} in M2.

5. Conclusion

Using similar methods, Bob can prove deg_c(g) < 4 and deg_d(g) < 4 to Alice. And this concludes the Low Degree Testing in zk-STARK.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store