Low Degree Testing in zk-STARK: Part 1

You can write a number (say 73678235) in radix-4 (becomes 10121003312123), and then you can verify the number is small by bounding each digit of its radix-4 form.

The problem of Low Degree Testing:

  • Bob wants to prove to Alice that he has a polynomial f(x) whose degree is lower than some number D.
  • Bob won’t reveal his f(x) to Alice, probably because someone’s private key is encoded in it. This is the “zk” aka zero-knowledge part.
  • Can Alice quickly verify Bob’s claim using sophisticated tricks?

1. Reduction of degree, by introducing dummy variables

For reasons that will be clear soon, Bob will reduce the degree of his polynomial f(x), by introducing dummy variables.

2. Why the reduction of degree

But why will Bob reduce the degree of his f(x)?

  • Alice picks 65600 random integers r1, r2, … , r65600.
  • Alice asks Bob for f(r1), f(r2), …, f(r65600), i.e. the value of f(x) at all these integers.
  • Alice constructs a degree 65535 polynomial F(x) from the first 65536 values.
  • Alice verifies whether the other 64 values are on F(x) too.
  • Alice accepts Bob’s claim if that is the case. Note then it is likely that F(x) = f(x).

3. The implementation

The real implementation of Low Degree Testing in zk-STARK involves Merkle proofs and finite field. We will go through it in Part 2.

  • Bob builds a Merkle tree M of f(x).
  • Bob picks a pseudo-random number A using the root hash of M. So Bob can’t cherry-pick.
  • Because deg_a(g) < 4, Bob can use some magic to compute g(A, b⁴, b¹⁶, b⁶⁴) for all b using special values of f(x).
  • Bob builds a Merkle tree M2 of g(A, b⁴, b¹⁶, b⁶⁴).
  • Bob picks a pseudo-random number B using the root hash of M2. So Bob can’t cherry-pick.
  • Because deg_b(g) < 4, Bob can use some magic to compute g(A, B, c¹⁶, c⁶⁴) for all c using special values of g(A, b⁴, b¹⁶, b⁶⁴).
  • …….
  • Bob sends some Merkle proofs to Alice, to prove the process is genuine.
  • Alice verifies these proofs and the process, and concludes it is highly likely that deg_a(g) < 4, deg_b(g) < 4, deg_c(g) < 4, deg_d(g) < 4, because otherwise Bob won’t be able to make these magical computations, unless Bob is extremely lucky and hits everything by coincidence.

--

--

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