Public and Private Inputs A public input in Circom is a signal in the witness that will be revealed to the verifier. For example, suppose we want to create a…

Circle FFT — Part 1: Building the Circle Domain Circle STARKs is a new zk-STARK scheme that has been implemented in Stwo and Plonky3, and it has been adopted by several zkVM projects. Its…

Square and Multiply Algorithm The square and multiply algorithm computes integer exponents in $\mathcal{O}(\log n)$ (logarithmic time). The naive way to compute an exponent $x^n$ is to multiply $x$ by…

Uniswap V2 Architecture: An Introduction to Automated Market Makers Uniswap is a DeFi app that enables traders to swap one token for another in a trustless manner. It was one…

Multiplicative Subgroups and Primitive Elements Introduction This chapter continues our study of group theory by exploring subgroups and generators. The concept of a primitive element will be introduced at the…

Computing the Current Tick Given sqrtPriceX96 In the previous chapters, we saw that the protocol stores the square root of the price instead of the price itself. Therefore, it is…

Uniswap V3 Factory and the Relationship Between Tick Spacing and Fees In early chapters, we introduced the concept of ticks, which discretize the price curve. A tick is a price…

ZK Proof of Selection Sort Most computations of interest are generally “stateful” — that is, they need to go through a series of steps to produce the final result. Sometimes,…

How a ZKVM Works A Zero-Knowledge Virtual Machine (ZKVM) is a virtual machine that can create a ZK-proof that verifies it executed a set of machine instructions correctly. This allows…

The Permutation Argument A permutation argument is a proof that two lists hold the same elements, but possibly in a different order. For example, [2,3,1] is a permutation of [1,2,3]…

ZK Friendly Hash Functions ZK-friendly hash functions are hash functions that require much fewer constraints to prove and verify than traditional cryptographic hash functions. Hash functions such as SHA256 or…

MD5 Hash In Circom In this tutorial, we will implement the MD5 hash in Circom both to compute the hash and to constrain in Circom that it was computed correctly.…

32-Bit Emulation in ZK The default datatype in ZK is the field element, where all arithmetic is done modulo a large prime number. However, most “real” computation is done using…

Modeling the Stack Data Structure in ZK This tutorial shows how to create a stack in Circom. Be warned — this chapter is long. However, the strategy for creating ZK…

Swapping Two Items in an Array in Circom This chapter shows how to swap two signals in a list of signals. This is an important subroutine for a sorting algorithm.…

Introduction to Stateful Computations in ZK When carrying out iterative computations such as powers, factorials, or computing the Fibonacci sequence, we need to “stop the computation” after a certain point.…

Quin Selector The Quin Selector is a design pattern that allows us to use a signal as an index for an array of signals. As a prerequisite, we assume the…

Conditional Statements in Circom Circom is very strict with the usage of if-statements. The following rules must be followed: Signals cannot be used to alter the behavior of an if-statement.…

Circom Components in a Loop Circom does not allow for components to be directly instantiated in a loop. For example, compiling the following code results in the error below. include…

Compute Then Constrain “Compute then constrain” is a design pattern in ZK circuits where an algorithm’s correct output is first computed without constraints. The correctness of the solution is then…

Indicate Then Constrain If we want to say that “x can be equal to 5 or 6” we can simply use the following constraint: (x – 6) * (x -…

Intermediate Signals and Sub-Component Circom’s primary purpose is to compile down to a Rank 1 Constraint System (R1CS), but its secondary purpose is to populate the witness. For most circuits,…

Symbolic Variables in Circom A symbolic variable in Circom is a variable that has been assigned values from a signal. When a signal is assigned to a variable (thereby turning…

Quadratic Constraints Circom Constraints A Rank 1 Constraint System has at most one multiplication between signals per constraint. This is called a “quadratic” constraint. Any constraint containing an operation other…

Circom Template Parameters, Variables, Loops, If Statements, Assert This chapter covers essential syntax, which you’ll see in most Circom programs. With Circom, we’re able to define a Rank 1 Constraint…