Intro to SNARKs 4: Proof systems in the wild

Transcript

everybody it's nice to see so many of you here for the fourth session I know that the second and third sessions were pretty intense but though if you manage to stick through it's very very worthwhile if you're going to be going into anything related to zedk Tech um that knowledge is going to go a long way to making understanding it easier um I'm going to talk about the session in a second just before we we get to that um again just general points got the course material you will be no this by now we can drop it in the chat if anybody is missing it um and now is really the best time to ask any more lingering questions this session might end up being a lot shorter um this session is also going to

be quite different in in style so ke Chong's here with me on the stage and he's going to kind of chime in asking questions whenever we're going over stuff to make it a bit more conversational and try and um you know emphasize uh perspectives and so if you ask questions in the chat as well we're going to be um answering those then there's the intro to snar channel we can ask async questions and that's for the future that Channel's active in the PSC Discord and you can use that whenever it's not just tied to to this course

um just G to before I go over the clarifications I just want to talk about this session again um the part of the idea in this last session is almost like a continuation of the first session in that the second and third session shouldn't be necessary to understand what's going on here although we'll mention those things briefly this is going to be much more of a kind of high level description and discussion again okay that's what I wanted to add but before we get there I just want to add some clarifications from from the third lesson and this is kind of just just repeating some of the things there to try and reinforce that info um so most snarks work with

elliptic curves um generally speaking if it's not postquantum resistant it uses elliptic curves elliptic curves are just generally kind of faster and provide abundant security but not against quantum computers specifically the dlog Assumption this discrete log problem where you're trying to take a curve point and figure out what number it is multiplied by the fact that we assume that's hard that allows us to hide values in elliptic curves and that's sort of the Crux of how we can embed elliptic curves into our protocols and our systems the main example or the best example for this is your wallet your

crypto wallet if you've got metamask or whatever else it is your public address is a curve point I mean It's usually the x coordinate because you know you got the coordinates It's usually the x coordinate of uh your um yeah of of of elliptic curve point and you made that because you multiplied the generator just some curve point we all agreed that will use together by your secret key which is just a big number but it's in a in a field and then we spend a fair bit of time on polinomial commitment scheme discussing how they work how they allow us to take a polinomial commit to it and

then make and then evaluate that Pol points and the system allows us to prove that these equations came from the same polinomial we committed to and that's very important in how our proof systems work and that's also one of the kind of modular component of proof systems that the proof the polom commitment scheme can sort of been SW po out for different systems generally speaking it's not a developer who will do this this is a kind of a ZK like real research expert who's making a new zero knowledge system for developers and you know people who want to use the tech generally speaking you're just going to take a system that's been implemented by somebody else

and make your own circuits there so in this last session Lesson Four part three because the online content it's part three um we're going to briefly look at how Pol polinomial commitment schemes are used to do verifiable computation in plon and that's just going to be a very high level description and a bit of a sketch we're briefly going to touch on what a constraint count is because this is a kind of a common topic of conversation and we're going to look around at a few different proof systems specifically plun itself grth 16 Halo 2 and ZK Starks and kind of say different things uh K Chong I cannot hear

you um yeah I can't currently hear you I don't know if anybody else can if they can't I'm sure somebody will say in the in the chat so if you're having a technical issue then no um oops okay well we'll continue hopefully he can he can figure that out and again just reiterating again please please please ask as many questions as you want here this is like for you guys can you hear me now now we can I can hear you yeah oh oh man I've been talking this whole time and I just saw everybody's ignoring me sorry that that's got to feel bad

man okay yeah I was I was saying trying to say before yeah this is very uh much more of an open session so feel free to ask questions uh this also you know especially like beginner introductory type questions like I'm going to be asking a few of those so feel comfortable um ask that and what I wanted to add in was like um errow was saying there you don't if you don't understand all the math behind it that he's going over it's okay I think it's actually more important just to like know it exists and when you hear things like no commitment schemes and elliptic curves and things like you kind of you've heard of it before and if you wanted to dive more you could but it's

okay to not understand all because I certainly don't so I just wanted to add yeah absolutely I mean this kind of how it goes it math is a is a language and the same as learning like a a human language whether it's Spanish or German whatever else in the beginning when you hear people speak you just kind of hear sounds and then the first step is learning to actually decipher separate words that people are saying and then to understand those words so here you know you you don't need to know that well what a group is but in the beginning it's kind of recognizing that group is a thing and understanding that term and bit by bit you can build on on on that knowledge and the questions you ask don't have to be related to exactly what I'm saying now it can be anything from a

past session or anything even kind of in general that we haven't touched upon so we're going to spend a bit of time now sort of going over what we discussed in the in the first session um here was this picture and I think it's really helpful to kind of just you know memorize this this picture these are really the rough steps of um a proof system and I'm just to give it a bit more Focus I'm going to sketch just just like draw that out line by line so we can kind of focus on it this is everything we've done so far okay let's

do knock fundamentals yeah we wanted to un emphasize this um this kind of graph because if if you under not the graph but the image because if you understand the whole thing you you get you understand most of it at quite a high level exactly like really that picture encapsulates I would say the minimum knowledge that most people should have about zero knowledge technology they don't need to go any deeper of course if you do you can do more with it but this not this like high level picture is sufficient for for most things um so it starts off with having a value idea

about something that you think would be valuable and usually it'll be a kind of you know on such a long word entrepreneur who will come up with a value idea and that person doesn't have to be distinct from the zedk expert they can also be an entrepreneur but that's just kind of like an entrepreneurial task more and we take that value so some examples would be how you know how you could use privacy like what you could add to privac to make it more private and the other thing is scaling so what you can scale so those have been most of the core ideas so far but there are many others yeah those are kind of the the main benefits of using this technology and

you know it's not those generally speaking the researcher who knows how to make the best zero knowledge snark they don't necessarily know about the business business world or or the medical world and and computational world and where it will find Value um so then we go to our idealized circuit which is kind of a sketch in more detail of like what kind of computation are we doing um and how does that solve this value idea so there is a bit of a sort of backward Arrow here showing how the idolized circuit would actually solve this problem or or contri that value and then and then comes in the

ZK engineer to um artize this into a circuit right remember that was this process step is where this step is where you would need to know the math right at this CK engineer before that you wouldn't have to know but this is where you you you kind of need to get more into the detail exactly like I've said before this is where a a lot of Z Engineers spend their time they they're making circuits so this is kind of quite math heavy so

circuit and then in here is where the witness is added and this is sort of our our zero knowledge this is the thing that's kept hidden and and private and secret so the witness is the all the values the prover adds into the circuit is that right and those some of those are private some of those can be public exactly so this is free that's our starting circuit then the witness is just the the remaining y values and um I now will try and make this a valid circuit so and now this

will be 3+ 1 be four 4 * 2 is8 and all the red values are part of the witness and this will remain secret but all the yellow values were known to everybody and yeah this is our filled in circuit and then from there anybody has any questions so far feel free to ask us or raise your hand or put in the chat here well not let's do make pols we take this circuit and from it we make our pols and that's based off how the proof

system works the proof system will dictate how you make these pols in actuality like you're not making pols this is um from this point onwards the library you're using is is doing all this for you but this is kind of what's Happening under the hood a little bit so Whispering words how do we fit a polinomial into a group to then use it um what we do is we'll we'll we'll make our just go further below instead we'll polinomial well we actually make several Pol omals and you know maybe this one is

3 + 7 x + 9 x^2 you know in reality these will be really long pols and the numbers will not be small they'll be huge numbers um if we evaluate this at like two for example get 3 + 14 plus x² 9 * 4 which is uh you know 3 + 14 + 3 6 which is 53 oops not one 53 um and instead of using this as a number we can instead kind of evaluate

it with our elliptic curve so we don't get out 53 we'll get out a 53 G where G is is on our elliptic curve and then because of this 53g itself you know G it's on elliptic curve but it's in a group The elliptic curve group that we discussed in the past couple sessions um so so now we have 53g instead which is also within that group because if you remember we mentioned that the groups are kind of self-contained if you add things together in a group you're still going to get something out in the group so in

this way we kind of get group items group objects from our pols and the sort of the purpose of that in terms of like using it per se is we want to look at the behavior of this group object to see if it behaves as we expect because if it does it's going to imply to us that it uh um that the computation was valid because the polinomial themselves represent this circuit would you like to explain towards the end the whole journey of a transaction which snar to generating proof and getting verified by the SN and

taking snar that uses some sort of table as well as plk 3 something so we can have a a brief look at that I think that would be better done towards the end because that's more involved and Technical and so we can do that in the sort of spare time at the end because this session itself in general should be a lot shorter so if I forget just remind me at the end um with our filled in circuit we go to our polinomial we we make the polinomial and then uh we commit oops wrong color maintain our blue we're going to

commit commit to these pols and this was the system we spoke about yesterday but sorry last session and that's actually kind of what's Happening Here when we evaluate these polinomial somewhere what we get out will call our commitment because it it sort of ties us into this polinomial but it doesn't reveal our polinomial and it's the polinomial commitment scheme that allows us to make use of this commitment and then we say we query our pols is the next step and previously

I've been drawing this as coming from the commit step because it happens afterwards but it it might make more sense to draw this from the makeer polinomial because we don't use the commitment in this step it kind of um we we're at least claiming in the proof system what we're supposed to do is is use those pols that we originally made um okay friendly if I I've mentioned that we're checking to see if the be polinomial behave correctly and I know that's kind of very vague but it's it's a little bit involved so I'm just trying to leave it very high level um it is not circuit dependent it is proof system dependent these these pols that we

make um plunk the proof system we primarily kind of talking about plon says if we make pols in this certain way then we should then then we can predict how these pols relate to each other and that's the behavior I'm actually talking about is how these pols relate to each other and based off that we should be able to determine if the if the um circuit is valid if I let me finish this kind of walk through of what we've already done and I can add to that just a a little bit so we'll query our pols and then what we get

out is our proof which is usually denoted as a Pi Pi symbol proof I and this all this stuff all this stuff this is the work of the prover that's what the the prover does they're putting in their witness and then they're making these Pol nomials and they're committing to them and they're querying them and this process takes a bit of time this is where computational power is used some of the trade-offs are if um touch on that a bit later but if you want to do this on a

phone for example the phone has to actually make the proof and it it uh it takes computational work and in not ins significant amount is the amount is what I should specify because afterwards is comes the pro sorry the verifier and what the verifier will do let's take a green the verifier will take in the proof and they'll also take in the original circuit um check we can call it Behavior or you know use the the verification method that the proof system tells us to use again the verifier doesn't actually personally have to do anything complicated they're

just using the plon library and the plon library has a function um to verify whether something is valid or not and if it is valid we're happy or the verify is happy and if we're not if it's not they're not happy so this is verifier okay so if you were a developer like what part of this if you understood this whole like Journey what part of it could you just ignore uh very good question uh for most developers

this um all this proof Mak sorry not proof making why does it keep changing my L let me do highlight instead all this polinomial making uh doesn't matter um in fact yeah the the primary thing that developers should be focused on is I've said a couple times before is this arithmetization process because most Z Engineers they're given kind of a specification of an idealized circuit and they've got to turn that into code that's what they spend most of their time on and it's not a straightforward

process to represent computation as within the limits of your proof system remember we have addition and multiplic um we've got these addition and multiplication Gates and that's very different to normal programming you know there's no I8 or u8 or u32 um ideally you shouldn't be using IF conditions um you can use for Loops it's kind of fine the nature of programming and in z circuits is is quite different and that's basically where all their time should be spent that being said you need to be able to debug a bit right a lot of programming is debugging

and figuring out why your thing doesn't work uh you might get proofs that don't pass in which case you want to understand a little bit what possibly went wrong and maybe where the the problem is it's of course going to be somehow in the way you designed your circuit because you can have s security flaws the primary being that like your code the circuit you made doesn't exactly represent the thing it's supposed to represent um so yeah it's it's really this arithmetization aspect and there is some maths related to that um or you know kind of analytical thinking like giving this process how do we represent

that with field elements and additional multiplication there are more gates of course like I've mentioned but we're using the very basic form here to limit scope um what are the things verifier depend on here and what makes verification take more time in snar Star we're going to get to Starks kind of later on maybe we can revisit them um yeah yeah we're going to touch on Star Starks later and we can we can touch that there but the verifier doesn't really depend on anything they just take in a proof and a and a circuit and check whether the proof is valid for

that circuit um but of course um for for verifiers you know it's not just it's not just whether they're sad or or happy because if a proof checks out then like so what why does it matter you know if you fill in a circuit correctly why should I care that goes back to the start of this whole process of sorry Direction go back to the value idea what does the circuit that a valid computation actually represent and if it means that you are the account owner and you want to send somebody some money then I'm a

bit more interested and then we can work with it um if more people have audio issues please let us know and we can attempt some thing just restart yeah prodct build has good idea on what end you place should be good idea typically story I think in ter in terms of like the much bigger picture where snarks are just one of the tools you're using if you know if you want to build an app

you might need a website you need Finance people business people Outreach you'll need the design of the app the idea the the snars are only really like a small part of it they might be for many many applications they're key and possibly Central but there's still a kind of segment of that that whole process I guess it boils down to like why are you using snarks and in what way are they being used in in your product um they they're used to confirm that computation was done correctly or to kind of scale or to add some some zero knowledge aspect I I think in most cases for like

I'm not sure I'm exactly answering the question here GI but for for end users that it shouldn't matter for end users what technology you're using you might want to give them um comfort uh um make them feel good that that what you're doing is it works well and is secure and it's safe but user experience- wise I don't think it should should matter to them like hopefully it should be very very seamless and fluid uh experience for them kind of going from the user story to the to the circuit is um in the user story you know the user wants to do this specific thing or have this feature in

them it have this feature and then the question is like is snark the right technology for this and if so what is the computation that's necessary of I guess what is the value idea of um in the user story yeah um oh I did miss oh sorry I missed some questions I'm an app called NE also import yes which is really nice this

topic but just quickly there adding two points litic curve to get the third what are the guarantees that a hacker will not trace the original points yeah um so you can't trace if you just add two points to get a third you can't trace to get the original because it's like literally unsolvable given just that information there are if if the field is size P then there are basically P many solutions and there's no way to distinguish between them you know if this is a circle because this is modular arithmetic if you add this point to this point you'll get out

this this point sorry and this is going to be quick but if you want to know what added to this point you have an infinite number of solutions in no way to determine between them um like you could have this point and that point or you could have this point and that point it's just like there's no way to decide from all the possible solution so a hacker can't go backwards in in way I guess the same as normal numbers like you know if we do 5 + 5 is 10 then how did we get 10 well it could be 5 + 5 but it could also be 6 + 4 or 7 + 3 or 11 minus one in this way the possible

answers but going back to kind of the high level there's just this picture here of um I understanding this picture is what most conversation will be related to when you become more of a specialist like you'll be talking more about is our arithmetization is it optimized you know is is it is it as small as we can make it and also is it secure does it represent it sufficiently well again you can have a security floor where um you know a hacker could maybe break it because you're not checking everything you're check okay

so can't see your it's just me yeah I just I just got a notification that I dropped off the internet give me just a moment um any more questions do you have along the way K Chong um no I think let's move on to the next section okay so I'm just reconnecting and then I can get back in there don't know whether I'll be still sh screen sharing that let's head back share screen there we go and we should be back so here we

wanted to this is a this is extracted fully from the online content and it kind of it's putting a lot of these pieces together so we want to go over it because it's quite dense um and this is in the context of the picture we just sort of Drew halfway through once we make the polinomial we can commit to them using our polinomial scheme right as we said and then we can proofs we make the proof by um we the term is opening commitments what that means is we take the polinomial we we committed to and we make a new evaluation from it and then we make a opening proof that

the new valuation came from the same polinomial we committed to and the purpose of that is so that we we kind of lock in the computation once we say we finished the computation we want to make sure we can't the prover can't change it again because of course if they could then um they they might be able to break the system so that's called opening um a commitment and we query the polinomial to get their opening or in part to get their openings um and a lot of this stuff is kept secret because of the dlog Assumption the discrete log assumption um the discrete log is sort of everywhere in elliptic curve cryptography but it's in

some places more than others because when you evaluate a polom you're adding lots of points together so it's already kind of mixed up and hard to to to to Break um but it is still embedded there because any single point we we can't go backwards from and that's like Central to the security which is exactly why quantum computers breaking it breaks the whole system because it is fully Central and tied to everything um and then we'll use the commitments analytic curve cryptography to check that they satisfy the expected relationship um and the the way we check

that they satisfy the relationship is the Schwarz zip or Lemo if you remember what ends up happening is that the polinomial we we'll make we'll kind of mix them together and we should essentially have two pooms that embed all the information from the computation and if it's if the computation has been filled in correctly these pols should be the same size and they should actually just be the same polinomial so what we'll do is we'll evaluate both of them at a random point and we'll compare and see if their evaluations are the same which is exactly the short zipple Lemma because

if they're evaluate if we evaluate them at a random point and their evaluations are the same and the polinomial are the same size then with 99.99999% probability um the polinomial is the same sorry if the evaluations are the same then almost definitely the polinomial are the same which should only happen if the computation was filled incorrectly you know that that can take a couple to go from sort of not too much mathematical background to to understanding that would take several hours and even then like it's connecting all the different pieces together to fully understand why it's the case it

just takes a long time to get used to but the beh like I saying the behavior we're expecting is that the polinomial will be the same size and that they'll be the same polinomial is is the the fact that they're the same basically the only information that's revealed is that kind of why it's um your knowledge yeah yeah um I mean that's what we we're more kind of checking that they're the same and if if they are the same then we're confirming that the computation was fil build in correctly um Z deog is mostly about

hardness and security right you said it's everywhere so it just kind of like guarantees a lot of these secure properties right right exactly exactly so in in Starks for example they don't use the dlog Assumption because they don't use elliptic curve cryptography but they have some other kind of security assumption so dlog is something that's often sort of forgotten about because it's just assumed to be true it's just a working condition but it is Central to to how these work um can't remember what a zero test is the the term really rings a bell um but yeah I can't fully remember that right now and then just before the halfway

point in fact it's probably further than halfway point and we have constraint count and I think I might have mentioned this along the way a of times but this is a topic of discussion because let's just Define it quickly that the constraint count is just the number of gates in your circuit so in in this little dummy circuit I drew here you know this is a useless Circuit of course real circuits will be a lot bigger but the constraint count is the number of gates in this case three in general it's probably in the millions and this is important because the larger the constraint count the longer it time the longer it takes to

make a proof so depending on your scenario if if you have some medical data at your hospital and you want it processed and to get it back and you want to make sure that it was processed correctly you're probably not in a in a rush you know it doesn't matter if it takes a while to process the data when you get it back as long as it's correct but if this might be a more user focused application and it's supposed to run on their phone phones and it's going to take 20 seconds or a minute or even 5 Seconds to make a proof kind of very bad you know UI really not ideal so we want to minimize constraint count as far as possible without compromising security so constraint count is is

pretty important constraint count like efficiency Pro time that's all like that's a big bottleneck right like a lot of the ZK engineers and research focusing on this and like new proof system are kind of focused on on this area also in some way right yeah yeah exactly I mean going back to this image again sometimes you might have a great value idea but it the circuit might just have a constraint count that's too high such that it makes it um not solvable with um at least like modern current snarks you if it's going to take billions of of of gates it's probably like completely possible I can't

remember what because the time limit doesn't grow linearly it's not like if the circuit is twice as big it takes twice as long the factor is a bit more than that because it well for most of them it's not linear it's it's super linear um n log n for for for elliptic curve cryptography generally the and then the last thing is that for a system like plon there is actually based on our setup there is a maximum circuit size if we want to go beyond that we've got to like reset it up again and it's just uh annoying um yeah so that's the kind of first half recap going over a bunch of that stuff and then the second half we're going to we're going to look over

the different proof systems just very briefly high level and and and talk about some of the differences should we take a break here K Chong or should we just kind of get through the rest um does anybody have any questions uh this is a beginner's course it's supposed to be an introduction so does anybody have like very basic questions like feel free to ask um here uh and we you know we have time later on too but I think we'll take some question then move on and if you need to take a break you can should we say at 50 Arrow like seven minutes yeah that sounds good

um3 this is the this is just a very short uh introductory course Jimmy um just like the the high level overview of everything so for more um Advanced material here the zerox parkour the best place to go next yeah we've got the there's links to the end of the the content um to a few places we tried not to over overload you with 30 links but there's a few there that that can be very helpful uh I don't think you need to

pause the recording I guess we can always just edit it out but uh there might even be questions that are useful to have in the recording yeah see the same thing um anybody in web 3 clubs have questions um it's okay to have it like a beginner question you can also raise your hand if you want to speak yeah in in terms of how we represent data in a in a circuit if you want

to hello you know how do we how do we get this into a circuit if this A and B and C A B and C are field elements so I'm answering the question how you get string into a circuit a field elements in you know some field F FP then yeah it's not clear how you get a a string in and it it takes more work you can't do this just in a single Gator or wire like if if you want to use asy for example um it was it like the American standard for communication information

whatever but it's a seven bit code that represents all the all the English language letters and uh you know full stop brackets things like that and some other other codes then if you want to do that is a seven bit code then what we want to do is we we want to make we'll call it either a subcircuit or a gadget it's kind of its own self-contained little circuit uh I'm just going to call it asky with a with a box and when we put in a it should basically output a it should output

a and it should also put out a oops all my stuff it should output one but only um output one only if a is less than what is between 0 and 2 to the 7 minus one because then that means it's kind of within our seven bit range but this is not a single gate

it takes a bit more work so you have to encode stuff and that has a bit of a cost uh when encoding a string and there's going to be a variety of ways to do this in more optimal ways there might be more advanced Gates that can kind of do it in one gate but then you've got to add additional component to your proof system so that part you know takes takes work uh so Whispering W when you're asking about bugs in the lowlevel proofs are you asking about bugs in the circuit creation or in the zerge proof scheme implementation uh the Z proof

implementation generally speaking these are wellmade because there's like a lot of contributors a lot of like good people who know what they're doing it's and they a lot of components are kind of the mathematical operations that have to be done basically proof systems are like kind of combining various mathematical operations in weirdly complex ways but the actual math that has to be done in each component is usually it's not easy but it's been done loads and loads before and it's well understood and it's implemented very well so you can kind of copy it over and then you've got to like make sure you integrate it well uh inte integrate together well so there's not often uh errors there because if there

is and you can you know sort of break it then like you really like it's it's hugely consequential because you can break everything um so there's a lot of work making sure that that there's no errors in the Imp ation um it kind also ch's question right about using different circuits you're using the same things again right yeah so the circuits can be reused as much as you want like once you write a circuit you know if this is the circuit that you made and you know this is a boring three gate circuit but it might be a circuit that is the transaction circuit for example once it's made you can reuse it and reuse it and reuse it as many times as you want

if you want to modify it then you know it'll take some work but you can reuse it if you're lucky you might even be able to reuse the circuit in a different proof system it depends on if the arithmetization between the different proof systems um meshes well together or if it's the same arithmetization okay we're at 102 so I think we can continue with the second half um I just put this slide here again so we can refer to it when we talk about

some of these other proof systems and we're going to go over these four grth 16 plun Halo 2 and Z STS this is just kind of a an overview of some of the different differences between them and we're going to investigate those one by one we'll start with goth 16 because it's sort of one of the earliest ones the 16 is because the paper came out in 2016 and yen grth is the person who wrote the paper so that's where it gets its its name from and the fact that it came out so long ago as far as zero knowledge goes means that it's been used a

lot so a lot of circuits have been coded with it for example Macy the the voting system at the p a project there and I think seore as well and a bunch of other places um have been used sorry have used Groth 16 so it's um and that that's not just because it it was one of the earliest ones that could be used there are some very good reasons to use Groth 16 most importantly is that it makes the smallest uh proofs if you want if proof size is the thing you want to optimized for most Gro 16 is is what you want to use so that's going to be important

if uh you know you got to store the proof online in like an expensive storage place um or you know tons of people want access to it or verify it you know then you might want to really optimize for this group size or if you're going to have loads of these maybe in a proof system it makes sense because sorry a voting system Ian depending on the scale you could have thousands if not millions of of these U of these proofs um one of the differences from plon is that it uses something called R1 CS arithmetization which is rank one constraint system and it you can't it's like tough it's a bit

harder to draw out what circuits look like um with R1 CS arithmetization this is one of the reasons chose PL CU you have these nice additional multiplication Gates but rank one constraint system it's not I wouldn't say it's like really hard to understand but it's just a kind of AIT a little bit Le less visual um one of the key drawbacks here is that if you remember what a trusted setup was is we briefly discussed it last session but some snarks you have to kind of prepare to make proof you got to do some setup in the beginning um in the case of Groth

16 you have to do this setup phase for every single circuit so once you make a transaction circuit you've got to do a setup and then once you've done that setup you can reuse that transaction circuit as many times as you want but if you want another circuit like a voting circuit or an evm you know block um the block verification circuit there's got to have there own their own separate uh trusted setups and as a reminder The Trusted setup if that's compromised that circuit is like unsafe to use I mean the the data from that trusted setup um but it it's the security is if if a 100 people take take

part you only need one person to be honest right yeah it's this toxic waste we call it um it people are supposed to kind of make this stuff together and then everybody deletes their share and if if a single person deletes their share they can't nobody can recover what was there but if everybody maintains their share and secretly talks to each other and then they put their shares together they can actually work out what the they can they know what the secret is and they can use it but these are done like online in a decentralized way so if you know if you or I just took part and we deleted it then suddenly it's it's safe and secure so there's some of the trade-offs of Groth 16 and

then we do plonk so of course a lot of most of what we've spoken about here is in reference to plon the arithmetization the addition multiplication is called plish arithmetization the polinomial commitment scheme uh the way I've been describing it is um yeah it's called kzg like named after the authors of that but it's a very straightforward commitment scheme where you just evaluate these polinomial the opening proof that I mentioned is a bit more complicated um but all that stuff related to that but plon doesn't have a trusted setup per circuit it has what we call a universal setup ceremony so that once we do the setup ceremony once you

can make any circuit you want in plon and uh do stuff with it there is one caveat that there is a Max size of the circuit if in The Trusted setup we we made a million values then the largest plunk circuit can have a million Gates if you want to go beyond that you can't take the previous million values and add 9 million or however many you want to add you've actually just got to redo the whole thing with a sufficient number um of values to be output and yeah like Aman is saying plon and clth 16 itself both use elliptic curve

cryptography so neither of them are are quantum secure or plausibly postquantum secure but because we have a universal setup as well and we we don't have to do it per circuit we can put a lot more effort into making this single trusted setup ceremony as good as possible you can run it over the course of a month or three months or however long and try and encourage as many people as possible to take part which is what you know many many people have done I think there's a actually a PSA project right called infinite powers of tow this trusted setup ceremony is sometimes called the

powers of tow ceremony because the values we make we call them they're sometimes called to and to squared and to cubed um is yeah the name give it to it and I think that's just one that's constantly updating to keep adding more security to it yeah that's right it is called Perpetual powers to Perpetual powers of right um and then we have Halo 2 so Halo 2 is what we call actually a recursive proof system I'm going to quickly sketch out what that means but let's touch on the other points first it uses the plish arithmetization so if you've written a a circuit and plon you can then kind of

just insert that circuit into Halo 2 and and already make use of it but the the things that are different in Halo 2 to to to plun is like committing to the polinomial and then how do we query them and then how do we verify uh in the polinomial scheme so a quick thing recursive proof means that we're not just proving our our current computation like if I'm the first person to make a proof I will make a proof of my computation and then when you Chong the second person he'll make his own proof of his computation but at the same time he will prove that mine is valid and instead of having two proofs

well we'll still have my proof but his proof will sort of contain my proof within it and in this way you can make a chain let's just quickly sketch that out so yeah you can make a proof of proofs basically exactly like C this is C1 computation and we get out Pi proof one and then we'll do computation two and we'll get out proof two Pi 2 and what happens is Halo 2 will actually just combine these into a single kind of Pi 1 1.2 now if we want to do a third

computation computation three we'll get out the the Third proof Pi 3 and then we can just put these two proofs together the same as we did before we can call this Pi 1.3 for proofs 1 to three and we can just keep adding in one at a time new computations to this because this this proof size like Pi 1: 3 it's not any bigger than the original computation sorry proof all three of these all these proofs are the same size so if we want to add if we want to do a fourth computation we can do that and get up

proof four and then we can just kind of squeeze it into here um squeeze them together get proof one one to five so now if we take this if we verify if we verify this it doesn't just verify C4 in a sense you know pi4 it also ver verifies computation three and computation two and computation one so this way we can this is why it's called like a recursive proof or incrementally verifiable computation bit by bit we're building up this whole chain and we can be sure of everything that came before uh you know a potential

application of this is if you can do this for for blockchain uh State verification then you can make a proof about the entire blockchain history or sorry Bitcoin history or or ethereum history and in a single proof uh be sure that everything you've received was valid without having to do all that computation yeah this is kind of what the zkm project is about basically turning everything all the transactions that happened in a block into a single proof which would be recursive so it would contain many other proofs but that single proof is all you need to verify everything that happened

in that block so it's very yeah practical application yeah it'll be like the current e State you sort of have and then you'll have um updates you know updates or transactions and you can kind of squeeze these in together to check that they were inserted correctly and that everything that came before was was valid as well um so folding is I can't remember if Halo 2 is Falls with specifically with in the

definition of folding but um Nova and many other proof systems do folding and this is I'm not I can't say for certain I can't remember right now whether payload 2 itself specifically is folding here but folding is this idea of taking two statements and make turn them into one statement but these two statements have to be kind of this the same thing they're both n sized NP statements and they're turned into two statements into one instance of the same statement um in in some sense what Halo 2 does is inof verification it does like the easy bit of proof verification and

with the hard bar the hard part it keeps adding the hard Parts together even though the the easy parts are done but in Nova the entire proof verification keeps getting folded together so I think Halo is not technically a folding scheme because it's kind of like a little bit off um in the online content we talk about cycles of elliptic curves and that's needed well that's what 2 uses to help make it possible but we thought might be more useful to focus on the idea of recursive computation in this online talk and then lastly we have uh Starks

Starks um so Starks satisfy all the properties of ZK snarks as well um but they they they specify and they call it a stark rather than a snark to add emphasis to the fact that there's no trusted setup ceremony there the the T it means transparent so what they're talking about there is that they don't need any setup ceremony so in this sense there's no Max um circuit size limit in the way there is when you have a trusted setup ceremony and it removes one of these kind of security assumptions most of us believe that the The Trusted setup ceremony itself is it's fully secure and you can you can

trust it if it's done in the right way it's good I mean I think one of the first TR trusted setup ceremonies I think for Zed cash which is one of like the OG privacy coins I believe there might have been kind of six people that took part in the trusted set setup ceremony at that level you know six people I would say that's that's not safe like it's not a good foundation you should have some concerns there but the modern ones will have hundreds or thousands of people uh taking part in a decentralized way there's no kind of keeping about who can take par and that's uh that set that uh yeah that design is is is much better yeah how much was the K how many people participate in that kzg ceremony the the ethereum one I think it's a few

hundred thousand oh is it wow I I mean I can't I don't remember it was it was one of it was a really big ceremony yeah when I was at Alo they they said they had a few thousand people take part in theirs which was was quite big at the time and also tornado cash I think also had a few thousand people take part in theirs um but you know again if if there's hundreds or thousands of people taking part you just need one person to be honest and not even necessarily honest but incompetent enough to to lose their share accidentally delete it or or whatever it's kind of very unlikely that hundreds of people would take part and not a

single one of them will remove that their part um in terms of the best St or most optimized one I I I I've worked with Starks less um but generally speaking proof the most optimized will depend on your scenario if you're trying to optimize for uh scaling or like what kind of computation you're going to be doing with it there'll be a few trade-offs to make and there isn't like one generic best um for overall although there'll be some decent choices but it it really is a context dependent um air stands for algebraic intermediate representation and you know similarly PL

uses addition multiplication Gates air has its own description the um that table yeah it might make more sense there is like the way basically Starks make ciruit it's all consideration right if you're G to choose Starks you gotta like want to use air or at least be willing to accept it I mean that's a really good point because if if you're a ZK engineer and you write circuits in plon which is what what I did um then the way You' write a circuit in in a star is is quite

different it it you if you want to represent the same computation in plon versus a stark it's done in very different ways and you can be amazing at doing it in plon but if you've not done it much in a stark then you you you might have a bit of a head star compared to others but you're essentially starting from scratch in terms of optimal ways to represent different types of computation does it when you use the different systems and uh arithmetization choices like the um how would you describe the difference is like when you switch from one to another is it like using a different kind of math yeah you're just comfortable in certain situations and less practic yeah exactly I mean I guess it's like using a

different programming language like the like the syntax is different for one and then the way the things you have to be careful of are quite different so like rust does a lot of checking formal verification and which can be annoying but it it also helps make programs that will always run and that will probably be faster it's a it's kind of annoying context switching it is sort of a different math that being said you know it's not like you know teaching French versus uh making food like there's still of course a lot of similarities but it um you if you're in the flow in one you constantly

translate into being in the Flow State for the other and I think there was one more thing to mention about stocks right so generally speaking if something is postquantum secure it's slower or its proof sizes will be larger this is kind of the core reason why we're not all just using postquantum secure systems there is a tradeoff um for being secure against quantum computers and that's that it's it's slower or uses more data so one particularly important thing there is that this applies a bit more to

encryption rather than snarks but if something is um not Quantum secure when it's encrypted then in 30 years time if quantum computers become a thing Whoever has access to that data can kind of unencrypt it or whether it's your secret key they can unencrypt it if if you've used your kind of secret key to encrypt a message they can un encrypt it in in 30 years time so that's a bit of a consideration with stocks many consumer applications if people are you know look at that data 30 years from now probably not going to matter but of course there are scenarios that that uh um you should be more

careful okay so that's essentially everything we wanted to go over now the things I would say to to think about and try and remember oh I didn't actually change these my bad the things I remember here maybe it didn't yeah so the things I remember here are the differences between the kind of different system this image is a great starting point of some of the the key differences and we've not even covered everything here we spoke about you know you've seen

plish arithmetization but you've not seen R1 CS or air arithmetization or what it actually looks like um first off knowing that those are things is good to know and then if it comes to it you might be able to explore what those are um the knowing the advantages of the different systems is quite helpful as well but in the core components like we didn't mention what a quadratic arithmetic program is um to be honest that's probably not going to be too relevant to to devs like something you really need to know about but uh in the bottom bottom right hash functions and Merkel trees those are things that you should really um know a bit about because those come up in various places like uh in in representing the state

we're going to use Merle trees and and hash functions together and then going back remembering this kind of image and all the detail there that's the core that I'd say that's the core to learn like the core kind of picture to memorize and then that gives us the proof systems um or was there anything that that you could think of that was kind of miss the main things that are missing from maybe that table about why you would choose each one because you've worked with a few of them um but I just kind of assume like the efficiency is a big one right um

arithmetization because that depends on the expert the your Stark your ZK engineer like what they're comfortable with um but I just wonder if there's kind of anything else like why you would choose different ones because I think I saw in the chat about um Beach system suits certain design desires from Whispering Woods so I just kind of wonder what kind of designs would be suitable for different things yeah yeah exactly I mean so the systems here they're quite sort of vanilla in terms of I'm saying they're quite basic but but plonk Halo 2 plony 2 plony 3 they give you a lot of variability in what gates are actually allowed it's not just additional

multiplication in in plon you can you can add in different types of gates if you do it might slow it down a bit but you can optimize your setup to be like we want these of gates and we probably don't need these so if we ever need to do them you can emulate them using the actual Gates um and that way you can specify the proof system to help you out out more so even within each system there's usually some some specifications that can be made but but in the Min Mac space the kind of key things are um the size of the the proof does does the size of the proof matter and do you want to trade off of that um does the Prov time matter and do you

want to try trade off for that does the verifier time matter because you could have like something that's a a slower approver but a faster verifier or a fast approver but a slower verifier there's all these kind of different tradeoffs and it's really system dependent on top of that you've got like e what reasons would you want a like a freed off like faster approver slower verifier and vice versa for that M I mean I guess for a faster approver if you want this to run on somebody's phone there's going to be much more limited comp computing power there particularly if it's like not just like you know modern iPhones and if it's older phones as well you might be willing to have a slower verifier there if you can have proofs be made a bit

more quickly on their own devices makes sense um all that being said as well the the Z space is still very and changing like a lot very quickly some of the things that came out recently there's Cluny 3 which actually I haven't had a time to really look at yet but I've heard people say that you know you got a lot of variability there and what it can do and it's like very optimal in a variety of other ways you've got um I think it's it SC1 I can't remember its specific name it my understanding is that you can actually just write your normal rust code and it will take your rust code and turn it into a circuit for you and remember I said that this

arithmetization is what we spend a lot of time our time on as Z circuit Engineers so in a way it's sort of taking away jobs but it's not exactly because you've still got to like make sure it it's functioning correctly and if it can translate generic rust code it's not going to be fully optimal and like you know for your specific use case and Company is it worthwhile to really do an as optimal circuit as possible and that's just like today you know those didn't exist a year ago and a year from now they'll be other things so it's very hard to to keep up with all of these so it's possible like in five years or so these systems were like some of these might not be used

anymore oh yeah yeah for for sure bit by bit they they'll be phas out like plunk itself I can't even remember if plon itself is really used in many places like it's a lot of the ideas they're embedded in other things in Halo 2 um but I'm not like aside from when a is like let's use this tool plon and then they build circuits in it and they start using it it's then very hard to change the wheels on the bus when it's going at 60 M hour so lots of them that already had them chosen will continue to use them and might do an update and change later to something uh faster but plunk itself as well keeps getting updated with new ways to to modify it that make the make it a bit faster in a variety of

ways um the the Russ circuit tool them I think is SC1 see okay it's from ah yeah I thought it was SC1 I'm trying to remember the name of the company as well I would recognize it but I can't say it right now I can I'll find that afterwards and and drop it in in the chat um going to some of the other questions so Spartan yeah Spartan's funny enough actually a like an older system came out a while ago but then they they kind of found SP one sorry

not yeah from uh s sync Labs is who it's from okay maybe I mean from that brief description there maybe I'm I'm I'm not saying what sp1 was correctly but maybe that it's in a more like a containered position um so Spartan came out a while ago but then I I I was going to I read lasso and then I was going to look at like the way they' modified Spartan but I think they made a bit of a change to Spartan and then used it in combination with lasso and and jolt to achieve what they're calling the proof Singularity um but ah I ask you after you finish yeah I

like each system takes a while let to even understand Spartan itself is probably at least a week's worth of time if not a month if it's your first time looking at it and then you've got all the other things that it's supposed to combine with so um it takes a lot of time to to go over each of them yeah part of why we wanted to do this was to give like one really generic overview and then as the different systems come out you could you could learn them also but it's all different details and components and stuff um but what I wanted to ask was how when you see something new how do you judge if it's like or it's like Pro actually promising because it just seems like there's so many things so like what

do you look for in like a potentially interesting system yeah I mean that's true I mean there's the initial kind of social construct thing of like who made it who's the company and what are other experts in the area saying about it and it's it's primarily a community effort like very few people have time each system is very complex and very few people have time to go and investigate whether all the claims are true and you might have some puristic to be able to guess as to whether something's actually possible or whether it it's just kind of marketing talk but you you primarily wait to hear from the experts who who have a bit of time to to check it out and then it even then it depends on on

its relevance like it it might not be a tool you could use anyway because of your spe ifications in which case it doesn't really matter that it exists even though it will make waves for for new uh projects so it's best just to trust the experts online who will go and post about it on Twitter their findings and their and their beliefs we should go over this last slide with the uh further exploration I just briefly talk through each of the links here these are in the online content uh I mean this is a Shameless plug but I wrote a kind of Halo 2 tutorial that's similar on gbur it it

shouldn't take too long to get through if you're interested in in Halo 2 en coding with it there's a star tutorial with um I think is it Alan shanc I can't pronounce his name correctly and that's sort of I think it was python coding but also looking at how Starks work so that's a bit of under thehood understanding of starks and figing out how to use them so that's also if you're interested in coding in Starks it could be a great place um ZK mesh is something I would extremely recommend it's a monthly newsletter um and it's got a bunch of research articles that were kind of popular in the past month so like research papers and then like more General articles and then videos so it's like separated by content type and you can just kind of look at the titles and

decide which ones are you think might be worthwhile to look at it's a really good way to keep up with the space um then bit more like detailed reading there's V Bin's blog posts are always great he has somewh the one that links here he's talking about Z KVM and kind of the design thinking there is more of a that one's more like thinking about how snarks can be used in in the blockchain space and then there's a plunk by hand which is really nice to understand the in the workings of plunk where it kind of sketches out um in these mini circuits I've been drawing with these kind of three gates it sort of takes one of those and actually makes the polinomial and shows you what happened

that's probably more like you know that might go deeper than most people want it's kind of understanding how to make a like code the proof system for example when you see the pl you can you can see how really complex it is in practice like when you go from the earth three gates to what they do in the plunk by hand it's like you have to have computers to do these things yeah yeah exactly but it's really nice to read yeah there's the psse Discord um yeah the PSC Discord there's tons of channels in there and plenty very very active people and it's all trying to be segmented for different projects and and

discussion topics so that's also of course very good then for a more advanced course there's zerox Park they have a lot of content out there and is very worthwhile to to look through yeah they have a lot of a lot of things you can get very Advanced starting Z Xbox yeah okay so I think that's all the kind of cool stuff we wanted to go over so well done for making it this far like these aren't straightforward topics and um to engag in conversations this is some of the most basic knowledge you you you should try and have but it never ends here as I'm sure you're fully aware and you've got to kind of keep going and going over this stuff and seeing it used

in different places seeing the different proof systems that are out out there seeing who's using them um seeing how they're all improving um it's kind of a never ending battle particularly when it's changes so quickly like really a year ago the space looked very different and yeah it's you can't keep up with it all you've got to be very selected with your time to decide what are you going to focus on like is it just you know do you want to spend a month trying to implement a circuits because that's going to help you become a bit more of a z engineer do you want to be a bit more of an entrepreneur but also have some Z expertise so you want to see how it's being used in different areas and how the different proof systems have trade-offs um do you want to be a

researcher and just kind of follow in a more specific area about how certain types of things are done uh do you be very uh conscious about how you commit your time um and maybe also tailor it to the kind of potential job you want to find yeah so thank you very much for here for being here yeah and yeah I just want to reiterate it depends on you know what you're looking for what you're trying to do so they're different paths to different things to understand thank you for um explaining all these things I mean it helps me a lot I definitely enjoy this whole process so

it's nice to just see where things fit together I think that that's very helpful to understand at least understand what you don't know which I I find to be one of the hardest things starting out yeah yeah I agree it's been extremely nice I mean Kong and I wrote all the content together like that wasn't me that was both of us together so um thank you to you as well massively that yeah been been extremely nice um also point out ch's post there as a a community chat tomorrow for for Macy Macy is the voting like the voting System project at uh at PSC it's something I'm I'm very interested in I'm quite into politics I think the having

an on a decentralized online safe secure voting system um is phenomenally an a phenomenally important tool so yeah I'm always like willing to shout out the Macy Macy project if you have any lingering questions yeah there's many projects different events in the PC Discord there's also a whole series a more advanced math series by Matan um that's also on the PSU too so there's there's many ways to get involved more yeah I mean I think the matan's um course I think even that's like at least 17 lectures if not more and even once you go through all of those you you you

know you'll have a pretty decent footing for all the maths involved but it just it never ends like you know you have researchers spending Decades of their lives and they understand tons of it very very deeply but there's still huge parts that they don't understand that well so it doesn't matter don't worry or feel bad if you don't understand that much of it yet like it really does take a while and nobody knows at all great um okay a project idea for getting hands ony um yeah I don't have any specific project ideas I mean maybe a good

idea I think you share with me there are a list of project ideas already right yeah there's like um bandada which is built on SEMA for they've got like projects yeah if you're interested in like working on something you could check out like kind of the psub and see what things are there um but yeah there's just tons of work on all different levels research levels efficiency circuit writing and then basically turning these things into user applications I mean yeah if you want to do something handson it doesn't really

matter matter what you do I assume the purpose is just to get more experience using it so all you really have to decide is that like I want to build this thing and it's best to keep that scope very limited just make it a very basic um object or function that you want to prove like it could be a Sudoku or something even simpler or or something that you're more interested in personally but you decide upon that and then you just stick with it and you follow it through until it's done because it's really the process there where you'll be learning things and if choosing the right circuit or thing to build is going to motivate you a lot better um that's you know kind of up to you to decide although of course looking online for for more recommendations can be helpful um but you know just choose

something really really basic and simple and try and build that because then that will be a really good starting point so that when you can go go beyond to have a discussion or have an interview that talks about it you'll have you'll be um you know have a lot to say all right I think we're going to close it there unless anybody has any more questions right thank you thanks erl thanks everybody for your attention and your precious time very appreciate it thank you K

Chong catch you all later