WTF Proving System!? - Trusted Setup

Posted on June 29, 2023

WTF are Proving Systems!? - Trusted Setup

A proving system is a framework or set of protocols that allows a prover to generate convincing evidence, called a proof, to convince a verifier of the validity of a statement without revealing sensitive information.

OK. Let’s back up a bit. Remember in my last story, the accountant made use of a computer, that was pre-programmed to check transactions and generate the stamp. That computer was an analogy for a proving system. That’s what we’re going to discuss in this post. Highly recommend checking out that article before you continue. Especially if you’re new to this.

Untitled

Who is this post for…

I’m talking to the builders out there, that want to integrate ZK proofs in their dApps. Which means you need to understand certain parts, but not all of it.

This post is going to be a bit long, but I promise it’s easy to read and digest. Still I need to split this topic up into 2 parts. So in this post we talk about the Prerequisites and in the next Proof Generation.

Before we start…sorry

OK. I promise we will get into it, but I need to tell you that there are some scope limitations to my breakdown. In simple terms we will focus on the type of proving system that works 1 way. What do I mean?

Non Interactive Proofs

Well in our proving system, the verifier doesn’t communicate back and forth with the prover. So in the example of my first article, when you(prover) have a badge(proof) that you can only hold when you’re 18+, the guard (verifier) just checks it. If the badge is OK, you get to go inside, if not you stay outside.

There is no communication between the guard(verifier) and you(prover) that the proof is not OK or why it isn’t OK. There is only a result from the check. The guard either opens the door or they don’t open it.

Maybe an easier way to understand it, is to pretend the “Verifier” is a door that scans badges and only opens if your badge is valid. Since the guard can actually talk to you…in real life. Let’s just say this guard is a robot. Yes. It is a robot.

Forget about the type of proofs for a minute

Secondly, we’re not going into ZK-Snarks, Starks, Barks(not a real thing). In my journey, I feel like understanding the different types of proofs is really a step 3/4. Even though the type of proof has some impact on the system. Still I would argue understanding the basics in system is more important, before diving into the types. But hey….that’s just me, what do I know.

Understanding the Components of a Proving System

Alrighty. First we’re going to discuss the major components of a Proving System. Then, we’ll talk about how the Proving System generates the proof. Dividing it into two parts was really important for me to understand. You see, when we talk about the generation of the proof, you don’t want to pause the process, then explain what a Witness is for example, and then go back in to the process. Non mademoiselle. What we want, is to understand the basic components and then dive into the process.

This is the anatomy of a Proving System, so the full scope of what you need to understand.

Screenshot 2023-06-23 at 13.36.24.png

A simplified version…

In my adventure of understanding Proving Systems, my main issue was that it difficult to picture in my head what a Proving System actually is. Some parts do something and some parts are principles for actors to adhere to. But they are all part of “the system”.

So 3 parts and as mentioned, focusing on Prerequisites in this post:

  1. Prerequisites
  2. Proof Generation
  3. Principles a Proving System must adhere to.

Before we dive into the nitty gritty details, it’s story time.

Back to the story - The Origin of the Computer: The Operating System

Remember 2 parts. First we talk about the pre-requisites. Story continues in the next part.

The Accountant was baffled how the computer was performing. I mean there was no way to corrupt it. He tried to open the computer, but even the screws were of the weirdest shape. No tool would fit! So he went to the King and asked how the computer was build.

The King gathered a group of people he could trust and were highly competent. The Council of Trust. This group of people set the rules for the computer system. Together they build an operating system (like Windows or MacOS) called the Rule Book. The computer runs on the Rule Book. This Rule Book only allows certain actions. Imagine on your laptop, only the Chrome browser runs, because your Operating System(OS) doesn’t allow any other program to run, but the Chrome browser.

One such a rule for the zero knowledge proving system, the computer, was that the underlying information should not be part of the report. So when the report is generated, it just states “OK” or “Not OK”, with the Stamp(proof). If this rule were to be neglected, the data would be public!

So the King did not want the Rule Book to be re-created. What if someone kidnaps the Council of Trust!? And forces them to recreate the Rule Book with the exception of sharing the data in the report! Well then someone else could build the computer and give it to the Accountant. And then the Accountant could manufacture a report, but with all the information in it! Not only that, if someone would want to create an identical report(ZK proof), the first part of achieving that would be to have access to the Rule Book. This would be disastrous, because then the King would get a report with a stamp, thinking everything is OK. But it’s not!

Thus the King ordered to destroy the blueprints for the OS. Then make sure that the part, inside the computer where the OS is stored, is locked with special screws and destroyed the tools that screws were used with.

If you’re reminded of the myth of the Mughal Emperor Shah Jahan, who build the Taj Mahal, then you’re somewhat correct. The myth suggests that Shah Jahan ordered the hands of the Taj Mahal's workers to be cut off or had them executed to prevent them from replicating the magnificence of the monument. Note, this is just a tale, never been verified, but explains the principle.

Trusted Setup

OK. I need to stop saying OK, but ok. Let’s take a break from the story and talk a bit about the dusty stuff. Then we link it back to the story. The first part we’re going to tackle, is something you will be hearing when you get your hands dirty with applied ZK, which is the Trusted Setup.

The phase of the Trusted Setup is critical…just saying, major boo boo if this isn’t secure and shit.

Quote from Vitalik:

A trusted setup ceremony is a procedure that is done once to generate a piece of data that must then be used every time some cryptographic protocol is run.

What is a trusted setup?

A trusted setup is a process to create a piece of data. This data is used as rules when the proof is generated. The data is often referred to as initial parameters or key. I like initial parameters, because it describes better why it exists. The process is often referred to as a ceremony.

Why do we need a trusted setup?

TLDR to set rules for the system so proofs are generated adhering to those rules.

The trusted setup gives a set of parameters that serve as a “rulebook” that the proofs must follow. The rules depends on what your “system” or “protocol” wants to do. Stay with me, here is where I tie it with my first article, the ZK principles.

For example, in a zero-knowledge proof system, the goal for the trusted setup is that the proof needs to adhere to the ZK principles or properties:

  1. zero-knowledge (the proof reveals no additional information)
  2. soundness(lying prover can’t trick honest verifier to believe invalid statement is valid)
  3. completeness (if input valid, zk-protocol returns true)
  4. computational integrity (the proof cannot be forged or manipulated).

So in this case we tell the trusted setup, give me a set of rules that I can use in the Proof Generation part. In the Proof Generation part, these rules are used to make sure that the proof is created in such a way, that it doesn’t violate these principles.

Remember I said the trusted setup is critical, major boo boo if we don’t use it. Well imagine a ZK proof generated, but we DO share the underlying information…well…kind of defeats the point.

In more complex words:

The trusted setup would include parameters that enforce these properties, ensuring that the resulting proofs adhere to the desired constraints.

It’s kind of important to also read it in a complex way, because once you dive deeper in to stuff, you will need to be familiar with the wording. Just saying, reading that wack sentence in the quote used to scare me and now it’s just another sentence.

How do we make sure the trusted setup is secure?

Ah, good question. Well here is where we talk about how a trusted setup is created in a secure way. Two main things are important for a trusted setup:

  1. Many participants
  2. Destroying the setup after the parameters (output) is created

Let’s start with point 2. Remember, that anyone having access to the setup and initial input parameters, can recreate the output. We don’t want that. To prevent that, the setup, together with the initial input, is destroyed. This prevents anyone to create a system to generate the same zk proofs our system creates.

Then the first point, a group of participants is selected or chosen. These participants could be experts in cryptography or other trusted individuals. In a simpler version it could also just be one person that you really really trust, just saying. Then, they come together and follow a specific protocol or algorithm to generate the parameters. This process usually involves each participant contributing some random information or performing specific computations. Once the setup is complete, the participants typically destroy or discard their individual contributions to maintain the security of the system.

trustedsetupvitalik.png

Source: Vitalik’s article

Who are the main actors in a trusted setup The main actors in a trusted setup are usually referred to as participants. These participants can be individuals, organisations, or a combination of both. They are responsible for collectively generating the initial parameters. It's important that these participants are independent and trustworthy, as any compromise or collusion among them could weaken the security of the system.

Now you might be confused as to why the picture below is showing a sequence and above you see everyone participating in parallel.

trustedsetupmultivitalik.png

Source: Vitalik’s article

Well you see, there different types of trusted setups. The whole process of creating the trusted setup and coordinating with the participants is called the ceremony. If by now you’re thinking wait, that sounds like a manual process. Gathering people, making sure they have their own secret and ensuring they all work together…it is.

Disclaimer

I know I said I wouldn’t go into different types of proofs and proving systems, but just a small note for you to bare in mind. In some types of zero-knowledge proof systems, like Groth16, a trusted setup is needed for each specific program or circuit you create. This means that for every new program you make, you have to go through a setup process. However, other systems like PLONK only require a single trusted setup that can be used for any program built with that system. Finally, there are systems like STARKs that don't require any trusted setup at all.

Honestly, I’m building up to the point that you could use Noir or SnarkJS to generate your own ZK proof and integrate in your dApp. Now the type we are focusing on are ZK-SNARKS. So, if you’re new to this, definitely forget about STARKS for now and don’t worry about the different types of proving systems. We not there yet mate.

Linking it back to the story

A quick picture how the story relates to the trusted setup. In our story the Council of Trust is the group of participants, responsible to create the Rule Book. The Rule Book is the output of the trusted setup, the initial parameters. Just like how we discussed in “security” for a trusted setup, the setup itself is usually destroyed, much like the blue print being destroyed and the tools for the special screws were destroyed.

Here’s where I stop

OK. You might still be wondering what a trusted setup looks like, tangible stuff. I get it. We’ll get to that part. At the end of the day, it is code what we will be looking at. If at this point you’re still a bit confused. That’s totally normal. You kind of need to read the end to end process for certain things to click. Like what are the initial input parameters or how is the setup destroyed, etc.

Furthermore in this article we won’t dive into the types of trusted setup, ceremonies, how trusted setup’s are created and how to create your trusted setup. I do this for a simple reason. When we will start generating our first ZK proof for our dApp, we wont actually perform a ceremony. DON’T GET MAD, you didn’t just waste your time reading this article. Hear me out. There are languages and tools out there that abstract away things like the trusted setup for us. It’s a great starting point. However, for an actual product, you will need to know how to perform a ceremony and know what a trusted setup is. For now it’s important to familiarise yourself with what a trusted setup is and why you need it.

Let’s dive into the next part which is the components that play a part in the Proof Generation….in the next post!