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

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

# 2. Why the reduction of degree

• 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

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

--

--

--

## More from Kitten Finance

https://www.kitten.finance/

Love podcasts or audiobooks? Learn on the go with our new app.

## Kitten Finance

https://www.kitten.finance/