# Low Degree Testing in zk-STARK: Part 2

--

Here is Part 2 of our Low Degree Testing Series. Part 1 is at:

https://kitten-finance.medium.com/low-degree-testing-in-zk-stark-part-1-c0ac6ef0de3c

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*# 1. The finite field

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

Let ** Fₚ** be the finite field with

**elements, where**

*p***is a large prime number (much greater than 256).**

*p ≡ 1 (mod 64)*For any ** x** in

**and any**

*Fₚ***, we know**

*n***. Because the multiplicative group of**

*x^{n+(p-1)} = x^n***is of order**

*Fₚ***.**

*p-1*Pick a primitive root of unity ** β** in

**The multiplicative group of**

*Fₚ.***is cyclic and generated by**

*Fₚ***. That is, for any**

*β***in**

*x***we have**

*Fₚ***for some**

*x=β^n***.**

*n*Therefore, instead of working with ** f(x)**, we can work with

**.**

*f(β^n)*We will write ** g(β^a, β^b, β^c, β^d)** as

**from now on.**

*{a, b, c, d}*# 2. The magic

Here comes the magic.

By Bob’s construction: ** f(β^n) = {n, 4n, 16n, 64n}**.

Hence: *f(β^{n+(p-1)/4}) = {n+(p-1)/4, 4(n+(p-1)/4), 16(n+(p-1)/4), 64(n+(p-1)/4)}**.*

We can simplify this formula using ** β^{k+(p-1)} = β^k**.

For example: ** β^{16(n+(p-1)/4)} = β^{16n+4(p-1)} = β^{16n}**.

The simplified formula is: ** f(β^{n+(p-1)/4}) = {n+(p-1)/4, 4n, 16n, 64n**}.

With this method, we have 4 formulas:

Here the ** {a,b,c,d}** expressions are only different in terms of their first variable.

Because ** deg_a(g) < 4**, we can interpolate these 4 values to quickly compute

**for any**

*{a, 4n, 16n, 64n}***.**

*a*The reason is similar to this: let ** X** be a unknown line (so its polynomial degree is less than 2). If we know 2 values

**and**

*X(u)***for some**

*X(v)***and**

*u***, and**

*v***, we can interpolate them to compute**

*u≠v***for any**

*X(a)***.**

*a*Therefore, Bob can quickly compute ** {a, 4b, 16b, 64b} **for any

**and any**

*a***, using values of**

*b***.**

*f(x)*# 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

**in**

*a***.**

*Fₚ*(2) Bob builds a Merkle tree ** M** for all these values of

**. Therefore Bob can use Merkle proof to prove any**

*f(a)***he sent to Alice is genuine.**

*f(a)*An example of Merkle proof, is how you get airdrops from UNI etc. The smart contract can quickly verify your amt of token, even when there are millions of users, by checking your Merkle proof.

(3) Bob uses the root hash of ** M **to pick a pseudo-random

**in**

*A***. Therefore Bob cannot cheat by cherry-picking a special**

*Fₚ***.**

*A*(4) With the magic in the last section, Bob quickly computes ** {A, 4b, 16b, 64b}** for all

**in**

*b***range, using values of**

*[0, (p-1)/4-1]***.**

*f(x)*Note if

then it goes back to theb > (p-1)/4-1case. So there is no need to compute that.b-(p-1)/4

(5) Bob builds another Merkle tree ** M2** for all these values.

(6) Bob uses the root hash of ** M2 **to pick 40 pseudo-random numbers

**in**

*b₁, b₂, …, b₄₀***range. Therefore Bob cannot cheat by cherry-picking.**

*[0, (p-1)/4–1]*(7) Bob sends the 40 values ** {A, 4b₁, 16b₁, 64b₁}, …, {A, 4b₄₀, 16b₄₀, 64b₄₀} **and the 40 Merkle proofs in

**to Alice.**

*M2*(8) Notice there were 160 values of ** f** in

**used to compute these 40 values of**

*M***. Bob sends the 160 values of**

*g***and the 160 Merkle proofs in**

*f***to Alice.**

*M*## 3.2 Alice’s task

Alice verifies all Merkle proofs: 40 proofs of ** g** in

**, and 160 proofs of**

*M2***in**

*f***.**

*M*Alice verifies each value of ** g** indeed comes from the interpolation of the corresponding 4 values of

**.**

*f*Therefore it is highly likely that ** deg_a(g) < 4**. Because Alice verified 40 cases of that, and Bob cannot cherry-pick these cases, and our finite field

**is huge.**

*Fₚ*# 4. Verifying the next variable

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

Now Bob will prove ** deg_b(g) < 4** to Alice.

Recall Bob has computed ** {A, 4b, 16b, 64b}** for all

**in**

*b***range in section 3, and built a Merkle tree**

*[0, (p-1)/4–1]***for it.**

*M2*## 4.1 Bob’s task

(1) Bob uses the root hash of ** M2 **to pick a pseudo-random

**in**

*B***. Therefore Bob cannot cheat by cherry-picking a special**

*[0, (p-1)/4–1]***.**

*B*(2) Bob quickly computes ** {A, 4B, 16c, 64c}** for all

**in**

*c***range.**

*[0, (p-1)/16–1]*The idea is similar to section 2. Bob has already computed these in section 3:

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

Then because ** deg_b(g) < 4**, Bob can interpolate them to quickly compute any

**.**

*{A, 4b, 16c, 64c}*(3) Bob builds another Merkle tree ** M3** for all these values.

(4) Bob uses the root hash of ** M3 **to pick 40 pseudo-random numbers

**in**

*c₁, c₂, …, c₄₀***range. Therefore Bob cannot cheat by cherry-picking.**

*[0, (p-1)/16–1]*(5) Bob sends the 40 values ** {A, 4B, 16c₁, 64c₁}, …, {A, 4B, 16c₄₀, 64c₄₀} **and the 40 Merkle proofs in

**to Alice.**

*M3*(6) Notice there were 160 values of ** {A, 4b, 16b, 64b}** in

**used to compute these 40 values of**

*M2***. Bob sends the 160 values of**

*{A, 4B, 16c, 64c}***and the 160 Merkle proofs in**

*{A, 4b, 16b, 64b}***to Alice.**

*M2*## 4.2 Alice’s task

Alice verifies all Merkle proofs: 40 proofs of ** {A, 4B, 16c, 64c}** in

**, and 160 proofs of**

*M3***in**

*{A, 4b, 16b, 64b}***.**

*M2*Alice verifies each value of ** {A, 4B, 16c, 64c}** indeed comes from the interpolation of the corresponding 4 values of

**.**

*{A, 4b, 16b, 64b}*Therefore it is highly likely that ** deg_b(g) < 4**. Because Alice verified 40 cases of that, and Bob cannot cherry-pick these cases, and our finite field

**is huge.**

*Fₚ*# 5. Conclusion

Using similar methods, Bob can prove ** deg_c(g) < 4** and

**to Alice. And this concludes the Low Degree Testing in zk-STARK.**

*deg_d(g) < 4*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/ ).