Content. Embedding lookup checks into Groth16 is unfortunately currently impossible. UltraGroth is a protocol designed to insignificantly modify Groth16 to introduce lookup checks that optimize arithmetical circuits written over R1CS. In this lecture, we consider the construction of UltraGroth, how to build interactive protocol over multi-round QAP, and efficiency of such construction.

Content. This lecture introduces a powerful tool to reduce the number of constraints in the arithmetical circuits representing complex non-native logic in the given zero-knowledge protocol. We consider two widely used lookup protocols: plookup and logup.

Content. This lecture introduces the first application of Sum-Check protocol for building SNARK over Circuit Satisfiability problem. Additionally, we specify how Sum-Check is used for Offline Memory Checking problem.

Content. This lecture introduces Sum-Check protocol which is a cornerstone of many modern zk-SNARKs. Additionally, we introduce the notion of multilinear polynomials and how to encode certain problems into the multilinear form.

Content. In this lecture, we consider Bulletproofs. This zero-knowledge proof system has logarithmic proof size, requires no trusted setup, and requires minimal cryptographic assumptions: only the discrete log assumption. In this lecture, we introduce inner-product argument and corresponding polynomial commitment scheme, and explain how to use it for range proofs and arithmetic circuits satisfiability.

Content. All previous lectures required (a) interpolation and (b) fast operations over polynomials. In this lecture, we consider the widely used technique to reduce the complexity of such tasks from quadratic to quasilinear. Namely, we consider:

• Barycentric Interpolation.
• Finite Field roots of unity.
• What are NTT and Inverse NTT problems.
• NTT algorithm derivation and implementation.

Content. Groth16 is not the only zk-SNARK protocol used in practice! In this lecture, we will consider the PlonK protocol, which is frequently used in various zkEVM implementations. Here, we cover:

• PlonK Arithmetization
• How gates work in PlonK. Custom Gates.
• Gate and Wiring Satisfiability Checks.
• Permutation Check over Polynomials.

Content. After covering the Groth16 zk-SNARK theory, we will move to the practical part of the course. Here, we will learn how to use Circom to create circuits and generate proofs. Here, we cover:

• Basic Circom syntax.
• Creating circuits.
• Generating proofs.
• Interpreting all the generated data such as .r1cs, .sym, proof.json, and how they relate to the previously covered theory.

Content. Finally, we consider one of the most advanced zk-SNARKs: Pinocchio and Groth16. Here, we cover:

• Turning QAP into succint verification over encrypted space.
• Making SNARK sound.
• Turning SNARK into zk-SNARK.
• Pinocchio Protocol.
• Groth16 Protocol.

Content. With R1CS in our hands, we are now ready to succintly represent it as a Quadratic Arithmetic Program (QAP). Additionally, we consider other basic theory before specifying the Groth16 protocol. Here, we cover:

• Turning R1CS into QAP.
• What is PCP, IPCP, IOP.
• Proof of Exponent.

Content. This is an opening lecture on SNARKs: technology we are using daily in our projects. Here, we cover:

• The definition of zk-SNARK.
• Arithmetic Circuits. Circuit Satisfability Problem.
• Rank-1 Constraint System (R1CS) in vector and matrix forms.

Content. Here, we will consider the most basic form of interactive proofs - Sigma Protocols. We will understand how to turn them into non-interactive proofs and how to use them in practice. Here, we cover:

• Schnorr Signature Scheme.
• Sigma Protocols.
• Examples of Sigma Protocols: Okamoto's and Chaum-Pedersen Protocols
• Combining Sigma Protocols.

Content. This lecture finally introduces the concept of Zero-Knowledge Proofs and their applications. Here, we cover:

• What is a cryptographic proof exactly?
• Interactive Proofs.
• Soundness and Zero-Knowledge definitions.
• Proof vs Proof of Knowledge.
• Fiat-Shamir Heuristic.

Content. In this lecture we will dive into the design and application of various cryptographic commit schemes that are often used in zero knowledge proof systems. All in all, here we cover:

• Hash-based commitments.
• Vector commitments.
• Polynomial commitments.

Content. This lecture will touch the central part of SNARKs: elliptic curve pairing, its properties and applications. But first, we will cover projective coordinates and how they can be used to optimize elliptic curve operations. All in all, here we cover:

• Relations and equivalence classes.
• Projective Coordinates.
• Adding points in projective coordinates. Scalar multiplication using double-and-add algorithm.
• Elliptic Curve Pairing.
• Pairing applications.

Content. Our primary focus will be on Finite Field Extensions, while also covering basics of Elliptic Curves. Here, we cover:

• Finite Field Extensions
• Algebraic Closure
• Elliptic Curve Definition
• Discere Logarithm on Elliptic Curves

Content. In this lecture, we will continue covering the basic mathematics used in cryptography. Here, we cover:

• Basic Security Definitions
• Polynomials
• Lagrange Interpolation: Shamir's Secret Sharing and Reed-Solomon Codes
• Schwarz-Zippel Lemma
• Number Theory

Content. In this lecture, we will cover the basic mathematics required for understanding Zero-Knowledge Proving Systems. Here, we cover:

• Basic Set Theory and Logic
• Basic Group Theory
• Fields. Finite Field Arithmetic.