Improving the prover cost by replacing the IVC with the Starky verification in plonky2

[Vishalkulkarni45]

We can use Starky to generate the proof for the loop function, which will run for a total of 600-700 iterations. In my opinion, Starky is ideal because the cost of verifying the starky proof of 600-700 iteration in plonky2 would be significantly lower compared to using IVC style Plonky2. Another reason for choosing Starky according to me is that we need to generate a proof for a loop, and STARKs are particularly efficient for proving recursive algorithms .Many people apply a similar approach by offloading the heavy computations to Starky and then verifying the proof using Plonky2.

[Vishalkulkarni45]

I'm interested in building this, and it would be really helpful if you could provide some insights or clarify a few doubts along the way. What do you think? @tremblaythibaultl @blowfish880

[Vishalkulkarni45]

Is there any specific reason for choosing IVC-style recursion over a tree-like recursion? In a recursive tree, we can enforce constraints between the inputs and outputs of the leaf proofs at the higher levels. 😅

[tremblaythibaultl]

Hi @Vishalkulkarni45,

I'm interested in building this, and it would be really helpful if you could provide some insights or clarify a few doubts along the way. What do you think?

That sounds great! We'd be happy to answer your questions along the way. I think a good medium for communication is the FHE.org discord where I (and other members of the FHE community) can give you clarifications when needed.

Is there any specific reason for choosing IVC-style recursion over a tree-like recursion? In a recursive tree, we can enforce constraints between the inputs and outputs of the leaf proofs at the higher levels.

It was not obvious at the time that using a tree-like recursion would yield a significant advantage over IVC. We're really interested in seeing how this paradigm can improve our VFHE prototype!

[Vishalkulkarni45]

We can optimize in two ways:
First, by replacing IVC with a recursive tree. With a recursive tree, we can generate proofs for 600-700 iterations and verify them in parallel. The total proving time would include the time for generating a proof for a single iteration and the time for recursively verifying these 600-700 proofs (requiring 2-3 different recursive circuits since 600 or 700 aren't powers of 2). The second method, as mentioned earlier, is to create a single STARK proof and verify it in Plonky2. I'll start with the first approach to evaluate performance and then move to the second. I believe the second approach will significantly reduce proving time but will take longer to implement.

Excited to built it