Alessandro Mazza - You could have invented ZK Proofs @alessandro-mazza

Good morning everyone. I'm Alessandro Mazza, I've been an engineer and communicator in the Bitcoin world since 2021, and in this regard, my goal is not so much to explain to you what if we had already invented Zik proofs but hadn't realized it, but rather to try to understand if we too could invent Zik proofs, if we could invent Zik proofs when we find ourselves solving a problem. And the only way to solve the problem is to invent zaprof, because what is kind of the goal of this story of mine today is to explain this technology to you, but also to make you understand that all these technologies, even if they are very complex, are not born with the ultimate goal of being complex or with the goal simply of creating a technology for the sake of technology itself, right? but they arise because there are challenges, there are problems and to solve these problems, let's say, man thinks and the best solution or sometimes the only solution is to have to create something new, as in the case of Zen Knowledge technology. So today's goal is to try to understand, starting from a problem, how we can solve this problem, and you'll see that in solving the problem we will actually, so to speak, invent zero knowledge, and in my opinion, it's also the best method for understanding zero knowledge because when you start from a problem and have to solve it, you understand all the sub-problems you have, and by having to solve each sub-problem, you then understand how the technology that allows you to do everything is born.

So let's start with our first actor in this problem. The first actor is called Paul. Paul, imagine, is an entrepreneur and he has spent a lot of money to buy calculators, computers, even graphics cards and maybe even ASICs, so calculators that have the sole purpose of performing extremely fast and extremely complex computations. And why did he do it? Because its only job is to solve a problem called the partition problem.

In Italian it would be the partition problem, but let's say it's called the partition problem because it's a problem that clearly originated in the English-speaking world, a bit like all computer problems. The partition problem: you are given a list of numbers as input. Let's take this list, so we have our list S which contains 1 5 7. The Partition Problem consists in having to find two subsets S1 and S2 such that the sum of the elements of S1 is equal to the sum of the elements of S2 where look obviously I understood it immediately from this example, they are S1 and S2 are subsets of S, they are not random numbers. If we do the math 1 + 1 + 5 equals exactly 7.

So S1 and S2 are said to be a valid solution to the partition problem given the starting list S. Now you say this problem is trivial, right? that is 1 5 7. Even more or less, I came to understand that to divide, no, into two subsets such that the sum of the elements of one is equal to the elements of the other was more or less this. But this is only easy because the list is made up of four elements and I made it easy for you because first of all it is not always possible to have a solution.

Just think if instead of s being made of 1 57 it was made of 1 2 57. It was already not possible to solve it. Furthermore, if S has a number of elements, think, I don't know, 10 million, you understand that even, well, the human mind just can't do it, but even a calculator has a hard time. This class of problems is called NP problems, or non-polynomial problems, which is a big word for saying they are very difficult problems even for a computer. And that's why Paul spent so much money fixing it.

He needs all that power to solve this problem and so nothing, Paul is actually happy because he spent that money, he is being paid maybe, no, by someone to solve this problem. Everything is fine. Very well, this is precisely the problem of Partition Problem. But now let's introduce the second actor in this system, Veronica. So, Veronica, imagine, she's a police officer, in the sense that her only job is to make sure Paul is doing his job properly.

This translates, if we go back here, into the fact that Veronica, given a starting list S , wants to verify that the S1 and S2 that Paul finds are actually a valid solution to the Partition Problem problem, alé Okay. This is, let's say, Veronica has to check the work, right? Okay, let's ask ourselves this question, that is, how does Veronica verify that Paul did his job correctly? This one right here, I mean, you also try to understand, right? Think about it, we understand how the problem works, so Solution S1 S2 such that the sum of the elements of S1 equals the sum of the elements of S2.

Veronica comes in and says, "I have to make sure you're doing the job correctly. How do we do it?" Nothing, they just sit there, think for a moment and then say, "Oh well." Eh, Paul finds the solution S1, S2 and sends it to you and Veronica sends it why? Because the hard problem is to find S1 S2, but given S1 S2 it is immediate to understand that the solution is valid.

Okay? So Veronica, if she knows S1 and S2, doesn't need a huge amount of computational power to verify that the solution is valid. This protocol works, that is, Paul finds the solution, sends the solution to Veronica, Veronica verifies that the solution is valid up to this point, that is, up to this point. Clear? Well, this works very well.

But why isn't it idyllic? It's not idyllic because a protocol like this, where Paul has to send his solution to Veronica, effectively means that Paul's work can be copied by everyone else, by anyone. So basically put yourself in Poll's shoes. He spent 100 million euros to buy all the equipment to solve the problem and then as soon as he finds it he has to send it to Veronica, which means that basically everyone has his solution available, so even someone who spent €2 copies his solution after 1 millisecond also has it. And so clearly Paul is happy, that is, he does it because he is forced to, but if he could do it differently he would do it and since Paul is an actor with a lot of money he looks for other ways.

Let's see if we can do better, that is, if we can still ensure that Veronica can verify the validity of the solution without Paul having to send her the entire solution. And so to do this we start with a little reorganization of the problem. So what you see in the slide is simply an alternative way of looking at the same problem. I always start with S, but instead of seeing the solution as S1 and S2 such that the sum of the elements of S1 equals the sum of the elements of S2, the solution is A. Auction for satisfying assignment.

And there are three requirements that A must satisfy to be a valid solution. The length of S must be equal to the length of A, that is, S has four elements, so A, to be a valid solution, must also have four elements and here it does. All elements of A are either 1 or -1 and in this case it has them. And then A * S. This, mind you, are two vectors, so yes it is called dot products, that operation there, and it is actually a very trivial operation, that is, it is performed by taking the first element of S, multiplying it by the first element of a, then you add the second element of S by the second element of a, you add all the elements until you reach the last one and it must be equal to 0.

Let's do an example, I'll show you that it is 0. 1 * 1 1 * 1 so we are 1 + 1 2 5 * 1 5 + 2 7 * -1 -7 + 7 0 This is the same problem as before because in fact instead of having S1 and S2 I have A where A in a certain sense you understand that all the elements that are 1 would be those that were previously S1, you see 1 5 and then -1 which would represent the 7 would be S2, so it is the exact same problem. I only represented it this way because this way I can go and make alternative constructions that will be useful for my problem. Well, I want to stop here for a moment to see if you have any questions about this thing because it's fundamental for later. So, is it clear to you?

Perfect. I mean, it's the same problem as before, I just, let's say, changed the way of representing it a little, but I didn't change the concept. At this point what I can immediately try to do is say "Okay, I have s. What I can try to do is create this W. W stands for witness, so even the letters are never random, let's say, because in an explanation you try to give the letters that also correspond to what you find in a textbook, for example.

Now, how am I calculating W? I calculate it as the partial sum of the doct, that is, it would be the partial sum of this A * S. In fact, how do you get it? Well, let's do it here too just to make you understand well. 1 * 1 and 1 is the first element of w.

Then I have the second element of s * second element of a 1 * 1 + the first one and therefore + 1 2. Then I have the third 5 * 1 5 + 2 7 and then I have 7 * -1 -7 + 7 0. So w 1 2 7 0. Once I have obtained W in this way, I do nothing else but translate all the elements on the right and the last element becomes the first, so it's a bit like a sort of clock, imagine it, can you see it? 1 270 becomes 0127.

Here, W is our witness for now and you'll see how useful it will be to help Paul find his solution, not send it to Veronica, but despite this, Veronica will be able to verify its validity. I want to point out that if A is a valid solution, w always starts with 0 because obviously, since the partial sum of the dot product is the partial sum and since a * s must equal zero, the last element, which then becomes the first because I translated them all, must be zero up to here. Maybe you might be wondering why I created W like this, but this is a construction, that is, when looking for a solution we make this attempt, that is, let's try to create this W and see if it can be useful to us. So let's move on. This W, well, it's not just a random W because it generates a wonderful property, this one.

Now, do you know what absolute value is as a mathematical property? That is, like the absolute value of 3 equals 3, the absolute value of -3 = 3. Basically, the absolute value, which would be those horizontal and vertical bars, takes a value, if it's positive, it leaves it as is, if it's negative it makes it positive. Very simple. And there's this wonderful property, that is, the absolute value of s i where i is a number, that is, it would be like 0, 1, 2, or 3 at most in this example, equal to the absolute value of w i + 1 - w of i.

Let's make an example, because you could do it for all the elements, eh, but let's do it for just one, so you don't have to trust it. Let's take I = 2, S2. So, the numbering in vectors always starts from 0, so S2 would be the third element, so s is so here we have 5 on the left. Let's look at the right side. W of 3 because I is = 2, so 2 + 1 3.

W 3 is 7. - 2 5, so 5 = 5. So the We've verified this property, but it applies to all the i's. This property is very interesting because it's a property that links S, which is our initial list that everyone knows, our starting point with W without going through the solution. So you can already see how we're shifting, let's say, our focus from S, that is, we're trying to create a relationship from S to W that never touches A, which is our solution.

What's the idea? The idea is I want to create a relationship that allows me to verify the validity of my solution A without ever having my solution A in the equation, because this way it means I don't have to give a, I just give W. Okay? I mean, we're here. Stop me, okay, because if there's something unclear, stop me first because the further we go, the more complexity increases.

We won't get to crazy stuff, okay, but stop me because that's the beauty of having something interactive. Let's move on. So the protocol now becomes like this. We have our starting list S and instead of having Paul immediately find the Solution, Veronica sends it, what happens with the new protocol is the following. Veronica asks Paul, or rather, sends Paul two consecutive numbers, for example, in this case she sends 0 and 1, but she could have sent, say, any number between 0 and 3, that is, between, say, 0 and the number of elements of s - 1.

Okay? Now he sends her 01. Paul takes 0 and 1, calculates w of 0 and w of 1, sends them to Veronica and Veronica verifies this property, that is, she verifies that S0 is equal to W1 - W0. To verify this property she needs W0 and W1 and that's why Paul sends them to her . Okay?

If Veronica can verify this property, that is, the SDI module etc. etc., then Veronica knows, she's convinced that Paul did his job correctly, but Paul never sent her solution A. Okay, so we've already unlocked, no, something new, innovative. Nice.

Do you see any problem with this protocol? I mean, just to see if you think what problem could there be? There are? Yes, this is an excellent point. Now, there are several critical points that are wrong with this protocol.

The one you touched on is the most important, but we'll look at it later. The first, meanwhile, is that one interaction isn't enough because someone with one interaction could have been lucky, that is, they sent him two numbers or what luck. That is, the property is verified, but he was very lucky, that is, Veronica is not 100% convinced, so we already start from the fact that we have to do more iterations, so first Veronica sends him 0-1, then she sends him W0 and WD1, then the second iteration, this time Veronica asks him for example 2 and 3 and he gives her back W2 W of3. In this way, having touched on all the elements, let's say that Paul Veronica, sorry, is more convinced. But there is also another problem, actually there are two more.

The first problem is that in this way we actually thought we had circumvented the problem without ever providing solution A, but in fact if we provide w at a certain point Veronica knows the solution. Because I'll show you a very concrete example with the first one, already with the first iteration Veronica knows the first two elements of W, that is, 0 and 1. And I'll point out that since Veronica knows how W is created, that is, we know that W is the doc and it is the partial sum of the Doc product between, that is, between S and A. So, already knowing 0 and 1, Veronica knows that the first two elements of A are 1 and 1. So in reality we thought our solution was not, we thought we had turned it around , but in the end Veronica still learns the entire solution and this is a serious problem because it means we haven't solved anything.

We've just taken, let's say, a tangential detour and we haven't solved anything. Another problem is who tells Veronica that Paulia by sending two random numbers instead of WD0 WD1 such that respect this property, but they are random numbers, that is, they are not the numbers of W, okay? There's nothing in our protocol that forces Paul not to lie. So this protocol not only not only, however If Paul behaves correctly, he makes Veronica understand what the solution is, so we haven't solved anything, but it's based on the, uh, solidity, on the truthfulness of what Paul says. Paul could easily lie, Veronica would have no way of understanding it, and that's fine.

Up to this point, let's say, we have to try to solve these problems, and so there are these, let's say, the three main problems, so the two values ​​aren't enough, so we need more iterations of the same protocol. The prover, that is, Paul, can lie, and that's not good, and furthermore, he's not zik, in the sense that in the end, Veronica understands the solution anyway. So, let's try to solve them all. So, let's say we've solved the first one by default, meaning to solve the first problem we just have to do more iterations of the same protocol. The other two, however, are very important, we have to solve them.

Let's start by adding the zik property. So, to add the ZKI property, we start by making changes that add randomness, therefore chance, to the protocol. So, let's start with Paul. Paul finds the solution to, but then first to start his entire protocol with the generation of W, he tosses a coin, if it comes up heads he leaves it unchanged, so what would the solution really be like. If it comes up tails he inverts its sign, so you see -1 -1 -1 1 completely inverted.

This is the first source of randomness, coin toss. Second source of randomness and obviously starting from the generated a's two different W's are generated. Ok? This is clear because W was the partial sum of the product between S and A. Changing A also changes W.

And so far nothing strange. But let's add the second component of randomness. Once I have calculated my w starting from which can be either normal or inverted in sign, I go and choose a random number R, in this example R = 4 and I add this element, this number, to each element of W and therefore I find what I have called here W' which on one side is 4 5 6 11 and on the other is 4 3 2 - 3. So with only two elements of randomness, a coin toss to, let's say, change the sign or negative of a and a random number to increase all the values ​​of wero, I get a w a. That is, having this W here and not knowing either R or the outcome of the coin toss, I basically have a lot more difficulty going back to what the real W and the real A were.

And by doing so, and by the way, be careful, Paul will do this at every iteration of the protocol, not just the first time. So at every iteration of the protocol, Paul tosses the coin, calculates the new A, calculates the W, takes a random number that is always different and adds all the numbers of W a with this element. By doing so, by the way , this is very important. The beauty of this randomness that we added is that it doesn't change the fundamental property and it may seem absurd, but if we do the calculations and with both Ws, both the one that started with A heads and the one that started with A completely inverted, they maintain the property. You can, I mean, you could easily do the test, let's do it because in any case the time There is.

Let's take S2 ​​again, so S2 is 5 and then there we have W3 which is 11 - W2 which is 6. 11 - 6 5, so 5 = 5 verified, so and the same thing would happen here, you see, we would have -3, -2 -5, absolute value 5. So we managed to create enough randomness to lose track of the real W, but still keeping our property unchanged. And so let's go back to our protocol. How does it work?

Now we always start with S, the initial list. This is clear, it's a piece of data known to everyone. At this point, before the protocol starts, Paul flips the coin. Paul already has the solution, eh, so Paul has already found it. Flip the coin, text tails.

Suppose it comes up tails, okay? and R is equal to 4. So what Pol basically does is since it's tails I go and select this part on the right where it's all negative, I calculate w and then I add 4 because we said R is equal to 4, then he chose it equal to 4 and so I get this w here, this prime w. And so when Veronica then sends me one and two as elements, that is, she tells me I want to know w1 and w2, Paul sends him W of 1 3 and W of 2 3 and 2. Very good.

And Veronica can again verify that this property remains unchanged, so she says, "Okay, actually, Paul, you did the job correctly." Let's try to understand if Ziki's property , that is, this time whether Veronica can or cannot, understand the real solution. And in fact, Ah, well, here I was showing you a new iteration of the loop. Here, at the second iteration of the loop, this is important, everything changes again, that is, you see that this time it's heads and R equals 1. This is fundamental, that is, each iteration of the loop, the random elements, that is, tails and no, sorry, not tails, the coin toss and the random number is always different.

This is very important. And it is precisely this randomness. Okay? I want to show you this slide. Here, after two iterations of the loop, these are the elements known to Veronica in addition to S.

That is, Veronica knows that in the first iteration of the loop w' 1 = 3 and w' 2 = 2. And here one might say, well, I'm having a hard time going back because there's too much randomness, but maybe let's do more iterations of the loop so I can try to understand more, right? But the second iteration of the loop w second 2 = 3 and that already messes things up, right? Because before it was equal to 2, the same, let's say, value, right? You see that they are already different and then W3 W second 3 = 8.

So, in fact, the protocol we managed to create has this magical property where Veronica can verify the validity of the solution because the property that, well, whatever we call that property, this one, this property here is always valid and this is the property that Veronica uses to understand whether Paul has done his job correctly or not. But she doesn't have enough elements to understand the solution because Paul has added too much randomness and does so at every iteration of the cycle. So as of today, my dear, we haven't solved the first problem because we simply said let's do more iterations of the same cycle, but also the third because now Veronica is able to verify Paul's work, but she can do so without knowing the solution. So at this point Paul is in the ideal solution, meaning he does his work correctly, he is able to prove that his work is valid without providing the solution, so his investment is also protected. Now let's say that Veronica, however, at this point asks herself, "Okay, that's fine with me because I don't want to know the solution, I just want to be able to verify it, but the current protocol is still too—uh, it has this weakness regarding the fact that I'm trusting you too much, Paul, because you could still give me all the numbers you want, there's no constraint on the numbers you 're giving me and so it's not good, let's try to solve this problem too.

Now what we need to insert to ensure that Paul is constrained to give numbers that truly belong to W and not to Random numbers are what's called a commitment, meaning Paul has to make a commitment to W before starting the protocol, before starting the iteration of each protocol, that is, each iteration of the protocol. Now, commitments can be made in a million different ways. We've seen Ethereum, for example, with the AP4844 update, which added commitments made with KZG cryptography, which is a very complex cryptography that, however, satisfies the requirements that Ethereum had. In our example, we're using one of the simplest forms of commitment that exist, namely Mercle Trees. Mercle Trees, by the way, I don't know if you're familiar with them, they're widely used in Bitcoin too and are a cryptographic form that gives , that is, it derives its name from a certain, I think Merkel, who over the years— honestly, I don't remember, but we're talking about a cryptography that's not recent, so it's something much older, but it's still used today and making a commitment is very simple.

In the leaf elements, the leaves, no, they're called that; I'm going to put the W numbers there. Here, keep in mind that now I'm taking a real W, that is, without added randomness, but the same thing applies if instead of having W I have the W' where the coin was first tossed and then I added the numbers, the random number R, it's the same thing. So I add the numbers of W and then I create the Mercalle root by doing the cryptographic ashun. And finally we can see our complete protocol. Look, the main difference is that in addition to them, at each iteration of the cycle, before starting, that is, before Veronica sends 0 and 1, Paul must share the mercol root of W'mo.

This is very important because now when Veronica sends 0 and 1, Paul not only has to return W' 0 and W' 1 but he also has to return the mercolle pat which is nothing other than the cryptographic tool such that Veronica is both able to verify the validity of the solution and is able to verify that the solution, i.e. W0 and W1, are in all respects part of W, that is, they are not random numbers, but These are the right numbers that are part of W. And at this point we have solved all the problems. So I am about to give you the chance, let's say, to move towards the conclusion, then maybe there will be time for questions, I'm happy to answer them.

I want to tell you that around November of this year the second version of Mastering Ethereum will be released, which I am happy to have co-written with Carlo Parisi who is also here and Nicolò Pozzolini who is not here but anyway we say we thank him remotely. And the second edition of the famous book by Antonopolus Master Ethereum. Now the second edition will be released completely updated, completely revised, so if you are Ethereum fans and really want to explore this topic too because the book also touches on zip proofs and much more, there will be this splendid book and as for me, you can find me both on X and on YouTube mainly where on YouTube a video comes out every Sunday or so, except in August when there will be a summer break. On X you can find me more or less every day. I publish, let's say, updates or even posts.

So thank you for your attention. Yes, there are no more slides, so nothing, space for questions if there are any.