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?

1. Reduction of degree, by introducing dummy variables

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.

--

--

--

https://www.kitten.finance/

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

Recommended from Medium

Beauty in numbers

Gradient Descent

DEMYSTIFYING THE “COMPUTER”

Living on a Knife-edge

Simple Naive Bayes

A simple but cool Math problem

Six steps? Resolving Tango Algorithm and breaking The Code

Anita Flejter and Hernan Brizuela from Ultimate Tango explain the structure of Baldoza sequence.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Kitten Finance

Kitten Finance

https://www.kitten.finance/

More from Medium

Best Cycling Routes in Dubai

My Experience in Github Externship’21— Hoppscotch

11 Ways to Increase Your Email Open Rate

An Essay: Gabbie Hanna Returns to YouTube With Podcast & Just Wants to Chill With Her Cat

Gabbie Hanna with color paint and make-up all over her face, hair, and shoulders.