Proof Parameters: FRI step list

[maxharrison00]

Is there a resource for understanding the tradeoff between different FRI step lists?

Looking at the codebase, it is easy enough to see that for any given program the prover requires that the product of 2^(FRI steps) plus the last_layer_degree_bound is equal to the trace length of the program. Beyond this however, what is the difference between using different values of FRI steps? What effect does this have on the soundness of the proofs?

The given STONE prover talk doesn't explore this from what I understand, and I can't find other resources explaining the parameter.

[liorgold2]

The FRI step parameters do not affect the soundness of the proof, but they affect the proof length and verification time.

As you increase a certain FRI step, more values need to be revealed from the corresponding Merkle tree but the number of Merkle trees reduces. However, the number of values that is revealed is 2^step, so the step cannot be too big. The last layer size plays a similar role - as you increase it you need less Merkle trees but reveal more values.

The exact formula is rather complicated, but we found that to get the minimal proof size steps of 3 are usually the best option, and the last layer should be of size 32 or 64. Exceptions are (a) possibly start with a step of 4 when the proof is really large (b) possibly end with a step of 2 or 2,2 to handle the remainder.

Some information can be found in StarkDEX Deep Dive: the STARK Core Engine in the "Proof Length Optimizations" section.

[maoudia-via]

We are also interested in understanding more about the configuration of FRI steps and would appreciate if there was a howto guide or documentation about that.

[MauroToscano]

A quick way to fix the FRI Steps is to take a look at the error, calculate the log2() difference between the two numbers the prover shows, and add or remove as many fri steps as to fill the gap

[lukaszcz]

A quick way to fix the FRI Steps is to take a look at the error, calculate the log2() difference between the two numbers the prover shows, and add or remove as many fri steps as to fill the gap

Sorry, this might be a basic question, but is there some way to extract the number of steps from e.g. the trace and use it to generate the right proof parameters (which at least don't make the prover crash)? I would like to be able to generate the required configuration files automatically based on the trace/program.

Is the trace format documented somewhere?

[Vid201]

https://github.com/anoma/juvix/blob/e2a6344f29a4b81204cc2a694e043113c16e9ad4/scripts/gen_stone_params.py