ZK10: Visual ProtoStar - Adrian Hamelink

Transcript

foreign [Music] good afternoon everybody um my name is Adrian I'm a ZK researcher and I've been working on unfolding for the last few months now um I know it's been a long day with lots of math so I wanted to keep things a bit light and focus on building up your visual intuition for what folding is now I want to note that this is going to apply mainly to the Nova sangria and protostar lines of work so I don't expect anybody to have read the papers before um and so like yeah with any good ZK analogy we obviously need a a very contrived real world example so if you'll allow let's take to the Sea as we

explore folding Island now the situation as follows we've got on falling Island there's like this very special fruit that grows on the shore and this fruit is rare and because it's on an island it's not exactly easy to get to but fortunately we've got a approver who knows how to get there and he picks the fruits and he brings them back to Mainland and he sells them to a verifier obviously uh the verifier just doesn't really trust approver so he wants to make sure the free he's getting is actually from this island and it's not some counterfeit fruit or some old fruit or so so he works for insurance he asks the Pervert to tell him the exact GPS coordinates of where he landed on this island

but this if the verified actually wanted to check this this would be not really practical since the verifier would actually have to um visit the island and uh if they're going there anyway they might as well just pick the fruit themselves and cut the middlemen right and this makes even less sense when um in the verify is placing many orders because uh like you don't want to be checking it at every time so like we want to try and come up with a better system for these two parties to interact so that everybody's happy at the end so we're going to come up with this folding like technique which is going to make things more efficient for the verifier and with only a little bit of extra work for the prover so this is a situation on the left here we've got uh the previous perspective

um he actually goes to the island so he sees it in all his glory and including the elevation and the verifier knows that this fruit grows on the specific on an island with a very specific shape but he only has a 2d view of it um so just to be clear we're interested here in like the elevation of the island and the shoreline so on the first delivery the approver is going to get to the island and he lands at a specific point P0 now he's going to note these coordinates he's also going to pick his fruit and then he sails back to the mainland sells the fruit to the verifier and gives him the coordinates now one thing to note is that because he landed on the shore well we expect the elevation of this point to be zero so the verifier just writes it down and

he's able to map the point on his 2D map now for the second visit the preview arrives at another Point P1 and again because it's a sea level we expect this uh the elevation to be zero right so he he he you know sit down he picks up the fruit but he's going to do a little something extra because what he wants to do is he wants to convey to the verifier that he's actually visited the island and he's not just like repurposing some old fruit or or selling whatever else so what can he do right now the information we have we have P1 and P0 what the proof is going to do is he's going to draw a straight line between P1 and P0 the verify is also able to do this because they've got the 2D map and the proverb is just going to walk from

P1 to P0 and record his elevation along the way now fortunately the prover is like in really good shape so this kind of height doesn't really bother him even though one it's not really a nice hike I guess um but keep in mind that this is way less work than having the verifier actually come to the island so this is acceptable for the Peru to do and so along the way he's going to record the elevation and when he gets back to Mainland he's going to give the verifier uh well the fruit uh the new Landing Corners P1 as well as his elevation map but that's he he he he he he created well he was uh there now obviously the verify doesn't trust anything of the previous giving him but we he can check one thing he's going to check that at least on this elevation map uh that both

P1 and P0 are indeed at elevation zero right and in this situation well this is a really nice situation to be in because what we've just done is that we've forced the prover to actually convey to the verifier that he visited the island and we forced the prover to be right about the elevation at every single point between P1 and P0 and not just the elevations at P0 and P1 so this is a nice situation to be in the in cryptography because we just first proved to be right in several places and and so what the verifier is going to do is he's going to say okay well I'm just going to check this elevation map in a single point so we did a good classic thing he samples around the point alpha

or rather a random scalar Alpha between zero and one and this is going to define a random midpoint between P0 and P1 what the math is saying here is just that uh P 1 Prime is like Alpha percent away from P1 in the direction of P0 now uh because the verify is able to compute this point P1 Prime by themselves because he's just looking at the map and drawing a line Computing the percentage Etc and he's going to use the previous elevation map to compute the claimed elevation of P1 Prime on this map and because the elevation map already contains the information about the elevation of P0 and P1 and we're just checking that the elevation map is correct well he can actually forget

about P0 and P1 and just focus on P1 Prime now just a great pickup from the previous perspective again so he's walked from P1 to P0 with this elevation map the verify assemble the random Alpha this defines a new random Point P1 Prime the elevation is given like this on the island and we can forget about the two previous points because what we really care about now is testing this elevation map and so we've reduced our problem from checking two different Landing coordinates to only checking the elevation of a single point on the island and if the Brewer was wrong at any point uh whether uh he was wrong about or he was lying about his Landing cornice P0 and P1 or he gave the wrong elevation map then with a really high probability

uh the elevation at of P1 Prime would be wrong but we're going to continue the prover is going to get back to the island for a third order and he arrives now at this new Landing Point P2 now again he's going to record the coordinates pick up some fruit and again he's going to draw up a straight line to where well the only coordinates that are remembered at this point is P1 Prime because we forgot about the other ones so he's just going to draw that and again he's going to walk there do a little hike this time it looks like this a bit more a bit more of a elevation but again he's in good shape and he does this he sells back to Mainland and again he delivers to the prover to the verifier the fruits the

new coordinate P2 as well as the new elevation map and just as before the verifier is going to check on this elevation map that with both poisons that he has in the claimed elevations these match up with the elevation map so now we've again reduced our problem of checking just the elevation map and we can ignore the two uh previous points um or well not yet because we still first have to sample a random midpoint using another challenge Alpha this defines again a new Point P2 Prime and again the verifier just needs to look at the elevation map which is not trusted at this point but it allows the verifier to at least check the elevation obtain the elevation of random point on this island and so again this is from the previous perspective we've got the elevation map

Drawn here a new random Point P2 Prime is sampled and we compute the elevation like this now this is really nice because now we've had three visits and we're left with only one point to check with one elevation and the way we've constructed this is that we've iterated our checks one above on top of the other and by only checking the elevation of P2 Prime here well we're able by checking just this point to verify and confirm with very high probability that the elevations of all three Landings were correct if the proverb was on the uh if he was wrong at any point whether he gave wrong Landing coordinates or wrong elevation Maps then

the elevation of P2 Prime would be wrong and so this is really nice the verifier would only have to come to the island once check one single point and he'd make sure that like everything that was done by the proverb before this was correct now so you may wonder how does that this actually relate to snarks um so now our analogy um this island here was actually defined by a polynomial and this polynomial you gave it a two quarter a coordinates X and Y and for any point on this island it will spit out uh the elevation you're at now um this is just like in a snark where like gates are these polynomial equations and the reason why we're

interested in the short is that these are the points where the equation um equals zero so we're interested in the valid witness points and in this example like you had P1 and P0 which works on the shore and trust me but this will evaluate to zero at this place and just as we can draw a line between two points uh on the map we can actually do the same thing with uh witness coordinates uh by simply interpolating between the two this defines a linear polynomial uh it's a line which uh Maps between the two which passes between the two points the elevation map is what sometimes referred to in the in these papers as the error polynomial or the slack polynomial and it's simply implied by evaluating the elevation over all the

points in the line so we just need to plug in our equation for our line into the gate equation or our Island equation and that will give us a polynomial that defines the elevation between p 0 and P1 and because it's a polynomial its degree is actually the same one as G well we only need to sample it at degree G plus one points and we knowing that we already have two evaluations which are the evaluations at zero which should give the the elevation of P0 and the uh evaluation at one which should give the elevation at uh one P1 which is also zero and so when the Pervert comes back with the map he actually comes back with a

couple of points sampled from this polynomial and when the verifier has sampled their random challenge Alpha well they're able to interpolate this polynomial and obtain the evaluation of uh the elevation map or the error polynomial and so just to bring things back a bit more to snarks if we have a more realistic case a multiplication gate for example which takes three coordinates x y and z um in this case we valid witness is considered a triple X Y and Z such that Z is equal to x times y and the error polynomial here is just equal to the composition of the thing I detailed before so you take the linear

interpolation between the two witness points w0 and W1 and plug that into your gate equation and this gives a complicated polynomial but it's still easy to evaluate and you only ever need to evaluate it in three points to get the full polynomial now I know I glossed over a lot of stuff but I hope I was able to um expand your intuition on protostar and if you have any more questions I'd be happy to talk about it more and yeah thank you for having me good day