SPARKs - Succinct Parallelizable Arguments of Knowledge

Explore a groundbreaking cryptographic concept in this 25-minute conference talk presented at Eurocrypt 2020. Delve into the world of SPARKs (Succinct Parallelizable Arguments of Knowledge) as introduced by researchers Naomi Ephraim, Cody Freitag, Ilan Komargodski, and Rafael Pass. Learn about this new paradigm in succinct arguments for NP, starting with a running example of delegation and an overview of the current state of the art. Examine the prover efficiency landscape and discover the innovative results and applications of SPARKs. Investigate the challenges of implementing SPARKs for small space computations, and understand the solutions involving updatable hash functions and pipelined Merkle trees. Gain insights into how these components come together to create a powerful new tool in cryptography.

Succinct Arguments for NP
Running Example: Delegation
State of the Art
Prover Efficiency Landscape
SPARKS: A New Paradigm
Results
Applications of SPARKS
Warmup: SPARKs for Small Space
Why doesn't this work?
First attempt
Updatable Hash Functions
Pipelined Merkle Trees
Putting it all together
Conclusion