Category: Zero Knowledge Proofs

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”…

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…

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…

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,…

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…

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…

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)$,…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…

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…