ZKStudyClub: Eclipse and Lunar with Matteo Campanelli

Transcript

so today for the zk study club we are here with matteo campanelli who's going to be presenting lunar and eclipse the commit and proof snarks with universal srss please take it away meteo and welcome hi everybody um i'm gonna tell you a little bit about two uh binary works uh they came one after the other although they were sort of concurrent in different ways and they had lots of cross-pollinations the topic is roughly starks with the focus on very very small proofs and universal srs if you know that means great otherwise i'm going to explain

that in a second and the focus is going to be on what we could call commit improvement so snarks were that deal efficiently with uh commitments as inputs this is a joint work with a bunch of people that are fiora antony fagno and ice karol uh from there and here come and a bunch of people from foster university digoranya university in concordia and i hope i'm not going to bore you too much if you know lots about this and if i say things that you know about the hope i'm not gonna

for you if those are not gonna confuse you feel free to jump in with any question in time i i think we can benefit from that that said yes quick recap but we're talking about just as a setup if i say zero knowledge proofs even in an interactive setting i'm talking about two parties approver and the verifier and we're getting is out of this protocol is that the verifier can be convinced after a run the approver knows some data some witness as we call it w such that a certain relation property rw so basically

one way to paraphrase this is you're trusting someone else's claims on the property about the property on some data you're not even seeing you haven't seen them you're not supposed to see them but you know that they know after that our setting is sort of a specialization of that what i mean by commit to improve here is you're trusting someone else's claims on data that you haven't seen but they can be pointed to what do we mean with this so think about the setting from before pmv interact why not but here we're gonna assume the p ahead of time maybe so we're just going to commit to the

data we're going to represent these commitments as an envelope and just going to put it on say a stool a table whatever like oh it's going to public publish it on a bulletin board or in uh commitment is again a um cryptographic primitive that allows us to enclose an object without revealing it so it hides usually the what the data are and it's binding you cannot there's no way you can open in two different ways right so p does that and then it can at the later time doesn't have to be right afterwards interacts with v and at that point v is convinced that

that envelope opens to some data such that a certain property holds so in what we're trying to say is that or the way i'm defining coming to brazilian knowledge is that we provide relation and we open the community at the same time which is it could be seen as a larger relation of course but we're gonna care about this setting for reasons i'll i'll say here why do we care about this then so often this is useful for compression and fingerprinting so imagine that the commitments commitments sometimes can compress a lot of the data and we can use this fact here's for example a toy example not so tall

imagine that the top three four or five hospitals in the united states or your favorite country are holding some sensitive database of uh health data of their patients and the government wants through uh some public money for example fund some machine learning been trained on this sensitive health databases so [Music] ask some researchers to train some models on these databases let's assume this is sort of semi-deterministic process whatever since it's public money maybe we want to prove to the public or to be able to

audit that these machine learning models have been trained correctly we could do that through zero knowledge because for example and commitment for zero knowledge proof as follows there's a public commitment to the data to the databases uh signed by the government the hospitals will not and and then whoever trained the model is able to provide a proof that zero knowledge proves the correct trend right another uh setting we could call it commit ahead of time which i'm gonna sort of exemplify in a specific way imagine that today i can publish on a bulletin board on the blockchain a sort of my credentials a commitment to

all that about me my credit history who i am when i was born a commitment signed by some authority of search cool i can uh keep living my life and then sometimes i'll need to prove something to my next employer i want to prove that a certain my my history data satisfy certain property and i can do the n0 knowledge using this commitment sort of as a placeholder i see there is a question chat but i cannot see it i can read it to you if you want okay thanks do we do we need cp if there is simple hash and sign

simple hashing sign uh you need you still need to hide that right hash and sign i'm not sure it tells me anything about the hiding thing so if you need zero knowledge if you need hash and sign just for compression yeah maybe you don't need your knowledge am i missing something well actually so gustavo asked that i don't know if gustav if you want to add more information yeah very very jumping the first example was interesting of sensitive data and then the machine learning models want to verify that that was the original data set uh why not just uh hash and sign that sensitive data oh it is

it's as you it's as you're saying so although it's uh i admit it could be slightly contrived given the how machine learning training occurs most times but what we're proving is not that the data are the original data that happens through a nation sign so you hashes you commit to them and then you sign that commitment basically it's a hashing sign what you're proving is whoever is training the model is proving to anybody else say to me and you and the public that the training happened correctly on those passion sign committed and signed data that makes sense

there was maybe there was like yeah that's helpful okay so in community ahead of time i have commitment to some data again and i can prove things later in time i don't know what i'm going to prove about this data i don't know what proof system i'm going to use it could happen in 30 years and so on so far my company could call me today to some data and 50 years from now i have to prove something to the government of the future and so on and so forth another example and i need to apologize because

i think this shot here and remove it another example is commit improve certain flavors of commitment can allow us to obtain modular or efficient composition improves here's an example uh let's assume we have a circuit which is sort of a heterogeneous that's one way to put this so it's made of a very algebraic part takes three hidden inputs three dumb weaknesses aw b and w shared right and let's assume it's made of two heterogeneous different parts a very algebraic one the one on top a very we

could call it boolean part an example of this is uh imagine you want to prove for public input y that you know x such that the hash of g to the x is equal to y now xiao may not cha itself may not be the best uh boolean flavored sort of it's not so algebraic flavor but it's more blend flavored than others but you can think of that as a some hash of sard and g2dx is a very algebraic flavored expression right so the example here what influence says imagine you have to process you have no proof system that specializes in both

your some proof systems that specializes in algebraic statements and some pro systems that specialize in other flavors which one do you use right you get this whole circuit um the end of these two things you need to compromise do i compromise sometimes it's both sure you now you are doubling the proof size but if you care about say proving time and you're saving significant factors then and that's a trade-off you can afford you should do that and then the intuition is that you take this intermediate state w or intermediate weakness you commit to it and then you do one proof with one specialized this red brick over here system

and one proof with the other and this together with the commitment is the proof to the whole relations any questions so far about this all right so pushing a little more still on talking about the background more concretely commit ahead of time allows you to do anonymous credentials if you're familiar with them basically what they said before and these have other applications for me to prevail appearing cryptocurrencies blockchains with privacy properties thing for example is probably cash where we're committing to

what's the commitment is a coin right or you're committed to the coin or the coins that commit the committee itself according to how you want to see it but you commit to something and then later you're proving you're spending spending it right and right this could also generalize to your personal deposition blockchains and anywhere you need data to the reference in it private manner we need their knowledge and succinctly so i don't want to to give you something as big as i want to have a fingerprint of sort so hope yeah hopefully that's i thought this was a question sorry hopefully that's

clear and this is sort of the general setting of commit improve but i haven't even started to get into uh what we're going to talk about which is commit improve snark so no interaction so far assume there's any type of uh proof and and i'm going to talk about certain trust model the universal srs setting universal structure reference string model so what we care about in these works is coming to bruce narcs so no commit improves zero knowledge in general but commit to improve systems with various very small proofs and an efficient verifier this is the seamless and interactive so this is just a string

we're giving around how do cp snarks different from snarks so in snarks you have you can model the property you're proving as a relation of sort here represent is this big block this is the circuit r it's going to take a public input x and a private input w as an example the x could be a message and w a signature and you can prove you know the signature and the syntax of the snark looks a little bit like this right uh forget about public parameters here and just keeping them but the proverb gives a proof the verifier takes it uses the public input on the algorithm verify and checks if it uploads one

in cp snark i'm sort of spelling out what the relation looks like right again what are you proving you're proving that there is there's an envelope the envelope here is this is a commitment there could be different envelopes right uh different coins different databases different commitments to databases different commitments to credentials and these are these c1cl you got all of them and your committee improve relations proven that um given in the public input x and this public input c1cl the

relation is satisfied so again i have you have these public commitments you as a verifier have them and the approver wants to prove to you that it knows a property for what's inside these and and the syntax is as representing the image accepted there's a type when the proof should also appear so on the right should be verify x c one c l and pi and below you can see we're doing the same thing there's a relation r and we're proving that x and w holds but also you have these commitments to portions to small parts of w this is very abstract but

one way to think about it is again you're proving a machine learning model on the training on machine learning mode on different databases they're all committed the commitments are public and these are the c1cl and the witness would be say the concatenation of these databases right and they appear in different places maybe the witness is something else as well so any question on this before i move on it doesn't look like it i think i think just so anyone who's just joined knows feel free to sort of jump in as

this is the study club it's quite casual and you're welcome to ask a question when you have one exam so if the setting is clear you could ask look the setting on the right is a special case of the setting on the left so way you're about to tell me why this work on cp snarks is interesting why wasn't this just nurse and the reason is that this ingredient extra ingredient we have the commitment right which could be say a person commitment normally it is something very altered with flavor it could also be a merkle tree we care about two properties often or that are handy that are useful that

it's nice to have that are important to have in certain settings and these properties are efficiency and interoperability and i'll say more about that so basically we and this is um a vision we push with for example in the lego snap paper with the dary flora and anis carol who i believe in the audience and also it's being standardized as a vision there's a working proof at the security standard working on this and basically you could always do this commitment opening in a circuit right you have a merkle tree which is your commitment in

just encode the opening there this is expensive that you are adding these extra constraints if you do if your commitment is a person commitment also you could do some tricks and i'm going to mention that and that will help you but in practice this is hard to do can you do better than that can you sort of specialize this extra part if you look at the uh bottom right picture these uh dashed orange lines right that sort of intuitively are trying to say oh yeah this commitment is open to this part of the w do you need to prove that explicitly in your circuit or not and

the answer is no you do something else and the other thing you care about is interoperability or commitments so maybe you have proof systems that has some type of commitment scheme [Music] uh for which is very friendly i'm gonna give an example in a second but can you how does it relate to other types of commitments let me clarify that i'm sorry so for example suppose you want to prove think of the committee of time setting today you want to commit to some data and five years from now you want to do proofs on that on those data and you

want to post this commitment on the blockchain today the timestamp is going to be done do you know what proof systems you're going to use in five years growth 16 was five years ago and it's uh what do you how do we know what proof systems we're going to use say it's going to be the most popular process in four years from now in 10 years from now and so on and so forth do you know what commitment you're going to do you already know the commitment you're going to use what possibly is going to happen is that you like to use a commitment that's going to stick around i'm not going to use a hash function say merkle 3 with ash function you don't know if it's going to survive scrutiny you're going to use something very

standard standard groups standard patterson maybe something some type of standard today so therefore you would like your proof system to be as compact this cp snarks thingy you would like it to be as compatible as possible with standard movements our focus is going to be on better same flavor thing thanks so there are some solutions like here i write unsatisfactory but there's a lot of qualifications are i mean they're unsatisfactory as general solutions solutions that can be applied in general so that are in general interoperable and efficient

so please take that with the low salt but exactly what they say you could put miracle trees or fetters and opening inside the circuit and then there you go like you can use standard commitments and so on and so forth but then that's expensive and i apologize for the handwriting but in something else you could do is some some very clever tricks for example you could use smart arithmetic and elliptic curves tied to your proof system think of what's being used in zcash for example use jab jab which is really really friendly to the ls12 381 and

it's going to give you some speedups there are other works that talk about uh curves that are so called start friendly cocoa as one a work i call her with my theater anderson paxel has a curve for the sub it's a curve embedded in the restrictor curve called jumper walking and this is going to give you more efficiency but still you are losing interoperability you're losing generality so you you may want to find solutions that are efficient in in general and interoperable in general

okay any questions on this that's it so this is why i'm going to push uh all i said so far he tried to do the following we care about proving stuff on commitments this is applications and we care about doing that designing protocols that work efficiently in a general manner okay it's fantastic to us special specialized approaches to this because there could be characters it could be limitations in okay narrow even

more the type of snarks we're going to talk about are snarks that try to have a slightly weaker truss model so if you're familiar with snarks you know that they need some type of reference string there must be a reference to it maybe the reference string is just random it's a uniform random string or just the parameters of a hash function you can see that way for if you're in the random oracle model but you need some type of reference and usually it's just a whole structure reference string which i'm going to talk about so we have the best trust model we can hope for in snark is called transparent model right which shows up in a bunch of works you

should also mention starks here it's got no trusted setup and so you can you can just use them right away without any authority computing this or you could have think of a system like growth 16 and others in the ballpark they have a so-called structure reference strength so you need in principle in authority that comes around samples a big secret it's sorry samples a secret then does a big computation on top of it and in publishes this very nice string the common reference string which is structured and everybody's going to use and now you need to be careful with a bunch of things you know you may want to

do an npc ceremony maybe or some other tricks and normally the key generation step is here is depend on the relation r so you take you give this authority the relation r and they're going to give you a structural reference strength which is dependent on that right it doesn't mean you cannot use it for other relations and why do what you could say is why don't you just give a very general relation like the universal so called the universal relation which is nothing to do with the universal i'm going to talk about later but so the relation that takes the nuclear circuit and basically computes any circuit on that well that's pretty expensive right you are having

asymptotically having a logarithmic uh additional factor here multiplicative so a model introduced in script 2018 is that of universal srs basically it looks like the one in the middle but the keygen step does not depend on the relation it just depends on the bound on the relations you're going to prove so basically you the there's still authority to examine this boundary that puts an srs a structure reference string and nothing now you can use it for

anything in what way you can specialize it for any relation and this specialization step is deterministic you don't need trust anymore so you do this step once and you can use for anything and this step does not incur that overhead i talked about this is the setting this is what it's underlying here because let's try some more this is the setting we're going to talk about here we're going to try and obtain commute to improve flavor snarks with the universal srs of a nice size and also i should say universal trust models are often paired with

another property update ability it just means i don't really need authority uh anybody can contribute to to dsrs to the randomness of the srs and if there's at least one part that's honest in this process we can trust the srs is done correct and this is this editing very more specifically we care about universality and to the pillar there's a chat question let's see if i can open it the sourcing plan necessarily interests us about running npc ceremony uh it's sort of uh so gustavo asks if if i interpret the question correctly

if when you talk about structure reference string i'm i always would need to talk about some trustee authority or mpc yes yes that's basically what we need in those settings it's sort of a shortcut name for that setting there are other intuitions in the name uh the fact that it's not random it's got some structures or retractor from which the structure comes from yes did the help yes thank you thanks cool

so after i don't know how many minutes of background i am able to give a flavor i give a little bit of taste of the results we have in lunar eclipse but they will need more background to understand them but i hope i'm not gonna lose you the scope on my presentation sort to give an introduction to the general techniques that are used here in our tweets so one way to look at the results in these papers from very very high altitude is we provide new ways to construct cp snarks with the universal inactive structure reference strength in a general manner there's some caveats to how generically but

it's arguable these are pretty general they can be applied to several proof systems before giving more details of pressing more background for that and this is going to bring me to a little bit of a digression that's important which is where do cp snarks or see business really come from right and you may have some opinions on the topic but really they come from none of the above places but they usually come from compilers on information theoretic objects and i'll tell you a little bit more what i mean here i hope you're not shocked by that but this is so these compilers on information theoretic objects uh is

a paradigm a part of the diagram by which we can construct snarks but it's also sort of really what naturally happens with natural where naturally snarks uh come from there are some theoretical results i'm not putting the exclusive references here we showed that if you have snarks you're basically obtaining information through the objects of the flavor i'm going to talk about so there is the statement this is where snarks come from is morally true in computational complexity theory if you wish so what do you mean with this uh usually snarks we do it's also private right what we do in practice

often implicitly or not is there's a nice information throughout the object i'll tell you more about that we use a nice crypto primitive or tool such as a commitment or a very uh dumb or simple proof system think polynomial commitments or vector commitments and then we put them together in an interesting way and obtain a cryptographic process such as a snark so our information theoretic object is something like a probabilistically checkable proof a pcp i'm going to give you some flavor of that later and it's an object here it's represented as a as a blueprint of sort there's a hologram holographic this word is going

to show up again of uh here the urban landscape of of an actual building for example but you need something to make it concrete this something is a cryptographic tool sorry the one on the left is a very lightweight object doesn't have any usually doesn't have any hardness assumptions it exists out there mathematically without any assumptions but then you need to move a little bit into the crypto world i want discrete log to be hard and so i can prove something and talking about things does this before enter i i'm going to try and clarify a little bit of this have i

lost many of you do you have any comments or questions i think we're doing okay i think if anyone has questions feel free to leave them in the chat or jump in so moving on let's look at an example of uh before i tell you about the type of information throughout the object we're going to talk about as a warm-up i'm going to talk about the classic information theory object here which is probabilistically checkable proofs if you heard about interactive oracle proofs iops are sort of a general and more general object than pcps pcps have a long history and basically

look like this i hope you've seen them before maybe it's a little hard if you've never seen them but their proof system but they're sort of abstract in the following way we have approver that has an input public input tax and a witness prio witness w and what it does it sort of pushes puts up in the sky a big string the pcp the probabilistically checkable proof which is a a proof that he knows the witness w but differently than the usual setting where we the very fire text in the proof reads it does some computation on it and checks if

everything goes if everything goes correctly here the verifier is just going to sample a few points of this pcp the pcp could be really large but the verifier just needs to sample a few points and okay i'm going to look at this point is that a point zero point randomly sampled usually or with some distribution and it's going to perform some tests on them and it's gonna accept or not what's the key intuition that the prover does not know the queries of the verifier it puts this thing in the sky it cannot change it it's there it's locked and then the verifier can ask very few

queries of course uh the obvious question is this is a nice obstruction but how do you ensure in practice that something is locked right something is there it's not gonna change and here we start entering a more concrete vision of that that's why this object is not very concrete but nice thing is that these objects do not come from cryptographic assumptions so how do we compile them so we have this object and we want to get to the setting on the right i have pcps on the left is information theoreted objects and i want to get to an argument system

i want to get to a succinct let's say for now interactive arguments right so just a proof to knowledge proof maybe where back the back and forth gives me a and convinces me and i'm going to use the classic compiler for this again i'm just warming up to what i'm going to tell you later about our work is through vector commitment you can think of vector commitments as miracle trees merkel trees are a vector and and the syntax here in this very ugly font is the following so you have a vector of objects you want vn and then the vector commitment again think of it as a miracle tree for example gives you a short

commitment of this root of the miracles we say and then there's an opening algorithm i can show by which i can show you that um i can open to subset j uh set subset of indices uh this vector this commitment and it provides your proof of open thinks of this as a bunch of paths in the miracle tree and an efficient verification algorithm takes them into the commitment the subset j the claimed vector j and again same type as before there should also be the proof of opening here actually in the last algorithm yeah so we can use this to compile

everything how do we do that if we have a pcp i think this is how we compile it i'm going to explain that in a second so the prover of the argument we're obtaining instead of pushing the pcp up in the sky say computes a vertical merkle root of it it does a vector commitment on it and it gives it to you so it gives you the root of this merkle tree which is a commitment to the big string if you know starks if you've seen iops this is a concept a type of compilation that technique that you've definitely seen

before and then we do the same thing as before the verifier now samples a bunch of queries but it gives them to the proverb and the prover answers with the same the pcp this big string and pcpq means just the q open the q points to keep projections of this pcp string plus a proofs of opening should be on the left pc pi open is vc.open of q and verify this two things checks the pcp thingy and use the proof of opening of the microtree's father he got this is kilian's compiler draculians from billy95

it's one of the first examples of this now this is a interactive argument how do you uh obtain a snark or snark out of this use filter mirror normally so you can compress all these steps so this is a general compiler that represents a pipeline i told you before this one well let's get back to our settings so cool this is a very interesting result and this basic technique based on numerical trees or vector commitments used in different places but we're going to use different specific elements here these three elements for us are going to be different what are they going to be

we're going to move from pcps to phps so php stands for polynomially holographic proofs and they're introducing lunar it really stands for polynomial graphic rfps but they really dare generalization they're they build on the work of algebraic holographic proofs president marilyn fractal idealized law degree protocols ildps in planck or polynomial ps in the compiler papers so if you know these given all these work phps are just a little

step that generalizes these approaches in in meaningful manners i'm not i'm not going to get into that in this to these presentations but sort of bring together unifies these approaches for example and they're going to be useful for us because there are now there are these uh abstract templates and they're our information theoretic object they're like pcps where in pcbs you have this big string but now they're going to be interactive there are iops if you're familiar with them so the verifier can send challenges and i'm going to give oracle access to things after a challenge there's going to be visual depiction of

this later and again these are oracles yes the responses of the prover are oracles but not to strings to polynomials we're going to exploit algebraic facts and polynomials and the queries that earlier were specific points of the vector now there are algebraic properties of these polynomials for example they uh i'm going to say the later but they are evaluations of the polynomials and random points degree checks and such now for compilation remember our wrench earlier was vector commitments now we're going to switch to polynomial so if you have this you can obtain

srs snarks so snarks with the universal srs that are efficient in practice and they have nice properties and what you get just to this is just a very partial and out of date um for example a sample of the type of snarks you get uh sonic marlin plonk didn't no 100 sure about sonic but definitely for marley and planck they you can straight forwardly yes also so you straightforwardly put them in this framework and this is just to give a flavor of the efficiency you get right these are snarks with universal srs

there are others of course here this list is focused on constant size proof size and other measures of efficiency those for starks so our focus here is on cp snarks uh can we have these nice general compilers to just tell you told you about for cp snacks [Music] i think you're doing good all right so we have general compilers for snarks we'd like to have general compiler for cp snarks

and efficient super snarks coming out of them with universal stress and lunar and eclipse introduced so this is all this long background to explain what the contribution here is now let's look a little bit more to what we do uh we propose new information to read objects in lunar we proposed a compiler in new information through the objects we obtain cp starts from this property and in eclipse we showed that polynomial holographic proofs with a certain we can call it decomposition property i'm going to give a rough

intuition but that later can be compiled it can be compiled uh in some manner with polynomial commitments the the interesting thing about you can ask how general is this so in general enough to obtain interest improve systems in eclipse we basically take variations of marlin plunk and sonic or rather the information theoretically equivalent to these systems in lunar we build on some of the modeling ideas to provide a family of phps with different tradeoffs and different

properties we showed you to compile them so the lunar compiler is a little bit more general but rely in they're very similar and all of these are similar to other compilers in literature but there are there's some tweaks here that i'm going to say later for example eclipse relies much on uh homomorphic properties or commitments that's a key point also really in lunar just to this is a caveat maybe there is a little bit there's an extra property we need from php's not gonna until later but arguably this property is basically your big i i cannot think of uh

proof system without the property and it's easy to to bring them to the property with certain tricks what i'm saying is lunar's compiler is fairly general also on the bottom of this slide you can see the qtc acronym we have for eclipse the intuition about that is that this is a commit improved snark right the commitment is a patterson and it's also a wink to luna cool so what do we get out of this remember we're trying to let's look at the asymptotics for a second for example how efficient are these things we have a relation that looks like the on the right

and our public inputs is x and l commitments okay and each of these commitments is committing to a portion of the witness which is say your size d so this is uh our notation and right so as far as we were aware general purpose proof systems with [Music] with this property so srs certain type of verification and proof side uh for example this ring table over here in

eclipse improvement eclipsing and lunar improvement they are uh for proof size and verification time you can see how while they have similar asymptotics in terms of proven time very close actually it is sort of a general thing because it depends on the sensation the proof size and verification time for a trade-off of sort so for example in lunar um in eclipse so from that eclipse you you have this logarithmic dependency on the the number of commitments in on the the size the what they're

committing to but you paying verification time so if you're committing too many things in this sorry if you're committing too many things sure this is inherent you need to read them but if you're committing two things that are big you're paying for it whereas this dependency for example doesn't occur in lunar but you have precise which is right now okay is this uh notation afraid of clear if you're in question just just ask so this is sort of a summary of the results and what i'm gonna do next is i'm going to give i'm going to get

back to the high level sorry the blueprint we talked about in case of phps we're going to open the box and i'm going to show in very abstract terms like a very high level how we tweak that and learn eclipse so we're going to see compilers from php's to stocks this is prior work and then the tweak to allow completion in the lunar compiler and the decomposition property we need the eclipse this is all going to be very very level and then a couple comments on these specific techniques maybe i'm going to go fast on all the

uh blueprint stuff and then maybe i'll so i can spend a little bit more time thickness remember pcps there was this here's an angle feature a php you might remember the ugly picture of the pcp which had disprover with the big string the verifier had the oracle access to the php you may remember tweaks pcps uh with uh two ways there's interaction so here you can see that the verifier can ask challenges that that's nice and after each challenge the the approver pushes something up in the sky pushes a p a polynomial p i yeah

so think of iops but with polynomials instead of strings and at the end the verifier uh this is the information through the object the verifier comes up with a bunch of queries queue but these queries and these queries are not these are not uh projections of a vector anymore these are algebraic questions the verifier is asking to these polynomials in the sky you can ask questions such as is the degree of p2 lower than this then do these polynomials satisfy this equation here isom q can include two random points and it can uh query the polynomials in the way say

in the example on the bottom right so some linear some combination is not the of the polynomial so you can ask equations of this sort so if you we need three things right to compile we need the information through the objects and the phps but we also need this ingredient this cryptographic primitive to obtain snarks on the right and what i'm about to describe is a non-compiler and this is polynomial commitments and what we care about is that your commitment to a certain degree the point on a certain degree the commitment is very small and it's sort of a proof system indeed this is not the language we use in lunar

we don't talk about polynomial commitment we talk about specialized food systems or snacks for only commitment to polynomial and this should allow you to prove evaluation of a committed polynomial uh give me a point and i'll tell you prove to you that the polynomial a list there degree and other properties of certain i'm going to introduce this this notation for polynomial commitments if you have a point on the pi i'm going to represent with the circle to point our commitment to it and this is in contrast to the square commitments from before the square commitments are the input to

my relation the input to the verifier that these commitments is these are part of the transcript these are part of the proof so we have a php right how do we compile it to um an interactive argument and then to snark we're going to do what we we're already doing we are going to do what we do with iops we're going to do pcps what i told you later with the merkle trees but in the different flavor so every time the verifier asks me a challenge as a proverb instead of putting something in the sky i commit to it and i give you the commitment to the polynomial and we do that again for all challenges that said and so that is them

until we have exhausted those rounds and finally we can say okay i'm going to ask you a query a bunch of queries and normally the verifier is oracle access to this right but now it doesn't so the approver says cool i'm gonna show you that these queries are satisfied and with respect to these commitments so we it gives an additional certificate early was approvable writing paths to the merkle tree and that's going to get this additional certificate and calling pi poly it's a proof of uh certain properties of the commitment an opening of polynomial commitments if you wish with queries q that's it and the verifier checks them

and so this is this gives you an interactive argument do you make a snark out of it you use fashion mirror for example but why let's get back to this right the the important point is we're getting we're talking about universal srs snarks how come the structure reference string is universal here what's the universe it was the srs ceresio in the first place it's actually it's the parameters of the polynomial so the setup of the snark is the parameters the polynomial commitments which just depend on the maximum degree of the polynomials

so and that's why it's it's universal it doesn't depend on specific relations the setup text input and bound on the size of the relation and there would be a degree the bound on the degree of the polynomials you're going to use later right so that's how you can use this blueprint to obtain users knocks this is uh her work how do we do the first tip snarks who is the same recipe for example remember we want to talk about commitments right and we are sort of we want to give commitments the

verifier can use to verify these things we are using commitments these circles over here in the transcript right why can't i use them these commitments are encoding the witness after all so they depend on something the um the witness in some way and this is a straw man i'm about to take in this life right just as the intuition could just reuse the ms commitments for the commitment thank you is the circle commitment as a squares so basically i prove something to you today about witness w and you give me this transcript this proof that depends on this sea ice right

this the circles yes can't i use them tomorrow in some way to to talk about the same witness again with different property well one there's a few problems with that one problem which i mentioned in this slide that's recently is in general this may break their knowledge and the intuition is that what you're doing with this pi polyq in the bottom right is you're proving certain things about what's in c1 what's in the circles but these commitments can for example sub keep being hiding keep uh the whole thing their knowledge only if you ask a certain amount of information

so you cannot query them again in general that's what i'm trying to say so we need to come up with something else i'm taking time again but we're sort of approaching up here and so there's um there's a little bit of uh something extra i need to do here and let let's think about the setting a little bit more first what's the syntax we want uh difference between the snark syntax specialized cp snap syntax is that we have this input commitments here i'm going to assume there's only one square and we know how to use the previous recipe

for the r part right a relation cpu relation is made of two parts into the opening and in the other the big block r the blueprint i just showed you can be used for the big blue for the big r part right that's what the compiler did gives me a snark for the relation so if i have an input x w and whatnot i use the snark part to prove something about x and w but i still need to prove something about the relation between w and this square thingy i need to prove that the square is open to w how do we do that we add an extra ingredient sorry for the handwriting again which is

sort of a linking proof pi length which depends on the squares and the circles basically links this input this long-term commitment you can think of it as this commitment that you made 30 years ago or last year on the blockchain or the coin or a stat like a state of blocking if you want to and you want to link it to the transcript to the commitments in the transcript give me a proof how they're looking to prove that what's in the square is connected to circles more specifically what does it mean in practice right so in lunar for example

uh basically we we need an extra property uh from the php which is we call streamline extractability you can think of it as a special extractability of sort it says that given the polynomials of the transcript you don't need any rewinding given the polynomials i just look at them and then over the witnesses and this is in practice this is true of many systems of all the ones you can think of because for example these polynomials encode say uh they if you have a witness the polynomials are use the witness uh components as coefficients or

they interpolate the witness interpolations so given this property what you do in pylink pylink is a specialized proof for the following first knowledge of this w such that uh the square thing opens to whatever fraction right portion of w this is what the important part in in each of these circles open to the point the right polynomial sort of polynomial commitment opening and that this extraction property satisfied by the pis committed nci in this service so

in so that's a lunar compiler an eclipse is similar but uses explicitly morphing properties so communicating needs this additional property so i'm not gonna discuss so much but basically said these polynomials you're getting the transcript can be composed in a nice way through addition all right so that's a very very high level view of these two compilers if you know how compilers for snarks work for starts based on holographic techniques you want to move them to the commit improve setting that sort of a template

of how you can do that for engine terminal i'm gonna say a few other things about linking the specific linking uh proof with lunar and the challenge is this uh so you have these long-term commitments right which are you can think of them as ksg polynomial commitments to the encoding of the weakness and and they appear and you're proving a certain property about them so for example you have if you commit into a database and the computation is some circuit that depends on some other

private witness of the database right now the with this the opening of this database could be anywhere in the witness you part of what you need to prove is that sort of some in some offset it's in some representation of the witness so given that you know that that is also encoded in the transcript commitments the several circles so basically this is not really informative really but you need to decompose these are all polynomials in different usually there are interpolation polynomials in different domains you decompose them appropriately is it's a is a pairing based linking

proof that uh since we do this for each of the committed inputs is of all that size each of these given a commitment square commitment ci um [Music] this linking proof is going to be a constant size by the l times this is where the asymptotics come from in eclipse we there's some similarities in the technique so overall be hard to summarize it here but there's an important there's a divergence in techniques at some point so first although i haven't said that explicitly the square commitments are different species here here we're talking just

the ci's square our normal person commitments and so given all these um dci hats over here in the equation they you can think of them as the square components and they have this sub witnesses w1 wl and what you basically do you give an additional commitment the squash system around and you give a sigma protocol like scheme to prove that this new commitment c on the left uh is basically it opens to a concatenation of these guys but then

this is since given the techniques this will be what's the asymptotic communication complexity of this it's ld because you have this w1wl and their each of size d and you have all of them but then you can use compressed signal and protocol tricks and get to logarithm which is what you you get to logarithmic size but there are some other approaches these are customers uh lunar is other things it's not only about commit to improve i'm just going to mention a couple things it also introduces this php's framework which generalizes previous approaches

it's been used in other systems to uh introduce a new constraint system you may know rank one constraint system and r1cs lite is a sort of simpler version it's got one less equation but it turns out this is this can be helpful to obtain more efficient stocks it's also sorry to be used and we offer concrete constructions uh which improved on the state of the art in several metrics although by now all i believe all of the metrics in which we improve though maybe there's a more fine-grained comparison one could they've been further improved by

basilisk this paper by calaraffos and the rancho topico they appear to crypto 21 and basically represents the state of our force knocks in the universal srs as far as as far as i'm aware okay so what did we see we saw how to build generic police we start with universal srs there's a couple difference between these two papers i told you about one is this is very modeling flavored proof systems and uses kcg as the proof systems uh is this commitment part of me where is the other eclipse this is peterson but offers community proof snarks for other proof systems besides besides

marlin flavored flank and sonic actually the techniques eclipse could be used on top of lunar as well and one could obtain something else okay and i'm just gonna close with some open questions so the table the first two rows of the table on the right represent what we obtain in these two systems right and if you look at the um verification can we put the verification time say among these two the past is lunars which is all well but that's inherent because your input is a commitment you cannot do better than if you read them but but can you improve say

improved size so can you obtain something which got got the best of both worlds so and even better can you get something which is not dependent on the number of commitments proof wise and probably this could be done and not in a trivial way of course you can always do that putting a proof system on top but can you use some do you have persistence that's friendly to the type of things we do and i believe there could be uh there are ready and there are existing techniques one could use that basically would uh use one level of specialized recursion in this the other open question is so can we

we have some which i gave you with some linking techniques linking meaning how do you go from input commitments to the transcript commitments right and other other techniques besides the one we use in these techniques we use can they be used for something else wherever we have polynomials in different population domains such and such yeah that's it thank you so much uh it actually ends the talk let me know if you have any questions cool thank you so much matteo oh i don't know if you can see me yeah i can see cool cool

okay a question related more to applications this is from gustavo where to get more info on proof correct training in machine learning preferably non-academic articles thank you for i come back come back to you i'm not an expert on the topic but i know some people who were work actively on that here at the olympia university for example if you you can write fantastic i'll take a look at that cool yeah and actually if you do share any of those links um maybe we can also share some of those in the youtube video in the show notes be underneath cool

and i think that wraps up the presentation so thanks again for coming on the zk study club session video stream and sharing this with all of us yeah from thanksgiving cheers all right so now we can just stop the video you can hit the stop button up at the top [Music] i think yours is still on