Folding schemes state-of-the-art review

[ninitrava]

Reading Protogalaxy and Protostar to better understand how can we benefit from folding schemes to improve prover efficiency and recursion.

Protogalaxy https://eprint.iacr.org/2023/1106 Protostar https://eprint.iacr.org/2023/620.pdf

[ninitrava]

Highlights so far:

• no ZK in the main papers (only FLIP&Prove is zk)
• schemes are Commit-and-Prove --> need to adapt proving system to this
• only homomorphic commitment schemes --> trusted setup needed, no FRI, no Merkle Trees
• folding for non-uniform relations may be costly --> Protogalaxy improves this