An update of our FRI analysis

We’ve published a new version of our simplified analysis of FRI! The security analysis does not change, however we do have a few new goodies. I’ll briefly highlight them and show you the relevant parts of the paper.

Thinking about parameters. We’re trying to make parameter selection easier and more flexible. Practitioners no longer have to choose to analyze their protocols “in unique decoding” or “at the Johnson bound”. The tradeoff is actually a continuous space and we make this more explicit in our explanations and theorem statement using the tradeoff parameter $\theta$.

To help us (and maybe you) make sense of this, we plotted the errors for mutual correlated agreement (the “proximity gaps stuff”), the folding rounds and the query rounds. A fun exercise in visualization, or plotting, is to vary $\theta^*$ and see how all three plots are affected.

I found these plots to be very helpful when understanding the effects of new proximity gaps results on the soundness of FRI. In a few words, new proximity gaps results either shift the MCA error to the left (when we find discover that a conjecture was wrong) or to the right (when we improve known bounds). This in turn affects the values of the folding round errors and query round errors. Maybe I’ll write more on this or produce some animations in the future.

The commit phase. We use our round-by-round soundness analysis of FRI to show that FRI has very strong properties. In particular, we show in section 5.4 that the so-called commit phase is in fact a binding and extractable commitment. As far as we know, ours is the first proof of this property. We have upcoming work showing that this is helpful when doing data availability sampling (e.g., FRIDA).

Batched FRI. The last addition is an appendix that covers batched FRI.