The intuition behind elliptic curve digital signatures (ECDSA) This article explains how the ECDSA (Elliptic Curve Digital Signature Algorithm) works as well as why it works. We will incrementally “rediscover” the algorithm from first principles in this tutorial. Prerequisites We assume prior knowledge of Elliptic Curve Arithmetic Elliptic Curve Arithmetic in Finite Fields Digital Signature […]
Trusted Setup A trusted setup is a mechanism ZK-SNARKs use to evaluate a polynomial at a secret value. Observe that a polynomial $f(x)$ can be evaluated by computing the inner product of the coefficients with successive powers of $x$: For example, if $f(x)=3x^3+2x^2+5x+10$, then the coefficients are $[3,2,5,10]$ and we can compute the polynomial as […]
The Schwartz-Zippel Lemma and its application to Zero Knowledge Proofs Nearly all ZK-Proof algorithms rely on the Schwartz-Zippel Lemma to achieve succintness. The Schwartz-Zippel Lemma states that if we are given two polynomials $p(x)$ and $q(x)$ with degrees $d_p$ and $d_q$ respectively, and if $p(x) \neq q(x)$, then the number of points where $p(x)$ and […]
Building a Zero Knowledge Proof from an R1CS Given an arithmetic circuit encoded as a Rank 1 Constraint System, it is possible to create a ZK-proof of having a witness, albeit not a succinct one. This article describes how to accomplish that. A zero knowledge proof for an R1CS is accomplished by converting the witness […]
Lagrange Interpolation with Python Lagrange interpolation is a technique for computing a polynomial that passes through a set of $n$ points. Interpolating a vector as a polynomial Examples A straight line through two points Consider that if we have two points, they can be interpolated with a line. For example, given $(1, 1)$ and $(2, […]
Polynomial Commitments Via Pedersen Commitments A polynomial commitment is a mechanism by which a prover can convince a verifier a polynomial $p(x)$ has an evaluation $y = p(x)$ at point $x$ without revealing anything about $p(x)$. The sequence is as follows: The prover sends to the verifier a commitment $C$, “locking in” their polynomial. The […]
Homomorphisms by Example A homomorphism between two groups exists if a structure preserving map between the two groups exists. Suppose we have two algebraic data structures $(A,\square)$ and $(B, \blacksquare)$, where the binary operator of $A$ is $\square$ and the binary operator of $B$ is $\blacksquare$. A homomorphism from $A$ to $B$ exists if and […]
Elementary Group Theory for Programmers This article provides several examples of algebraic groups so that you can build an intuition for them. A group is a set with: a closed binary operator the binary operator is also associative an identity element every element having an inverse We also discussed abelian groups. An abelian group has […]
Abstract Algebra Abstract Algebra is the study of sets that have one or more operators on that set. For our purposes, we only care about sets where the operator is a binary operator. Given a set with a binary operator, we can categorize those sets based on how the binary operator behaves, and what elements […]
AliasCheck and Num2Bits_strict in Circomlib An alias bug in Circom (or any ZK circuit language) occurs when a binary array of signals encodes a number larger than the field element can hold. We will refer to signals and field elements interchangeably in this article. We refer to the characteristic of the field as p. Loosely […]
Finite Fields and Modular Arithmetic for ZK Proofs This article is the third in a series. We present finite fields in the context of circuits for zero-knowledge proofs. The previous chapters are P vs NP and its Application to Zero Knowledge Proofs and Arithmetic Circuits. In the previous chapter on arithmetic circuits, we pointed out […]
Arithmetic Circuits for ZK In the context of zero-knowledge proofs, an arithmetic circuit is a system of equations that models a problem in NP. A key point from our article on P vs NP is that any solution to a problem in P or NP can be verified by modeling the problem as a Boolean […]
P vs NP and its application to zero knowledge proofs The P = NP problem asks: “If we can quickly verify a solution to a problem is correct, can we also quickly compute the solution?” Most researchers believe the answer is no, i.e., P ≠ NP. By understanding the P vs NP problem, we can […]
Hacking Underconstrained Circom Circuits With Fake Proofs The <-- operator in Circom can be dangerous because it assigns values to signals but does not constrain them. But how do you actually exploit write a POC (proof of concept) for this vulnerability? We will be hacking the following circuit: pragma circom 2.1.8; template Mul3() { signal […]
What are Pedersen Commitments and How They Work Pedersen commitments allow us to encode arbitrarily large vectors with a single elliptic curve point, while optionally hiding any information about the vector. It allows us to make claims about a vector without revealing the vector itself. Motivation When we discuss Bulletproof Zero Knowledge Proofs, they will […]
Elliptic Curve Point Addition This article describes how elliptic curve addition works over real numbers. Cryptography uses elliptic curves over finite fields, but elliptic curves are easier to conceptualize in a real Cartesian plane. This article is aimed at programmers and tries to strike a balance between getting too math heavy and too hand-wavy. Set […]
Circom language tutorial with circomlib walkthrough This tutorial introduces the Circom language and how to use it, along with common pitfalls. We will also explain a significant portion of the circomlib library in order to introduce common design patterns. A note about production use Circom is a fantastic tool for learning ZK-SNARKS. However, because it […]
Elliptic Curves over Finite Fields What do elliptic curves in finite fields look like? It’s easy to visualize smooth elliptic curves, but what do elliptic curves over a finite field look like? The following is a plot of $y² = x³ + 3 \pmod {23}$ Because we only allow integer inputs (more specifically, finite field […]
R1CS to Quadratic Arithmetic Program over a Finite Field in Python To make the transformation from R1CS to QAP less abstract, let’s use a real example. Let’s say we are encoding the arithmetic circuit $$z = x⁴ – 5y²x²$$ Converted to a Rank 1 Constraint System, this becomes $$\begin{align*} v_1 &= xx \\ v_2 &= […]
Groth16 Explained The Groth16 algorithm enables a quadratic arithmetic program to be computed by a prover over elliptic curve points derived in a trusted setup, and quickly checked by a verifier. It uses auxiliary elliptic curve points from the trusted setup to prevent forged proofs. Prerequisites This article is a chapter in the RareSkills Book […]
Evaluating a Quadratic Arithmetic Program on a Trusted Setup Evaluating a Quadratic Arithmetic Program (QAP) on a trusted setup enables a prover to demonstrate that a QAP is satisfied without revealing the witness while using a constant sized proof. Specifically, the QAP polynomials are evaluated at an unknown point $\tau$. The QAP equation $$\sum_{i=1}^m a_iu_i(x)\sum_{i=1}^m […]
Quadratic Arithmetic Programs A quadratic arithmetic program is an arithmetic circuit, specifically a Rank 1 Constraint System (R1CS) represented as a set of polynomials. It is derived using Lagrange interpolation on a Rank 1 Constraint System. Unlike an R1CS, a Quadratic Arithmetic Program (QAP) can be tested for equality in $\mathcal{O}(1)$ time via the Schwartz-Zippel […]
Elementary Set Theory for Programmers Why another set theory tutorial? The target audience for this piece is the sort of folks who don’t care about abstract math unless they see a direct use-case for it. They want to get the essential parts they need and move on. This piece caters to that audience. Our end […]
Bilinear Pairings in Python, Solidity, and the EVM Sometimes also called bilinear mappings, bilinear pairings allow us to take three numbers, $a$, $b$, and $c$, where $ab = c$, encrypt them to become $E(a)$, $E(b)$, $E(c)$, where $E$ is an encryption function, then send the two encrypted values to a verifier who can verify $E(a)E(b) […]
Converting Algebraic Circuits to R1CS (Rank One Constraint System) This article is explains how to turn a set of arithmetic constraints into Rank One Constraint System (R1CS). The focus of this resource is implementation: we cover a lot more corner cases of doing this transformation than other materials, discuss optimizations, and explain how the Circom […]
How Tornado Cash Works (Line by Line for Devs) Introduction to Tornado Cash Tornado cash is a cryptocurrency smart contract mixer that enables users to deposit crypto with one address and withdraw with another wallet without creating a traceable link between those two addresses. Tornado cash is probably the most iconic zero knowledge smart contract […]
ZK-addition-dapp with Noir and Nextjs We will demonstrate a step-by-step exploration of a basic zk-dapp designed for verifying additions. This application enables users to prove that the sum of two numbers, X and Y, equals Z without disclosing the actual numbers on the blockchain. Although solving this problem does not necessarily demand zero-knowledge proofs, we […]
Zero knowledge programming languages Zero knowledge proof moon math Zero knowledge proofs demonstrate you executed a computation correctly without revealing the inputs to the computation. A zero knowledge programming language is a convenient way to represent that computation. A common, but misleading analogy for zero knowledge proofs is “I can prove I’m over 21 without […]