ZK Study Club: Part1 Polynomial Commitments with Justin Drakes

Transcript

I think we can now kick off there might be a few more people joining as we go but this is the study club the ZK study club this is sort of a thing we've been trying to do every month where we get together and talk about a topic or a paper and for this session we have Justin Drake who's actually going to talk about polynomial commitments and I think this is such a great foundational topic for us to actually cover in this format just so for anyone who's sort of joining for the first time we like the way that this is made and the sort of idea is that this is supposed to be a bit more of a like an intimate presentation not something like we're just watching Justin speak so if we have questions or

if there's anything that we want to say I think maybe Justin you give some moments for people to ask or you can also put like in the chat sometimes people will put questions in there if they're if they don't want to interrupt right at that moment but this should be pretty interactive so yeah I might have to turn off my camera because my connection is also good but I'm here and I'll jump in every once a while cool all right Justin you want to take it away cool so yeah I'm I'm going to talk about normal commitments and it's kind of a really exciting kind of topic in the context of Universal we have all

these since Universal constructions and like this this one of the United you know fiying concepts is polymorphic methods so just to give a little bit of historical perspective here so we've had the initial paper the Katzie and all from 2010 that defining formal commitments and gave an initial construction based on parents and then kind of in in the recent years we've had kind of other constructions that kind of gave different constructions for for polynomial commitments so we have the

the green one here and bullet proof and fry which as we'll see can be photo planning on putting your commitment schemes and then we also have kind of in the context of these Universal troop systems hyrax and and V SQL and so they fit in kind of the zio key part so as we'll see that there's this unifying framework which is made of two parts a cryptographic part with commitments and then information theoretic parts with with IO piece and so in blue we have the IOPS and in green we have the cryptography and then in in recent years yeah so you know over the

years we've had more and more kind of i/o keys and very very recently we have had this boom of IOPS and we kind of reached an all-time high in terms of you know citations for this initial paper that was in 2010 and I think you know we'll see more and more interest in this new construction of real commitment schemes and by the way I've shared the the slides in the telegram chats and all of these links are clickable if you want to go and learn more later okay so what is a primal commitment scheme I guess before defining that I want to define the concept of polynomial Oracle which

is kind of a an abstraction of a functionality and so basically what we have here is we have an approver who has a polynomial and this polynomial can be very very big and with lots of information to describe it for example the many very large degree with lots of coefficients and so what the the prover can do is he can encode is polynomial in in an Oracle and then the the verifier he doesn't really care about the details of the polynomial he only wants to make evaluation so he has the evaluation points and he can make queries to the Oracle and the Oracle will respond with

the evaluation here so this is kind of the functionality we have a an encoding a query and then a response and there's the same thing with polynomial commitments so but we use slightly different language so we have a polynomial F the approver will commit to the polynomial hence the attempt on your commitment and so this will be a binding curriculums and then the verifier can ask to open at a specific point and then the prover will prove to you cryptographically that the evaluation of the polynomial F at Z is indeed what the prover claims it to be so that's the basic definition if you really want to

kind of follow through kind of the nitty-gritty with all the fine details this is the full definition of a commitment schemes as as as appeared in Marlon and I must admit you know I don't follow all the details here so yeah I mean I think that's maybe even an opportunity for improvement for cryptographers and then to try and find better ways of expressing these concepts formally because it really is difficult for a non-conservative writer actually you understand you know all the subtleties expressed just a quick question is there any intended property of knowledge or lack thereof like the Krueger doesn't want to

reveal anything about the polynomial perhaps yes so there's this extra extra ability extract ability prophecy which is and that's basically like knowledge soundness basically the proven is to know the polynomial not only there's kind of another property which is usually discussed which is hiding also known as zero knowledge and here it's actually not super important I'd say in the context of this discussion and the reason is that you can kind of build in zero knowledge not at the at the

cryptographic layer but at the IOP layer and the information theory so you're going to add kind of blinding factors in the polynomials but it turns out that as far as I can tell all the known plenty more commitment schemes you can also have kind of blinding I mean hiding at the at the cryptographic layer as well if that's what you want I mean my philosophy I guess is to try and and keep the cryptography to a minimum and so you want to have very contained kind of there's very small but powerful black box and then all the interesting stuff kind of happens outside and so my personal kind of preference would be to

put blinding at the IOT layer but you can do either I guess and you can see here there's kind of a hiding definition which is this whole yeah huge hugely complicated thing that I don't understand okay with hiding for cos a commitment sis and actually very easy because the commitment is first opening proof and the commitment are both very small but for some of these larger polynomials such as those you get with with the groups of unknown order with better proofs and you

actually have a logarithmic number of elements say proving hiding at the IP layer is a bit nasty so improving I mean the the poly mode commitment failure is nasty because there's more sorry to hear that do you mean that it's more nasty at the polynomial commitment layer because you're saying that the proofs are larger said there's more absurd festive leakage of information I guess both so trying to sort of hide it and the IP layer would be sort of a bit confusing because where

you should put you're hiding blinding values is going to depend on your commitment scheme okay because the way interpreted plum for example the high hat is not a program o'clock okay right okay so there's more subtle them there's some IOPS which dark and friendly to blinding and then there's some maybe that I'm much more difficult you know it's not that it's like a polynomials reveals so little information that if you want to put the binding in that IP layer is quite easy to do but if you're trying to compare them with different types of polynomial commitments is sometimes more tricky okay I see okay so you're basically you're saying that the blinding at the

IOP layer is actually dependent on how you compile so which what animal commitment scheme you use yeah okay interesting okay so this is kind of the the big picture that I'm gonna try and describe so basically you have these these three three fields so you have computer science information theory and cryptography and they kind of license segregates it so where you start with is in the on the left side here with with your circuit and your witness so actually you know even to get to that point you you

you might have to do a lot of work so you might have a you know high level Python code which you will compile down to like a ramp program or a circuit and then you'll you'll translate it to our one CS and then you might do other things like translate into the QA keys and the blah blah but at the end of the day you have you have basically an encoding of your circuit and your witness which is going to be friendly to the middle bit the the information theory and what you want is kind of on the right side here to have a universal slot because that is creative out of this framework so what are the other components that go in the middle here so

we have this encoding of the circuit and the witness as polynomial oracles and here is basically you know the reason why we use Oracle's here is is to get succinctness right because we this is there's a huge amount of information encoded here in circuits and the witness and if we want submit succinctness you know we need to have some sort of tool to compress the information and this this is what it is yeah Pauline on Oracle and then the polynomial Oracle's kind of interact well with the whoops with an interactive Oracle proof so interactive Oracle proof is when you have the approval and the verifier and

they're talking to each other and the prover sends Oracle's and to verify the verify can query these Oracle's and then the verifier can also send challenges in the form of kind of random randomly sampled fuel elements or two to the prover so is this an interactive thing and out comes the snob but there's a few missing pieces here so you know in order to have the the the randomness [Music] you need a random Oracle and in order to actually kind of have a stock you need

you need to instantiate the Oracle so the Oracles are these kind of abstractions which don't really exist in your life and you want to instantiate them or might serialize them and so you're going to use a hash function to instantiate the random Oracle that's known as the fear shamya heuristic and here this is the important part you're going to have a polynomial commitment scheme that is going to instantiate the the polynomial Oracle's and yeah this is very clean boundaries which makes makes it much much easier to reason about so you know there's been this this flood of new constructions but actually once you conceptualize them and listen framework

it becomes much simpler and clearer does that make sense to everybody so you know within each each of these columns we kind of have various computation steps so I mentioned you know you might go from Python codes into a circuit to r1 CS etcetera to polynomials and then here you kind of have this cliff where you encode your information into Oracle's and and what you lose here this first cliff is a little bit of soundness but

so basically you go from having perfect soundness to statistical solvents and then here there's also a few compilers internal so you know you're gonna you know you might add your random Oracle to remove the verifier and I things like that and then when you want to go past this boundary you're gonna have another cliff basically where you instantiate your Oracle's and you're going to lose also a bit of soundness there so you're going to go from statistical soundness to computational science I guess one of the interesting things

here is that here when you go when you encode your circuit into polynomial Oracle's you because the circuit is fixed you can actually do this encoding ahead of time in a sort of offline phase and this allows you know this is actually kind of a requirement for six sickness of the verifier so that's and then the verifier has a very small encoding of the circuits and one of the terms used here for these pre postings proposed this thing is kind of holography so you basically take your circuit and

you encode it into a polynomial commitment okay so you know I mentioned that in order to have succinctness we need to kind of compress the circuit and the witness and you know it turns out that the modern framework uses polynomial of course but you might ask you know white polynomial Oracle's various other things you can try and do to compress and you know maybe the simplest thing you can do is you have a lot of objects you can kind of put them in a set and you can ask you know the verifier did what the queries at the

very part could make is you know set membership is this object part of that set and it turns out this this cryptographic relative called an accumulator which basically instantiate this kind of set Oracle and it's you know there's there's RSA accumulators there's mobile treat all sorts of things and so the thing is you know there's kind of a hierarchy of Oracle's that you can can choose from you know the the least powerful is going to be let's say this the set Oracle but you can try and get more powerful things so you can try and and use it better

Oracle which is another little element as opposed to being a kind of on all that set you can try and have a load that we test polynomial Oracle and you can also have in a product Oracle and basically as you go down this this hierarchy you gain in expressiveness so in from the point of view of the information theory DD IOT you can do more powerful stuff but that comes at a cost right because each of these Oracle's they need to be instantiated with a corresponding cryptographic primitive so for example

the the primitive corresponding to the vector or core is going to be a better commitment and you want to be in a position where you're happy with the costs associated with you go to graphic intensive and can the historically speaking we've kind of gone all the way down to the inner product so schemes like like graph 16 went all the way to the inner product and schemes like bulletproof on you know also also had this inner product argument and I would claim that like there's this this barrier of practicality between polynomial commitment schemes and inner

products where like the price that you have to pay to go from heat from here to here is just too high and you just don't wanna cross this barrier and specifically the price that you have to pay so for example in the case of pairing based arguments is that you have a trusted set up which is non universal so you can you kind of have to bake your inner product queries in the trusted set up you know which is it's very expensive in practice because because during all these trusted setups per circuit is very very expensive and so this is why we're kind of in kind of the modern locks we kind of dialing it down a little bit

we're having something a little less powerful and I which is the poly Malcolm and it turns out you know through through various recent discovery is like like sonic and plunk and Molly and that's actually polynomials are pretty damn powerful and you don't actually you don't actually need the expressiveness of the inner product to do schnapps does that make sense and you know the way the reason why I call it the hierarchy is because you know there's kind of four some constructions there's a natural way to amplify them from one to another so whoops so for example you can take a noisy accumulator and you can amplify it

and make it stronger to Norris a vector commitments and so that's what you know very big doin's and others have done for example and you can take a better commitment and then you can amplify that to a low degree test and this is basically what Frye has done right so I mean I'll go through the details of Frye but this is effective Rodong if you start with a vector commitment you can get a low degree test and then it turns out that all the constructions that we know of for plan your commitments can be also made into low degree tests or vice versa you can take the low degree test

and kind of amplify your commitment so you have this nice hierarchy and then it turns out that all the inner product arguments can also be for surprise polynomial commitments as schemes because basically the the query that you make is gonna be a very structured one where you you take the the the soup so if you want to evaluate X what you do is that you take the inner product with 1x x squared X cubed etc so does that make sense ah I'm really I personally really really liking the way you're laying a lot of

this out it's incredibly helpful okay yeah there's this tug of war you know you there's a trade-off and it turned out that the sweet spot in my opinion and you know we've nailed it is the the polynomial commitment and this is why this primitive is so important okay so this was kind of motivation and now I want to tell you a bit more about the actual constructions what did a fundamental commitment schemes actually looked like so we kind of have four different flavors and these four flavors kind of correspond to four different areas of cryptography and a

map so we have constructions that are based on on hash functions and that's fry so the setup is very easy you just pick a hash function and you know kind of common to all the the discussion here is implicitly we have a prime fee of the field over which the polynomial is defined so F F is going to be a field H is going to be a hash function and it turns out that very very often we want to do FFTs so what we're going to do is we're going to take a a subgroup of the field which is going to be the roots of unity so generally you want you feel to

have so-called hi to ethnicity which is which means that it has it has very you know large group like roots of unity so W will be the generator and I will be a primitive loose immunity in the field and this is your hash function so all of this is kind of transparent there's no chance that setup no nothing like that and this is what the commitment looks like so you're going you have your function f and basically you're going to evaluate it on some sort of evaluation domain and the evaluation domain is going to be you some sort of subgroup some some some

some some roots of unity and here D it's quite small but D is the the degree of the polynomial and what you're gonna do is you're gonna evaluate it on the domain which is greater than the degree of the polynomial so what you're doing is you're kind of adding a redundancy right this turns out it's called a reed reed-solomon code where you kind of can extend the you know you normally you know a polynomial is can be uniquely described by by evaluating at a deep point where d is its degree but here you're gonna be evaluated at more than the points K times D and K is going to be relatively small

you know like 8 or 16 okay and then you're gonna take the Merkel root of these elements so this is what you know the hash function comes in for for the commitments and you can see how how kind of basic queries can can be made here so you know the verifier might say okay give me the evaluation of F at this kind of root of unity which I choose of my choosing and then the prover will give you the evaluation and the corresponding so that was hash functions my slides are

all slowest for those okay the next construction is with pairings so you have you have a g1 and g2 these are your you have this Haring friendly setup and you have generators g1 little g1 generates a big g1 little g2 a generator of big G - and you have your pairing and what you also have is a secret like a field element which is secret and which is encoded in this so-called powers of tau so in our case it would be powers of

s and basically that allows you to construct this commitment here so the the specific powers is going to be s the powers of s times G 1 the the generator G 1 and so here basically what we're doing is that we're encoding kind of coefficient by coefficient using the powers of town okay and then we have a very recent construction which is based on unknown order groups so that's the the uuo here

um and here what you have is a group of a little order so something like an RSA group for which you don't know the factorization of the RSA modulus right so now I say modulus is the product of two large Prime's you can factor a factorization is hard and in order to know the order of the group because we need to factor to find the true factors so that's one example under an older group you have a generates a G in G and you have some some large integer which you know we'll talk about and then this is your commitment so it's actually you know some what's you know in the same

flavors here you kind of encoding the the coefficients and so it turns out that you know this this part here without the G it is like a huge integer so you take your polynomial and you're gonna encode it as an integer like a very very large integer and then groups of unknown order they kind of designed to commit to integers and the reason is that because you don't know the order of the group you kind of you can't reduce by the order of the group so you know you don't use kind of keeps wrapping around and you don't know where where you end and so it's it's very very

difficult for the prover to to cheat so this this basically groups of oh no no they are great to encode integers and so you need to be to do a little bit of work in order to properly encode your polynomial as an integer and then you have this final construction which is based on on discrete log groups by the way I should say that this is called docks and this is a recent work and also by been a bit bones and others and then you have the discrete the log and group construction where basically you have you have an elliptic curve and you kind of have a randomly chosen elements in mg

which are going to be some sort of a basis and they're going to be independent relative to discrete logs and you're basically going to take like the the linear combination there's a basically the point in the vector space generated by these these random elements and this is how you encode your polynomial and this is how basically bullet proofs work and so we have fry and a cat a dog and bullet proof I mean any questions so far so I'm just trying to give flavor yeah I have questions like in the unknown or the groups is Q secret no Q is public all right yeah

so I'm Q is going to be on the order of P to the power log D I believe and P is going to be basically the the prime the size of your field so f is a prime field P is the size of the field and basically the reason why you want Q to be you know large is so that the the encoding to an integer is kind of well-defined you can kind of uniquely decoded back to a polynomial and to avoid these these problems of overflow and basically you

want the individual coefficients here to be very well isolated so there's no pollution between them so if you want to work you to wrap around every time when you raise it to some power right okay so so you have this commitment right and it's an algebraic commitment like these last three here are very much algebraic and so you're gonna want to make use of the algebra right so you're going to do you know auditions and do multiplications on these things and when you do these algebraic operations you're going to basically

affect these discussions here so if you do an addition until you have two of these points is zero all the way up to ad and then be zero we're too busy and you take the sum of these two well now suddenly you can have a 0 B 0 plus B 0 and then all the way up to ad plus BD and in the world of coefficient or in the world of polynomials the coefficients can they kind of in local to every monomial right so if you add if you add you know something in X and something in x squared then you know they're never gonna kind of interfere

with each other but if you if let's say a zero is very very close to Q so zero is large and NB 0 is larged and then suddenly you're gonna have an overflow you have a 0 plus B 0 is greater than Q and so you're summing two constant terms but they're going to interfere they're gonna overflow into the X term yeah yeah qualify that Thanks yeah yeah so you have this these nice for Norfolk

properties here additively from Norfolk and also multiplicatively from effect so it's not a fully homomorphic but there's a caveat and the caveat is that these homomorphisms they only work if these coefficients are small and so a lot of the work and docks is just proving that these coefficients are small but I'll talk about that later okay so we have these four flavors now let's kind of look qualitatively like what what what what can we tell already just by looking at the setups so the nice thing about the hash function in the setup is that you have very very nice property you have it's transparent

the setup is six int meaning that the the information that the proven needs to have to generate the proof is tiny it's unbounded meaning that you can prove statements that are arbitrarily large you mean you can have a circuit with a billion gates trillion gates that doesn't matter there's no limit the setup is updatable in the sense you know you can just change the hash function if you design your the old hash function this is broken that's that's fine easy to do and it's also you know possibly post quantum so the hash function based on commitments at least

from the qualitative standpoint are very very attractive and then you have kind of almost the opposite which is the pairing group so pairing group they're not transparent you need to do a set up they're not succinctly in the sense that the bigger the plenum will come the bigger the polynomials you want to commit to the more information the proven is to have and it gets really really bulky like tens hundreds of gigabytes terabytes potentially of information so not successful is a downside also not unbounded so if you do a set up which is going to be your powers of tau set up our powers of s

your powers of s are only going to go up to seven sighs and so even though you're gonna have a universal scheme it's only gonna be universal up to a certain size and so that that's yet another downside of pairings and it's updatable but you know there's a lot of caveats here so one is that it you know it turns out that in the world of the you know there's lots of herring friendly you know groups there's you know bien to 5/4 yes 12 21 and people are looking into you know like recursion friendly stuff like you know M&T for 126 viewed as 12th grade 3 7 7 and so basically for every

one of these curves you have to do a different setup which is which is not fantastic and it's also not both quantum but you know as we'll see kind of the pairing groups from a quantitative state statement they're amazing and hash functions from a quantitative statement are kind of Menna so you know it's kind of a yin and Yan you know it's a trade-off space here so it kind of depends what you care about if you wouldn't care more about kind of pure is Ehrman's and I'm kind of a long-term thinking or do you care about like very very pragmatic I want to get

stuffed on you know today kind of attitude and then you kind of have RSA groups which was you know somewhat in between so not transparent like parent groups but they have kind of a few killer features relative to bang groups one is that their 16th so the the set up in an RSA group is one single RSA modulus and that's it's no did you know the modulus is going to be 3,000 bits or 2,000 bits so just a you know a few hundred bytes and that's that's all you need as improver in order to generate the proof so it's very handy very lightweight that you know in stock

comparison to parents the advantage is that it's it's unbounded so you know you really have universality you know you're not kind of constrained by the size of your of your powers of Tao you can you know you can have circuits which have a billion a trillion gates that's not a problem on the downside here is not updatable unlike I did the the the ceremony for before RSA moduli we don't know of any that's kind of a table so it's kind of a one-time thing and then you kind of need to trust this one-time setup without

kind of the niceness of continuous continuously updating but the cool thing here is that it's not like you know there's like ten different flavors or of RSA groups you know like the elliptic curves it's like this one type and so you know there's no bike shed in here there's no you know cleverness you just you just do this one set up wonderful um so they'll read the messages if there's some questions and it's also not no quantum and so and and in this this is the kind of another

group of unknown order so we know of two two types of groups of unknown we know the RSA groups and the class groups and from a qualitative qualitative standpoint class groups are significantly better than our secrets the reason is that they have this transparent set up and you know automatically that makes them updatable so you know basically the set up is just pick a large primer and you know just you can create a new group of unknown order just by you know sampling neutrons so that's that's that's very easy to generate these these class groups and actually Tia which is a blockchain

project that is looking to use class groups for DDF you know that's one of the reasons why I chose class group is because you can update them very often so if you're worried about the security of your classroom you know you're worried that an attacker given you some amount of time can find the order of your class group well if you update it fast enough and then you're making it harder for the for the adversary because if it takes and say a whole week to find the order when you update every 10 minutes then there's no way the attacker can can actually disrupt your system which is nice and also post quantum so it turns out that kind of burn as a general heuristic any group of unknown order is going is

not going to be post quantum and and the reason is is easy because Shor's algorithm is kind of designed to find orders of things and so you know this this little hope that we will find a group of known order which is post Crichton which is a bit sad and then we have the discrete log the final type of set up which you know is kind of a strange beast it's kind of yet at different points in the trade of space where it's transparent which is very nice unbounded updatable not post quantum but it has this kind of big

downside which is it's it's not succinctly the the amount of stuff that you need to prove the statements and grows with the size of your statements and it turns out there's an even bigger downside which is that the same thing happens for the verifier so the verifier is actually not six int it takes linear time to do to verify the dispersed any questions here on the qualitative and comparison with the setup for the discrete group not be succinct because it is transparent meaning you can get it

from a pseudo-random function doesn't change the verifying many oh yes yes so I guess it's a question yeah so what Mary is saying is that you can you know on-the-fly generate your setup because all you need is a random Oracle that will kind of hash to your discrete log group but it turns out that in practice I believe this is not what is done and the reason is that there's a cost associated with actually instantiating the random Oracle so you basically need to run all these hash functions and need to compute in real time so I think

what's done in practice is that you you know ahead of time you're going to pre compute everything and it's even possible that there's like no pre-computation goes beyond just computing really the the basis elements like I mean probably someone else in this room there's better than me but I mean maybe Zack might even know there's these fancy like multi exponentiation algorithms like do sub-linear do these require pre-computation well they're required to compete the the generators because I think in the discrete looks at

and you just so very large number generators you can place a point of reference you you can get some linear [Music] commitment schemes and there was cute log setting for both of their farm for the setup but sub Liddy here is just a lot of great because the complexity is the square root of you or like your commitment degree falling on the ring so it still is right so I think what Zach was saying is like basically two things number one

that if you want to use these fancy sub linear multi exponentiation alga rooms you need to pre-compute the bases and so this is kind of a nice justification for the fact that it's not success and then the other thing that just just to add just to add to that the number of bases you need will be equal to the square root of your like degree the thing you put it into so okay I guess it depends on what you mean by succinct is this kind of succinct but not like practically it's full it's the way okay interesting no it also say this okay and we're saying that kind of there's like different schemes that are also

based on discrete log would have a different trade of space so you might have square root verify a time but you might have your more more proof of timing yeah precisely you can okay it's very very far time that gives you okay okay so now I've kind of done with the qualitative we can look into the quantitative and here in for the hash function based schemes you know everything is kind of and especially matter is the kind of the proof size where you have this this square factor

log squared as opposed to just log and and the reason you have this log squared factor is because as we'll see you know it's it's is a recursive scheme with log and round and in each round you need to do these commitments which themselves will cost you know log a log factor so log times log log squared and what this means in practice is that you have relatively large proofs you know on the order of of hundred kilobytes or hundreds of kilobytes you know on you know between 100 and 200 or maybe between 50 and 100 for for forming the wall sockets in

verify time it doesn't look fantastic because you have this square here but actually the verifier is mostly just hash functions which are pretty fast and cheap so not to worry about very first time improve the time is okay I guess and then you have the parent group where here you know with like wow you know constant proof size constant vary for a time and an optimal proof of time for the plan you know commitment scheme but I must have a there's a little caveat here on the on the linear time here is that if you and we'll discuss this later if you if you start by encoding your

coefficients in like wrong space then even just to do the evaluation just that you need to do a Fourier transform and that's gonna cost you a log log factor so this this optimal performance is only if you started the the monomial basis yep and then you have the the groups of unknown order which are as pairings but kind of better than better than the hash function so you kind of lose this log square and you're

down to log which is kind of nicer so I think I hope I'm not too loud with the background here but I think this may be a little unfair to the hash functions okay because I'm one I think there's a sort of oranges to apples I may be wrong but I think if you look at bid operations then you're already measuring the hash functions and in bid operations here right because I think it's log squared because you do this like lagdi hashes and you're thinking of every hash is right I think that's what you're

you're doing yes and if you look at right it's oh one in the pairing group if we if we think of like the group operation is one which i think is natural to do for simplicity but but I think in this table it comes out unfair to the hash functions because I think in bid operations the the middle column is going to go up to over log D and the UO column is going to go up to log squared I should verify that but I I think that's what's gonna happen if you measure everybody in bit operations right because you need to you need to work with a group of size at least D so

every operation is gonna be like log D interesting right so I mean right this is kind of oranges to apples and this is why we have the Big O notation so kind of partly remove the constants like these are different operations and this is a paring operation and this is a bit operation yeah yeah yeah if if you if you say bit operations on the first and group operations on the second and third that's yeah that's fine I think right where we sometimes go around that technicality is explicitly including the security parameter in the Big O notation

which I'm never sure is the right thing to do because it can introduce the same confusions but it's an option but but I think for the O of one you would also need to include D you'd also need to think of D as a constant because when lambda is always going to be bigger than D oh okay yeah I guess and then the question if the hash function is still log squared D if you you assume lambda is a constant larger than the I'm not sure right yeah maybe it is because maybe it's actually log squared D times like log the

security parameter in the hash function right yes so you know the same comment can be said about the hash functions that as D becomes very very large you need to increase the size of your of the hash outputs to come and so I guess Mary's comment that you know you just assume the security parameter is greater than the degree and then you just put the security camera on the table yeah that's that's probably fair yeah for sure and I guess in the context of pairing groups in one way one reason why it's conceptually simpler do you think of them as constant is because you know we pick a pairing group which has

sufficient security for you know all circuits practically known to humankind and you know but you know technically you know if you want to consider kind of galactic circuits which are kind of greater than what humans can do then then this model this this model breaks down but in practice this is a reasonable simplification simplification I guess okay and then we have the the discrete lock groups which kind of instead of being very balanced like like the group of unknown order where it's kind of all orange you kind of have a more variance

so you have a better pruvit time but much worse verification time so you know there's there's no free lunch here in this in this trade-off space like this these are four very different constructions and and you know that's in a way it's good but in a way because you know you can just pick a construction which which fits fits your application but in a way it's kind of bad because I mean we need to keep in our minds the whole trade of space ends and make the right decision it would be much simpler if we just had one construction to rule them all and you know maybe we'll have one of these soon and you know one reason why i'm and you know cautiously

optimistic is because you know these these pointy more commitment schemes as a construction they were kind of an obscure thing but now like the center stage so more attention i think will be given to them okay so this more question i don't know if there's a clear answer either but so i freaked I asked moves it it's dark we're sessions with the kind of firm the checksum algorithm in that kind of the hyrax and the Libre schemes are kind of the intentional with polynomial commitments or they're comparable and if so then where would

where would it fit in this is different these comparisons I mean is that was that a clear question and then you want the group answer it and so one thing I would say about checksum is it is designed for boolean polynomials as opposed to how many meals over finite fields and therefore it has quite a different flavor to when we're trying to do things over finite fields

and different trade-offs for sure so it makes it quite hard to compare it directly and you will get a proof size which is logarithmic a verifier time which is logarithmic and a privat time which is I think D log D yeah thank you but you can't use it for the same kinds of functions yeah thanks I I want to make an informal argument why pairings will win because the picture I have in

my head is that in ten twenty years when if this stuff on the optimistic case becomes standard and in use everybody's using it you know you have in some engineer that doesn't know all these nuances were talking about and he's just gonna pick the most efficient thing he's not gonna pick something less efficient because of some nuance that is you know very removed from him and abstract so that that's why I think pairings will will win so the counter arguments that would be that in twenty years you know you'll be able to buy it or build a quantum computer or something that's maybe not large enough to bring crypto

but scary enough that cryptographers would frown upon you know people deploying crypto that is not post quantum oh yeah soma yeah my argument is assuming pairings and discrete log is not harshly broken yeah yeah I would agree with that then you know I mean there is one thing to be said about the hash functions which is interesting which is that basically the the main way where they inferior to the rest is that they have large proof sizes but it turns out that if you take a historical

perspective and you look at mega trends and computing bandwidth is it is cheap and is you know it keeps on getting cheaper and cheaper so you have this law called Nielsen's law which is kind of the equivalent of Moore's law for bandwidth and it says that every every year you have a 50% increase in in bandwidth and what we found is that the the equipment law for computation like for raw CPU horsepower just is known on exponential it's kind of oh it's a little bit tiny very very slow exponential something like 3% of the year so you know you're comparing 50%

increase every year to 3% increase every year and and you know like in in in 10 years time I made the calculation the 100 100 kilobytes will correspond roughly to to 2 kilobytes and so in 20 years time it will be even less you know like a hundred kilobytes will be nothing it will be you know the equivalent of you know maybe less than a hundred bytes and so you'll get all this all the benefits really because the only thing you have to pay for is data but data will be so insanely cheap in 20 years that that's also a definitely a way

forward well still there's a question if data on a distributed ledger will be insanely cheap I don't know if that will follow the the same law or if you're arguing that it will yeah so what we have seen is that it has been followed on the theorem at least and the reason is that if theorem was launched about five years ago and then in the next kind of hard walk which is happening in just a few days there is kind of a gasp and adjustment while we're making data cheaper and we're making it significantly cheaper we're making it I forget exactly but something like I know five times cheaper something about and

you know this this this multiple roughly corresponds to you know the five year time span that has happened between when it really launched and today and so it's possible that you know we will make more hard Fault in the future to lower the gas price or we'll have kind of dynamic pricing where the the the gas cost of data will kind of decay exponentially relative to the other opcodes in the FM virtual machine I'm inclined to say that's it it's short of analysis making progress it doesn't make sense to choose a winner because each of these settings I mean you've seen in every single slide they

have different trade-offs which means that different schemes would be suitable for different solutions so they're all good in their own setting the greens yep I mean you know for example if you look at discrete logs it doesn't look very attractive because you have this verifier blow-up in the whole point of sicknesses on blockchains is that you know the blockchain is very weak and it doesn't have much computational powers to verify these things but it turns out that bitcoin is actually do love the discrete log setting and the reason is that they already have the discrete log assumption within the cryptographic stack in the signatures in ECDSA

and they only care about proving very small statements you know things like arrange proofs I know to get confidential transactions and so if you have a tiny tiny tiny circuits then actually you know the discrete log setting is very attractive so yeah it's very much gonna depend on on your on your personal preferences and on your specific you know the size of your circuit and things like that but I mean the the nice thing is that in the IOT world there isn't so much bike shopping it's like I'd say it's it's much clearer how you can you know compare the IOPS so

you know you could say you know you know without any any question about any doubts you could say that the kind of for example plunk is just better than sonic as a stock and and you know no one will bike shut you on that but or argue with you but it's here there's there's a lot of personal opinion that comes into play at the idea cryptographic layer and you know and like cryptography right like philosophically it's it's you know it's it's faith it's like religion writing you have these assumptions no one knows where they're true just like no one knows whether God exists or not and and you kind of pick your religion and yeah that's kind of a similar

similar thing so I realized that we already know past the hour and I've I don't think I've even gone through one feather of my slides holy oh wow okay well then I guess that sort of leaves us to this part of the thing which is we decide well do you want to do another one I mean I'd be more than happy to continue as people that participate this has been fantastic and I would gladly join another session I really appreciate her ontology it's helpful someone who is not sound how far

with all the intricacies of all the papers it's helpful to see it laid out like this next second that yeah I would feel less guilty about slowing you down if you had another session to do more slides something be up for we can talk we could talk about this on an idiom you don't have to do it I've done all the work to prepare the slides that was the hot dog the presentation is easier that would make sense for us yeah I mean here's a very good point to break actually because I've kind of given the motivation and I've given the the

high-level comparison and then from the next slide onwards I actually dig deep in the actual specifics of the constructions so here would be a good place to bake