Low Degree Testing in zk-STARK: Part 1

You may have heard about zk-SNARK, zk-STARK, etc., which can be used for ETH Layer 2 scaling and more. An excellent explanation is Vitalik’s blog post:

https://vitalik.ca/general/2017/11/09/starks_part_1.html

The Low Degree Testing in zk-STARK can be confusing for most newcomers. It is usually explained using a recursive algorithm.

Here we provide an alternative explanation without recursion. The basic idea is simple:

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?

If you think Alice can ask Bob for some values of f(x), then you are on the right track.

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.

As an example, let f(x) = x²⁰⁰ -3x⁵⁰ +4x⁶ -2. Its degree is 200.

We can reduce the degree of f(x) from 200 to 3, if we introduce dummy variables a= x, b= x⁴, c= x¹⁶, d= x⁶⁴.

Here is the process:

The xⁿ term in f(x) becomes the a^i b^j c^k d^l term in g(a,b,c,d), if n is l k j i in radix-4.

So, the x²⁰⁰ term in f(x) becomes the a⁰ b² c⁰ d³ = b² d³ term in g(a,b,c,d), because 200 is 3020 in radix-4.

Therefore, the degree-200 f(x) becomes a degree-3 g(a,b,c,d), and f(x) = g(x,x⁴,x¹⁶,x⁶⁴).

As another example, a degree-65535 f(x) can become a degree-3 g(a,b,c,d,e,f,g,h), and f(x) = g(x,x⁴,x¹⁶,x⁶⁴,x²⁵⁶,x¹⁰²⁴,x⁴⁰⁹⁶,x¹⁶³⁸⁴).

2. Why the reduction of degree

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

Here is the reason. As an example, consider this idea for Alice to verify Bob’s claim of deg(f) < 65536:

• 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).

Here we ignored lots of important details. This is just the rough idea and needs more conditions to work. Yet we can feel it is a reasonable idea, because Alice verified so many random points, it is difficult for Bob to cheat.

However there are at least two issues: (1) Bob is sending lots of points to Alice. (2) Alice can reconstruct Bob’s curve f(x), so it’s not a zero-knowledge proof.

In zk-STARK we will verify claims of astronomical degree. It’s impractical for Bob to send that many points to Alice.

But with the trick in the last section, we can reduce a polynomial f(x) of degree n, to a polynomial g(a,b, …) of degree < 4, by introducing log₄(n) dummy variables. So the verification can be much more efficient.

And this is the basic idea of Low Degree Testing in zk-STARK.

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.

As an example, assume Bob’s claim is deg(f) < 256.

Bob constructs g(a,b,c,d), such that f(x) = g(x, x⁴, x¹⁶, x⁶⁴).

The task is to prove deg_a(g) < 4, deg_b(g) < 4, deg_c(g) < 4, deg_d(g) < 4.

Here is the simplified overview:

• 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.

And we will explain the magic and the details in Part 2:

https://kitten-finance.medium.com/low-degree-testing-in-zk-stark-part-2-7c729118d10c

We are Kitten.Finance ( https://www.kitten.finance/ ) and we are working on multiple DeFi products and our own L2 solutions. You are welcome to read our Medium for details ( https://kitten-finance.medium.com/ ).