# The Moon and the Maths

## Chapter 1 - The Sea of Tranquility

This is an exploration of the Moon and the 'Moon Maths' that underlies Zero Knowledge Proofs.

Starting at the Apollo 11 landing site our journey will take us around the moon, each chapter introducing a new area of Maths.
The journey is based on the outline of the Moon Math Manual, a fantastic resource for learning ZKP Maths.

### What will we take on our journey?
- The Moon math manual ([download link](https://github.com/LeastAuthority/moonmath-manual/releases/latest/download/main-moonmath.pdf)) this is the guide to the maths we will be discussing, and we can try some of its exercises as we travel.
- Some music to help us think, an appropriate choice would be [Apollo Atmospheres and Soundtracks by Brian Eno.](https://en.wikipedia.org/wiki/Apollo:_Atmospheres_and_Soundtracks)
- Charts to help us navigate, fortunately NASA has made many charts [available](https://www.lpi.usra.edu/resources/mapcatalog/).

For companions we have Peggy and Victor :
Peggy will take the role of the person creating proofs, with Victor the verifier of the proofs.
Victor is a sceptic and always concerned that Peggy maybe trying to cheat him and provide an incorrect proof.
Peggy is most concerned about privacy, she wants to limit the information she provides to Victor.

We are ready to set off, but where are we going ?

Our journey takes us from the well understood landscape of the Sea of Tranquility to the mysterious dark side of the moon, from basic mathematics to elliptic curves and the processes used in ZKP systems

Our itinerary :

- **Chapter 1:** Sea of Tranquility (The basics).
- **Chapter 2:** Bay of Rainbows (Polynomials).
- **Chapter 3:** Ocean of Storms (Finite Fields).
- **Chapter 4:** Apennine Mountains (Abstract Algebra).
- **Chapter 5:** The Far Side (Elliptic Curves).
- **Chapter 6:** Sea of Moscow (R1CS).
- **Chapter 7:** Crater Tycho (Trusted Setup).
- **Chapter 8 :** The North Pole (Groth16 and True Zero Knowledge).

### A conflict in the Sea of Tranquility

There is a conflict between **Verification** and **Privacy**.
Imagine you want to prove you are 18, you could hand over a driving licence or passport, revealing your name, address, and exact birth date.
You give away _everything_ to prove _one thing_.
In the digital world most blockchains choose transparency, great for verifiability but no privacy
Banks emphasise privacy, your details remain private to the outside world, but transactions are not verifiable, we have to trust the bank.

The solution to the conflict lies with Zero Knowledge Proofs (ZKP) , we can have both verifiability (mathematical proofs) and privacy, the person verifying the proof learns no new information.

There are many analogies to help visualise ZKPs , lets try some :

Imagine that our journey to the moon started out as a secret search for an alien artifact (as happened in 2001 : A Space Odyssey)
As a research student you think you have discovered the site of the artifact in a photograph, and you need to share this with your supervisor, but if you give the exact coordinates, he will claim the discovery for himself.
A way round this would be to cover the photograph with a large piece of cardboard with just an artifact shaped hole in the cardboard. Your supervisor would be able to see the artifact through the hole, but not gain a frame of reference from other landmarks and so not learn the location.
They know you found it, but they have zero knowledge of _where_ it is.

Of course physically covering information is no use for digital assets, we need mathematical constructs to allow us to hide information.

Our journey then is an exploration of the mathematical concepts we need to create and verify zero knowledge proofs.

---
## Leaving the Sea of Tranquility

The aim in this first chapter is to establish the background in a well known setting, in the Sea of Tranquility (Mare Tranquillitatis).
Our destination is the **Bay of Rainbows**, some 1,500 kilometres away.
Initially we will head north to take us to the the Sea of Serenity (Mare Serenitatis) .


To the right: the sun is rising in the East.
Behind us the Earth hangs permanently in the sky at about 60 degrees elevation. It never moves.

### The lunar surface
The ground we are travelling over is grey and flat. The surface is called 'regolith' it is a collection of shattered rock and charcoal grey powder that covers the bedrock. It has been formed by meteorite impact, but the particles are sharp and can easily damage equipment. .

The horizon is deceptively close only a few kilometres away curving sharply because the moon is small.
There is no atmosphere to scatter the light, so there is no 'distance' haze. A rock 100 metres away looks as sharp and black as a rock 10 kilometres away. It is easy to lose your sense of scale and perspective.

Similarly in the realm of proofs it is easy to lose perspective, we need to establish some rules.
## The ground rules for ZKPs

Analogies are fine, but we need to clarify more rigorously what our requirements are for a ZKP. If we were to build a ZKP system it would have to follow 3 rules

- **Completeness :** If Peggy is honest and the statement she is proving is true, the math always works. Victor will always accept her proof

- **Soundness :** If the statement is false, Peggy cannot cheat. The probability of fooling Victor is negligible.

- **'Zero Knowledgeiness' :** If the statement is true, Victor learns nothing else. He is unable to reverse engineer the proof to find any of its secrets.

One hurdle many have encountered when studying ZKPs is the terminology involved, making sense of unfamiliar symbols and terms slows us down, acts as a drag on our understanding.
So while we are on familiar ground, lets go through some symbols we will be using, starting with the classification of numbers.

If you cast your mind back to school we progressed from using numbers that felt familiar and were used for familiar task such as counting, on to fractions, and then stranger numbers such as pi. Overtime we would have become more rigorous in our classification of these numbers.
Fortunately on this journey we stay with the simplest types of numbers.
### Integers
These are whole numbers, we represent them with the symbol $\mathbb{Z}$
### Rational Numbers
These are numbers that can be represented as a ratio of integers for these we use the symbol $\mathbb{Q}$

### Integers , division and remainders
Imagine we have decided to only work with Integers.
If we divide two integers we may get an integer as a result, for example 12 divided by 4 gives 3, but if we divide 13 by 4 we don't get an integer, but we could say we get 4 with a remainder of 1.
In ZKP maths we are often just concerned with remainders, like when we are telling the time we may only be interested in the minute hand rather than the hour hand, here the minutes represent a remainder.
Doing arithmetic in this way is called **modular** arithmetic, often called Clock Maths.

### Congruence
If we explore the remainders we see a concept called congruence, this is grouping together integers that produce the same remainder under division.

For example

13 divided by 4 gives remainder 1
17 divided by 4 gives remainder 1
21 divided by 4 gives remainder 1
and so on

The numbers 13, 17 and 21 ... are said to be congruent.

We will investigate more arithmetic in chapter 3 when we reach the Ocean of Storms and look at fields.

---

We leave the Sea of Tranquility, rising up to our left is the **Apennine Mountain Range**.
These are 5,000 metre peaks higher than the Alps forming a massive wall.

The **Crater Plinius** stands sentinel here. It is a sharp, 43km-wide crater with a central peak.

We are leaving the familiar behind and heading for the unknown, time to introduce more terminology and concepts.

### Computational Asymmetry & The Witness

As you read about ZKPs you will come across the term 'witness', this is what we call the secret data, the information that Peggy knows and wants to prove she knows, but doesn't want to reveal to Victor.
The statement is the claim that Peggy is making, she is claiming that she knows the witness, it is this claim that is to be proven.

A fundamental concept in cryptography is Asymmetry, we shall return to this many times in the journey.
In computation there is a difference between _doing_ the work and _checking_ the work.
For example
- **Finding the Alien Artifact (The Witness):** This is hard. It requires a vehicle, fuel, time, and luck. It is computationally expensive.

- **Checking the Photograph (The Statement):** This is easy. It takes a split second.

If solving a problem were easy, we wouldn't need a proof—we would just solve it ourselves.
ZKPs rely on this imbalance, indeed this is an aspect of ZKPs that can seem too good to be true.
We can prove we have done the "hard work" (found the Witness) without forcing the Verifier to redo the whole journey.

This comes into play when we design ZKP systems, we often say that the system needs to be 'succinct' , that is the proof should be small enough to be manageable, and the time taken to verify it should be reasonably short.
Later in our journey I will be much more rigorous about these definitions.


### The Crossing into the Sea of Rains (Mare Imbrium)

We cannot drive over the Apennine mountains. We have to pass through the **Hadley-Apennine Gap** (this is where Apollo 15 landed).

This is a narrow corridor where the mountains meet the marshy **Palus Putredinis** (Marsh of Decay).

To our immediate left, a massive winding canyon called **Hadley Rille**, to the right, the towering Mount Hadley.

We won't climb the Apennines yet that is a challenge for Chapter 4, when we tackle the heavy lifting of Abstract Algebra.

Once we clear the mountains, the world opens up. We enter the Sea of Rains.
This is a gigantic, flat impact basin.
It is an ocean of stone.
We have 1,000km of open driving here.

We navigate by three massive craters in the distance: **Archimedes**, **Autolycus**, and **Aristillus**.

## Crossing the Terminator
As we travel northwest we will come to the terminator line, marking the boundary between day and night.
On Earth light is reflected from the atmosphere giving a period of dusk.
The lack of atmosphere on the moon means that the change from day to night is much more abrupt.

Such a sharp distinction between light and dark is something we want for our proofs. we want an exact and easily tested cutoff between a valid and an invalid proof.

In the underlying maths, we achieve this through probability. While theoretically 'probabilistic', the chance of a false proof being accepted is so vanishingly small (like guessing a specific grain of sand in this desert) that for all practical purposes, it is a sharp, solid wall.
Victor can be as confident in the math as he is that the Earth will never set

## Looking ahead

The shadows are getting longer. The math is about to get steeper.
Next stop: **Sinus Iridum** where we will learn that every secret is just a point on a polynomial curve.

---

# Chapter 2: Polynomials in the Bay of Rainbows

We have travelled from the Sea of Tranquility into the Sea of Rains, now to the Northwest is our destination, the Bay of Rainbows.

The travel across the Sea of Rains is quite smooth, but our companions **Peggy** and **Victor** have been arguing all the way, arguing about the design of ZKP systems.

**Victor**: The trick with the cardboard was fun, but I'm not looking through a hole in some cardboard every time I want to check a proof.

**Peggy** : Of course not, we'll have a numeric representation of the proof.

**Victor**: It shouldn't be a lot of work to verify either. If it takes as long to verify as it takes to do the original computation, why have a proving system?

**Peggy**: True, we make it quick to verify.

**Victor**: And I don't want you telling me what to check. You might mislead me. I want to be able to check the proof however I like.

**Peggy**: OK, but don't think you are going to reverse engineer the proof and find my secret.

**Victor**: That's fair, but is this all possible? Will I need to learn some obscure and difficult mathematical objects to do this?

**Peggy**: Not at all. In fact, one of the major mathematical objects we will use is something you already know: the Polynomial.

We come over the final ridge into **Sinus Iridum**, The Bay of Rainbows. It is a massive, flat plain of basalt, but what catches the eye is the **Montes Jura** mountain range that curves around it.

In the low lunar light, the bay floor is in shadow, but the sun catches the peaks of the mountains, creating a perfect, glowing 'C' shape floating in the darkness. Astronomers call this the Golden Handle.


By NASA, LRO - http://lroc.sese.asu.edu/news/index.php?/archives/828-A-Great-Place-to-Rove!.html#extended

Peggy points out the curve of the mountains to Victor.

"Look at that arc, that is a polynomial. On the ground, it's just a pile of scattered rocks, but from up here, you see the structure. You see the curve that connects them."

## Polynomials

Fortunately for us, polynomials are straightforward, yet powerful mathematical objects that we have most likely some experience of from our schooldays.

A typical polynomial might look like:

$$y = 2x^3 + 4x^2 + 9x + 7$$

The polynomial is made of a number of terms added together, where a term is a variable to some power multiplied by a coefficient, such as $2x^3$.

The above is a univariate polynomial, we have just one variable $x$, but we can have multivariate polynomials that have more than one variable such as:

$$z = 8x^2 + 3y + 4x + 9$$

Some of the properties of polynomials make them useful in ZKPs:

1. **Simple to manipulate:** We can do arithmetic on polynomials quite simply.

2. **Dual Representation:** They have two forms: a **coefficient form** (as above), or a **point value form** (where we list the points the polynomial passes through). There are simple means to convert between the two.

3. **Capacity:** They can contain a lot of information; we can construct polynomials with millions of terms.

4. **Identity Testing:** We can say with certainty and with minimal checking—even checking just one point—whether two polynomials are the same or different.

Lets dig into some of those points in more detail :

### Point 2: The Two Views

If you imagine a polynomial plotted on a graph, we could describe it either by its equation (coefficients) or by the points it passes through.

- **Coefficient Form:** This is the "God's Eye View," like our **Golden Handle**. You see the whole curve as a single equation.

- **Point Value Form:** This is the view we get from the ground. On the ground, visiting specific coordinates, you don't see the curve; you just see "At mile marker 1, the altitude is 200m."

If we have the coefficients, we can easily calculate points. But what if we only have the points and want the curve?
We can use a process called **Lagrange Interpolation**.

### How Interpolation Works :

How do we force a smooth curve to hit a random set of points? We use a technique that acts like building a mountain range. We don't build the whole curve at once; we build it point by point.

For every specific coordinate we want to hit (e.g., at $x=1$, height=5), we create a small mathematical 'ripple' that peaks exactly at that spot and is zero everywhere else. When we add all these ripples together, they combine to form one single, complex curve that fits every single point perfectly.

### Point 4 is crucial to Victor's role

This seems impossible. How can checking just one coordinate tell you if an entire complex polynomial is correct?

This brings us to the **Schwartz-Zippel Lemma**, the mathematical bedrock of our journey. It relies on a simple geometric truth:

**Different curves rarely touch.**

Imagine two different polynomial curves winding across the Bay of Rainbows.

- They might cross each other once.
- They might cross twice.
- They might cross a thousand times.

But here is the key: The space they exist in (the Field) is vast larger than the number of atoms in the universe. Compared to that vastness, even a thousand crossing points is nothing.

#### A Verifier's Test

Victor picks **one random point** $x$ from the entire universe of numbers. He asks Peggy to evaluate her polynomial at that point. He compares it to the evaluation of the expected polynomial.

1. **If the height (the y value) is different:** The polynomials are definitely different. Peggy is cheating.

2. **If the height is the same:** There are only two possibilities.

- **A:** The polynomials are identical everywhere. (Peggy is telling the truth).

- **B:** The polynomials are totally different, but Victor just happened to pick one of the tiny handful of points where they cross. (Peggy is lucky in the extreme).

Because the field of possible points is so huge, **Possibility B** is statistically impossible. Therefore, if the polynomials agree at just **one random point**, Victor can be overwhelmingly confident that they agree **everywhere**.

Victor is starting to realise that polynomials are going to be useful since they:

- Make it hard for Peggy to 'cheat' and convince him of an incorrect proof.
- Make his job of checking a proof relatively quick; testing a single point should tell him if two polynomials are different.

So *if* we could just reduce our ZKP system down to checking if two polynomials are the same, then Victor is going to be a happy verifier.
However this is all getting a bit too hypothetical for him

**Victor:** OK, let's take a concrete example. Imagine you have a password and I want to check that it contains more than 8 characters. You're not going to want to share your password with me. Can we do this with ZKPs?

**Peggy:** Yes, I could write a program that takes the password as an input and outputs "True" if it is the right length. However, we have to be careful _what_ we are proving. I will make the claim that I ran the program against my password and got "True" as an output.

**Victor:** Would I be able to see the program code before you ran it?

**Peggy:** Indeed, there would have to be agreement between the prover and the verifier before we produce a proof, so that we both know what we are trying to prove and what the process is.

**Victor:** OK, so you run your program and it produces an output. If I want to absolutely be sure you didn't cheat, I would need to know that the program ran correctly, and applied the password length check. Will I have to check the program execution step by step?

**Peggy:** That would take too long, and anyway that might reveal the witness (the password I want to keep secret). We need a way to summarise the program execution in a way that still gives zero knowledge about the witness. That means taking our program execution details which we call the **Execution Trace** and going through a series of transformations. You can think of the Trace as the tracks left by the rover as we progress. We need to prove the track exists without showing the path we took.

**Peggy:** Polynomials are part of the overall process, but we need other maths also.

**Victor:** I thought we might.

### Looking Ahead: The Problem of Precision

We have established that polynomials are the perfect vehicle for our proofs. But as we look out over the beautiful curves of the Bay of Rainbows, we hit an engineering problem.

In the real world, curves are smooth. To measure a smooth curve perfectly, you need infinite precision (using decimals that go on forever, like $\pi$). But computers are finite.
They can't store infinite decimals. They need to apply rounding to numbers
In cryptography, rounding anumber is fatal. If you are off by a tiny fraction of a decimal, the proof fails.

We need a world where we can have the complexity of curves but the exactness of integers. We need a world that doesn't stretch into infinity, but stays contained.

With this in mind we head West to the Oceanus Procellarum the Ocean of Storms to find a field where the horizon wraps around itself.

For more resources about ZKPs and Maths visit our [Academy](https://academy.extropy.io)
This content will always be free, if you would like to support our work, you can donate
to the following addresses :
Bitcoin : bc1q528tct2mgn7zl99reuaj0ag770asgeurce5kkl
Ethereum : 0xcc1E7bdA08Abdcf164E9D2E4f78aEDb1d811593D