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) 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.
- Charts to help us navigate, fortunately NASA has made many charts available.
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.
For more resources about ZKPs and Maths visit our Academy
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
Top comments (0)