Information on zkSTARK protocol

[kc1212]

Does the code under https://github.com/risc0/risc0/tree/main/risc0/zkp implement a specific zkSTARK protocol? It'd be great if someone can provide a few references to academic papers.

[flaub]

@pdg744 or @jbruestle do we have any references to answer this question?

[hamidelmaazouz]

@kc1212, here are some academic papers:

1. https://dl.acm.org/doi/pdf/10.1145/22145.22178
2. https://dl.acm.org/doi/pdf/10.1145/62212.62222

They have lots of citings that you can navigate on Google Scholar.

Projects similar to Risc0:

• (Matter Labs) zksynch
• (Ethereum) zkEVM

Other resources:

• https://ethereum.org/en/zero-knowledge-proofs
• https://ethworks.io/assets/download/zero-knowledge-blockchain-scaling-ethworks.pdf

[kc1212]

@hamidelmaazouz thanks for the references but I'm more interested in the protocol used in risc0 rather than references to the literature from the field.

For example the code uses FRI (https://github.com/risc0/risc0/blob/main/risc0/zkp/prove/fri.h) which suggests that it's using one of the Reed Solomon IOP protocols. I'm curious about which protocol is used exactly.

[pdg744]

@kc1212
Sorry somehow missed this thread.
Our protocol is essentially PLOOKUP + DEEP-ALI (from the DEEP-FRI paper) + original FRI protocol.
LMK if you have more questions.

[pdg744]

with parametric batching (as opposed to affine batching) for constraint linking in DEEP-ALI & for FRI batching

[pdg744]

A complete description of the zkSTARK protocol and all the associated references is now available at https://dev.risczero.com/proof-system-in-detail.pdf