# A Friendly Introduction to Zero Knowledge

**Not updated to latest version yet 2023-06-19**

*Main text last updated 2023-06-11*

*NOTE: This is a draft. The text is a copy of the original text for easier feedback. /Oskar*

*Main diff from May 27: New introduction and clarified/simplified things in main text*

## Introduction

Zero Knowledge Proofs are magic. They allow us to do things we couldn't dream of before.

Let me start by a few quotes to tickle your brain. Some might be familiar, while others might be new to you.

> Any sufficiently advanced technology is indistinguishable from magic.
> - Arthur C. Clarke

> Civilization advances by extending the number of operations we can perform without thinking about them.
> - Alfred North Whitehead

> I have made this longer than usual, only because I have not had the time to make it shorter.
> - Blaise Pascal

> Privacy is the power to selectively reveal oneself to the world.
> - A Cypherpunk's Manifesto

> The future is already here. It's just not evenly distributed yet.
> - William Gibson

Magic technology, advancing civilization, short letters, privacy and a future that's already here. That's Zero Knowledge Proofs (ZKPs) in a nutshell. What's going on?

In the last century, computers and the Internet have taken over the world. These technologies are everywhere, in everything we do, for better or for worse. On top of these we build platforms, companies, empires. These are things like your MAMAA (Microsoft, Apple, Meta, Alphabet, Amazon). Then there's the belly of the beast - your payment networks, governmental services, and the plethora of B2B applications that silently run the world. Finally, there's a long tail of other things - your cute filter image app, your language learning platform or online community.

When you input some data into yet another online service, you do so expecting to achieve a specific goal. It might be a very small goal, like reaching out to a friend or distracting yourself from work, or it could be something big like applying for a mortgage. But what happens to all this data? This includes both the data you consciously know about and the iceberg of hidden data that you are not aware of. Will what you are trying to achieve actually happen, or will there be some problem, either straight away or a year from now?

Who actually understands these systems and the consequences of how we use them? And how they, in turn, use us? While some people might understand some systems better than others, no one understands all of them, and even less how they interact together to create unforseen consequences.

What's a human to do? Trust. But who do you trust? And why?

This is a hard problem. Our human brains have not evolved to think about this. The Internet, great as it is in connecting us and making things easier, have created a a bit of a mess in this regard. In the past, when you had a private conversation with someone the wind would blow away the sounds you made. When you were locked out of your house, you could get a locksmith, or break the lock yourself. When you are locked out of your Google account and stare at an "Access denied" screen, who do you talk to? No one, you are standing in front of an invisible and impenetrable castle.

ZKPs can help. Maybe not with everything, everywhere or right this moment. But with many things, in many places and more and more. In the rest of this article I'll try to convince you why and how. Let's follow the magic.

## What is a Zero Knowledge Proof?

*This section introduces the notion of a Zero Knowledge Proof*

This is the first in a series of posts on Zero Knowledge Proofs and their application. In it we'll look at what Zero Knowledge Proofs are, why you should care, how they work, and see where they can be used.

Imagine you go to a bar and can prove you are over 18 without revealing anything else, including your ID with personal information on it. Or you can prove that you've paid your taxes correctly, without revealing the details of your income or assets to anyone. These are the kind of things Zero Knowledge Proofs (ZKPs) enables. The term *zero knowledge* simply means we don't reveal any more information beyond what is intended.

ZKPs allow you to prove something without revealing anything but that the statement is true.

What does this mean? Let's take the classic example of "Where's Waldo". The game is about finding Waldo in a big picture. I can prove to you that I know where Waldo is, without revealing the location of Waldo. How?

Imagine I have a picture of "Where's Waldo" and a large piece of paper that's four times the size of that picture. I make a small hole in the paper and put this paper in front of the "Where's Waldo" picture, carefully positioning it so that Waldo is visible through the hole. This means you can see Waldo, but only Waldo and nothing else. You thus know that I know where Waldo is, but I haven't revealed anything about where Waldo actually is located in the picture.


This is obviously a toy example, but hopefully it gives some intuition for how such a proof is even possible. But what does this mean? What are we proving more exactly? We'll dive deeper into this down the line, but for now let's see what ZKPs gives us more generally.

With ZKPs you can prove arbitrary statements in a general-purpose fashion. More specifically, ZKPs allow us to prove something in a private and succinct way.

This is extremely powerful as we'll see next.

## Why should you care?

*This section explains why someone might care about it, including going into detail on privacy, compression and the general-purpose nature of ZKPs*

Reading the above section you might think, "ok that's kinda neat I guess but why should I care". That's a completely reasonable take. In fact, you probably shouldn't! Just like you shouldn't care about how computers work, where AI is going, or any of these things.

Why *might you care*? Because you are curious and want to understand how ZKPs work, and what type of interactions it unlocks. The mechanism is very general, and the intuition for a lot of people working in the space is that it is fundamentally a new paradigm that unlocks a lot of new things. We are seeing this already, and it seems like we are just at the very beginning of this. In the rest of this section I'll try to give you some intuition as to why and how.

Before going deeper into that, let's understand what ZKPs give us at a higher level. They give us primarily one or both of the following properties:

1) Privacy (more formally known as zero knowledge)
2) Compression (more formally known as succinctness)

What do we mean by these two notions? Here are some ways to think about these properties.

### Privacy

There are a lot of things we want to keep private. Here's the definition of "private" in the Oxford Dictionary:

> belonging to or for the use of one particular person or group of people only.

We have private conversations, private bathrooms, private parts. Business secrets, sensitive personal information, in the privacy of your own home. Keys, doors and locks.

Privacy is normal and all around us, and it is closely related to notions of self-sovereignty, self-determination and independence. These notions come so naturally to us that many important documents, such as the *US Bill of Rights* and the *United Nations Charter* recognizes them as fundamental rights, for individuals and nations respectively. [xx1]

More formally, the privacy property in ZKPs is often called *zero knowledge* or *hiding* [xx46]. A ZKP is hiding data that is irrelevant for some application to function, and this data is then *bound* together with the relevant application data. These notions are a bit more formal, and they enable privacy. Privacy is a broader and more generally applicable concept, so we'll keep focusing on that for now.

In the digital world, also known as cyberspace, as opposed to meatspace, privacy is very important too, but often neglected. Here's the definition of privacy given a *A Cypherpunk's Manifesto*:

> Privacy is the power to selectively reveal oneself to the world.
> - A Cypherpunk's Manifesto

Conversations, passwords, credit card information. These are examples of things we want to keep private online. The Internet is an amazing tool that connects us all, but it is also an open and wild sea. There are a lot of strangers and predators, and keeping certain information private is vital. Without it, things like online shopping or private messaging would be impossible.

You might think, "we can already keep things like passwords private, what's the big deal?". In a limited sense and for these specific examples, you are correct. We'll have to use a bit more imagination to truly understand what general-purpose programmable privacy enables.

As an example, consider how Augustine in his *Confessions (400 AD)* found the act of "silent reading" by St Ambrose, a bishop, to be out of the ordinary. At the time, most people would read out loud. [xx2]

> When [Ambrose] read, his eyes scanned the page and his heart sought out the meaning, but his voice was silent and his tongue was still. Anyone could approach him freely and guests were not commonly announced, so that often, when we came to visit him, we found him reading like this in silence, for he never read aloud.


Nowadays, everyone takes silent reading for granted. It is even hard to imagine that it had to be invented.

We'll get a glimpse of what these inventions using ZKPs, both existing and upcoming, look like in future sections.

### Compression

> I have made this longer than usual, only because I have not had the time to make it shorter.
> - Blaise Pascal

To compress something is defined as:

> to press something into a smaller space

Similarly, succinctness is defined as:

> the act of expressing something clearly in a few words

ZKPs having the property of compression means we can prove that something is true with a very short statement. For example, that all the steps in some computation have been executed correctly. This is most immediately useful in situations where some resource is in high demand and expensive. This is true in the case of the Ethereum blockchain, but it is also a very useful property in other circumstances. What is more remarkable, is that the size of this proof stays the same regardless of how complex the thing we are trying to prove is!

What do we mean by "proof" and the "size of the proof"? These are mathematically precise notions that possess a great deal of nuance. We'll go deeper into this notion of a proof in the context of ZKPs in future sections. For now we can think of it simple as a short statement that we know is true, or can somehow verify is true.

In a typical whodunit like a Sherlock Holmes murder mystery, the detective gathers evidence until they can prove that the perpetrator has committed the murder. They then prove exactly how they know this in a grand finale. We can think of this final statement as the proof. [xx16]

More formally, we call this property *succinctness* [xx]. This is what keeps the size of the proof the same regardless of what we are trying to prove. In the context of public blockchains, this also relates to the notion of *scalability*. For public blockchains like Ethereum, where block space is limited and expensive, ZKPs can make transactions a lot cheaper and faster. How? We create a proof that some set of transactions have taken place, and put that tiny proof on-chain, as opposed to having all transactions take up space on the blockchain. With ZKPs, this can be made very secure and we'll look at this in more detail later in the application section.

Succinctness is a general property and orthogonal to "blockchains" - they just happen to be a good fit, for many reasons, which we'll go into later. More generally, having short proofs that something is true is very useful. There are a few ways to see why.

One way of looking at it is to consider *transaction costs* [xx3]. Generally speaking, the lower these are the more value and wealth is created. If there are fewer things to verify, or it is easier to do, then we can do things more freely and with ease.

Sometimes when we fill in a form we are asked to write our email twice to confirm it is correct. The idea is to protect against human errors and make the transmission of data more robust. There are also things like checksums, where an extra digit in your UPS package code, credit card number or ISBN code for books acts as a simple check that all the numbers are probably correct. All of these are - obviously - not meant to protect against malicious use, but only against innocent mistakes. [xx4]

In computer file systems, a _hash_ function is often used to ensure the integrity of files. If something happens to just a small part of a file, corrupting it, the hash changes completely. Because the hash is succinct (say, a 32 byte string), it is easy to keep around and check even if the underlying file is huge. In this case, hash functions ensures integrity in a secure way. If we checked the integrity of a file by just keeping a copy of the file it'd be a lot more unpractical and less used. Big file, small file, it doesn't matter, the hash stays the same size. The succinctness of a hash enables this use case.

Let's take a step back from talking about compression, succinctness and proofs. We'll go on a little detour into knowledge, mental overhead and trust. We'll then connect this back with ZKPs the end of the section.

In your everyday life, what do you know is true, and why? If you see the sun rise every day you likely expect it to rise again tomorrow. In the modern world, we are largely protected from the harsh environment in nature, but on the flip side we have a lot of other, more modern, concerns. Many of these related to various institutions we deal with on a daily basis.

If you are able to withdraw cash from your bank every day, do you expect to be able to withdraw it again the next day? Most people would probably say yes, but not everyone all the time. This depends on a lot of factors: if the bank is trustworthy, if you're living in a safe jurisdiction, if something major has happened in the world economy recently, what your personal circumstances are like etc. All of these things together make up some data points, and based on that you make a determination.

This is obviously a trivial example, but life is rife with such interactions. All of this can be seen as a form of mental overhead. The extent to which this is a concern can depend on your personal situation and the complexity of your day-to-day dealings. For instance, a business might give these factors a lot more thought when entering into a contract with another party.

We create mechanisms to counteract it, like using reputation services, independent auditing, fines to discourage bad behavior, accreditation by some trusted institution, etc. All of this is basically duct tape to get at the basic fact: is this what it claims to be, does it follow the rules we have determined, and is it trustworthy and usable?

All of this mental overhead gets compounded when you are dealing with multiple institutions, jurisdictions, companies, people. You can get cascading effects, such as your bank failing and you being unable to pay your employees, thus leading to your business being unable to service its customers [xx5]. More control measures are needed. More pauses to consider if things are right and what can go wrong.

I'll end this section with a quote:

> Civilization advances by extending the number of operations we can perform without thinking about them.
> - Alfred North Whitehead [xx43]

With ZKPs and succinct proofs we are able to introduce more certainty and clarity in opaque systems. This gets even more powerful when we consider *composing* ZKPs. That is combining multiple proofs into one in some fashion, such as with aggregation or recursion.

All this presumes we can translate some of the computations or 'rules' - which are often messy and inconsistent - into a form that ZKPs can comprehend. How can we do that? Now we are starting to get to the second "why" and moving towards the "how". Like opening up a Russian nesting doll, we are getting closer and closer to the core.


### General-purpose

Recall that ZKPs allows us to prove arbitrary statements in a general-purpose fashion. Why does this matter and how is this powerful?

It is the same as the difference between a calculator and a computer. One is meant for a very specific task, and the other is general-purpose. It is the difference between this:


And a modern computer.

Recall the specific examples we gave above to represent privacy and succinctness more concretely. A password is a private piece of information that allows you to login to some service [xx6]. In the case of a hash of some input data, such as a file, it is gives us something succinct to check equality to.

We can visualize a hash function as follows:

input -> [ cryptographic hash function ] -> hash

The hash function, say SHA256, is a specific cryptographic construction that took a lot of time and many people to make secure. The hash itself also doesn't prove anything, it only makes sense when compared with something else, such as having direct access to the file.

In the case of ZKPs, you can have any private and any public input. Private means only you can see it and public means anyone can see it. In the example above, the file is considered public input. The logic inside the box is general purpose and can compute anything a computer can.

private and public inputs -> [ program ] -> proof

We have turned what was originially a problem of cryptography or math into one of programming. To see why this is extremely powerful, consider some of the following examples.

We can now prove that we know the (private) data that results in a certain hash. This means you can prove that you are in possession of a certain file, such as an important document or message.

To better understand the power of doing general-purpose computing on a cryptographic construct, let's take a closer look at group signature. Group signatures are a way for a group of individuals to sign a document together, without revealing who they are. For example, the Federalist Papers were signed by the pseudonym Publius which represented multiple individuals. There is a special-purpose cryptographic protocol for it, which is very impressive and took a lot of cryptographic engineering to develop. But with ZKPs we can express the same thing in just a few dozen lines of Circom code [xx8].

Due to its general nature, we can easily make ad hoc constructions. For example, you might have an ID card that has your full name, address and other personal information. To enter a event you might need to be over 18, and have a valid ticket. You might not want a random person or online system to see your address, or risk having your ID be stolen. With ZKPs you can prove that:
- You possess a valid ID
- The ID is issued by an approved institution in the last 5 years
- The ID has not been revoked or reported stolen recently
- You are over 18 years of age
- You have paid for a valid ticket to the event
- The ticket has not been used before

All without revealing any single fact about yourself other than what is listed above.

With ZKPs, we now have a *better tool* for people to coordinate in various ways, and especially when it comes to systems where you want *privacy* and *succinctness*. We'll see even more examples in the application section.

Often, it is your imagination that is the limit in terms of what you can express.

### Why now?

*This section explains why ZKPs are a thing now*

Why are ZKPs becoming a thing now? There are both technical and social reasons for this.

Technically, ZKPs are fairly new. Mathematically they've only existed for a few decades [xx9]. Similar to computing itself it then took a while to become performant and practical even in theory. [xx10]

After that, someone had to take these papers and cryptographic protocols and turn them into something practical. The first notable example of this was Zcash, the privacy-preserving cryptocurrency, in 2016. It started as a whitepaper written by cypherpunks and researchers [xx15]. The first version was an impressive feat of research and engineering applied into an end product and system. While the system had many issues and was far from optimal, it was the first real practical example of using ZKPs in the real world. This showed people that it was possible and practical to use ZKPs in the real world. This led to an explosion of research and engineering efforts in ZKP, which continues to this day.

Public blockchains like Ethereum and Zcash had a big role to play in this. What blockchains excel at are things like censorship-resistance and transparency. This comes at a cost of lack of privacy and scalability, something that ZKPs excel at. In this sense, they are a natural fit. Couple that with the blockchain community's appetite for advanced cryptography [xx12] and it is no wonder a lot of the innovation is happening at the intersection between blockchain and ZKPs [xx13]. Due to the many well-capitalized blockchain projects, this has also led to more investment into research and engineering into a traditionally more academic space.

Considering the complexity involved, spanning applied mathematics, cryptography, papers on specific ZKP systems, implementing novel proof systems, tooling, and applications that touch other complex domains, things are moving extremely fast. Every year - even every month - there are new research papers with novel techniques, improved tooling, and applications. The feedback loop between new research and it being implemented and then used are getting tighter. While still difficult, it is getting easier and easier to get started. As tooling is improved, developers need to understand the math behind ZKPs less and less.

In terms of performance of ZKPs, there's a form of Moore's law happening. Moore's law is the observation that the number of transistors doubles about every two years. This is what led to the computer revolution. In ZKPs, things that were just pipe dreams a few years ago, seen as completely unpractical, are now being executed on, things like zkVM and zkML. As a rule of thumb, it has been observed that things improve by an order of magnitude every other year or so [xx14]. We have no reason to believe this will stop any time soon.


## How does it work?

*This section explains how Zero Knowledge Proofs work at a high level*

This section provides a high-level overview of how ZKPs work. It will not include any mathematics or code.

### Basics

We start by introducing some terminology. There'll be a few new terms to learn, but as we go along, you'll get the hang of it.

- **Protocol**: system of rules that explain the correct conduct to be followed
- **Proof**: argument establishing the truth of a statement
- **Prover**: someone who proves or demonstrates something
- **Verifier**: someone who vouches for the correctness of a statement
- **Private input**: Input that only the prover can see, often called **witness**
- **Public input**: Input that both prover and verifier can see, often called **instance**

While it is useful to learn the terminology used in the field, some metaphors can be helpful to get a better sense for what's going on. We'll introduce more terms as we go.

Protocols exists everywhere, and can be implicit or explicit. In the game of chess, the protocol is that you have two players who take turns to play a move according to the rules of the game until the game ends, and one person wins or there is a draw. In theory, the time it takes to make a move doesn't matter, but in practice we try to minimize the communication costs between th]he two parties interacting. We can thus think of it is as a really fast game of chess.

We can think of Sherlock Holmes as the prover, and in his final statement he produces an elegant series of arguments, a proof, that someone is the murderer. This must then be verified by a verifier to be true, for example by a judge or jury, *beyond a reasonable doubt* [xx17]. It is called a prover because it is the entity producing the proof, which must then be verified. Because the proof is self-contained, anyone can be a verifier, including you as the reader, who must be convinced of the reasoning provided to make the story believable. [xx20]

The private input would be some knowledge that only Sherlock Holmes knows, for example some secret information someone whispered in his ears. This is often confusingly called witness, presumably because a witness in a court room has some private information and this is added onto the pile of evidence. In the case of ZKPs, this private information would not be shared with the verifier, or judge and jury in this example.

ZKPs establishes a *protocol* between a *prover* and a *verifier*. This protocol is *non-interactive* if the prover and verifier don't have to interact directly, like in a game of chess or in a dance. Instead, the prover produces a single self-contained proof, and at some later point this gets verified. Most ZKPs start off as *interactive*, that is requiring multiple back and forth, and we then use some mathematical tricks to make it non-interactive [xx18]. You can think of non-interactivity kind of as two chess players who, after uttering a few words, know every single move the other player will play, so they don't even start the game because they already know how it will end.

There are many types of ZKPs. One of the most common ones is zk-SNARKs, which stands for Zero Knowledge Succinct Non-Interactive ARguments of Knowledge. Zero Knowledge and Succinctness correspond to privacy and succinctness above, respectively. Non-interactive was mentioned. Arguments of knowledge is basically a proof [xx22]. There are many different types of zk-SNARKs too.

A good mental model is to think of ZKPs as a zoo. There are a lot of animals there, and we can categories them in various ways: these animals have four legs, these have stripes, Bob brought these in last year, etc. Some categories are more useful than others. In addition to zk-SNARKs, there are also zk-STARKs (S stands for scalable and T stands for transparent). In fact, some ZKPs don't even have Zero Knowledge! These are usually called just SNARKs. As a community, we often call this zoo of different animals ZK, even if there are many systems that don't actually use the Zero Knowledge property. [xx19] We'll look into these different properties in detail a bit later.

### Protocol

Going back to our protocol, we have a prover and verifier. The prover creates a proof using a *prover key*, private input and public input. The verifier verifies the proof using a *verification key* and public input, and outputs true or false.

We have two new things, a prover key and a verifier key. This is what allows the prover and verifier to do their magic. You can think of them as a regular key that allows you enter somewhere and do something, or you can think of it as a magic wand that allows you to do something. We get these keys from a special ceremony called a *setup*, which is an initial preparation phase that we won't go into detail on in this article [xx49].

Notice that only the prover has access to the private input. How does the prover use the prover key, private input and public input to turn it into a proof?

Recall the illustration of a ZKP from before:

private and public inputs -> [ program ] -> proof

We have a special program (formally known as a *circuit*) that encodes the logic a user cares about. For example, proving that they know the data that results in a certain hash value. Unlike a normal computer program, this program is made up of *constraints* [xx51]. We are proving that the constraints hold together with the private and public input.

Finally, the verifier takes this short proof, combines it with the verification key, public input and the special program with all the constraints and convinces itself beyond a reasonable doubt [xx51] that the proof is correct and outputs "true". If it isn't correct it'll output "false".

This is a somewhat simplified view but it captures the essence of what is going on.

### Constraints

What are these constraints that make up the special program above? A constraint is a limitation or restriction. For example, "a number between 1 and 10" is a constraint. The number 7 satisfies this constraint, and the number 11 doesn't. How do we write a program as a set of constraints? This is an art on its own, but let's start by looking at a simple example: Sudoku.

In the game of Sudoku the goal is to find a solution to a board that satisfies some constraints. Each row should include the numbers 1 to 9 but only once. The same goes for each column and each 3x3 subsquare. We are given some initial starting position, and then our job is to fill in the rest in a way that satisfies all these constraints. The tricky part is finding numbers that satisfy all the constraints at once.


With ZKPs, a prover can construct a proof that that they know the solution to a certain puzzle. In this case the proving consists of using some public input, the initial board position, and some private input, their solution to the puzzle, and a circuit. The circuit consists of all the constraints that express the puzzle.

It is called a circuit because these constraints are related to each other, and we wire these constraints together, kind of like an electric circuit. In this case the circuit isn't dealing with current, but with values. For example, we can't stick any value like "banana" in our row constraint, it has to be a number, and the number has to be between 1 and 9, and so on. [xx47]

The verifier has the same circuit and public input, and can verify the proof the prover sent them. Assuming the proof is valid, the verifier is convinced that the prover has a solution to that specific puzzle.

It turns out a lot of problems can be expressed as a set of constraints. In fact, any problem we can solve with a computer can be expressed as a set of constraints.

### Some properties

We say that a ZKP has certain technical properties:
- Completeness - if the statement is true, then the verifier will be convinced by the proof
- Soundness - if the statement is false, the verifier won't be convinced by the proof, except with a negilible probability
- Zero Knowledge - if the statement is true, it won't reveal anything but the fact that it is true

Additionally, for zk-SNARKs, the proof is succinct, meaning it basically doesn't get bigger as the circuit gets more complex [xx24].

There are many other properties we care about when it comes to practical ZKPs:
- What mathematical assumptions is the system making?
- How secure is it?
- Does it require a trusted setup?
- How hard is it to generate the proof? In time and other resources
- How hard is it to verify the proof? In time and other resources
- How expressive is it? That is, how easy is it to solve problems in
- Does it allow for aggregation and recursion of proofs?
- Are there good implementations of it that can be used by programmers?
- And so on

As you can see, there are quite a lot of considerations and different variations of ZKPs. Don't worry though, the gist is basically the same, and depending on where your interest lies you can remain blissfully unaware of many of the technical details involved. Going back to the zoo metaphor, just like with animals, you might not want to become a biologist. Instead, you might want to work with some animals, or maybe you just want a pet, or even just pet your friend's dog.

## Applications

*This section gives examples of current and future applications of ZK*

There are many applications of ZKPs. Generally, though we are still in the early stages. A lot of the focus is still on the underlying protocols and infrastructure, as well as blockchain-specific applications. In this section we'll look at some of the more interesting applications. We'll start by looking at applications that are live now and then look at those on the horizon.

> The future is already here. It's just not evenly distributed yet
> - William Gibson [xx25]

### Live now

**Electronic cash**. To make a cash-like payments systems online it needs to be fungible and private like physical cash. Fungibility refers to the property of a commodity being replacable by another identical item. That is, there's no difference between your money and my money, they are equally valid forms of payments. We can use ZK to make the transaction graph private, unlike in Bitcoin or Ethereum. This way, your transaction history remains private, ensuring that electronic cash is fungible. This is currently live in systems like Zcash, and related systems like Tornado Cash [xx26].

**Anonymous signaling.** Often, we might need to prove our affiliation with a group that possesses certain characteristics, without revealing our identities. One such example is proving that you are part of some group of people, another is voting. This means you don't tie your identity to sensitive actions such as which party you voted for, or reveal other unnecessary information. Currently live in systems like Semaphore, and similar mechanisms with many variations exists.

**ZK Rollup.** The Ethereum blockchain space is limited and expensive with a lot of demand. A stratified approach to scaling, which allows for more, cheaper, and faster transactions, is used. We use a so called Layer 2 (L2) rollup, that does transactions separate from the main blockchain (L1). Once a certain number of transactions have hit the L2, it "rolls it up" to the L1. ZKPs are great for this because we can (i) prove that transactions are executed correctly and (ii) create a succinct proof that takes a small amount of space on the L1. This makes transactions cheaper and faster for users, with near-equal security. Due to the complexity of proving the execution of the entire Ethereum Virtual Machine (EVM) many ZK Rollup solutions only focus on exchange of simple commodities and assets. Currently live in systems like Loopring, zkSync Lite, dYdX. [xx27]

**ZK-EVM.** Similar to ZK Rollup, but more general. Ethereum has an EVM which acts as a worldwide globally shared, general purpose computer (that anyone can write to). By writing the logic of this machine using ZKPs we can prove the correct execution of any program written on Ethereum and construct a succinct proof that it was executed correctly. This has several use cases, but most immediately for scaling and allowing for cheaper and faster transactions. Unlike ZK Rollup, these are universal and any type of transaction or program can be executed. Currently live in systems like Polygon zkEVM, zkSync Era with several others on their way. [xx28]

**ZK-VM.** Partially due to the complexity of targeting a "snark-unfriendly" platform like the EVM, many projects have chosen to do a new blockchain, separate from Ethereum. This means they can optimize the VM to work better with ZK in the first place. Depending on the specific system, this allows for privacy and succinct verification of blockchain state. Mina is live, and systems like Aleo are under active development. [xx40]

**Dark Forest**. Dark Forest is an incomplete information real-time-stratey game. Incomplete information games based on ZK have a "cryptographic fog of war" where players can only see part of the world, as enforced by ZK. Compared to traditional games like Starcraft, not even a central server has access to all the information. Due to its programmatic nature this enables novel ways of playing a game. [xx32]

**ZK Bridges**. Bridges allow you to move assets between different blockchains and systems. These bridges be hard to make secure, and they often get hacked. With ZK, we can bridge assets more securely and faster, without relying on trusted third parties or error-prone approaches. Currently live with zkBridge and also being worked on by projects such as Succinct Labs. [xx31]

**Private identity**. As more siloed systems require and host our online identities [xx33], it is desirable for individuals to be able to own, aggregate and keep these fragmented online identities private. Currently live projects like Sismo enable this, and other projects are working on similar systems. [xx34]

These are just a few examples and by no means complete. We didn't talk about things like private non-repudiable reputation, exporting web2 reputation, sybil-resistant denial-of-service protection, coercion-resistant proving, anonymous airdrops, proving degrees of separation, etc.

### On the horizon

**ZK-EVM (Ethereum-equivalance)**. There are different types of ZK-EVM, and the more challenging ones to implement are the ones that are fully Ethereum-equivalent. Other ZK-EVM takes some shortcuts to make it easier to generate proofs. With a fully Ethereum-equivalent ZK-EVM there's no difference with the current Ethereum system. This means we can prove the correct execution of every single block in existence in a succinct proof. You can use a phone to verify the integrity of the entire chain, relying solely on mathematics, without needing to trust third parties or use expensive machines. Currently being worked on by the ZK-EVM Community Edition team. [xx30]

**General purpose provable computation**. Most computation in the world doesn't happen in the EVM, but in other system. WASM and LLVM-based programs are very common. We can leverage the same approach in ZK-EVM to do general-purpose private provable computation. For example, we can prove that a database contains a specific record, without revealing any other information. Currently being worked on by many different teams, for example Delphinus Labs, RISC Zero and Orochi Network. [xx38]

**ZK Machine Learning (ZK ML)**. We can prove that some computation was done correctly privately, off-chain, and then publish a proof that the computation was done correctly. This means we can use private data for training better models, without revealing that data. For example, sensitive documents, voice or even things like DNA to find health problems. This improves both scalabilty and privacy for users. Current proof of concept (PoC) exists for things like MNIST, a common test to recognize handwritten digits, and people are working on more complex things like neural networks inside ZKPs [xx36]

**Photo authenticity**. Prove provenance of content such as photos and videos, including standard post-processing edits. That is, prove that a photo was taken at a certain time and place, and has only been edited with basic resizing, cropping, and use of greyscale (AP approved list of operations). Some work has been done, including a PoC. [xx35]

**Compliance**. Prove that a private transaction is compliant with some regulation, or that an asset isn't on a specific black list. Prove that an exchange is solvent without revealing their assets. Some work has been done by systems such as Espresso Labs, and some systems have simple versions of this already.

**Autonomous worlds**. A continuation of things like Dark Forest. A world can be physical or conceptual, like The World of Narnina, Christianity, The World of the US Dollar, Bitcoin or Commonwealth law. Depending on where these worlds run, these can be autonomous if anyone can change the rules without damaging its objectivity. Currently being explored by 0xPARC in the context of games and creating these worlds. [xx41]

**Proof of data authenticity**. Export data from web applications and prove facts about it a private way. Uses the TLS protocol which means it works on any modern website. Currently being worked on by TLSNotary. [xx37]

**Nuclear disarmament.** Allow people inspecting nuclear sites to confirm that an object is or isn't a nuclear weapon without inspecting any of the sensitive internal workings of said object. Paper with physical simulation work exists. [xx39]

**Peace talks and high-stakes negotiation**. Often in negotiations people have certain hard limits that they do not wish to reveal to their counterparty to weaken their ability to negotiate. By explicity encoding these, two parties can negotiate over some highly complex domain and reach an agreement without revealing the details of their precise parameters and limits. This allows people who do not trust each other to fruitfully come to some agreement. Likely requires some breakthroughs in Multi-Party Computation (MPC), which allows us to do computation on shared secrets.

Again, this didn't mention all the types of things people are working on or thinking about. There will surely be many more things in the future. As you can tell there are a lot of things we can do with ZK.

You might wonder why many of these applications involve a blockchain. This was partially answered in the previous section "Why now?". ZK is an orthogonal technology to blockchains like Ethereum and we can do without the blockchain, but quite often it is simply a good tool that makes sense to leverage.

Similarly, the group of people working on these things and the immediate problems they care about are often overlapping. As the space matures, we can expect the "blockchain" of ZK applications part to disappear as simply an implementation detail, and this has already happened to some degree. Looking further, the "ZK" part will likely also fall into the background and it'll simply be an application which happens to use ZKP.

Finally, when cryptograpy for online messaging and similar was developed it was used and developed by the military and Internet companies. It was not something that was innovated on by the mail office or some company involved in the secure transport of physical goods, even if in theory that was a possibility. [xx29].

I'll end this section by a quote from Barry Whitehat, a well known ZK researcher who works with the Privacy and Scalability Explorations (PSE) team at the Ethereum Foundation, when asked for predictions on the future of ZK:

> "By 2040, someone will have won a Nobel Peace Prize for using Zero Knowledge Proofs." [xx42]

Outlandish and bold? Certainly. Will it turn out to be true? Maybe not. But could it? Absolutely. It is an intriguing prospect to consider. What is the difference between the mental model that sees this as a real possibility, versus one that writes it off immediately? What would have to happen for such an event to be a realistic outcome?

ZKPs represents a new and incredibly potent tool. Often, it's our imagination about its potential applications that limits us.

## Conclusion

*This section summarizes the article and provides next steps*

In this article, we've looked at what ZKPs are, why we should care about them and when they are useful. We've also looked at how they work and what properties they give us. Finally, we looked at some applications, both current and future ones.

I hope this has led you to better understand the nature of ZKPs, and perhaps led to some aha-moments and inspired some new ways of thinking about things. Perhaps it even helps you follow the magic of ZKPs in the future.

In future posts we'll go even deeper into some of these aspects, and we'll also look at more technical aspects to better understand how ZKPs work and where they can be used.

If something specific piqued your interest, or there is something specific you'd like to see in future articles, feel free to contact me on Twitter or by email. I'll include the best comments as footnotes!

## References

*This section includes references, needs to be updated a bit*

[xx1]: While the concepts are related, there's some legal controversy around if the "the right to privacy" itself is protected.
[xx2]: Some people have different interpretations of this specific passage, but it still the case that humans made the transition from primarly oral storytelling to silent reading at some point not too long ago.
[xx3]: Transaction costs is an economic concept.
[xx4]: In a checksum, we do some basic operation like adding and subtracting the initial digits, and if the final digit isn't the same we know something went wrong.
[xx5]: While more common in less developed countries, this happened recently with bank failures in the US.
[xx6]: In well-designed authentication schemes the provider doesn't see your password either, just a salted hash of it.
[xx8]: Group signature example: https://0xparc.org/blog/zk-group-sigs
[xx9]: Since 1985, and the authors late won a Godel prize. We can compare this to public-key cryptography, which took many decades until it was used for things like TLS.
[xx10]: For example, Lambda calculus and Lisp machines were completely unpractical when first proposed. Dan Boneh made the observation that making prover time quasilinear is what really made ZKPs practical in theory.
[xx12]: BLS signatures used in Ethereum Consensus Layer were deployed and used to secure billions of dollars just a few years after the paper was released.
[xx13]: Dan Boneh, an applied cryptograpy professor at Stanford, is a great example of this in terms of his involvement in various cryptocurrency related projects.
[xx14]: Heard about this from a gubsheep who runs 0xPARC, but has popped up a few times. This also matches the authors own experience, working on RLN and noticing 1-2 order of magnitude improvements in things like prover time in a few years.
[xx15]: See the original Zcash whitepaper.
[xx16]: Kudos to Juraj for suggesting using murder mystery as a way to explain the notion of a proof: https://twitter.com/jurbed/status/1650782361590669313
[xx17]: In a legal setting, false positives do happen, see for example the Innocence Project. in a mathematical setting we can make this false positive rate very precise, and it isn't even close to a fair game. That's the power of mathematics. We'll look at this more in future articles on probabilistic proofs.
[xx18]: This is done using the Fiat-Shamir heuristics.
[xx19]: A more accurate name might be (zk)S(T|N)ARKs but this is a bit of a mouthful, so people tend to use ZK as a shorthand. See for example the name of the ZK podcast, the ZK proof standard, etc. ZK is the most magical property of ZKPs, in the author's opinion.
[xx20]: You'd probably want to ask Sherlock Holmes some follow-up questions first though, before throwing our prospective murderer in jail. It is possible Sherlock Holmes is trying to fool you! In ZKPs we assume the prover is untrusted.
[xx21]:
[xx22]: Sometimes people make a distinction between these two, but it is a fairly technical one and not something we have to concern ourselves with right now.
[xx23]: The number of atoms in the Universe is currently estimated at around ~2^265. The security margin for ZKPs depends on the specifics of the proof system and parameters, so it might be a bit lower for many real-world systems. But it is still an astronomical number. Other comparable numbers: the number of grains of sand on Earth is roughly 2^63, and the number of stars in the observable Universe is around ~2^77. The security margins of ZKPs is usually at 2^128 or above, which is a lot higher than either of these.
[xx24]: There are different notions of succinctness, and this depends on the specific proof system. Technically, we call proofs succinct if they are sublinear in time complexity.
[xx25]: Allegedly a quote by William Gibson, see https://www.nytimes.com/2012/01/15/books/review/distrust-that-particular-flavor-by-william-gibson-book-review.html
[xx26]: With many new versions being developed, like Aztec, Railgun. Tornado Cash works quite differently from Zcash, acting more as a mixer. Tornado Cash was also recently sanctioned by the US government. There are other alternative like Monero and Wasabi, that are not based on ZKP but have similar goals.
[xx27]: This is similar to how the traditional banking system works too, where there are multiple layers of settlement happening. It is just hidden from most end users.
[xx28]: There are different types of zkEVM, and the difference can be quite subtle. See this post by Vitalik: https://vitalik.ca/general/2022/08/04/zkevm.html
[xx29]: A familiar story: see Sears vs Amazon.
[xx30]: See note above for more on this distinction.
[xx31]: In Dark Forest, some people write very complex bots that play the game on its own. They even form private DAOs and create smart contracts that play the game semi-autonomously.
[xx32]: Telepathy by Succinct Labs is one such project. There are likely many others.
[xx33]: A weird, but surprisingly accurate, statement.
[xx34]: Proof Carrying Claims/Data by 0xPARC, is one such example.
[xx35]: See https://medium.com/@boneh/using-zk-proofs-to-fight-disinformation-17e7d57fe52f
[xx36]: See https://0xparc.org/blog/zk-mnist, there are also people doing things like neural networks in the more modern efficent proof systems.
[xx37]: See https://tlsnotary.org/
[xx38]: See for example https://github.com/DelphinusLab/zkWasm Orochi Network, and RISC Zero https://www.risczero.com
[xx39]: See https://web.archive.org/web/20170703142802/https://www.pppl.gov/news/2016/09/pppl-and-princeton-demonstrate-novel-technique-may-have-applicability-future-nuclear
[xx40]: Mina allows for succinct verification of the whole chain, whereas Aleo focuses more on privacy.
[xx41]: See this essay by ludens at 0xPARC for more details on this idea: https://0xparc.org/blog/autonomous-worlds
[xx42]: Quote from panel at Devcon5: https://www.youtube.com/watch?v=hBupNf1igbY&t=1897s
[xx43]: Full quote: "It is a profoundly erroneous truism, repeated by all copy-books and by eminent people when they are making speeches, that we should cultivate the habit of thinking of what we are doing. The precise opposite is the case. **Civilization advances by extending the number of important operations which we can perform without thinking about them.** Operations of thought are like cavalry charges in a battle — they are strictly limited in number, they require fresh horses, and must only be made at decisive moments."
[xx44]: This is just the data that you _see_. There's a lot of information you can't see that you are also submitting.
[xx45]: Succinctness has a precise mathematical definition, but we won't go into this in this article.
[xx46]: Zero knowledge has a precise mathematical definition, but we won't go into this in this article.
[xx47]: Technically speaking, it is an *arithmetic circuit*, because we are dealing with numbers.
[xx48]: Alice and Bob are commonly used characters in cryptographic systems, see https://en.wikipedia.org/wiki/Alice_and_Bob
[xx49]: Setups are multi-faceted and a big part of the security assumptions of a ZKP. They are a bit involved mathematically, and to give them full justice would need a dedicated article. There's a great layman's podcast on The Ceremony Zcash held in 2016 that you can listen to here: https://radiolab.org/podcast/ceremony
[xx50]: Technically this is called proving knowledge of the *preimage* of a hash.
[xx51]: Technically speaking this is an arithmetic circuit, but we won't introduce details of this in this article.
[xx52]: Strictly speaking ZKPs are a form of *probabilistic proof*. This means that we get confidence in a probabilistic, and not absolute, sense. Don't worry though, this possibility is extremely negligible. It'd be roughly as unlikely as picking out a specific atom out of all the atoms that exists in the Universe, see [xx23].