zkSTARKs - A deep dive into the FRI protocol

General Zero-Knowledge
1

Hi all!

The following is a deep dive into zkSTARK’s method for low-degree testing. It give the relevant mathematical background and details. I’d appreciate any thoughts/comments!

https://www.orbs.com/fri-protocol/

Enjoy, and feel free to contact me here or on idanp@orbs.com

3 Likes
2

Hey @idanP, this is a great write up! So far it is the most easy-to-read and in detail description of the maths behind the FRI protocol that I have seen. I very much like the fact that you provide all the mathematical background needed to understand Reed-Solomon Codes, including proofs of claims / lemmas, as well as giving out some exercises for all to do.

Some questions that I had after going through the post (though not fully in detail):

  • How does the commitment scheme used in the commit phase affect the proving complexity? In other words, is the proof based on knowing all the pre-images to the values in the merkle tree? (Albeit, this may be out of scope for the FRI protocol)
  • Where are the main points of possible efficiency improvements / optimizations?
  • How does the soundness of the FRI protocol affect the overall zkSTARK construction? I understand that there is also the Fiat-Shamir soundness to keep into account

Thanks again for sharing this!

3

You may know that DEEP-FRI ( https://arxiv.org/pdf/1903.12243.pdf ), published recently, improves upon FRI.

4

Hey Daniel, thanks for the feedback!

These are great questions. Some thoughts off the top of my head:

  • The commitment scheme is definitely a major point for optimization, as Merkle proof make the bulk of a zkSTARK proof. I think the size of the underlying field can also be a factor. Also, one should consider different choices for the constant \eta (representing the dimension reduction between each iteration of the protocol) and their implications.

  • I think that low-degree testing is the main soundness obstacle in the overall zkSTARK paradigm. Regarding the Fiat-Shamir soundness, I’m not sure but I don’t think it is taken into account in the soundness analysis in the paper. That’s definitely something to keep in mind.

Maybe if there is someone from Starkware in the crowd, they can shed some more light :slight_smile:

Thanks for leaving some food for thought!

5

Thanks! I did not know that (was too busy writing the blogpost :slight_smile: )

I’ll read it soon and perhaps add a note to the above.

6

Do you guys know if there’s a link that works for this resource :o?