Pratyush Mishra on Tiny Proofs, Folding, Low-Memory SNARKs and More

Pratyush Mishra discusses his research on SNARKs, focusing on tiny proofs, folding schemes based on hash functions, and low-memory SNARKs, highlighting their applications in computer security beyond blockchain. As a co-maintainer of Arcworks and an assistant professor at the University of Pennsylvania, he acknowledges the contributions of his students and colleagues, including Sebastian Angel and Tal Drabin, to the field.

Mishra notes the rapid evolution of zero-knowledge proof (ZKP) research since 2021, with diversification into hash-based and error-correcting code-based SNARKs, and the exploration of ZKP properties in low-memory and distributed environments. He discusses the practicality of SNARKs, acknowledging past performance issues but recognizing improvements and a growing industry focused on enhancing their capabilities. While traditional contracts may suffice for some business applications, he emphasizes the critical need for strong guarantees in areas like software security.

The conversation delves into tiny proofs, questioning the claim that Groth's Groth 16 proof is the smallest proof system and discussing advancements leading to smaller alternatives. Mishra explains the construction involving two G1 elements and one G2 element within a pairing-friendly elliptic curve, noting ongoing questions about achieving lower bounds in proof sizes. Various approaches, including polynomial interactive oracle proofs and polynomial commitment schemes, have emerged since Groth's work.

The discussion also covers folding with hash functions and their post-quantum security, with existing studies suggesting that adapting security guarantees for folding is feasible. The efficiency of hash-based ZKVMs utilizing recursive proofs is examined, with a focus on how accumulation is integrated into these systems. The conversation highlights the significance of proximity claims as a bottleneck in SNARKs and discusses frameworks like FIX and FACTS that utilize code-switching techniques to enhance proof sizes and efficiency.

Mishra and others explore low-memory proving methods, including Ligero's streaming prover and the Scribe model, which allows for efficient processing with limited memory. They discuss ongoing efforts to achieve smaller proof sizes and succinct verifiers, identifying recursion as a potential method for low-memory SNARK construction. The conversation also touches on non-blockchain applications, including projects focused on proving document integrity and server response specifications, as well as verifiable database queries.

The evolution of cryptocurrency education is noted, with a growing interest in integrating ZK concepts into cryptography courses. The discussion concludes with recognition of Mishra's contributions to the field and the diverse directions of his research projects.