Deep Dive into the FRI Protocol

The goal of this write-up is to expand on the mathematical details of “FRI”, a low-degree testing protocol, a key component of ZK-STARK, a computational integrity proof system that has been gaining a lot of attention with the rise of blockchain technologies. Since our focus will be on the mathematical details rather than the high-level overview of blockchain and ZK-STARKs, it is advisable to first understand the background and context of the problem this protocol aims to solve, for which we recommend reading Vitalik Buterin’s excellent introductory posts: Introduction to ZK-STARKs and Introduction to the FRI algorithm.

Put simplistically, ZK-STARK is a protocol that allows an entity to prove to another entity some computational claim. Examples of such claims are:

• “I have calculated the first 1,000,000 elements of the Fibonacci sequence”.
• “I have a secret key SK that corresponds to the public key PK”.
• “This Bitcoin transaction is valid”.

With ZK-STARKs one can prove such claims in a succinct way, meaning that a verifying entity need not re-execute the computation, rather she can just validate the proof itself, a much simpler computational task. The proof is also publicly verifiable, and no interaction with the prover is required.

Another key feature, especially in the context of blockchains, is Zero-Knowledge: The verifier does not learn anything other than the validity of the claim. In the transaction example above — the verifier can verify that the transaction is valid, but she does not learn the identity (public key) of the payer, nor of the payee, nor the amount being transferred.

There are quite a few such proof systems out there, each with their own pros and cons, and their comparison is beyond the scope of this post.

To prove a claim, the prover encodes the claim as a polynomial equation, and the validity of the claim is derived from verifying two facts: that the equation holds, and that the polynomials in the equation are of degree smaller than some integer d known to the verifier. FRI (a really short acronym for “Fast Reed-Solomon Interactive Oracle Proof of Proximity”) tends to the second item. It is a protocol that allows the prover to provide proof that a function
f: F → F is the evaluation of some degree <d polynomial.

The organization of the text is as follows: we first describe and analyze a naive approach for low-degree testing. Then, we describe the FRI protocol, stressing its advantages over a straightforward protocol. Following the protocol, we address the main goal of this file, which is giving the mathematical background and details showing that the protocol is complete, meaning that an honest prover’s proof is always accepted by an honest verifier. Finally, we address the soundness of the protocol. We give an example of a proof of a false claim and analyze the probability that it is nonetheless accepted by the verifier.

Since this text contains a lot of mathematical symbols, it is presented below as an embedded pdf. Enjoy the read, and for any comments, feel free to contact me at idanp@orbs.com.