Hash-based Folding Schemes

on YouTube ↗52m

" summary

Introduces interactive oracle reductions and a hash-based recipe using Merkle commitments plus Fiat–Shamir to compile IORs into succinct folding reductions; builds WARP, an accumulation scheme instantiable with any linear code, that achieves a linear-time prover and a verifier that makes O(lambda) queries (security-parameter-dependent, essentially independent of statement length). Key techniques: proximity batching via random linear combinations, prover recommitment to combinations, and a new straight-line extraction without an error-corrector using mutual correlated agreement and erasure decoding.

AI-written summary · about

" chapters (15)

1. 0:00Hash-based folding schemes intro
2. 1:07Three talk goals
3. 3:16Folding schemes defined
4. 4:41Hash-based succinct arguments recipe
5. 6:27Interactive oracle reductions
6. 11:28Examples of reductions
7. 16:25Trivial folding scheme
8. 18:34Nontrivial folding goals
9. 21:11Batch protocol details
10. 29:40Accumulator relation and codes
11. 32:53WARP accumulation scheme
12. 35:25WARP soundness
13. 38:58Straight-line extraction
14. 45:25Open questions
15. 48:16Q&A

" related talks

• 01h 08mTutorial on Proof SystemsAbhishek Jain · Minimal Complexity Assumptions for Cryptography 2023
• 01h 15mTo interact or not to interact: Cryptographic proof systems and the Fiat-Shamir heuristicAlex Lombardi · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 09mProofs - Practice 1Justin Thaler · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 15mProofs - TheoryYael Tauman Kalai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 59mDelegating Computation IYael Tauman Kalai · Cryptography Boot Camp 2015
• 01h 06mOblivious RAM IIElaine Shi, Daniel Wichs · Cryptography Boot Camp 2015
• 28mEvolution of Optimistic Rollup proofsProtolambda · Protocol Berg 2023
• 29mCorrelation-Intractable Hash Functions via Shift-HidingAlex Lombardi, Vinod Vaikuntanathan · ITCS 2022