# STARK proofs ELI5

- Speakers: [Henri](https://streameth.org/speakers/henri)
- Channel: [Devcon 7 SEA](https://streameth.org/devcon_7_sea)
- Date: 2024-11-12
- Duration: 08:17
- Watch: https://streameth.org/watch/6732fea080d989c5b7b42256

## Description

Let's face it, ZK proofs are intimidating. But they don't have to be!
ZK proofs are complex not because of the depth math they use, but because of the large number of fields of mathematics they leverage features from.
In this talk, we'll break down STARK proofs into simple blocks and colorful analogies so that you get a good high level overview of how they work

## About the speakers

### Henri

Hello, I'm Henri. I'm the head of ecosystem at the Starknet foundation. 
I like breaking things that are hard to understand into simple terms, so that they are easier to understand & get excited about.


## Transcript

Everyone, welcome. My name is Henri Lutot. I work at the StarkNet Foundation where I'm the head of ecosystem. And I'm going to try to explain Stark proof like you're a five-year-old. There's many ways to explain proof. This is mine. It's not perfect, but I hope you learn something. So how I'm going to go about it is the following way. I'm going to first explain quickly what is proving, what we're trying to achieve. I'm going to talk about something that is called arithmetization. I'm going to talk about execution traces and how they get used into proofs. I'm going to talk about error correction code, and then I'm going to try to put everything together so that you have a clearer picture. So first, let's talk about proving. What is proving? Proving is a person trying to execute a computer code, and that person is called a prover, and he's trying to convince the verifier that the execution happened correctly without the verifier having to re-execute the computation. Now the kicker where this gets interesting is that there's an asymmetry between prover and verifier and it's very efficient for the verifier to verify rather than re-execute. So we save a lot on compute on the verifier side. So that's what we're trying to do. So first, now, how do we do that? We first use one step that is called arithmetization. Arithmetization, from a high level perspective, is the act of turning a computation into a set of polynomials that represent said computation. I'm not going to go too deep into that, but assume the following. When you use a computer, you know that your computer program can be turned into logic that gets executed on transistors and on zeros and ones. You can get the same result by having your computation represented as polynomials. And when you design a computer program that you want to prove, you have an expected polynomial, which is the polynomial where every execution of your program will have points falling on it. Okay? Now let's talk about an execution trace. What is an execution trace? The execution trace is the equivalent of the step-by-step log of you executing a program. If you were using a CPU, for example, it would be the register of the list of all actions, all registers, all ,, all memory steps at every single step of the execution of your program. So executing your program is the sequence of all those specific steps. Now, what do we do with this execution trace when we're trying to prove is we're turning that execution trace also into a polynomial. So you take all those data points and you turn them into points and you interpolate a polynomial that will go through this execution trace. So now you have two polynomials, right? You have the expected polynomial, the one that defines the program you're trying to prove, and you have the executed polynomial, which represents the execution you just ran. So what do we do with that? We apply something on top of it that is called error correction code. Error correction code is something that is used in telecommunication to transmit data and verify its integrity. It gives you two properties. One, you can detect error very easily. And two, you can recover from those errors. But we're not trying to recover from errors. We're trying to detect those. So we're using those techniques on those two polynomials to check if the execution polynomial is as close as possible or the closest way possible to the expected polynomial. That's how error correction code is used in StarkProve. So now wrapping it up, what we're trying to do is to convince the verifier that the execution happened over the same polynomial that the execution happened over the same polynomial that the polynomial he was expecting, which was defining the computer problem he was trying to solve. And with error correction code, we're just taking any tiny mistake that might have happened somewhere and we're amplifying it. So instead of having to check every point in the execution, the verifier can just take a few points and then check using error correction code whether there was an error somewhere. I hope that makes sense and you learned something. And here's the actual explain line 5 explanation of stark proofs. Stark proofs are five years old worst nightmare. When you're going to the swimming pool and somebody tells you, hey, if you pee, it's going to turn red and everybody will see it. Stark proofs are the exact same thing for computation. If you try to cheat at a single place, it's going to blow up everywhere and everybody will see it and will know you're a cheater and you're not going to be able to convince the verifier that you did your computation correctly. Voila, thank you. Thank you, Harry. We should probably invent something that makes your p-turns red and poor. Any questions? Ah, this one. I'll do this one. How do error-correcting codes and polynomial commitment schemes differ? I'm not entirely sure I can answer this question. I don't know enough about it, so I'm sorry. Oh, I see another hand here. This lady. By the way, thank you so much for the ELI five. I want to really understand a bit more when you say you take a few points out at the ECC stage, you take a few points and amplify it. Is that right to understand that as a statistical probability that it might have an error that you cannot detect because the sampling wasn't done to capture those points, or is that just we should feel comfortable believing that as long as it passes, it is error free? I'm not sure I understand your question, but I think what you're saying is, is there like, depending on I think what you're saying is, is there like, depending on how much samples you're taking, you have a different level of certainty. Yes, that's actually the case. When you're taking samples, you're going to see error with a probability, and the more sample you take, the lower the probability of you catching, of not catching an error. All right. Any other questions for Henry? Oh, there's one here. Hey. So do I understand properly that this verifier needs to have this execution polynomial like a like a sample that it needs to check whether it's following the same steps? Yes, it does get a form of a, it does get some sample from the execution trace. Originally in proof there are protocols so that the verifier asks the prover, hey can I get this point? Can I get this point? And then he verifies a few, but using some fancy cryptographic technique, you can actually get away with just giving, the prover can get away with giving a bunch of random points and having the verifier just use them off the bat. We take one more question. Ah, there's one there. If the prover can select the points to send to the verifier, can he select the points in such ways that the verifier won't be able to detect the error? So the fancy cryptographic technique I mentioned makes it so that he can't select points that are comfortable for him. So then he can't really cheat. Hopefully.