# 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 digitof its radix-4 form.

The problem of Low Degree Testing：

- Bob wants to prove to Alice that he has a polynomial
whose degree is lower than some number*f(x)*.*D* - Bob won’t reveal his
to Alice, probably because someone’s private key is encoded in it. This is the “zk” aka zero-knowledge part.*f(x)* - 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

**to**

*200***, if we introduce dummy variables**

*3***,**

*a= x, b= x⁴***,**

*c= x¹⁶***.**

*d= x⁶⁴*Here is the process:

The **xⁿ** term in ** f(x)** becomes the

**term in**

*a^i b^j c^k d^l***, if**

*g(a,b,c,d)***is**

*n***in radix-4.**

*l k j i*So, the ** x²⁰⁰** term in

**becomes the**

*f(x)***term in**

*a⁰ b² c⁰ d³ = b² d³***, because 200**

*g(a,b,c,d)***is**

**in radix-4.**

*3020*Therefore, the degree-200 ** f(x)** becomes a degree-3

**, and**

*g(a,b,c,d)***.**

*f(x) = g(x,x⁴,x¹⁶,x⁶⁴)*As another example, a degree-65535 ** f(x)** can become a degree-3

**, and**

*g(a,b,c,d,e,f,g,h)***.**

*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
, i.e. the value of*f(r1), f(r2), …, f(r65600)*at all these integers.*f(x)* - Alice constructs a degree 65535 polynomial
from the first 65536 values.*F(x)* - Alice verifies whether the other 64 values are on
too.*F(x)* - 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

**, to a polynomial**

*n***of degree**

*g(a,b, …)***, by introducing**

*< 4***dummy variables. So the verification can be much more efficient.**

*log₄(n)*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
of*M*.*f(x)* - Bob picks a pseudo-random number
using the root hash of*A*. So Bob can’t cherry-pick.*M* - Because
, Bob can use some magic to compute*deg_a(g) < 4*for all*g(A, b⁴, b¹⁶, b⁶⁴)*using special values of*b*.*f(x)* - Bob builds a Merkle tree
of*M2**g(A, b⁴, b¹⁶, b⁶⁴).* - Bob picks a pseudo-random number
using the root hash of*B*. So Bob can’t cherry-pick.*M2* - Because
, Bob can use some magic to compute*deg_b(g) < 4*for all*g(A, B, c¹⁶, c⁶⁴)*using special values of*c*.*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*, because otherwise Bob won’t be able to make these magical computations, unless Bob is extremely lucky and hits everything by coincidence.*deg_d(g) < 4*

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