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 p elements, where p ≡ 1 (mod 64) is a large prime number (much greater than 256).
For any x in Fₚ and any n, we know x^{n+(p-1)} = x^n. Because the multiplicative group of Fₚ is of order p-1.
Pick a primitive root of unity β in Fₚ. The multiplicative group of Fₚ is cyclic and generated by β. That is, for any x in Fₚ we have x=β^n for some n.
Therefore, instead of working with f(x), we can work with f(β^n).
We will write g(β^a, β^b, β^c, β^d) as {a, b, c, d} from now on.
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 {a, 4n, 16n, 64n} for any 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 X(u) and X(v) for some u and v, and u≠v, we can interpolate them to compute X(a) for any a.
Therefore, Bob can quickly compute {a, 4b, 16b, 64b} for any a and any b, using values of 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 a in Fₚ.
(2) Bob builds a Merkle tree M for all these values of f(a). Therefore Bob can use Merkle proof to prove any f(a) he sent to Alice is genuine.
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 A in Fₚ. Therefore Bob cannot cheat by cherry-picking a special A.
(4) With the magic in the last section, Bob quickly computes {A, 4b, 16b, 64b} for all b in [0, (p-1)/4-1] range, using values of f(x).
Note if b > (p-1)/4-1 then it goes back to the b-(p-1)/4 case. So there is no need to compute that.
(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 b₁, b₂, …, b₄₀ in [0, (p-1)/4–1] range. Therefore Bob cannot cheat by cherry-picking.
(7) Bob sends the 40 values {A, 4b₁, 16b₁, 64b₁}, …, {A, 4b₄₀, 16b₄₀, 64b₄₀} and the 40 Merkle proofs in M2 to Alice.
(8) Notice there were 160 values of f in M used to compute these 40 values of g. Bob sends the 160 values of f and the 160 Merkle proofs in M to Alice.
3.2 Alice’s task
Alice verifies all Merkle proofs: 40 proofs of g in M2, and 160 proofs of f in 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 Fₚ is huge.
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 b in [0, (p-1)/4–1] range in section 3, and built a Merkle tree M2 for it.
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.
(2) Bob quickly computes {A, 4B, 16c, 64c} for all c in [0, (p-1)/16–1] range.
The idea is similar to section 2. Bob has already computed these in section 3:
- {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.
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 c₁, c₂, …, c₄₀ in [0, (p-1)/16–1] range. Therefore Bob cannot cheat by cherry-picking.
(5) Bob sends the 40 values {A, 4B, 16c₁, 64c₁}, …, {A, 4B, 16c₄₀, 64c₄₀} and the 40 Merkle proofs in M3 to Alice.
(6) Notice there were 160 values of {A, 4b, 16b, 64b} in M2 used to compute these 40 values of {A, 4B, 16c, 64c}. Bob sends the 160 values of {A, 4b, 16b, 64b} and the 160 Merkle proofs in M2 to Alice.
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.
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 Fₚ is huge.
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.
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/ ).
