zkStudyClub: *BONUS * Halo optimisations and constructing graphs of elliptic curves by Daira Hopwood

Transcript

this is the bonus Zeke a study club we weren't able to finish off Dara's presentation last week and so we decided to do this the original presentation is called halo optimization and constructing graphs of elliptic curves and Dara where are we maybe you can give a little bit of a recap and help us get oriented so we basically did the constructing graphs of elliptic curves bit and we still have the halo optimizations but to do I should have switched around that I don't really okay do I need stop absolutely okay so the story so far is that we defined what

graphs of elliptic curves are basically you have a bunch of Prime's that give the fields of definition of your curves and you you defined the elliptic curves as edges between those Prime's we explained why it's it can be difficult to construct and that cycles of curves and there's a category of um cows called complex multiplication curves that solve this problem so we defined that and we talked a little bit about but Issa's of

endomorphism rings but all we're going to take from that part really is the idea of an end morphism amp which is it gives you a shortcut to scalar multiplication on the curve and then we talked a little bit about constructing graphs that include pairing friendly curves and it's some live coding for that okay and I think that's that's a summary of what we did last time so now we're going to jump straight into accumulation schemes so a

recent paper on this that came out after the halo paper it's this PCMs 2020 and it basically formalizes and the idea behind halo it's actually a slightly simpler version of what we do in halo so the basic idea is you have a proven system that part of what you need to do to to verify proofs is quite expensive so you don't want to have to do that every time you're iterating the

recursive proof system so what you do instead is you have a way to combine this expensive part of the verification so that you only need to do that once at the end so your circuit here is verifying a previous proof and it's also combining and this accumulator with the accumulator generated by this by this verification so that's the idea but there's a complication

so you're proving system can only efficiently do arithmetic in one field so and that's not the same field as the field of definition of the elliptic curve so if you try to implement it exactly as shown in the diagram then you'd have to do lots of wrong field arithmetic and that will be very expensive so what we do instead is something like this so the purple colored things are one of the fields in your cycle and the orange cord things of the other field and the this convention

is actually taken from Isaac meddlers presentation on on the pickles proving system and these are nicely contrasting colors I hope if the if there are any colorblind people here purple things on the left and orange on the right and then we have the arrows here kind of fq flavored proofs so the proofs that are easy to verify when you can do arithmetic in fq and here this is a proof that's easy to verify if you can

do arithmetic in FP so you basically just alternate between to proving systems one defined on FP and they were defined on FQ so I know I just want a sort of complain that would frustrated me about well maybe to a degree halo but also the this PCMs paper that I I like it very much is that they didn't do this sort of extra step of yeah exactly like this this diagram because really this is nothing this is precisely why I'm doing it now yeah they're saying we're formalizing halo but to really do that

you need to do this yeah moving between two accumulation schemes so you proof at the end you end up with two instances of the accumulation scheme that you need to track and one proof which is dependent on on where you are with your odd and number of steps or an even number of steps and this is just the case for incrementally variable computation IVC where you have just a chain of proofs that you want to verify the more general thing is called PCD your proof carrying

data where you have a directed acyclic graph of things you want to prove so so as part of the problem but it turns out there's there's a complication still because your proofs are actually not just in one field so your proof consists of some values in one field and some values in the other field so these are what we call deferreds

so instead of sending them to the other proof system we defer them until the next step in the same field and then similarly here so they they basically bypass the next step and they can get checked in the south after so that way we only ever have to do arithmetic in the right field not the wrong field and then at the end you end up with so to deferreds one in each field that you also have to check in addition to the final proof and the

final accumulators okay so that's basically it for the the incremental computation case you just have a train let's see how it goes for when you have a general directed acyclic graph so that the arrows here means that this node on the middle left is dependent on the proofs on the top left here and top middle here and similarly and so on and you see this there's one proof here that is used in two places so what happens

when we we have to basically assign these two one proof system or the other so to FFP RFQ so if we do that find that we have two add another so dummy-proof here which is just wrapping this orange one and then we have the proofs alternate along every path okay so everything is still efficient and in in this particular example we only needed to add one proof to do that general we might have to add any number so that diagram didn't show the the

deferreds but you can see that these if they skip one proof and go on to the next one so here and so on it's that cool yeah so I just I want to try to get also the basic case like sort of clear ah yeah my head like say you're using the buddha lloyd proof you know polynomial commitment scheme so you have right if i i never remember this but you have like in the verification you have like the linear number of field operations and a linear number of group

operations or is that is that true or surfa the-- to decide the accumulation scheme only takes a linear number of group operations you know there's no field operations oh for the commitment scheme you're saying there's it's only group operations so let's go back to here okay yeah the this decider here and here is only doing a multi X basically a multi scalar multiplication okay see and but so the polynomials I'm

admits can it only has like some multi X but there's also these operations of the verifier that are just in the field that are just checking some some equation i yeah so these are in the second so we have raising you have two things to check we have two deferred from the previous instance on we have the proof from from the other side breathing system and I forget which of these field operations in which are group operations realist we have to ask about okay you you you have some field

operations and some group operations but that the field operations are directly in FP and the group operations are in the elliptic curve over FP so both of them more efficient yeah I will try to just remember if like if the field operations you also have to accumulate or is so this includes there's a verification operation that you need to do on the accumulator so so the amounts of the operation are the the two things that you want to accumulate and you have to verify it and the output is the

accumulator going into the next and proof darah are you going to show us at some point more explicitly what exactly are each of these arrows here like the deferred and the accumulate I'm not because I think that was in Shaun's presentation so if you if you go back to the at the YouTube video for that guy remember how much detail he went into but but if I were to explain that I basically just be pointing you to figure 1 as the halo paper okay thanks okay

right so okay we this is where we were up to just adding in the defense of the graph so this is one way of doing it you just add and dummy proof only way you need to and the other way of doing it would be this so you add a rapper proof after each node so that's more regular which might be useful for some protocols if say you didn't know the the structure of the directed acyclic graph in advance might be easier to do this so this looks kind of complicated when you add in the

deferreds but it's not that bad really you just so each proof has it has the the proof itself it has a list of deferreds in each field so the one that was the ones that were added in the immediately preceding step and the ones that were added in the step before that you see what it's not clear you so so here for example if you just take a slice through through any of these

hours then you would have at this proof you would have to punish two-thirds one purple deferred and you would have this proof and then you would have the accumulators okay that's a good place does anyone have any questions because I can't see the chat no chat so far I don't think okay cool so the other thing we need to know if we're going to optimize this is to what

restaurant ization what circuit model hello uses so it's exactly the same model as Sonic so I assume that people are reasonably familiar with our wants yes in I once yes you have these constraints were any of a B or C is a linear combination of variables and in Sonic or halo you have to split those out so we have each multiplicative constraint introduces three fresh

variables and then separately we have linear constraints which can refer to these variables that were we're introduced in the multiplicative constraints G you can't directly for example say a times a equals a which would be a boolean constraint on a you would need two extra linear constraints so we would have a 1 times a 2 equals a 3 and then a 2 minus a 1 equals 0 and a 3 minus a 1 equals 0 and that would be your boolean constraint

but in practice it's pretty easy to translate between us and our wants yes so you don't really have to worry very much about needing different optimizations for for the Sonicare specialization as you would for I once yes it's all the same ideas and I think for some pathological circuits you you might end up having to add dummy multiplicative constraints just to introduced variables so if you finding you need to do that then just try and reduce the number of them and you can

usually get away with the same number of multiplications as in I once yes okay so the hello verification circuit consists of these are the two operations that dominate the performance so we need multi scalar multiplications and we need to implement Fiat Fiat summer because halo is it uses the time paradigm we start with a interactive proof system and we instantiate the verify we replace the verify with a hash function okay and

then so as well as verifying the apparent proof as it were we also need to verify some application circuit so we need to have not over optimize for these two operations we need the second model to be flexible enough to to do other things that people might want to do but as it turns out people very often want to do elliptic curve arithmetic or hash functions anyway so it's not too much of a problem in practice okay so how do we do scalar multiplication so using

primordial virus curves of this form so is that the obvious way to do scalar multiplication for a variable base I'm just using double and add it would take four multiplications for the doubling three to add the base point P and then two because you need to compute either to a or to a plus P so you basically you

conditionally switch on the x-coordinate and then separately for the y-coordinate it's like cost of two constraints so that would cost us four plus three plus two is nine constraints up a bit so this ticket describes how to do it in six multiplications per bit it's based on this paper so the idea is so you just rearrange this to a plus P plus a and then so that gives you two improvements so the first of all you can compute so so I'm

assuming here that people basically know how to do elliptic curve addition on short phosphorus curves is that a reasonable assumption you I can go through people are not familiar with them okay I'm going to assume that people are basically good yeah you you compute the Accord between the two points and then it's obvious from that so you can save needing the cord between these points P

and a because you can compute it from so between the points a plus P and a because you can compute that from the cords that you and you had for a plus P so that saves you one multiplication and then here you can save another notification because instead of doing a conditional here and you just add plus P or minus P and you can compute at this plus or minus P in one constraint because you only have to

negate the conditionally negate the y-coordinate and then so it turns out that you can adjust the scalar so that adding plus or minus P you can use that to construct an algorithm that that works like the one atom so you end up with six constraints for it here so this cost the conditional negation cost one this cost three and then two for this addition because you didn't need to

compute the lamda separately okay so we can do even better than that you can do it in 3.5 sultans for a bit instead of six hang on my my fern is beefing at me I just need to nope nothing important so what we're going to do is process two bits at a time and processing two bits is going to take seven multiplications so we end up

with an average of 3.5 so the idea is to use these endomorphisms on the curve so this Phi function is the end of autism and this is easy to compute because it sounds like you just need to multiply the x coordinate by a constant so it's very easy so you can compute one of these four are used to one of these four points dependence on P in just two constraints so all you do is take two random bits and use those to decide which of these four points you're going

to add so that's what we're doing here one computing Si and then use the same trick as in the previous slide to add one of these four points and so you end up multiplying by a scalar that is dependent in some way on all of your random bits so it turns out that we we don't need to pick the scaler that we're going to

multiply by directly from the outputs of the hash we can just pick the random bits and they're multiplied by a scalar that's dependent on those random bits and as long as that doesn't lose any entropy and then we're fine so we need 128 bits of entropy in the add the scalar that we're multiplying by so so you're looking I mean in a like a Paterson hash context I can understand that you just want to not lose entropy but like in a snart verification context

I mean aren't really giving like a scalar a and you need to multiply exactly by a it turns out no so that if you look at the proof in the appendix of the paper nothing actually depends on choosing a specific scalar so it it doesn't need to be full length it just needs to be sufficiently unpredictable so that's why we only need 128 bits of entropy and that gives you roughly 128 bits security level

I'm a little hazy legged well yes I'm mixing things up but like aren't the scalars like in when you have like the commitment scheme aren't they like powers of some some X some random acts or something or maybe you're talking about the Scylla 70 yes I'm talking about so I'm assuming right this this is for like we're doing Halo so the main thing you need to do is like this scalar multiplication for the approve that the opening of the polynomial is is correct yes so

yeah I sort of hazily removed so I thought there like that the scaler is not completely to your choice so you're picking these these random bits according to fish on the it's just a way of picking fear Charlie challenges it turns out that we need the challenges to be squares but that's fine because what we can do is compute the scaler that we multiplied by this buying this algorithm and check that it's the square and if it isn't

then we just rewind the randomness and try the proof again you okay so what do we need in order for this to be correct we need to prove that this the mapping from the random bits to the effective scalar it doesn't lose any entropy so an easy way to prove that is to show this one-to-one and then it it loses no entropy at all so the first part of we split that into two parts we

show that the map from the random bits to these a and B values is 1 to 1 and then the map from that from that to the effective scalar is 1 to 1 so for the first part of that it's proven in the paper but it turns out that you can you can simplify the problem by just looking at the the first element of these sequences that vary so will you to prove that this is injective you have these

you split your random bits into the ones that are that are affecting a and the ones that are affecting B and then so it's the function is injective when it gives different outputs for different inputs so consider the first element of CD and differs and then you can show that these sums different modulo 4 and using that argument you can show that it's

sufficient to consider these two cases so K equals 1 when the the sequences of length once you only have 2 bits and K equals 2 so when you only have 4 bits okay Aira um sorry I'm just getting a little lost here what is the problem that you're guarding against the the problem is that you could have collisions in this function so he had collisions than you would have less entropy in the scalar than in the original input bits you'd have to increase the number of bits in order to keep it equally secure

oh this is for Fears Shamir in order for theorem here to be secure yeah exactly ok ok thank you ok thanks for that ok so basically this function from the the two cases that we need to track here and basically it these lattices if you remember in the first part we said that the generalized scalars that were multiplying by and can be considered as elements of a lattice so this direction

so from the origin along these red dots corresponds to applying the endomorphism and then this from the origin to the right corresponds to just ordinary multiplication so what the fact that all of these colored dots are distinct is just saying that this property here holds and then so for the second part where we're going from this pair of values into the effective scalar we so we use this argument we know that each of a and

B is in this fixed range and so let's just consider this Z to a town what we're trying to do is proving that the minimum distance between any two values of any two distinct values of Zeta a for a in this range so the minimum distance is greater than another copy of the range so that means that when you add Z to a and B the range for B will fit

between the gaps and not possible by the use of Zita a does that make sense wait so I'm trying to so you're saying a for it to be injective a is in this range yep so so little a is in this range is also in this range Oh if the yeah surf the minimum distance between any two distinct values of Z to a is greater than this value then it must be interactive because we we can

basically what we'll have is say that this is one possible value of z2 a then we'll just have a you so let me do explain this diagram this red line here is 0 and then we have positive values to the right and negative values mod Q to the left so our Q is something like suit of 250 something so if I show this video

basically what it's doing is plotting all the possible values of Z to a because it turns out that the the neck the next value of the minimum distance will always come near the origin so if we if we just shows okay so these green lines here are the search space for the next the next minimum distance so we're zooming in on the next element of the

search space you can see that these values here is living in oh it's really the minimum distance between the bimah distance between two values of Zeta a for a in this range okay oh and you're saying if those are larger than like it's larger than another copy of the range then we're fine because it must be you want to well maybe twice the range no just just

one copy of the range so astray it turns out that we we computed this and it turned out to be 2 to the 185 or so just just less than two hundred to two hundred ninety-five so this is obviously much greater than two to the 65 plus two to the 64 so I fine boys so I'm just trying to do the proof in my head so assume for contradiction that there's a collision so right so zetta a plus B equals a prime plus B Prime yep or some a be a prime B Prime and then you you move everything to one side or you move

the dizzay to say to one side so you get Zeta a minus a prime equals B prime minus B wait so so you have it seems like what would you need so you see one that it can't be that Zeta like a - a prime equals B minus B Prime so so what do you have on the right hand side is like it's not just an element of the set it's like a difference so the difference can be no maybe twice as large as no because let me just ask you

and that this is a single sided range so so say for example that our two values of c2a were this one and this one okay the two red lines here and then the possible values of M G so a plus B then it's a band which starts at each of these red lines and stretches to the right by two

sixty five plus two sixty four so provided that this distance is greater than that then the bands won't coincide so sorry wait again the sorry could you repeat that mantra got it okay so so imagine that each of these lines we draw each of those lines is like an element Zeta a yeah and each of these lines is a is a Zeta a and then we can add to that

any value B in this range Rane so provided the distance between the lines is greater than the size of the range and it's one-to-one no I think that it showed that shows that like Xena a plus B can't equals a 2 a prime but it doesn't show I think that a plus B can't equal say to a prime plus B Prime I may be getting this wrong but if it I think maybe you need you need to like needs to be larger than twice the range

maybe another way to say it is that like you put a little ball around each of these lines of radius 2 to the 65 plus 2 to the 64 and those balls don't intersect so any B you add I'm saying this line either Bo they need to be the distance you'd be twice that's right you've got your Zeta and Zeta a prime yeah you want to see that they don't they don't touch but the thing is right the Zeta a can have a B that helps him like go but also that the Zeta Zeta a prime can maybe have a B prime that helps him go into your other direction no because this this range here is from

zero symmetric range it's okay in Sarah all right sorry I think yeah I think that's why that's what I yeah if it was magic range sudden you'll be right I guess the question if they're okay and I guess you're saying also there's no wraparound right because the Zeta is about 128 right so I think also there's no wraparound every that's what this that's what we computed here we computed the minimum distance taking into account record I think right there's no there's no great because the Zeta is like about well I guess it depends on the curve but I think right the Zeta is about 2 to the

128th at least no no that that's what makes this problem difficult the Zeta so you can construct and curves in which later is around and 228 but the the tweedle curves found on that so because they didn't know how to at the time so yeah Zeta will be 2 2 it will be greater than 2 to the 250 so that's what makes this problem complicated okay you're seeing a tweedle curves azita is almost if Zeta was less than 228 then it will be trivial

oh sure maybe it's better to work with Zeta because right you have Zeta and Zeta and Zeta squared no I mean like if I'm so we did also we don't actually so we don't use the endomorphism squared we just use it once because if if you look at the algorithm here we're only applying Zeta to the base point we're not applying it to the accumulator at any point oh yeah I'm saying anything not to use both of them but right you could just could you maybe use a two squared instead of zinc like supposing square is like that happens to be nicer in the sense that it's closer to 2 to

the 128th oh yeah yes you can only yep you absolutely can and in fact so remember when we were constructing this week the the inverted lollipops it turns out that when you're constructing those you can arrange for the and C two values to be half length so he wanted to do it that way you could that's not the way we did it there's also potentially the option to

use six values here instead of four so that would be minus P P you know minus five P 5 P minus five squared of P Phi squared yeah so yes that could work but it makes this computation the minimum distance even more complicated so I didn't do that and it only actually saves you a fraction of a multiplication per bit so I'm not sure that's really worth of complexity okay so that that's the multiplicative scale

and multiplication optimization there's actually another one that we didn't use in the prototype implementation and didn't include in the paper which is that so when you're doing a multi scalar multiplication you can share the doublings so what you would do in that case is you can get it down to 2.5 multiplications a bit so for this you have to assume that you don't hit any exceptional cases and the addition but

what you would do is add together all of the base points that you want to add at each step so suppose that you have base points P and Q you would calculate one of these four points for P and then another one of the four points for Q and you would add those together and then you would do that for whatever the width of your multi scalar multiplication is

and then only at the end you would do this you do the doubling effectively and I think that costs 2.5 multiplications for bit because it's effectively five multiplications to add and each of these modified base points so you need one two for the conditional negation one for the conditional endomorphism and then three to add the point so that's five face but then you have to divide it by

two because you're processing two bits at the same time so it comes out it's a 2.5 for a large number of faces but you end up having to use the discrete log relation sumption to to say that you never end up adding two points in and getting the zero point or adding two points with the same X coordinate okay so let's go on first of all are there

any questions about the scalar multiplication part so so sorry it started repeating myself a little but just to understand so this is scalar multiplication Oh like only in the future um your context like it's not yeah you can't really use this for general well you could use some of the oxidization so I describe for general multiplication but this particular one you can only use if you're multiplying by a random scalar right but this one this one here that that gives you six

months for scale a bit you can use that fat new scale right but the the endomorphism yeah it makes it you can't it's only from you yeah so so if you use the half length let's see you might be able to do something more efficient if you relying on the half length Zita I'm really psyched about that very much okay and then let's go on to a fear show me so you have this protocol between this interactive protocol between

approver and a verifier they both know the instance so verifier sends a random challenge see mom improver sends part of the proof and verify sent another Challenger and so on and then at the end the verifier can decide whether the proof is valid or not so we want to make this into a non interactive protocol there's a perfectly standard transformation here but in this case what we're going to do is use a duplex sponge for the hash function so

that's a particular hash construction that depends on a permutation so we we choose a permutation that is efficient on our field and we split the state of the hash function into two parts so the idea is that this part on the right here will be hidden from attacker so if this is one field element field element is going to be about 256 bits at least so we end up with 128 bit security because

there are square root attacks on us so notice here that we will only need to do one to compute one permutation per challenge so if we did this differently if we explicitly hashed all of the previous transcript so the things that have been sent in the interactive protocol across the transcript so we could hash all of the previous transcript and then have use

another iteration to get the challenge and they're just expunged we'd combine this into one permutation it's that clear so the this constriction is ideal for coming because it's almost optimal see you couldn't get away with doing less than 1/2 cryptographic permutation per challenge and the idea here is that the approver can't cheat by modifying it's what it outputs because that will unpredictably

modify the verifiers next challenge ok so I feel I'm missing something here so you're saying like what is the board sort of straightforward thing so that the most straightforward thing would be to you have some general hash function color H and you have a state so you hash the state to get at the next state but then you have to

produce an output from the challenge so you would have hash of state comma input and then not I guess if you thought then it would it would be similar to this one oh so you're saying so here instead of hashing the challenge and I your your story soaring them yes so this this hidden part of the state here sorry I mean the

this I could never gets to influence us directly yeah I'm trying to understand more the left part so there's this see soar high and then you feed that into yeah into the person to to a permutation so that's what you mean sorry you mean the store is like a permutation so this is depending on the fact that the tour is that it's not actually it's or its addition but this

just needs to be to be one-to-one in the sense that any possible pi-1 gives you a different input to the permutation this this F is not a compressing hash it's a oh I see the fascination I see but you're saying but but it's okay that sorry different pairs like seep I will I'm just thinking of this plus is a

bitwise XOR so so different pairs yeah that's it was originally so so for duplex fundraiser was originally defined as a at soar in the paper but it just needs to be group operation basically but so right so different pairs cc1 PI once a will give the same input into F that's right but the at the point where c1 has already been chosen each so c1 is considered to be fixed then each different PI one will produce a

different input to F and therefore a different c2 right so an attacker can't manipulate pi-1 and keep so what you're trying to protect against is that the attacker knows c2 and is able to to choose c1 to make it work to make the proof work well the attacker right I mean can't it seems like he can they can say there's a c2 they they like so they can for any see what oh okay

I was gonna say for any see one they can choose a pie one that will give see to but so so the difficulties they have so they can't influence this so this behaves basically like a random permutation and therefore so so given C 1 yes they can pick a ac2 and then run the permutation backwards oh I think I think

miss I can't actually because they don't know what this would be sorry I think I'm missing part of the context so you're saying because I'm thinking of approver just making a non-interactive proof so the prover puts everything into the the hash but you're saying somehow this is a setting where the prover had doesn't have control about on this right part like he doesn't know the right part about well he does know it but the it's a difficult problem if you're only given C 2 and this value here then you can't from that compute what PI 1 would be you

can if you know the output of this so this arrow here then you could run F backwards and compute PI 1 if you're only given this input and and this then you can't do that anyway so that there's a proof in the duplex punch paper that basically says that this is a secure hash oh it was confused if this is a observing that it is exactly the

abstraction that you need for Fiamma okay so if that was confusing so we can apply some optimizations here so if we were actually using XOR for this operation then we would have to decompose the inputs into bit and that's expensive in the circuit but we actually only need it to be a group operation so it's we use addition modulo the the field size and that works fine and all of the proofs for this duplex punch so I'll go through the other thing

we can do is we can compress the inputs so it's sufficient to have a compression function that works in almost all cases so let's say that we're trying to input two curve points which in fact is exactly the case that we need inhaler so the the obvious way to do it is using uncompressed points so that would be for field elements and or we could use compress points but then the compression

requires decomposing our our coordinates into bits so that's expensive but we can compress to care points into three field elements probabilistically under it's just like this so we take the x-coordinates and then we add the y-coordinates it turns out that that's sufficient to determine the input and therefore it's it's a secure compression in this context so we do have to track that these

inequalities hold but we can check these very efficiently in the circuit and then if they don't hold them we could try again with different randomness but the probably that probability is like it's negligible anyway we don't actually use this in the prototype implementation but it's described in the the accompanying notes which I posted to the telegram funnel ok so the other thing that we can do is so that the size of this element of the

sponge state is called the rate so that's the size of input that we can take in for one computation of F and it's also the size of output that we can produce for one computation of F so we just choose the rates to be as small as we can so that we have one F evaluation her round of the interactive protocol I'm as shown in the title okay and in in practice that will be log n rounds for

where n is the size of our circuit basically and then so to do this efficiently we want to choose an F that's that we can compute in the circuit and we use rescue which is one of the recently developed circuit efficient ashes so we also consider Poseidon but there's a paper that it doesn't break for Sidon but it suggests that security margin is a little bit less the designers outperform so I think

if you compute if you adjust the number of rounds for Poseidon so that it looks equally secure to rescue it turns out the rescue is a little bit more efficient and it's also more efficient to compute rescue outside a circuit because it she is the true now it's Poseidon that's more efficient to compute outside of a second of mind but you're mainly interested in the in-circuit cost how to second cost so rescue has a parameter which is the

this S box function so we need to choose that we choose the curves so that that will be a permutation we can't choose the minimum value of this this exponent which will be three because that conflicts with I'm using endomorphism and it gives us more advantage to use the atom office and then to choose exponent three here okay so that's basically it any questions about that part of it the algebraic hashes

you so that was the end of talk thank you thanks Tara you're welcome Arielle we're about to ask something that the the questions don't have to be restricted to the second half of the talk if you if you want to ask any questions about the first half that you didn't think of good last time then that's fine

at the risk of go ahead area yeah you go ahead okay at the risk of belaboring this Viet Zamir question I think you mentioned that you save like roughly a factor of two and the hashes there but I'm a little confused by that because like in just plain vanilla Fiat Jimmy are you only doing one hash for a proven message so where's the savings come from so it's it's the fact that you would have to so if you that the inefficiency comes from the hush mode so typically to producer a

collision resistant a shot or actually a hash that can be used as a random Oracle you would need to compute the permutation twice or your compression function twice for each instance of the hash factory of two comes from okay thanks maybe it yet another follow-up question why is it important that F be a permutation I for that you will need to look at the duplex punch paper okay yeah maybe we should plop that into the show

notes or something yeah I'm sure someone that can look it up and just put it in the chat now okay I'm done thanks okay so I add to miss the end of last time the so right now what the thing you're constructing is you have some curve and like two curves below it or something like what is the current like instantiation you're focusing on because it has carrying is it like what's have a specific slide that I'm trying to

get back okay this is it so where we hello can just use a a very simple cycle of not pairing and Leake has a two cycle so this this first part of the talk it about half of it was about how to construct two cycles in general and then I went on to her so how can how to construct graphs they include pairing friendly curves the latter isn't strictly needed for halo but suppose

that you wanted to have a proof system with shorter proofs or to make the final proof easier to verify in that case if if you're prepared to make the the trusted setup trade off then you could use say 1/2 pairing cycle and what that allows you to do is you take the the halo proof and then you verify it in say I got 16 circuit or a blank circuit and

then you that ends up with a shark so you can still if you want to do the conservative verification of the original Halo proof but you also have the option of verifying the they've got 16 or blank proof but to make that work efficiently you need the so there are two ways of doing you can use the half pairing cycle so for the main recursion you just wouldn't use the fact that this is a a pairing friendly curve you don't

use it at the end to get the shark or you could use this inverted lollipop thing and then use this pairing friendly curve to to get the final proof but if if you want a shark then you can't use the pairing dependent and proof system in the recursion itself because that depends on a trusted setup which is what you want to avoid for a shark you you want to be able to to take proofs say that the pairing friendly proof system

was broken you want to be able to take your proofs and then regenerate the pairing friendly part of it to accelerate them the verification again are you are you do you have a favorite or one that you're focusing on in terms of the shark versus invaded for most of what we're doing it doesn't matter so most of the research we're doing is how to optimize the verification circuit and

how to optimize the the discrete log proof system and that doesn't depend on what which of these 3 cycle instructions use the trade-off basically is in curve size so if you use this non pairing friendly cycle then you can use 256 bit curves for each of thank you he is the half pairing cycle then they have to be around version 84 bits or 400

bits depending on who you ask and I mean some people say 460 bits so obviously hyper so you know I think the number field sieve I know maybe some people still say 256 yeah I think the community has settled on the idea that 206 bits with embedding degree 12 probably isn't conservative enough for the long term but yeah and then so for this symbol

we pop and this R and Q can be 256 bits again and then P depending on what care family this poem friendly curve is in P can be I say 384 bits of used BLS 12 or it can be 320 240 bits of use SSAT whereas for this were both cares in the cycle of pairing friendly you would need

about seven hundred sixty eight bits so that was the original MNT for I'm auntie sick cycle yeah I mean in terms of right the advantage of the inverted lollipop is I mean the disadvantage is the trusted set up well maybe the the size but great I mean though so if you're using it in a shark then maybe you don't mind as much about the trusted set up because if you so so you can easily prove so you have an invalid proof for the pairing friendly

system you can prove that it's invalid so let's say you were using this in a block for an application so on the train you would have the discrete log based proof and also so shortcuts to verify the the pairing based proof so if you ever get a case where the at the pairing brace proof validates and the discrete log proof doesn't then you know that the pairing based proof system is broken

so at that point you can either stop the train if you have enough control over the blockchain to to do that and restart it with a fixed proof system or you can fall back to just verifying the discrete log base proof you and you can potentially the latter automatically although there might be denial of service issues with doing that if you are relying on the fact that the opponent based proofs are simply a less expensive to profile yeah we did this a little bit happen how many

people when were worried switched to these universal obtainable setups I mean who someone or how many people are really disturbed anymore by by the setup I think maybe more than you think because I mean we don't just have to convince our own community of cryptographers we have to convince the general public and there's always going to be some degree of doubt in proof systems that rely on trusted setup I

think I mean it it depends on your philosophy in your politics but I know that at least some of the louder critics of C cache make a big deal about the fact that he uses a I trusted setup yeah but that was before like if he would describe to them the process of the universal universal dateable setup how many of them would give the same criticism it's not some one-time thing between a small bug I mean it's kind of moot if you can make the discrete log

setup if you can make the discrete log proof system efficient enough then you don't need the setup you know I'm thinking you know it's not it's not just the setup itself that can potentially be compromised it's the fact that you're using more complex and cryptography because you you have to you you not only have to be to trust the experts you have to convince and the general public who's using your protocol that this complex moon mass is something

that they should be relying on but that's gonna be challenging you know pairing or not barring I mean that's a better scenario so if you're trying to convince a Bitcoin people they seem to be perfectly okay with poly proofs of Manero people to me I mean performance is gonna is gonna win them so I mean we're looking at the earth bearing because at least 1/2 we can we can do grow cysteine so that's the idea in the gaming performance will be if you can

make the verification circuit cheap enough then the fact that you have a linear time decider is not really that much of a big deal if you can make it less than a second say right especially if you're you have a protocol that relies on because if proof state so that you're actually having to verify fewer proofs you don't have to verify a proof spend or pair output you might only have to verify one proof for the whole block channel for one block because obviously

yeah you have to to redo that verification of preaching your blocks that comes in mm-hmm yeah that's be like the challenge core daisen time to swab the answer to reduce that but we're catching up only takes one verification I mean my perspective on that is eventually the person who you need to convince is some is you know the engineer non crypto expert ten years from now who needs to implement the system okay so they would prefer not they would prefer not to have to implement pairings because not

implementing something is always you know they're gonna have a library cassia's they're gonna have the library of these systems and [Music] sorry Carl and and they're gonna be you know like us they're gonna be rate optimization annex so even if you get the DL systems too you know for X Factor preparing systems then they're you know they're gonna be from their perspective you know they're not going to think trusted set up philosophical issues they're saying okay this if you just download this file which is the universal dales if they do we'll set up writing speaking we'll just be like if you just download this file you get this

4x speed up that that's what's gonna be in the read and write but you're really much more than 4x it's poor except a very optimist I I don't I don't agree because you have smaller codes with the DL only system I mean if if if you were right about and you could convince the rest of the cryptographic community that it's okay to use 256 bit pairing from the curves and then yeah those would definitely be more efficient but as it is say use 384-bit pairing friendly curves then that's

going to cost at least double on your calves orthotic maybe three times more you're saying that when just from you when using 381 bit for the pairing yeah all of your arithmetic be all systems are as well this will be more efficient than the herring systems I mean I think not for verification but for proving Oh

[Music] because all of the the field arithmetic will be between two and three times more expensive but you have this change you have this chain of login hashes right for example things like that sounds like the beginning of a debate type study clubs - this discrete biomasses pairings yeah like I feel like this conversation there's like large camps that actually

represent those two sides I wonder if we should have everybody try no would it be fun could we do it do we have people have strong opinions on this apart from me and Arielle I think in a larger study I made there definitely are to be fair IDC Arielle's argument here yeah you can certainly make the argument that universal setup is fine I think it will be difficult to to convince the general public that you know relying on in maths

I think eventually the general public won't like if it's if it's almost trusted enough people won't care oh well I mean objectively you are relying on moon that's right it's a tiny proportion of people that can actually understand these things on the understanding the pairing based systems is maybe a bit more complicated than understanding the discrete log systems I don't know maybe maybe there's not that much difference and I mean how much do we understand about right we use things without understanding them weak in society

we we hope that the wreck there are experts and those things understand them and I actually I think you're not quite right there because it take a complicated thing like a car I mean maybe this is not quite so true now in the days of electronic engine management systems but at least 20 years ago it was perfectly possible to to learn car meetings and many many people did and were able to maintain their cars and understand and some that's how they

worked but now they don't like well no they don't but I don't think that anyone actually thinks that's a good thing oh I don't know a lot of people I don't think they just sort of don't care right like the cars in a way are better I know that their car there's more lovers out there who would disagree here but like there you need more expertise to actually fix them you need different kinds of tooling you need to like all these things but at the same time it is more for black box but people still consume them and like them and they last long and I don't know we should have this well I think for

this study club we should probably wrap up but I think this conversation in other forums and other places because I I would be curious to hear I think it's a fascinating philosophical argument about to what extent we should be relying on complexity in the things that we use and my supposition is that we'll probably using things that are too fragile I mean not just in cryptography but in general but especially in cryptography well from a decomp no naughty come here in me in the chat some people about the cars some

people don't care others making their cars via software so conclusion there Dara thank you can I say big thank you to for doing the bonus thanks for coming back I was gonna be an amazing three parter actually man like three-part resource that I hope is helpful to people I hope so too and so I guess we'll speak to you all in the study Club and till next time okay