Checking low-degreeness of last FRI codeword in recursive verifier

[jan-ferdinand]

Let's discuss ways to check the low-degreeness of the last codeword in FRI and analyze which of the approaches is the least complex one with regards to recursive proof verification.

Currently, we do FRI (depicted here with a measly 2 co-linearity computations) in the following way:

Suggestion 1: Use current ISA & FRI

We use only currently available instructions to write a TritonVM method performing INTT and check the low-degreeness of the resulting polynomial.

Suggestion 2: Modify ISA

We create a dedicated instruction intt.

Suggestion 3: Modify FRI

We change FRI in the following way.

Split-and-fold continues beyond the last codeword, creating co-linearity-computation-collapsing codewords (“clcc codewords”). Each clcc-codeword can be sent in the clear, just like the last codeword can.¹

For rounds involving at least one clcc-codeword, co-linearity indices can coincide, collapsing a co-linearity computation – hence the name clcc. Whenver such a collapse occurs, the verifier needs to check whether the values at the corresponding indices are, in fact, the same. For example, in the picture below, a collapse happens between the pink and the turquoise co-linearity computations. The turquoise value was computed by the verifier, the pink part was sent in the clear by the prover, allowing for a meaningful comparison.

The last clcc-codeword is of length one, which means computing INTT is trivial – it is the identity operation. This constant polynomial is called (orange) c in the picture above. The only remaining check the verifier has to perform is between c and the last computed co-linearity.

Questions to answer for cost/benefit analysis:

• How costly is arithmetization of INTT?
• What are typical expected FRI-domain sizes?
• How many co-linearity checks will be performed?
• How many clcc-codewords will be created?
• (At least) how many co-linearity checks will collapse in a given clcc-round?
• If only the merkle root of the clcc-codeword is sent: how long is one authentication path at that clcc-round?

Using all of the above:

• How many extra elements are put in the proof due to clcc-codewords?
• How many elements are not put in the proof stream if last codeword and (some) clcc codewords are only commited to?
• Which suggestion is the best?

(Originally issue number 15 in the internal issue tracker.)

Footnotes

1. It might be better to build Merkle trees from the longer clcc-codewords. This is an open question. ↩

[jan-ferdinand]

This issue is de-facto blocked by not having a benchmarking target. We need the recursive Verifier first. See #7.