Category: Zero Knowledge

Roots of Unity in Finite Fields This article explains what Roots of Unity in a Finite Field are and how they are intertwined with multiplicative subgroups. The reader is expected…

Multiplication of Polynomials in Point Form Polynomial multiplication is widely used in zero-knowledge proofs and mathematical cryptography. But the brute force or traditional approach for multiplying polynomials runs in $\mathcal{O}(n^2)$,…

The Fundamental Theorem of Finite Cyclic Groups The Fundamental Theorem of Cyclic Groups provides guarantees about the existence of cyclic subgroups within a cyclic group. In the context of the…

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…

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 ExplainedThe 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.…

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…