In this tutorial, Vitalik Buterin provides a comprehensive and intuitive explanation of the GKR (Goldwasser–Kalai–Rothblum) protocol, a highly efficient interactive proof system widely used in zero-knowledge (ZK) proving systems. GKR is particularly well-suited for computations that are large in two dimensions: layered and batched, such as Poseidon hash functions and LLM inference. Its key advantage lies in avoiding commitments to intermediate layers—only the inputs and outputs need to be committed—drastically reducing computational overhead.
The article walks through the core building block of GKR: the sumcheck protocol, which recursively reduces a claim about a large computation to a claim about a single point evaluation. Using a simplified version of the Poseidon2 hash function, Vitalik demonstrates how GKR works by reversing the computation layer by layer, applying sumchecks at each step.
Several optimizations are discussed, including reducing the number of values per round from 5 to 3 using Gruen’s trick, and batching linear sumchecks. These techniques enable GKR to achieve single-digit overhead in practice, compared to ~100x overhead in traditional STARKs.
Vitalik also touches on polynomial commitment schemes and security considerations, such as Fiat–Shamir soundness. He concludes that while GKR is not zero-knowledge by itself, it is a powerful and general-purpose proving engine that can be wrapped in ZK-SNARKs or STARKs and applied to a wide range of computations beyond hashing, including machine learning inference.
In this episode, Anna Rose and Guillermo Angeris talk with Kevin Lacker, creator of Acorn, a theorem prover utilising AI. They explore what theorem provers are, their history, and how they’re used today. Kevin shares how Acorn brings in AI to simplify the proving process, letting users naturally write mathematical statements while the system checks the correctness of those statements. It’s built to feel more like natural math, unlike tools like Lean that demand every step.
They also explore the benefits of including AI in math, and also the challenges that come with it such as hallucinations, and how Acorn could speed up research in areas like zero-knowledge proofs. The dicussion also covers the history of mathematics, community building around Acorn and its open math library, acornlib.
This post proposes adding an opcode, OP_STARK_VERIFY, to Tapscript that verifies a bounded-size STARK proof. The goal is to enable on-chain verification of a Zero Knowledge Proof with transparent, post-quantum-secure assumptions, without resorting to ad-hoc Script encodings (e.g., OP_CAT) or enshrining a large family of arithmetic opcodes. We outline the motivation, threat model, bounding/pricing approach, initial opcode semantics, and open questions. Feedback welcome on scope, parameter bounding, pricing, alternatives, and challenges.
It is clear that this proposal is far from being fully fleshed, and presents already multiple significant challenges, the main one being about credible neutrality with respect to the need of choosing a specific flavor of STARK protocol.
The main goal is to gauge the interest about enshrining native ZK verification (i.e OP_STARK_VERIFY, OP_GROTH16_VERIFY) into Bitcoin at some point.
It’s also an interesting thought experiment to start thinking about the challenges that this would imply.
These are lecture notes from his graduate-level Theory of Cryptography course taught at Georgia Tech and University of Michigan.
Feedback (or even better, pull requests) welcome!
This class is an introduction to the theory of quantum computing and quantum information. Topics covered include:
The fundamental postulates of quantum information theory
Entanglement and nonlocality
The quantum circuit model
Basic quantum protocols, such as quantum teleportation and superdense coding
Basic quantum algorithms, such as Simons’ algorithm, the Quantum Fourier Transform, Phase Estimation, Shor’s Factoring algorithm, Grover search, amplitude amplification
Quantum error correction and fault-tolerance
The goal of the course is to provide a rigorous foundation for future research/studies in quantum computing and quantum information, and along the way provide students with an understanding of the state of the field, and where it’s headed.
No background in quantum physics is required. However, having familiarity and comfort with abstract linear algebra is a must.
In this course, we will cover the mathematical foundations, implementation aspects, and applications of zkSNARKs.
This course requires a basic background in discrete mathematics (at the level of CIS 1600), and a basic background in algorithms and complexity (at the level of CIS 3200).
If you're interested in our ZK Insights or have ideas for similar content to share, we highly encourage everyone to head over to our Github repo and submit a Pull Request. Join forces with like-minded ZKPunks to co-create!
✨ Github repo link: https://github.com/ZKPunk-Org/zk-insights
✨ Web collection version: https://insights.zkpunk.pro/
Special thanks to: Kurt
Editor: Purple
Share Dialog
No comments yet