Introduction

This page hosts documentations and specifications for some of the cryptographic algorithms of Mina. For the Rust documentation, see here.

Note that this book is a work in progress, not necessarily reflecting the current state of Mina.

Authors: Izaak Meckler, Vanishree Rao, Matthew Ryan, Anaïs Querol, Joseph Spadavecchia, David Wong, Xiang Xie

In memory of Vitaly Zelov.

Terminology

This document is intended primarily to communicate mathematical ideas to programmers with some experience of math.

To that end, we will often be ambivalent about the difference between sets and types (in whatever programming language, but usually I am imagining some idealized form of Rust or OCaml). So for example we may write

• $A$ is a type

• $A$ is a set

• A is a type

and these should all be interpreted the same way, assuming it makes sense in the context. Similarly, we may write either of the following, and potentially mean the same thing:

• $a:A$

• $a\in A$

• a : A

We use

• $\to$ for function types
• $\mapsto$ for defining functions

Also, we usually assume functions are computed by a program (in whatever sense of “program” makes sense in the given context). So if we say “let $f:A\to B$”, we typically mean that

• $A$ and $B$ are types in some programming language which makes sense in the context (or maybe that they are sets, again depending on context)

• $f$ is actually a program computing a function of the type $A\to B$ (again, in whatever sense of program makes sense in context)

Groups

Groups are an algebraic structure which

• are used in most widely deployed signature schemes

• are used in most widely deployed zk-SNARKs

• generalize the notion of a collection of symmetries of an object

• generalize certain aspects of numbers

I will not touch on the last two too much.

First let’s do a quick definition and then some examples.

Definition. A group is a set $G$ with a binary operation $\ast :G\times G\to G$, an identity $e\in G$ for that operation, and an inverse map $({)}^{-1}:G\to G$ such that

• $\ast$ is associative: $x\ast (y\ast z)=(x\ast y)\ast z$ for all $x,y,z$.

• $e$ is an identity for $\ast$. I.e., $e\ast x=x\ast e=x$ for all $x$.

• $({)}^{-1}$ is an inverse map for $\ast$ with identity $e$. I.e., $x\ast x^{-1}=x^{-1}\ast x=e$ for all $x$.

So basically, an invertible binary operation. Definition in hand, we can see some examples:

• The integers $\mathbb{Z}$ with $+$, $0$ as identity, and negation as inverse.

• For any natural number $n$, the integers mod $n$. This can be thought of as the set of numbers $\{0,\dots ,n-1\}$ with the operation being $+$ followed by taking remainder mod $n$. It can also be thought of as the group of rotations of an $n$-gon.

• For any set $X$, the set of invertible functions $X\to X$ (a.k.a permutations) with function composition as the operation, the identity function as the identity, and function inverse as the inverse operation.

• The set of translations of a plane $\mathbb{R}\times \mathbb{R}$ with composition of translations (since the composition of translations is a translation). The identity is translating by $(0,0)$ and inverse is reversing the translation. This is equivalent to the group $\mathbb{R}\times \mathbb{R}$ with coordinate-wise addition as the operation and coordinate-wise negation as the inverse.

• The set of rotations of a sphere with composition as the operation, doing nothing as the identity, and performing the rotation in reverse as the inverse map.

• For any field $F$, the set $F^{\times }:=F\setminus \{0\}$, with field multiplication as the operation, $1$ as the identity, and $x\mapsto 1/x$ as the inverse map. This is called the group of units of $F$.

Sometimes, instead of $x\ast y$ we simply write $xy$ when $\ast$ is clear from context.

Abelian groups

An abelian group is a group in which $\ast$ is commutative, meaning $x\ast y=y\ast x$. Typically, in that case, we write the group operation as $+$ instead and we write the identity as $0$.

Some examples are

• the integers with addition

• the integers mod $n$ with addition

• the group of units of a field $F$

• the real numbers with addition

• the rational numbers with addition

• the real numbers with multiplication

• the rational numbers with multiplication

• vectors of integers of some fixed dimension with coordinate-wise addition

• The set of polynomials over a ring $R$, $R[x]$ with addition

Abelian groups are equivalently described as what are called $\mathbb{Z}$-modules. A $\mathbb{Z}$-module is like a vector space, but with the integers instead of a field.

Basically a $\mathbb{Z}$-module (or equivalently an Abelian group) is a structure where you can add elements and where it makes sense to multiply a group element by an integer.

If $G$ is an abelian group, we can define this “multiplication by an integer” as follows. If $n\ge 0$, then for $g\in G$, we can define $n\cdot g$ by

$$n\cdot g:=\underset{n}{\underbrace{g+\cdots +g}}$$

and if $n<0$, then define $n\cdot g:=|n|\cdot (-g)$. Or equivalently.,

$$n\cdot g=\underset{|n|}{\underbrace{(-g)+\cdots +(-g)}}=-\left(\underset{|n|}{\underbrace{g+\cdots +g}}\right)$$

This is the general sense of what is called scalar-multiplication or sometimes exponentiation in cryptography.

Cyclic groups

A cyclic group $G$ is a special kind of abelian group. It is an abelian group generated by a single element $g\in G$. That is, a cyclic group $G$ (generated by $g\in G$) is one in which for every $h\in G$ we have $h=ng$ for some $n\in \mathbb{Z}$.

Groups in cryptography

Many cryptographic protocols are defined generically with respect to any abelian group that has a “hard discrete log”.

Let

• $G$ be a cyclic group

• $g$ a generator of $G$

• $\mu$ a probability distribution on $G$

• $\mathcal{A}$ a set of algorithms of type $G\to \mathbb{Z}$ with runtime and memory usage bounds. In other words, a set of tuples $(P,t,m)$ where $P$ is a program of type $G\to \mathbb{Z}$, $t$ is a bound on the time that program can be run, and $m$ is a bound on the amount of memory that program can use.

  In practice you fix this to be something like, the set of all computations that can be run for less than 1 trillion $.

• $\epsilon \in [0,1]$ a probability, usually taken to be something close to 0 like $1/2^{128}$

Then we can define the $(G,g,\mu ,\mathcal{A},\epsilon )$-computational discrete-log assumption which says:

For any $(P,t,m)\in \mathcal{A}$, if you sample h from G according to $\mu$, then the probability that $P(h)\cdot h=g$ is smaller than $\epsilon$, assuming $P$ successfully runs within the given resource bounds.

Sometimes this is called the computational Diffie–Helman assumption. Basically what it’s saying is that for a group element $h$ sampled randomly, you can’t practically compute how many times you have to add $g$ to itself to get $h$.

Another really important assumption is the no-relation assumption (TODO: name).

Basically what this says is that randomly selected group elements have no efficiently computable linear relations between them. Formally, letting $G$ be a group and $\mu$ a probability distribution on $G$, and $\mathcal{A}$ a set of programs (with resource bounds) that take in a list of group elements as inputs and outputs a list of integers of the same length.

Then the $(G,\mu ,\mathcal{A},N,\epsilon )$-no-relation assumption says for all $(P,t,m)\in \mathcal{A}$, for any $n\le N$, if you sample $g_1,\dots ,g_n$ according to $\mu$, letting $[e_1,\dots ,e_n]=P([g_1,\dots ,g_n])$, it is not the case that

$$e_1\cdot g_1+\cdots +e_n\cdot g_n=0$$

except with probability $\epsilon$ (assuming program $P$ runs in time $t$ with memory $m$).

Generic group model

Elliptic curves

Now, what are some concrete groups that we can safely make the no-relation or computational discrete log hardness assumptions about?

Well, the most efficiently implementable groups that people have come up with – and that we believe satisfy the above assumptions for $\mathcal{A}$ being the class of realistic computations and $\epsilon$ being something like $1/2^{128}$ – are elliptic curves over finite fields.

Giving a complete definition of what an elliptic curve is requires a lot of math, and is not very useful from the point of view of cryptography. So we will give a definition that is not complete, but more useful.

An elliptic curve $E$ over a field $F$ is a set of the form

$$\{(x,y)\in F\times F\mid y^2=x^3+ax+b\}$$

for some $a,b\in F$, plus an additional point $O$ which is called the point at infinity. Basically it’s a set of pairs satisfying some equation of that form. The data of the elliptic curve itself is just the field $F$ together with the constants $a$ and $b$.

What is special about elliptic curves is that there is a way of giving them a group structure with simple to compute operations that we believe satisfy the hardness assumptions described above.

Group negation $(-):E\to E$ is defined by

$$-(x_0,y_0)=(x_0,-y_0)$$

so we just negate the $y$ coordinate.

The identity for the group is $O$, the point at infinity. For that point we may also therefore write it as $0$.

Group addition is more complicated to define, so we will not, but here is what’s worth knowing about how to compute $(x_0,y_0)+(x_1,y_1)$

• There are three cases

  1. $x_0\ne x_1$

  2. $x_0=x_1$ and $y_0=y_1$

  3. $x_0=x_1$ but $y_0\ne y_1$. In this case it turns out $y_0=-y_1$ and so the two points are inverse, and we return $O$

  In cases 1 and 2, the algorithm to compute the result just performs a simple sequence of some field operations (multiplications, additions, divisions, subtractions) with the input values. In other words, there is a simple arithmetic formula for computing the result.

Elliptic curves in Rust

Elliptic curves in Sage

Serializing curve points

Given a curve point $(x,y)$ we know $y^2=x^3+ax+b$ and thus $y$ is one of the two square roots of $x^3+ax+b$. If $y$ is a given square root, the other square root is $-y$ since $y^2=(-y{)}^2$. So, if we know $x$, then we almost know the whole curve point: we just need a single bit to tell us which of the two possible values (i.e., the two square roots of $x^3+ax+b$) is the y coordinate.

Here is how this is commonly done over prime order fields ${\mathbb{F}}_p$, assuming $p\ne 2$. Remember that we represent elements of ${\mathbb{F}}_p$ as integers in the range $[0,p-1]$. In this representation, for a field element $y$, $-y$ is the integer $p-y$ (or $0$ if $y=0$). Thus, if $y$ is odd, then $-y$ is even (since $p$ is odd and an odd minus an odd is even). Similarly, if $y$ is even, then $-y$ is odd (since an odd minus an even is odd).

So, for any $y$, unless $y$ is 0, $y$ and $-y$ have opposite parities. Parity can easily be computed: it’s just the least significant bit. Thus, we have an easy way of encoding a curve point $(x,y)$. Send

• $x$ in its entirety

• The least significant bit $b_0$ of $y$

Given this, we can reconstruct $y$ as follows.

1. Compute any square root $Y$ of $x^3+ax+b$

2. If the least significant bit of $Y$ is equal to $b_0$, then $y=Y$, otherwise, $y=-Y$

In the case of Mina, our field elements require 255 bits to store. Thus, we can encode a curve point in $255+1=256$ bits, or 32 bytes. At the moment this optimized encoding is not implemented for messages on the network. It would be a welcome improvement.

Projective form / projective coordinates

The above form of representing curve points as pairs – which is called affine form – is sometimes sub-optimal from an efficiency perspective. There are several other forms in which curve points can be represented, which are called projective forms.

The simple projective form represents a curve $E$ as above as the set

$$\{(X,Y,Z)\in F^3\mid (Y/Z{)}^2=(X/Z{)}^3+a(X/Z)+b\}$$

If you think about it, this is saying that $(X/Z,Y/Z)$ is a point on the original curve in affine form. In other words, in projective form we let the first two coordinates get scaled by some arbitrary scaling factor $Z$, but we keep track of it as the third coordinate.

To be clear, this means curve points have many different representations. If $(x,y,z)$ is a curve point in projective coordinates, and $s$ is any element of $F$, then $(sx,sy,sz)$ is another representation of the same curve point.

This means curve points require more space to store, but it makes the group operation much more efficient to compute, as we can avoid having to do any field divisions, which are expensive.

Jacobian form / Jacobian coordinates

There is another form, which is also sometimes called a projective form, which is known as the jacobian form. There, a curve $E$ would be represented as

$$\{(X,Y,Z)\in F^3\mid (X/Z^2,Y/Z^3)\in E\}$$

so the triple $(X,Y,Z)$ corresponds to the affine point $(X/Z^2,Y/Z^3)$. These are the fastest for computing group addition on a normal computer.

Take aways

• Use affine coordinates when the cost of division doesn’t matter and saving space is important. Specific contexts to keep in mind:

  • Working with elliptic curve points inside a SNARK circuit

• Use Jacobian coordinates for computations on normal computers, or other circumstances where space usage is not that costly and division is expensive.

• Check out this website for the formulas for implementing the group operation.

More things to know

• When cryptographers talk about “groups”, they usually mean a “computational group”, which is a group equipped with efficient algorithms for computing the group operation and inversion. This is different because a group in the mathematical sense need not have its operations be computable at all.

Exercises

• Implement a type JacobianPoint<F:Field> and functions for computing the group operation

• Familiarize yourself with the types and traits in ark_ec. Specifically,

  • todo

• Implement fn decompress<F: SquareRootField>(c: (F, bool)) -> (F, F)

Rings

A ring is like a field, but where elements may not be invertible. Basically, it’s a structure where we can

• add

• multiply

• subtract

but not necessarily divide. If you know what polynomials are already, you can think of it as the minimal necessary structure for polynomials to make sense. That is, if $R$ is a ring, then we can define the set of polynomials $R[x]$ (basically arithmetic expressions in the variable $x$) and think of any polynomial $f\in R[x]$ giving rise to a function $R\to R$ defined by substituing in for $x$ in $f$ and computing using $+$ and $\cdot$ as defined in $R$.

So, in full, a ring $R$ is a set equipped with

• $(+):R\times R\to R$

• $(\cdot ):R\times R\to R$

• $(-):R\to R$

• $0\in R$

• $1\in R$

such that

• $(+,0,-)$ gives the structure of an abelian group

• $(\cdot )$ is associative and commutative with identity $1$

• $+$ distributes over $\cdot$. I.e., $x\cdot (y+z)=x\cdot y+x\cdot z$ for all $x,y,z$.

Intro

The purpose of this document is to give the reader mathematical, cryptographic, and programming context sufficient to become an effective practitioner of zero-knowledge proofs and ZK-SNARKs specifically.

Some fundamental mathematical objects

In this section we’ll discuss the fundamental objects used in the construction of most ZK-SNARKs in use today. These objects are used extensively and without ceremony, so it’s important to understand them very well.

If you find you don’t understand something at first, don’t worry: practice is often the best teacher and in using these objects you will find they will become like the bicycle you’ve had for years: like an extension of yourself that you use without a thought.

Fields

A field is a generalization of the concept of a number. To be precise, a field is a set $F$ equipped with

• An element $0\in F$

• An element $1\in F$

• A function $\mathsf{mul}:F\times F\to F$

• A function $\mathsf{add}:F\times F\to F$

• A function $\mathsf{sub}:F\times F\to F$

• A function $\mathsf{div}:F\times (F\setminus \{0\})\to F$

Note that the second argument to $\mathsf{div}$ cannot be $0$. We write these functions in the traditional infix notation writing

• $xy$ or $x\cdot y$ for $\mathsf{mul}(x,y)$

• $x+y$ for $\mathsf{add}(x,y)$

• $x-y$ for $\mathsf{sub}(x,y)$

• $\frac{x}{y}$ for $\mathsf{div}(x,y)$

and we also write $x^{-1}$ for $\mathsf{div}(1,x)$ and $-x$ for $\mathsf{sub}(0,x)$.

Moreover all these elements and functions must obey all the usual laws of arithmetic, such as

• $x+(y+z)=(x+y)+z$

• $x+y=y+x$

• $x+(-x)=0$

• $x+0=x$

• $x(yz)=(xy)z$

• $xy=yx$

• $\frac{x}{y}=z$ if and only if $x=zy$, assuming $y\ne 0$.

• $1\cdot x=x$

• $x(y+z)=xy+xz$

In short, $F$ should be an abelian group over $+$ with $0$ as identity and $\mathsf{sub}(0,-)$ as inverse, $F\setminus \{0\}$ should be an abelian group over $\cdot$ with $1$ as identity and $\mathsf{div}(1,-)$ as inverse, and addition should distribute over multiplication. If you don’t know what an abelian group is, don’t worry, we will cover it later.

The point of defining a field is that we can algebraically manipulate elements of a field the same way we do with ordinary numbers, adding, multiplying, subtracting, and dividing them without worrying about rounding, underflows, overflows, etc.

In Rust, we use the trait Field to represent types that are fields. So, if we have T : Field then values of type T can be multiplied, subtracted, divided, etc.

Examples

The most familiar examples of fields are the real numbers $\mathbb{R}$ and the rational numbers $\mathbb{Q}$ (ratios of integers). Some readers may also be friends with the complex numbers $\mathbb{C}$ which are also a field.

The fields that we use in ZKPs, however, are different. They are finite fields. A finite field is a field with finitely many elements. This is in distinction to the fields $\mathbb{Q},\mathbb{R}$, and $\mathbb{C}$, which all have infinitely many elements.

What are finite fields like?

In this section we’ll try to figure out from first principles what a finite field should look like. If you just want to know the answer, feel free to skip to the next section.

Let’s explore what a finite field can possibly be like. Say $F$ is a finite field. If $n$ is a natural number like $4$ or $87$ we can imagine it as an element of $F$ by writing $\underset{n}{\underbrace{1+\cdots +1}}$.

Since $F$ is finite it must be the case that we can find two distinct natural numbers $n<m$ which are the same when interpreted as elements of $F$.

Then, $m-n=0$, which means the $F$ element $\underset{m-n}{\underbrace{1+\cdots +1}}$ is $0$. Now that we have established that if you add $1$ to itself enough times you get $0$, let $p$ be the least natural number such that if you add $1$ to itself $p$ times you get $0$.

Now let’s show that $p$ is prime. Suppose it’s not, and $p=ab$. Then since $p=0$ in $F$, $ab=0$. It is a fact about fields (exercise) that if $ab=0$ then either $a$ is 0 or $b$ is 0. Either way, we would then get a natural number smaller than $p$ which is equal to $0$ in $F$, which is not possible since $p$ is the smallest such number. So we have demonstrated that $p$ is prime.

The smallest number of times you have to add $1$ to itself to get 0 is called the characteristic of the field $F$. So, we have established that every finite field has a characteristic and it is prime.

This gives us a big hint as to what finite fields should look like.

Prime order fields

With the above in hand, we are ready to define the simplest finite fields, which are fields of prime order (also called prime order fields).

Let $p$ be a prime. Then ${\mathbb{F}}_p$ (pronounced “eff pee” or “the field of order p”) is defined as the field whose elements are the set of natural numbers $\{0,1,\dots ,p-1\}$.

• $0$ is defined to be $0$

• $1$ is defined to be $1$

• $\mathsf{add}(x,y)=(x+y)\mathrm{mod}p$

• $\mathsf{sub}(x,y)=(x-y)\mathrm{mod}p$

• $\mathsf{mul}(x,y)=(x\cdot y)\mathrm{mod}p$

• $\mathsf{div}(x,y)=(x\cdot y^{p-2})\mathrm{mod}p$

Basically, you just do arithmetic operations normally, except you take the remainder after dividing by $p$. This is with the exception of division which has a funny definition. Actually, a more efficient algorithm is used in practice to calculate division, but the above is the most succinct way of writing it down.

If you want, you can try to prove that the above definition of division makes the required equations hold, but we will not do that here.

Let’s work out a few examples.

2 is a prime, so there is a field ${\mathbb{F}}_2$ whose elements are $\{0,1\}$. The only surprising equation we have is

• $1+1=0$

Addition is XOR and multiplication is AND.

Let’s do a more interesting example. 5 is a prime, so there is a field whose elements are $\{0,1,2,3,4\}$. We have

$$\begin{array}{rl}\frac{1}{2}& =1\cdot 2^{5-2}\\ & =2^3\\ & =8\\ & =3\end{array}$$

where the last equality follows because everything is mod 5.

We can confirm that 3 is in fact $\frac{1}{2}$ by multiplying 3 and 2 and checking the result is 1.

$$\frac{1}{2}\cdot 2=3\cdot 2=6=1$$

so that checks out.

In cryptography, we typically work with much larger finite fields. There are two ways to get a large finite field.

1. Pick a large prime $p$ and take the field ${\mathbb{F}}_p$. This is what we do in Mina, where we use fields in which $p$ is on the order of $2^{255}$.

2. Take an extension of a small finite field. We may expand this document to talk about field extensions later, but it does not now.

Algorithmics of prime order fields

For a finite field ${\mathbb{F}}_p$ where $p$ fits in $n$ bits (i.e., $p<2^n$) we have

• Addition, subtraction: $O(n)$

• Multiplication $O(n^2)$

• Division $O(n^2)$ I believe, in practice significantly slower than multiplication.

Actually, on a practical level, it’s more accurate to model the complexity in terms of the number of limbs rather than the number of bits where a limb is 64 bits. Asymptotically it makes no difference but concretely it’s better to think about the number of limbs for the most part.

As a result you can see it’s the smaller $n$ is the better, especially with respect to multiplication, which dominates performance considerations for implementations of zk-SNARKs, since they are dominated by elliptic curve operations that consist of field operations.

While still in development, Mina used to use a field of 753 bits or 12 limbs and now uses a field of 255 bits or 4 limbs. As a result, field multiplication became automatically sped up by a factor of $12^2/4^2=9$, so you can see it’s very useful to try to shrink the field size.

Polynomials

The next object to know about is polynomials. A polynomial is a syntactic object that also defines a function.

Specifically, let $R$ be a field (or more generally it could even be a ring, which is like a field but without necessarily having division, like the integers $\mathbb{Z}$). And pick a variable name like $x$. Then $R[x]$ (pronounced, “R adjoin x” or “polynomials in x over R” or “polynomials in x with R coefficients”) is the set of syntactic expressions of the form

$$a_0+a_{1}x+a_2{x}^2+\cdots +a_d{x}^d$$

where each $a_i\in R$ and $d$ is any natural number. If we wanted to be very formal about it, we could define $R[x]$ to be the set of lists of elements of $R$ (the lists of coefficients), and the above is just a suggestive way of writing that list.

An important fact about polynomials over $R$ is that they can be interpreted as functions $R\to R$. In other words, there is a function $\mathsf{eval}:R[x]\to (R\to R)$ defined by

$$\mathsf{eval}(a_0+a_{1}x+\cdots +a_d{x}^d)=(y:R)\mapsto a_0+a_{1}y+\cdots +a_d{y}^d$$

where $x$ is just a variable name without a value assigned to it and $\mathsf{eval}$ maps it to a field element $y$ and evaluates the function as the inner product between the list of coefficients and the powers of $y$.

It is important to remember that polynomials are different than the functions that they compute. Polynomials are really just lists of coefficients. Over some fields, there are polynomials $p1$ and $p2$ such that $\mathsf{eval}(p1)=\mathsf{eval}(p2)$, but $p1\ne p2$.

For example, consider in ${\mathbb{F}}_2[x]$ the polynomials $x$ and $x^2$. These map to the same function ${\mathbb{F}}_2\to {\mathbb{F}}_2$ (meaning for $x\in R={\mathbb{F}}_2=\{0,1\}$ it holds that $x=x^2$), but are distinct polynomials.

Some definitions and notation

If $f$ is a polynomial in $R[x]$ and $a\in R$, we write $f(a)$ for $\mathsf{eval}(f)(a)$

If $f$ is a polynomial, the degree of $f$ is the largest $d$ for which the coefficient of $x^d$ is non-zero in $f$. For example, the degree of $x^3+2x^{10}$ is 10.

We will use the notation $R[x{]}_{<d}$ and $R[x{]}_{\le d}$ for the set of polynomials of degree less-than and less-than-or-equal $d$ respectively.

Polynomials can be added (by adding the coefficients) and multiplied (by carrying out the multiplication formally and collecting like terms to reduce to a list of coefficients). Thus $R[x]$ is a ring.

Fundamental theorem of polynomials

An important fact for zk-SNARKs about polynomials is that we can use them to encode arrays of field elements. In other words, there is a way of converting between polynomials of degree $d$ and arrays of field elements of length $d+1$.

This is important for a few reasons

• It will allow us to translate statements about arrays of field elements into statements about polynomials, which will let us construct zk-SNARKs.

• It will allow us to perform certain operations on polynomials more efficiently.

So let’s get to defining and proving this connection between arrays of field elements.

The first thing to understand is that we won’t be talking about arrays directly in this section. Instead, we’ll be talking about functions $A\to F$ where $A$ is a finite subset of $F$. The idea is, if $A$ has size $n$, and we put an ordering on $A$, then we can think of a function $A\to F$ as the same thing as an immutable array of length $n$, since such a function can be thought of as returning the value of an array at the input position.

With this understanding in hand, we can start describing the “fundamental theorem of polynomials”. If $A\subseteq F$ has size $d+1$, this theorem will define an isomorphism between functions $A\to F$ and $F[x{]}_{\le d}$, the set of polynomials of degree at most $d$.

Now let’s start defining this isomorphism.

One direction of it is very easy to define. It is none other than the evaluation map, restricted to $A$:

$$\begin{array}{rl}{\mathsf{eval}}_A& :F[x{]}_{\le d}\to (A\to F)\\ {\mathsf{eval}}_A& (c_0+\cdots +c_d{x}^d)=a\mapsto \sum _{i\le d}{c}_i{a}^i\end{array}$$

We would now like to construct an inverse to this map. What would that mean? It would be a function that takes as input a function $\phi :A\to F$ (remember, basically an array of length $|A|$), and returns a polynomial $f$ which agrees with $\phi$ on the set $A$. In other words, we want to construct a polynomial that interpolates between the points $(a,\phi (a))$ for $a\in A$.

Our strategy for constructing this polynomial will be straightforward. For each $a\in A$, we will construct a polynomial $f_a$ that is equal to $\phi (a)$ when evaluated at $a$, and equal to $0$ when evaluated anywhere else in the set $A$.

Then, our final polynomial will be $f:={\sum }_{a\in A}{f}_a$. Then, when $f$ is evaluated at $a_0\in A$, only the $f_{a_0}$ term will be non-zero (and equal to $\phi (a_0)$ as desired), all the other terms will disappear.

Constructing the interpolation map requires a lemma.

Lemma. (construction of vanishing polynomials)

Let $S\subseteq F$. Then there is a polynomial $v_S\in F[x]$ of degree $|S|$ such that $v_S$ evaluates to $0$ on $S$, and is non-zero off of $S$. $v_S$ is called the vanishing polynomial of $S$.

Proof. Let $v_S={\prod }_{s\in S}(x-s)$. Clearly $v_S$ has degree $|S|$. If $t\in S$, then $v_S(t)=0$ since $x-t$ is one of the terms in the product defining $v_S$, so when we evaluate at $t$, $t-t=0$ is one of the terms. If $t\notin S$, then all the terms in the product are non-zero, and thus $v_S(t)$ is non-zero as well. $\square$

Now we can define the inverse map. Define

$$\begin{array}{rl}{\mathsf{interp}}_A& :(A\to F)\to F[x{]}_{\le d}\\ {\mathsf{interp}}_A& (f)=\sum _{a\in A}\frac{f(a)}{v_{A\setminus \{a\}}(a)}\cdot v_{A\setminus \{a\}}\end{array}$$

Since each $v_{A\setminus \{a\}}$ has degree $d$, this polynomial has degree $d$. Now we have, for any $b\in A$,

$$\begin{array}{rl}{\mathsf{eval}}_A({\mathsf{interp}}_A(f))(b)& =\sum _{a\in A}\frac{f(a)}{v_{A\setminus \{a\}}(a)}\cdot v_{A\setminus \{a\}}(b)\\ & =\frac{f(b)}{v_{A\setminus \{b\}}(b)}\cdot v_{A\setminus \{b\}}(b)+\sum _{a\ne b}\frac{f(a)}{v_{A\setminus \{a\}}(a)}\cdot v_{A\setminus \{a\}}(b)\\ & =f(b)+\sum _{a\ne b}\frac{f(a)}{v_{A\setminus \{a\}}(a)}\cdot 0\\ & =f(b)\end{array}$$

Thus ${\mathsf{eval}}_A\circ {\mathsf{interp}}_A$ is the identity.

So we have successfully devised a way of interpolating a set of $d+1$ points with a polynomial of degree $d$.

What remains to be seen is that these two maps are inverse in the other direction. That is, that for any polynomial $f\in F[x]$, we have

$${\mathsf{interp}}_A({\mathsf{eval}}_A(f))=f$$

This says that if we interpolate the function that has the values of $f$ on $A$, we get back $f$ itself. This essentially says that there is only one way to interpolate a set of $d+1$ points with a degree $d$ polynomial. So let’s prove it by proving that statement.

Lemma: polynomials that agree on enough points are equal.

Let $F$ be a field and suppose $f,g\in F[x]$ have degree at most $d$. Let $A\subseteq F$ have size $d+1$.

Suppose for all $a\in A$, $f(a)=g(a)$. Then $f=g$ as polynomials.

Proof. Define $h:=f-g$. Our strategy will be to show that $h$ is the zero polynomial. This would then imply that $f=g$ as polynomials. Note that $h$ vanishes on all of $A$ since $f$ and $g$ are equal on $A$.

To that end, let $a\in A$. Then we can apply the polynomial division algorithm to divide $h$ by $x-a$ and obtain polynomials $q_a,r_a$ such that $h=q_a(x-a)+r_a$ and $r_a$ has degree less than 1. I.e., $r_a$ is a constant in $F$.

Now, $$0=h(a)=q_a(a)\cdot 0+r_a=r_a$$ so $r_a=0$ and thus $h=q_a(x-a)$.

Note that $q_a$ is 0 on all elements $b\in A$ with $b\ne a$ since $h(b)=q_a(b)(b-a)=0$, but $b-a\ne 0$.

Thus, if we iterate the above, enumerating the elements of $A$ as $a_0,\dots ,a_d$, we find that $$\begin{array}{rl}h& =(x-a_0)q_{a_0}\\ & =(x-a_0)(x-a_1)q_{a_1}\\ & =\dots \\ & =(x-a_0)(x-a_1)\dots (x-a_d)q_{a_d}\end{array}$$

Now, if $q_{a_d}$ is not the zero polynomial, then $h$ will have degree at least $d+1$ since it would have as a factor the $d+1$ linear terms $(x-a_i)$. But since $f,g$ both have degree at most $d$ and $h=f-g$, $h$ has degree at most $d$ as well. Thus, $q_{a_d}=0$, which means $h=0$ as well.

This gives us the desired conclusion, that $f=g$ as polynomials. $\square$

Now we can easily show that interpolating the evaluations of a polynomial yields that polynomial itself. Let $f\in F[x{]}_{\le d}$. Then ${\mathsf{interp}}_A({\mathsf{eval}}_A(f))$ is a polynomial of degree at most $d$ that agrees with $f$ on $A$, a set of size $d+1$. Thus, by the lemma, they are equal as polynomials. So indeed $${\mathsf{interp}}_A({\mathsf{eval}}_A(f))=f$$ for all $f\in F[x]$.

So far we have proven that ${\mathsf{interp}}_A$ and ${\mathsf{eval}}_A$ give an isomorphism of sets (i.e., a bijection) between the sets $A\to F$ and $F[x{]}_{\le d}$.

But we can take this theorem a bit further. The set of functions $A\to F$ can be given the structure of a ring, where addition and multiplication happen pointwise. I.e., for $f,g:A\to F$ we define $f+g:=a\mapsto f(a)+g(a)$ and $f\cdot g:=a\mapsto f(a)\cdot g(a)$. Then we can strengthen our theorem to say

Fundamental theorem of polynomials (final version)

Let $d\in \mathbb{N}$ and let $A\subseteq F$ with $|A|=d+1$. With

$$\begin{gathered} {\mathsf{eval}}_A:F[x{]}_{\le d}\to (A\to F) \\ {\mathsf{interp}}_A:(A\to F)\to F[x{]}_{\le d} \end{gathered}$$

defined as above, these two functions define an isomorphism of rings.

That is is, they are mutually inverse and each one respects addition, subtraction and multiplication.

The fundamental theorem of polynomials is very important when it comes to computing operations on polynomials. As we will see in the next section, the theorem will help us to compute the product of degree $n$ polynomials in time $O(n\log n)$, whereas the naive algorithm takes time $O(n^2)$. To put this in perspective, if $n=2^{16}$, $n^2$ is $4096$ times larger than $n\log n$ and the gap only gets bigger as $n$ grows.

Schwartz–Zippel lemma

Computer representation

There are three common representations for polynomials used in computer implementations.

1. Dense coefficient form. A degree $d$ polynomial is represented as a vector of length $d+1$ of all the coefficients. Entry $i$ of the vector corresponds to the coefficient $a_i$. This corresponds to the DensePolynomial type in arkworks. Sometimes this is also described as writing the polynomial “in the monomial basis”, because it amounts to writing the polynomial as a linear combination of the monomials $x^i$.

2. Sparse coefficient form. If a polynomial does not have very many non-zero coefficients, the above representation is wasteful. In sparse coefficient form, you represent a polynomial as a vector (or potentially a hash-map) of pairs (usize, F) where F is the type of coefficients. The polynomial corresponding to the list [(i_0, b_0), ..., (i_n, b_n)] is $b_0{x}^{i_0}+\cdots +b_n{x}^{i_n}$

3. Evaluation form. We fix an index set $A\subseteq F$, with $A=\{a_0,\dots ,a_d\}$, and represent a polynomial $f\in F[x{]}_{\le d}$ as the vector [f(a_0), ..., f(a_d)]. By the fundamental theorem of polynomials, this is a valid way of representing the polynomials, since the coefficients form can be obtained by using the ${\mathsf{interp}}_A$ function.

The evaluation form is very important. The reason is that multiplying two polynomials in the evaluation form takes time $O(n)$. You just multiply the two vectors entry-wise. By contrast, the coefficient forms naively require time $O(n^2)$ to multiply.

Now, there is a trick. For certain sets $A\subseteq F$, we can efficiently translate between the dense coefficients form and the evaluation form. That is, for certain $A$, the functions ${\mathsf{interp}}_A$ and ${\mathsf{eval}}_A$ can be computed more efficiently than $O(n^2)$.

Multiplying polynomials

The algorithm that allows us to multiply polynomials in $O(n\log n)$ is called the Cooley-Tukey fast Fourier transform, or FFT for short. It was discovered by Gauss 160 years earlier, but then separately rediscovered and publicized by Cooley-Tukey.

The heart of Cooley-Tukey FFT is actually about converting between coefficient and evaluation representations, rather than the multiplication itself. Given polynomials $p$ and $q$ in dense coefficient representation, it works like this.

1. Convert $p$ and $q$ from coefficient to evaluation form in $O(n\log n)$ using Cooley-Tukey FFT
2. Compute $r=p\ast q$ in evaluation form by multiplying their points pairwise in $O(n)$
3. Convert $r$ back to coefficient form in $O(n\log n)$ using the inverse Cooley-Tukey FFT

The key observation is that we can choose any $n$ distinct evaluation points to represent any degree $n-1$ polynomial. The Cooley-Tukey FFT works by selecting points that yield an efficient FFT algorithm. These points are fixed and work for any polynomials of a given degree.

The next section describes the Cooley-Tukey FFT in detail.

Fast Fourier Transform (FFT)

This section describes how the Cooley-Tukey fast Fourier transform works. As we learned in the previous section, the key is to select evaluation points that yield an efficient FFT algorithm.

Specifically, say we have $\omega \in F$ such that ${\omega }^n=1$, and ${\omega }^r\ne 1$ for any $0<r<n$.

Put another way, all the values $1,\omega ,{\omega }^2,{\omega }^3,\dots ,{\omega }^{n-1}$ are distinct and ${\omega }^n=1$.

Put yet another way, the group generated by $\omega$ inside $F^{\times }$ (written $⟨\omega ⟩$) has size $n$.

We call such an $\omega$ a primitive $n$-th root of unity.

Suppose we have an $\omega$ which is a primitive $2^k$th root of unity and let $A_k=\{1,\omega ,\dots ,{\omega }^{2^k-1}\}$.

The FFT algorithm will let us compute ${\mathsf{interp}}_{A_k}$ for this set.

Actually, it is easier to see how it will let us compute the ${\mathsf{eval}}_{A_k}$ algorithm efficiently.

We will describe an algorithm $\mathsf{FFT}(k,\omega ,f)$ that takes as input

• $k\in \mathbb{N}$
• $\omega \in F$ a primitive $2^k$th root of unity
• $f\in F[x{]}_{<2^k}$ in dense coefficients form (i.e., as a vector of coefficients of length $n$).

and outputs the vector of evaluations $$[f(1),f(\omega ),f({\omega }^2)\dots ,f({\omega }^{2^k-1})]$$ and does it in time $O(k{2}^k)$ (which is to say, $n\log n$ if $n=2^k$).

Notice that naively, computing each evaluation $f({\omega }^i)$ using the coefficients of $f$ would require time $O(n)$, and so computing all $n$ of them would require time $O(n^2)$.

The algorithm $\mathsf{FFT}(k,\omega ,f)$ can be defined recursively as follows.

If $k=0$, then $\omega$ is a primitive $1$st root of unity, and $f$ is a polynomial of degree $0$. That means $\omega =1$ and also $f$ is a constant $c\in F$. So, we can immediately output the array of evaluations $[c]=[f(1)]$.

If $k>0$, then we will split $f$ into two polynomials, recursively call $\mathsf{FFT}$ on them, and reconstruct the result from the recursive calls.

To that end, define $f_0$ to be the polynomial whose coefficients are all the even-index coefficients of $f$ and $f_1$ the polynomial whose coefficients are all the odd-index coefficients of $f$. In terms of the array representation, this just means splitting out every other entry into two arrays. So that can be done in time $O(n)$.

Write $f={\sum }_{i<2^k}{c}_i{x}^i$, so that $f_0={\sum }_{i<2^{k-1}}{c}_{2i}{x}^i$ and $f_1={\sum }_{i<2^{k-1}}{c}_{2i+1}{x}^i$. Then

$$\begin{array}{rl}f(x)& =\sum _{i<2^k}{c}_i{x}^i\\ & =\sum _{i<2^{k-1}}{c}_{2i}{x}^{2i}+\sum _{i<2^{k-1}}{c}_{2i+1}{x}^{2i+1}\\ & =\sum _{i<2^{k-1}}{c}_{2i}(x^2{)}^i+\sum _{i<2^{k-1}}{c}_{2i+1}x\cdot (x^2{)}^i\\ & =\sum _{i<2^{k-1}}{c}_{2i}(x^2{)}^i+x\sum _{i<2^{k-1}}{c}_{2i+1}(x^2{)}^i\\ & =f_0(x^2)+x{f}_1(x^2)\end{array}$$

Now, notice that if $\omega$ is a $2^k$th root of unity, then ${\omega }^2$ is a $2^{k-1}$th root of unity. Thus we can recurse with $\mathsf{FFT}(k-1,{\omega }^2,f_0)$ and similarly for $f_1$. Let

$$\begin{array}{rl}[e_{0,0},\dots ,e_{0,2^{k-1}-1}]& =\mathsf{FFT}(k-1,{\omega }^2,f_0)\\ [e_{1,0},\dots ,e_{1,2^{k-1}-1}]& =\mathsf{FFT}(k-1,{\omega }^2,f_1)\end{array}$$

By assumption $e_{i,j}=f_i(({\omega }^2{)}^j)$. So, for any $j$ we have

$$\begin{array}{rl}f({\omega }^j)& =f_0(({\omega }^2{)}^j)+{\omega }^j{f}_1(({\omega }^2{)}^j)\end{array}$$

Now, since $j$ may be larger than $2^{k-1}-1$, we need to reduce it mod $2^{k-1}$, relying on the fact that if $\tau$ is an $n$th root of unity then ${\tau }^j={\tau }^{j\mathrm{mod}n}$ since ${\tau }^n=1$. Thus, $({\omega }^2{)}^j=({\omega }^2{)}^{j\mathrm{mod}{2}^{k-1}}$ and so we have

$$\begin{array}{rl}f({\omega }^j)& =f_0(({\omega }^2{)}^{j\mathrm{mod}{2}^{k-1}})+{\omega }^j{f}_1(({\omega }^2{)}^{j\mathrm{mod}{2}^{k-1}})\\ & =e_{0,j\mathrm{mod}{2}^{k-1}}+{\omega }^j{e}_{1,j\mathrm{mod}{2}^{k-1}}\end{array}$$

We can compute the array $W=[1,\omega ,\dots ,{\omega }^{2^k-1}]$ in time $O(n)$ (since each entry is the previous entry times $\omega$). Then we can compute each entry of the output in $O(1)$ as

$$\begin{array}{rl}f({\omega }^j)& =e_{0,j\mathrm{mod}{2}^{k-1}}+W[j]\cdot e_{1,j\mathrm{mod}{2}^{k-1}}\end{array}$$

There are $n$ such entries, so this takes time $O(n)$.

This concludes the recursive definition of the algorithm $\mathsf{FFT}(k,\omega ,f)$.

Algorithm: computing ${\mathsf{eval}}_{A_k}$

• $\mathsf{Input}f=[c_0,\dots ,c_{2^k-1}]$ the coefficients of polynomial $f(x)={\sum }_{i<2^k}{c}_i{x}^i$
• $\mathsf{Compute}W\leftarrow \left[1,\omega ,{\omega }^2,\dots ,{\omega }^{2^k-1}\right]$
• $\mathsf{FFT}(k,\omega ,f)\to \left[f(1),f(\omega ),f({\omega }^2)\dots ,f({\omega }^{2^k-1})\right]$
  • $\mathtt{if}k==0$
    • $\mathtt{return}f$
  • $\mathtt{else}$
    • $\mathsf{Compute}{f}_0=[c_0,c_2,\dots ,c_{2^k-2}]$ the even coefficients of $f,$ corresponding to $f_0(x)={\sum }_{i<2^{k-1}}{c}_{2i}{x}^i$
    • $\mathsf{Compute}{f}_1=[c_1,c_3,\dots ,c_{2^k-1}]$ the odd coefficients of $f,$ corresponding to $f_1(x)={\sum }_{i<2^{k-1}}{c}_{2i+1}{x}^i$
    • $e_0\leftarrow \mathsf{FFT}(k-1,{\omega }^2,f_0)$
    • $e_1\leftarrow \mathsf{FFT}(k-1,{\omega }^2,f_1)$
    • $\mathtt{for}j\in [0,2^k-1]$
      • $F_j\leftarrow e_{0,j\mathrm{mod}{2}^{k-1}}+W[j]\cdot e_{1,j\mathrm{mod}{2}^{k-1}}$
    • $\mathtt{return}F$

Now let’s analyze the time complexity. Let $T(n)$ be the complexity on an instance of size $n$ (that is, for $n=2^k$).

Looking back at what we have done, we have done

• $O(n)$ for computing $f_0$ and $f_1$
• two recursive calls, each of size $n/2$
• $O(n)$ for computing the powers of $\omega$
• $O(n)$ for combining the results of the recursive calls

In total, this is $O(n)+2T(n/2)$. Solving this recurrence yields $T(n)=O(n)\cdot logn=O(n\log n)$. Basically, there are $\log n$ recursions before we hit the base case, and each step takes time $O(n)$. $\square$

Now, in practice there are ways to describe this algorithm non-recursively that have better concrete performance, but that’s out of scope for this document. Read the code if you are interested.

Using the FFT algorithm to compute ${\mathsf{interp}}_{A_k}$

So far we have a fast way to compute ${\mathsf{eval}}_{A_k}(f)$ all at once, where $A_k$ is the set of powers of a $2^k$th root of unity $\omega$. For convenience let $n=2^k$.

Now we want to go the other way and compute a polynomial given an array of evaluations. Specifically, $n$ evaluations $\left[f(x_0),f(x_1),\dots ,f(x_{n-1})\right]$ uniquely define a degree $n-1$ polynomial. This can be written as a system of $n$ equations

$$\begin{array}{rl}f(x_0)& =c_0+c_1{x}_0+\dots +c_{n-1}{x}_0^{n-1}\\ f(x_1)& =c_0+c_1{x}_1+\dots +c_{n-1}{x}_1^{n-1}\\ ⋮& \\ f(x_{n-1})& =c_0+c_1{x}_{n-1}+\dots +c_{n-1}{x}_{n-1}^{n-1},\end{array}$$ which can be rewritten as a matrix vector product. $$\left[\begin{array}{c}f(x_0)\\ f(x_1)\\ ⋮\\ f(x_{n-1})\end{array}\right]=\left[\begin{array}{cccc}1& x_0& \cdots & x_0^{n-1}\\ 1& x_1& \cdots & x_1^{n-1}\\ ⋮& ⋮& \ddots & ⋮\\ 1& x_{n-1}& \cdots & x_{n-1}^{n-1}\end{array}\right]\times \left[\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_{n-1}\end{array}\right]$$ This $n\times n$ matrix is a Vandermonde matrix and it just so happens that square Vandermonde matrices are invertible, iff the $x_i$ are unique. Since we purposely selected our $x_i$ to be the powers of $\omega$, a primitive $n$-th root of unity, by definition $x_i={\omega }^i$ are unique.

Therefore, to compute the polynomial given the corresponding array of evaluations (i.e. interpolation) we can solve for the polynomial’s coefficients using the inverse of the matrix. $$\left[\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_{n-1}\end{array}\right]={\left[\begin{array}{cccc}1& 1& \cdots & 1^{n-1}\\ 1& \omega & \cdots & {\omega }^{n-1}\\ ⋮& ⋮& \ddots & ⋮\\ 1& {\omega }^{n-1}& \cdots & {\omega }^{(n-1)(n-1)}\end{array}\right]}^{-1}\times \left[\begin{array}{c}f(1)\\ f(\omega )\\ ⋮\\ f({\omega }^{n-1})\end{array}\right]$$ All we need now is the inverse of this matrix, which is slightly complicated to compute. I’m going to skip it for now, but if you have the details please make a pull request.

Substituting in the inverse matrix we obtain the equation for interpolation. $$\left[\begin{array}{c}{c}_0\\ c_1\\ ⋮\\ c_{n-1}\end{array}\right]=\frac{1}{n}\left[\begin{array}{cccc}1& 1& \cdots & 1^{n-1}\\ 1& {\omega }^{-1}& \cdots & {\omega }^{-(n-1)}\\ ⋮& ⋮& \ddots & ⋮\\ 1& {\omega }^{-(n-1)}& \cdots & {\omega }^{-(n-1)(n-1)}\end{array}\right]\times \left[\begin{array}{c}f(1)\\ f(\omega )\\ ⋮\\ f({\omega }^{n-1})\end{array}\right]$$ Observe that this equation is nearly identical to the original equation for evaluation, except with the following substitution. $${\omega }^i\Rightarrow \frac{1}{n}{\omega }^{-1i}$$ Consequently and perhaps surprisingly, we can reuse the FFT algorithm ${\mathsf{eval}}_{A_k}$ in order to compute the inverse– ${\mathsf{interp}}_{A_k}$.

So, suppose we have an array $[a_0,\dots ,a_{n-1}]$ of field elements (which you can think of as a function $A_k\to F$) and we want to compute the coefficients of a polynomial $f$ with $f({\omega }^i)=a_i$.

To this end, define a polynomial $g$ by $g={\sum }_{j<n}{a}_j{x}^j$. That is, the polynomial whose coefficients are the evaluations in our array that we’re hoping to interpolate.

Now, let $[e_0,\dots ,e_{n-1}]=\mathsf{FFT}(k,{\omega }^{-1},g)$.

That is, we’re going to feed $g$ into the FFT algorithm defined above with ${\omega }^{-1}$ as the $2^k$th root of unity. It is not hard to check that if $\omega$ is an n-th root of unity, so is ${\omega }^{-1}$. Remember: the resulting values are the evaluations of $g$ on the powers of ${\omega }^{-1}$, so $e_i=g({\omega }^{-i})={\sum }_{j<n}{a}_j{\omega }^{-ij}$.

Now, let $h={\sum }_{i<n}{e}_i{x}^i$. That is, re-interpret the values $e_i$ returned by the FFT as the coefficients of a polynomial. I claim that $h$ is almost the polynomial we are looking for. Let’s calculate what values $h$ takes on at the powers of $\omega$.

$$\begin{array}{rl}h({\omega }^s)& =\sum _{i<n}{e}_i{\omega }^{si}\\ & =\sum _{i<n}{\omega }^{si}\sum _{j<n}{a}_j{\omega }^{-ij}\\ & =\sum _{i<n}\sum _{j<n}{a}_j{\omega }^{si-ij}\\ & =\sum _{j<n}{a}_j\sum _{i<n}{\omega }^{i(s-j)}\end{array}$$

Now, let’s examine the quantity $c_j:={\sum }_{i<n}{\omega }^{i(s-j)}$. We claim that if $j=s$, then $c_j=n$, and if $j\ne s$, then $c_j=0$. The first claim is clear since

$$c_s=\sum _{i<n}{\omega }^{i(s-s)}=\sum _{i<n}{\omega }^0=\sum _{i<n}1=n$$

For the second claim, we will prove that ${\omega }^{s-j}{c}_j=c_j$. This implies that $(1-{\omega }^{s-j})c_j=0$. So either $1-{\omega }^{s-j}=0$ or $c_j=0$. The former cannot be the case since it implies ${\omega }^{s-j}=1$ which in turn implies $s=j$ which is impossible since we are in the case $j\ne s$. Thus we have $c_j=0$ as desired.

So let’s show that $c_j$ is invariant under multiplication by ${\omega }^{s-j}$. Basically, it will come down to the fact that ${\omega }^n={\omega }^0$.

$$\begin{array}{rl}{\omega }^{s-j}{c}_j& ={\omega }^{s-j}\sum _{i<n}{\omega }^{i(s-j)}\\ & =\sum _{i<n}{\omega }^{i(s-j)+(s-j)}\\ & =\sum _{i<n}({\omega }^{i+1}{)}^{s-j}\\ & =({\omega }^{0+1}{)}^{s-j}+({\omega }^{1+1}{)}^{s-j}+\cdots +({\omega }^{(n-1)+1}{)}^{s-j}\\ & =({\omega }^1{)}^{s-j}+({\omega }^2{)}^{s-j}+\cdots +({\omega }^n{)}^{s-j}\\ & =({\omega }^1{)}^{s-j}+({\omega }^2{)}^{s-j}+\cdots +({\omega }^0{)}^{s-j}\\ & =({\omega }^0{)}^{s-j}+({\omega }^1{)}^{s-j}+\cdots +({\omega }^{n-1}{)}^{s-j}\\ & =\sum _{i<n}({\omega }^i{)}^{s-j}\\ & =c_j\end{array}$$

So now we know that

$$\begin{array}{rl}h({\omega }^s)& =\sum _{j<n}{a}_j{c}_j\\ & =a_s\cdot n+\sum _{j\ne s}{a}_j\cdot 0\\ & =a_s\cdot n\end{array}$$

So if we define $f=h/n$, then $f({\omega }^s)=a_s$ for every $s$ as desired. Thus we have our interpolation algorithm, sometimes called an inverse FFT or IFFT:

Algorithm: computing ${\mathsf{interp}}_{A_k}$

0. Input: $[a_0,\dots ,a_{n-1}]$ the points we want to interpolate and $\omega$ a $n$th root of unity.

1. Interpret the input array as the coefficients of a polynomial $g={\sum }_{i<n}{a}_i{x}^n$.

2. Let $[e_0,\dots ,e_n]=\mathsf{FFT}(k,{\omega }^{-1},g)$.

3. Output the polynomial ${\sum }_{i<n}(e_i/n)x^i$. I.e., in terms of the dense-coefficients form, output the vector $[e_0/n,\dots ,e_{n-1}/n]$.

Note that this algorithm also takes time $O(n\log n)$

Takeaways

• Polynomials can be represented as a list of coefficients or a list of evaluations on a set $A$

• If the set $A$ is the set of powers of a root of unity, there are time $O(n\log n)$ algorithms for converting back and forth between those two representations

• In evaluations form, polynomials can be added and multiplied in time $O(n)$

  • TODO: caveat about hitting degree

Exercises

• Implement types DensePolynomial<F: FfftField> and Evaluations<F: FftField> that wrap a Vec<F> and implement the FFT algorithms described above for converting between them

• Familiarize yourself with the types and functions provided by ark_poly

Commitments

A “commitment scheme” is a cryptographic scheme that lets us provide a “commitment” to a given piece of data, in such a way that we can later “open” that commitment.

I recommend checking out section 2.4.1 of David’s book Real-World Cryptography. There are two properties we typically expect of our commitment schemes:

• Hiding. A commitment to a piece of data should not reveal anything about that data.

• Binding. There should be no ambiguity about what data is committed to. That is, it should not be possible for the committer to open the commitment to a piece of data other than the one they originally committed to.

There are various kinds of commitments that allow opening in different ways, revealing only part of the data, or some function of the data. Sometimes it is even useful to elide the hiding property entirely— so-called non-hiding commitments.

Simple commitments

The simplest kind of a commitment is one in which opening reveals all of the underlying data. Let’s give a simple construction of such a scheme for committing to field elements. Suppose we have

• ${\mathbb{F}}_p$ a prime order field, with $p$ being rather large (say on the order of $2^{256}$).

• A hash function $h:\mathsf{List}({\mathbb{F}}_p)\to {\mathbb{F}}_p$.

Then we define

$$\begin{gathered} \mathsf{commit}(x,r)=h([x,r]) \\ \mathsf{open}(c)=(x,r) \\ \mathsf{verify}(c,x,r)=true/false \end{gathered}$$

The argument $r$ of the $\mathsf{commit}$ function is data that must only be known to the committer (until the commitment is opened). When a committer wants to commit to a field element $x$, they sample a random “blinder” $r\in {\mathbb{F}}_p$ and hash it together with $x$ to form the commitment.

To open the commitment $c$, they simply provide the committed value together with the blinder. Alternatively, if the verifier already knows $x$, they can just provide $r$, i.e. $\mathsf{open}(x,c)=r$. Finally, given the commitment and the opening, we can verify whether the input was the value originally committed to using the $\mathsf{verify}$ function.

If the hash function is collision-resistant, then this function is binding (because there’s no way the committer could find another preimage of $h([x,r])$).

If the hash function is one-way, then this commitment is also hiding (assuming $x$ is revealed only as part of the opening).

Commitments are often used in protocols between provers and verifiers. The following illustration provides an example with a prover named Peggy and a verifier named Victor. $$\begin{array}{lcll}\text{Peggy}& & \text{Victor}& \\ \begin{array}{r}\mathsf{input}\\ \mathsf{blinder}\end{array}\}\to \boxed{\mathsf{commit}}& ⟶& \mathsf{commitment}& \\ & ⋮& & \\ & & & \\ \mathsf{commitment}\to \boxed{\mathsf{open}}& ⟶& \mathsf{input},\mathsf{blinder}& \\ & ⋮& & \\ & & \begin{array}{r}\mathsf{commitment}\\ \mathsf{input}\\ \mathsf{blinder}\end{array}\}\to \boxed{\mathsf{verify}}\to true/false& \end{array}$$