ZKDL
Camp

About

ZKDL Camp is a series of internal lectures on Zero-Knowledge Proving Systems at Distributed Lab. Here, we will understand "from scratch" how SNARKs (Groth16, PLONK), STARK, Bulletproofs (in the future, perhaps also Folding schemes) work.

It is important that this course is designed for a full low-level understanding of these protocols and, accordingly, all the mathematics on which they are based. That is why the course covers not only zk itself and its application directly but also the basic level of mathematics needed to understand zk and cryptography in general.

Summary

If you want to check all lectures, codebase or slides combined, you can use links provided below:

Lectures

Lecture 11: Programming ZKPs in Circom

Speaker: Kyrylo Riabov

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.

Lecture 10: Pairing-based zk-SNARKs

Speakers: Anton Levochko and Dmytro Zakharov

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.

Lecture 9: Quadratic Arithmetic Program. Probabilistically Checkable Proofs

Speaker: Anton Levochko

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.

Lecture 8: SNARKs. Arithmetical Circuits

Speaker: Anton Levochko

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.

Lecture 7: Sigma Protocols

Speaker: Dmytro Zakharov

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.

Lecture 6: Introduction to Zero-Knowledge Proofs

Speaker: Dmytro Zakharov

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.

Lecture 5: Cryptographic commitment schemes

Speaker: Denis Riabtsev

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.

Lecture 4: Projective Coordinates and Pairing

Speaker: Dmytro Zakharov

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.

Lecture 3: Finite Field Extensions and Elliptic Curves

Speaker: Dmytro Zakharov

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

Lecture 2: Security, Polynomials, Lagrange Interpolation

Speakers: Dmytro Zakharov and Denis Riabtsev

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

Lecture 1: Algebra Basics

Speaker: Dmytro Zakharov

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.