zkStudyClub: Multi-scalar multiplication: state of the art & new ideas with Gus Gutoski (Consensys)

Transcript

all right so welcome Gus guitar ski am I saying that right very good cool well welcome to the study Club today Gus is gonna be sharing with us a presentation on multi scalar multiplication so yeah take it away great thank you Anna and so before I begin thanks to Anna and everyone in the audience for accommodating this extra long ZK Study Club session I will do my best to make it worth your while we will be starting off gently and that is for the benefit of a wider audience who might be viewing this recording later on but for those experts who are in the room right now you know just sit tight and we will get into the weeds at some okay

um so just to start off we should define what we're talking about so we're gonna talk about this multi scalar multiplication problem many of you are probably aware of this but it's just good to see it written formally it's also known as multi exponentiation or just multi X so the problem is defined by a cyclic group G and this group has a large order and we usually write its order in terms of its bit length B so for example if B is 256 then the size of your group is 2 to the 256 and this is what we think of for you know a conventional elliptic curve group so an instance of the problem consists of two things a list of group elements called inputs and a list of scalars or integers

called scalars and the the goal of the problem is to produce this output group element here I guess if you follow my mouse cursor you can see this linear combination of the inputs and this is the output so the goal is to come up with a solution for this problem that minimizes the number of group operations as a function of n here and n is the number of inputs we're gonna write our groups additively which is why we call it multi scalar multiplication but you know this also works if you write it multiplicatively and that's why people call it multi exponentiation just just as a point of interest there's another useful operation other than plus so

first of all you have subtraction but you also have endomorphisms on the curve I'm not sure how useful they are for multi ax but I'm glad you planted that seed because we will be talking about that later never met this person before in my life folks oh just one thing a few of you just joined just try to meet yourselves if you're not speaking because there's a little bit of background noise thanks right maybe just to kind of elaborate on Dara's point there you can define the problem abstractly on an abstract group and allow yourself only access to the group plus operation but of course if you do that you can come up with a very

general solution but you're you're denying yourself access to certain tricks that might be available in certain special cases of groups such as elliptic curves where you do have efficient minus operations and you do have end morphisms and we will talk about that later ok so yeah so there's a naive solution to this problem that doesn't rely on any of the group structure and it's just to use the familiar double and add algorithm to compute each term in the linear combination and then add them all up so the expected number of group operations grows roughly as this so like based on if you assume you're scalars are random it takes roughly 1.5 times B group operations to perform the double and add

and then you multiply that by n to add them all up so you get something like 384 times n if your group size is 256 bits so the question of course is you know this is okay but can we do better and I have a stupid little sarcasm note here no we can't do better let's all stop and go home of course we can do better that's why we're here today so let's see let's see how much better we can do ok so before we dive into how exactly to solve this problem as I said we're gonna start gently so we're gonna motivate this problem a little bit so I mean many of you will already know this since this is a ZK study club but the motivation is for the firm zero knowledge proof at least my motivation is from zero knowledge proof so the idea is that you

have a program P and you want to be able to prove that you know inputs to that program that yield a certain output possibly without revealing anything about and input and possibly saving a verifier a bunch of computation in the process so the rough idea is that you have this one-time setup that you run and it spits out a proving key and a verification key and the claim is that the prover says I know a secret input X such that when you run this program on input X you get output Y so the prover who knows this secret inputs will do a bunch of computation using his input and the output and the key to produce this little thing here called a short proof and then a verifier who is extremely computationally limited will take this

proof and only the output Y here and of course is verification cheek and he will do some checking algorithm and this checking algorithm is very fast its runtime is independent of the size of the secret input X and he will output accept or reject based on whether he believes the proof so typically as many of us know these proofs are supposed to be so small and so fast to verify that we can post them on chain and then everyone who's taking part in your blockchain protocol and running the consensus algorithm is assumed to be have enough computational power to actually check these proofs by contrast the actual creating of the proofs is a little bit more computationally intensive this is not done by everybody in your whole consensus network it's usually done off chain as they say okay

so an example of one of these zero knowledge proof is called growth 16 it's also called a snark you've probably heard that before so here is a very gross gross simplification of the growth 16 protocol that's just kind of tailored to our discussion on multi scalar multiplication so if we let n denote the size of the secret inputs accepted by the program the proving key then contains among other things in group elements which will write as G 1 through G n and then the idea is that given a size n secret input for the program the prover deduces the integers from you know by running the computation he reduces these integers and computes this linear combination of the inputs all right and then the proof contains this output G

among other things ok so as you can see here in order to produce a proof a prove or must solve the multi scalar multiplication problem okay are you motivated yet okay so just to summarize this motivation then a program takes a size and secret input which implies that as your knowledge groover must do a multi scalar multiplication of endpoints okay so for example the Z cache spend program I believe is on the order of 40,000 the size of the MSM resulting from it is on the order of 40,000 at least that's far sapling if I remember correctly and for another example you can consider this rollup idea which is a scalability solution Lee I think it's more than that

I think it's see isn't it 90,000 I think it's 90,000 I need those okay I might be going from old literature or I may have just simply missed something but thank you okay so 90,000 that's good to know okay so another example would be a scalability solution called roll-up and for this one the idea is to kind of basically take as many transactions as you can and put them into a proof so basically the bigger the end you can support for these roll-ups the better okay so just to give you an idea of what where what is at the state of the art right now we're kind of shooting for programs that are on the order of 10

million or even a hundred million inputs or possibly more so I believe it is known that the cost of a multi scalar multiplication count accounts for roughly 80% of the work done by approver to generate a proof so this is a significant bottleneck in the proof was computation and people have talked about this I just took this quote you know one from many from Justin Drake you know focus on multi exponentiation that's kind of the big bottleneck and this is from the zero knowledge podcast okay so yes so takeaway multi scalar multiplication dominates prove your costs further costs dominate zero knowledge proof costs improvements for multi scalar multiplication immediately yield improvements for zero knowledge

proof efficient efficiency all right we've driven that point home and I've even managed to throw in a shout out to the zero knowledge podcast [sighs] okay so let's uh let's dip our toes into the state of the art then for this multi scalar multiplication and here is where I shame Lee advertised my own work here so I belong to these ek team at consensus Rd and we recently open sourced a project that we called narc and it's available in github there's I will make the slides available and the slides have a few links so you can find these things and look at our cool logo yes so currently given arctor supports the grass 16 protocol for BL s

or BN curves so these are curves of the order of 256 bits and in our implementation of multi scalar multiplication the number of group box scales like 16 times n plus some constant that we'll see later ok so if you compare this with a naive method that I gave at the beginning of the talk which scales like 380 four times in that's of 24 times improvement so that's pretty good and that 24 times is really the multiplicative factor on n here that's ignoring the constants and really since since we're trying to support as large instances as possible the the key target here is to reduce this multiple of n that we see and we're willing to absorb a relatively large constant and this is fixed base it's not right all of

the bases are fixed well so so far I haven't stipulated that but yes in zero knowledge proof all the bases are fixed and you can take advantage of that and I will get into that later in the talk ok so the best solution that I know of is called well I don't know if it really has a good name I call it the bucket method it's you could argue that it's a special case of Pinter's algorithm although you have to squint pretty hard to see that so the best description in the literature and the academic literature that i'm aware of is from a relatively old paper from 2012 this is a paper on batch forgery identification for ECDSA or something like that maybe

noir anyway it's for signatures and the point is that the description of this bucket method is kind of tucked away inside section 4 of this paper so it's not even the focus of the paper and yet it still seems to be the most concise and clear description of the bucket method that I'm aware of so yeah so I guess part of my goal with this talk is to kind of address what I see is this problem of like a relative lack of literature on the multi scalar multiplication problem from academia by comparison a lot of ink has been spilled on the single scalar multiplication problem in the cryptography community okay so how does the bucket method work so the high-level strategy well

that's just my own echo sorry the high-level strategy is going to start with your large instance where your scalars are B bits long and reduce it to several sub instances of the multi scalar multiplication problem where the scalars are only seen bits long and you can choose this C so you choose C to be small enough that you can do special tricks on then you use special tricks to solve each of these C bit ms/ms which we'll talk about shortly and then once you've solved them you recombine them to get the final solution so this is a relatively straightforward part so I will talk a little bit about this but this is by no means the meet I will pause for a moment are there any questions while we're at it Oh looks like Dara has posted the link thank you very much all

right hearing no questions I will continue okay so first we're just going to talk about this reduction from B bits to C bit multi scalar multiplication it's quite simple basically you choose the C that you're comfortable with you write each scalar in binary and you partition the binary scalars into C bit parts so here's a simple example if I consider 12 bit scalars I have the scalar 1368 write it in binary take it three bits at a time and I get my parts and this works up to two three two five three zero so I have a question in the single scalar multiplication case some of the methods I'm use variable lengths windows depending on the bit pattern I

assumed that that isn't possible here because your bit patterns are basically random over all of the scalars is there a way around that or where it's not true uh I don't think there is and I would be very curious if someone does have a way around it I spent a little bit of time thinking about this and I couldn't come up with anything good so near the end of the talk I will talk about methods for single scalar multiplication and how easy it is to translate them to multi scalar multiplication but basically the outlook is not good at least as far as I can tell but thank you really it this is just kind of me working by myself in my desk here remotely so I haven't had much chance to collaborate with others on

this ok ok so yes so back to this reduction then so so ok yes so we've partitioned all of our scalars in this way and then we're going to deduce a bunch of instances of the C bit MSM and the way we do that is as follows it's probably you can guess this it's pretty straightforward the first instance uses the first part of each scalar the second instance uses the second part and so on in this example we have four parts so we have these four sub instances of the C bit MSM problem that we want to solve ok so let's pretend that we've solved them and now because I'm at the beginning I just want to focus on this reduction from secret are from B bit to C then so let's let's pretend that we've magically

somehow solved these cbits MSM problems and we want to recombine them to get the solution of the original problem that we have ok so we have these solutions and now this is pretty easy because everything's in binary we can just recombine them in a relatively obvious way where you just double C times and add the next one and that's it and then the final answer is this combined thing that you see here and if you go through and you count the number of group ops that you used it looks like this and this is relatively insignificant like B is of the order of 256 here C is less than B so this is peanuts this is not a significant cost okay so let's with with that reduction of the

way let's talk about the tricks to solve C bit Nemus ohms so ready for tricks ok so I think the best way to explain the bucket method is to actually just give an example so basically what you do is you have you're see bit problem here so in this example C is 3 so the scalars are all 3 bits there between 0 & 7 I've removed all the 0 terms so let's start with the first term so we have the first input is G 1 and it's coefficient is 6 so we put G 1 into a bucket labeled 6 right similarly the second input as a coefficient of 2 so we put G 2 in a

bucket labeled 2 we have a 6 again for G 3G 4 s goes into a bucket number 1 and so on so at the end I think I've done an example with 14 terms here and we might have a state of buckets that looks of this so now the idea is that you add up the contents of each bucket into these buckets somes s here so I've written all these out explicitly down here as you can see and so so let's pause now and count the group operations we've used so far so the expected cost to compute each of these buckets on Geordie could you please mute sounds

like somebody's not in pain Geordie [laughter] I think you got a actually Oh God yeah I think I think I can mute him do it you can mute him totally ok I did that all right excellent ok let's continue so what's the cost of computing these bucket sums well you're gonna have to go through all of the inputs so there's at least n now of course the first term in each bucket you don't have to actually use a full plus operation it's merely an assignment because the bucket is empty so we subtract the number of buckets and it looks like this ok so far so easy oops there we are okay so now now

we have to we're going to combine these bucket sums to get the answer that we want now remember this is an answer to the C bit MSM problem okay now it turns out that if you just compute this convenient little linear combination of your bucket sums it just magically equals this this is may not be obvious at first glance but it's quite easy to check with pen and paper so basically what we now have is another little instance of the MSM with these inputs s1 through s7 these bucket sells and but now the scalars are fixed sequential known in advance okay and I've listed those points here so we can kind of take advantage of that to compute this little MSM much more

quickly than we might otherwise do so the algorithm to do that describes in the paper I referred to earlier you basically it gives you this simple algorithm which is very fast so you kind of keep two running counters one is your Sun for the whole thing and one is for the next term that you want to add so you start at the top you have s7 you add that to your running counter then to that you add s6 and then you add that some to your running counter then to that s 7 plus s6 you at s5 and then add that to your running counter and so on alright and it's pretty easy to see that when you do this you will end up with this sum here so this is a pretty fast method for computing this little MSM

here it's something like 2 times and operations where n is equal to I guess 7 in this case so here's a person more precise count of the group ops so in this case the number of buckets is on the order of 2 to the C and you need 2 for each one so this is what you end up with something like 2 to the C plus 1 and don't worry I'll clean up all these bucket counts later on when we combine everything together ok so actually well I guess we'll do that right now let's let's accumulate all of these costs for the bucket method and we're gonna stick to theory for this slide and we'll go to practice on the next slide ok so if I take the previous counts from previous slides here and I add them all together I get something

that looks like this and if I strip away in significant terms this thing in the box is a good approximation of the run time of the bucket method so remember B is the bit length of your scalars C is this constant that you choose n is the number of inputs and this 2 to the C is roughly the bucket accumulation cost so if you just look at this you want to choose see to minimize this so at least theoretically the minimum occurs when C is roughly equal to the log of n which is the log of the number of inputs okay so let's suppose for now that you choose C in this way and then at first glance it looks like the asymptotic scaling looks like this where you have something that scales roughly

with the Big O of n over log n which is good sub linear in the number of inputs and you have a multiple of B here okay um now a couple of theoretical quibbles because I have a background in theory this is not really totally asymptotic because you can't always choose C to be the log of n because C has to be less than B so if n gets ridiculously large you no longer have this option available to you so let's just kind of see how that might work so like let's to pick a stupid extreme example suppose that I have only single bit scalars so really this is just kind of a subset sum problem at this point you're just for each input you're just deciding whether or not to include that

in the product I think maybe intuitively we can all see that it's kind of hard to do better than linear in this case like how do you compute a subset sum without actually doing whole event operations and indeed this breaks down here I cannot choose C equal to the log of n if C has to be less than one okay so yes so n log n scaling is impossible in this case oh n is the best we can do but back to the case of interest here where our group order is of the size 256 bits that's quite large and you know we will no matter how high an end we can support we will never ever be asked to compute an MSM of two to the 256 inputs so for all practical sized inputs that we care about we can achieve this analogue in

scaling but just you know for the theoretical purist we don't get Big O as n approaches infinity okay let me talk about the practice and then I'll pause for questions okay so that's that's great for asymptotics so let's look at some actual numbers that you might see in the in the wild okay so here's our approximate cost of the bucket method again a large instance is roughly of the size sake and million so say login is from 223 okay so so in can arc this project that I've worked on

we observed peak performance at C equals 16 so this yields the cost that I claimed earlier where we have 16 times n and the constant here is roughly is 2 to the 12 here so the 16 times n comes from the fact that you have B which is 256 divided by C which is 16 gives also 16 okay so the puzzle is so I just observed earlier that the theoretical minimum happens at C equal log n but we chose C equals 16 which is significantly less than 23 which is the log of n so why did this happen why do we observe peak performance in this way well there are a couple of reasons that we could speculate over the first one is that the memory use scales exponentially in see

here this is the cost of accumulating buckets or storing all the buckets yes and so like I said when C gets up this pretty large and you're using a heck of a lot of memory and perhaps memory could be a problem become a bottleneck another another useful observation is that you have fewer nasty little edge cases if your choice of C actually divides B so 16 divides 256 the next highest divisor would be 32 which would be way too large because you don't have 2 to the 32 memory available for this so if you you know you don't have to do this but if you do do this then you don't have to worry about things like you know for example your 256 bit

scalars are usually stored in for 64-bit limbs so if C does not divide 64 then you'll have a you'll have you know some sub instances that straddle two different limbs and you'll have to do some you know annoying computation to do that so perhaps that would contribute to a slowdown for C that aren't friendly in this way ok ok so now we can move on to the next section of the talk but I guess before we do I will pause briefly for questions okay and hearing no questions I will continue but please feel free to interrupt okay so that's that's basically the bucket

method Oh Anna yes actually Dara were you about to say something so what what does the curve look like if you choose I see away from 16 is it just say only a small improvement of sequel 16 relatives equals 8 or sequels 32 or is it quite a big how I think it's pretty sharp because basically you want to choose C so that so that n over C is equal to 2 to the C over C so I guess you know the more you deviate from the optimum this 2 to the C

doubles or halves relative to in here so you deviate quite quickly so like for example this constant so with the C equals 16 we get a 2 to the 12 here which is insignificant right versus 16 times 10 million but you know the theoretical optimum occurs when the constant is roughly equal to this 16 times then yeah oh I see so because it's exponential then yeah increasing C has a big effect very quickly okay all right I have a question Gus a I missed the first 10 minutes of your talk but

are you going to also go through related work I'm curious how all of these MSN's compared to one another asymptotically and in practice I will go through some related work as it relates to the improvements that I've been searching but I guess as I said earlier it seems to me that the bucket method is actually the state of the art it's kind of the best known algorithm in practice so I I've seen an algorithm very like this called Boss Hogg Airbus Costa throw on the correct term for it or I don't know exactly what was invented when okay yeah I just want to give proper credit right right well if you want to give proper

credit I highly recommend following that link that Dara posted earlier this is the 2012 reprint dan Bernstein is one of the authors of that paper and as we all know he's very good at attributing credit where it's due so he does actually mention boss Koster and Strauss and pip enger' and there's a lot of over at least okay sorry let me pause for a second here relative to the MSM problem where you have many inputs and only one output a lot of these algorithms start to look very similar they have they're they're basically all variants of the same idea so yes there's a lot of history behind them and a lot of them were developed in a more general setting where you have many inputs and many outputs instead of

just one output so that's where they start to diverge but but yes if you want more history look at that I think based on my reading of that 2012 paper basically the bucket method is kind of like kind of like the best of all of those basically but of course I'm willing to be you know proven wrong in that but but I believe in my experience for a different end some algorithms perform better than others so this was definitely a case for libous algorithms as you used them for n equals 1000 N equals 30,000 and then n equals a million yeah well that feedback is nasty yes that is

that is correct and in fact even in arc we use a simpler windowed exponentiation for small instances but I'm more interested in very large instances here for anything Gus just to avoid that echo again I think there's one person who's still unmuted if you could just meet them that would probably be smart see that I think it looks like me no who's me I don't know how to pronounce I don't see anybody muted sorry I don't sneeze muted yeah there we go okay great okay all right I couldn't find that person but

I'm glad somebody has somebody paying attention okay all right thanks everybody okay all right shall we resume then okay so um yes so that's the basic bucket method so I want to talk now about ideas to improve the bucket method so there are several approaches you can take I'm gonna talk a bit about parallelism but that's not the main focus of this talk but it's probably worth mentioning I'm also going to talk about methods for pre-computation this is good because in our specific case it's a fixed base MSM as dara mentioned earlier so we can take advantage of the fact that we know all the inputs in advance to do some pre computation there are also there's a lot

of techniques as I mentioned earlier there's a lot of literature on single scalar multiplication and so I'm gonna have a few slides on how the extent to which we can borrow techniques from single sale scalar multiplication and then at the end I do have a slight improvement that I haven't seen anywhere else so we'll talk about that and we'll look at ways to generalize it and I'll throw that open to the community to see if we can come up with something even better okay so let's start with parallelism this part is relatively straightforward so basically the idea is that suppose I'm on a machine with many cores can I make this faster and the answer of course is yes but the question that you're interested in when you talk about

parallelism is how how well can I use the parallelism some problems lend themselves better than others to parallelization as many of us know so a good natural boundary for parallel computation here is this partition into C bit scalars because basically each little C bit MSM is almost completely independent of the rest they only have to talk to each other at the end of the convey computation when you combine them all to get the answer so you know you can just kind of for each part of your partition of your scalars you can just a court to it and I have a little diagram here but really it's pretty straightforward so under this scheme you can easily make full use

of up to B over C cores because that's the number of parts you have so you know a concrete example if you're working in 256 bit groups and you choose C equals 16 that means you can easily use up to 16 cores of course each core needs its own memory for bucket accumulation so each core uses 2 to the C memory so now if you tweak C you're really changing your your using even more memory than before ok so what about what happens if we have more than B over C cores available I mean there's talk of you know for very large proved or rather for proofs of very large circuits we might you know Commission some Amazon instance with a bunch of cores and we want to use those

course more intelligently so suppose we have a lot of cores available can we use all of them well yes you can but at this point the the benefits of parallelism start to slip a little bit I mean there's still significant benefits but it's no longer as clean and perfect to divide as it was in the previous slide so here's one way to split things up this is basically the the most obvious way you could possibly think of you start with the jagged B bit MSM with n inputs and you just take the first half of the inputs solve that MSM take the second half of the inputs solve that MSM and then add them two together it's like doesn't get more basic than that so then of course the idea is that each of those

two halves you split it into you run them in parallel and of course each of those two halves you do you can run each C bit MSM in parallel so if you do if you split your original problem into two parts and you can use up to two times B over C cores of course you can replace two with any number you want here but you are introducing a bit of inefficiency here so in particular in this example these two MSM instances of size Emma n over 2 cost more group operations than one MSM of size n and that's really because you're kind of doing the same bucket accumulation cost twice here you have to do one bucket accumulation here and one and the same thing here whereas if you did them all at once you could only have to do that once and that's kind of where this sub

linear scaling and over long end kind of makes itself known I guess so just a note in ganar qui did not do this we just limited our parallelism to B over C course and that was it if there's you know if there's demand for that we can look into that some other time okay yeah so that's all I wanted to say about parallelism nothing deep here if anyone has any other further comments on parallelism I'd be happy to listen but hearing none I will move on okay so let's talk about this fixed baseness of our problem or perhaps we can use pre-computation so the idea is that the inputs to our problem are known in

advance they're given in the proving key of the snark so we want to use this to our advantage so how do we do this so the idea is to pre-compute a bunch of points and then store them so you know some examples off the top of my head here for each input G you can store 2 times G 3 times G 4 times G and so on up to say the bucket lengths or perhaps you might store some big multiple of G like some power of 2 and then you know that squared and all the way up to some hamm for some constants km that you choose or maybe you can combine various inputs and maybe you want to compute various subsets so here you know this example you might partition your inputs into sets of size 3 and you compute all

combinations of 3 elements in those sets so each of these things you could try and the goal for doing this would be to kind of get a smooth trade-off between pre computed storage versus runtime of your algorithm so one problem I have to note right off the bat is that large MSM instances already use a lot of memory so to have even more points in pre computed storage is kind of asking a lot so for example if I'm working with a hundred million points goon Ark means roughly 58 gigabytes to store enough BLS 12 3 77 curve points to produce the zero knowledge proof for a program with the size and secret input right so 58 gigabytes is a lot of memory and if I'm storing many multiples of

that then I'm gonna run out of RAM okay now here's a question I haven't had really time to explore perhaps perhaps you know if you use some gigantic hard disk space you could store points on disk but maybe just reeds might be too slow if anyone has any insight on that I'm curious to know I'm pretty sure they'll be too slow um here's a point at which you might be able to use the endomorphism because that effectively gives you double the storage place for free because you can optionally apply the endomorphism to each point you've stored later we will you're you're way ahead of me

and I'm sorry that you have to wait til we get there but we will get there okay okay okay so first I'm going to introduce a naive pre-computation method for the bucket method just so you can kind of get a feel of how this might work so suppose that for each input g i pre compute every multiple of G up to the number of buckets I have is everyone else hearing my telegram or is that just me I'm gonna fix it telegram okay okay yes yes store all these store each scalar multiple up to the number of buckets

okay so then the idea is that if you recall the goal of solving seebut MSM is to compute this linear combination for secret scalars but of course if I already have each of those in storage and there's really no bucket accumulation left to do I can just immediately add them to my output so there's no need to compute bucket sums there's no need to accumulate these bucket sums I can just put them directly in the output so if you do this the number of group ops reduces to this which is roughly this thing in the box here which is B over C times n so I guess I don't have a convenient I guess you'll have to imagine there you can compare this to the 2 to the C that was inside the inside the parentheses here you can just completely eliminate that with this with this pre-computation of

course the extra storage space required scales as 2 to the C times n because you have to store a multiple G for every input G this is a massive amount of storage space so as an extreme example suppose I choose C all the way to the limit of 256 then I'm storing 2 to the 256 times endpoints which is totally unrealistic but then I only need exactly n groupbox I can just go through for each input I can pick the scalar multiple I need and add to my output I get the absolute minimum possible number of group ops of course that's unrealistic a more realistic example so if I'm considering and of roughly the order I guess what is that 10 million or something 256 groups and a more modest C like C equals

16 then the extra storage required to do this would be 550 billion elliptic curve points which is very large okay so that's bad so let's see if we can find a trade-off because that was what I'm the way I presented it is kind of an all-or-nothing approach ok so instead suppose we have limited storage so for each G we're going to pre compute K points where K is basically as many as we can fit so I'm gonna start pre-computing the largest multiples first and then stopping when I run out of space so I'm just gonna compute 2 to the C minus 1 times G all the way down to 2 to the C minus K times G ok so then the idea then is that the bucket method is used for only the first you

know the first two to the C minus 1 buckets - the K that I've already stored ok so that way I only have to compute these buckets sums the first well all of them minus K and I have to do bucket accumulation for all of them except the final K so the total cost in grubach scales like this basically I keep highlighting this K in red so you can see the difference so basically I have a minus K in here alright so as so whatever I can set K to I can subtract K inside the parentheses here the extra storage cost is K times endpoints choose K as big as you can store so the takeaway from here is that if you have only a small storage capacity then you get only a negligible improvement if you want a non negligible improvement at

least from this method you you can only achieve it with very large storage capacity so basically at first glance it seems as though at least for this method of pre-computation you don't get much but we will revisit this later in the talk and get the better trade off okay so that's all I wanted to say about pre-computation I will again pause briefly if anyone wants to chime in with a comment is it better to pre-compute different k points take possibly mine spread out in the space between zero and two to see oh yeah that's okay that's the next thing

all right I'm going ahead so no no I'm not going to talk about this I'm done with pre-computation now I spent a while thinking about this I couldn't make something convenient work so I just kind of gave up on that but if you come up with a better idea please do share okay okay this by the way while we're on the topic this business of combining different subsets of inputs this is actually what pip injures algorithm does in well okay so I wasn't gonna talk about pip injures algorithm but I will mention that pip injures algorithm can be divided into four different cases there's input and output partitioning and input and output

clumping and if you do this where you combine every subset of a bunch of parts this is roughly corresponds to output partitioning in pictures algorithm for those of you who are familiar with that but I'm not going to talk about that anymore I had toyed with the idea of making a completely separate talk on pip injures algorithm and you know maybe if I can find the time I will do that but let's get back to what we're talking about here okay so let's move on to lessons from single scalar multiplication so many of you probably know this so this might be review but you know for those of you are not experts let's just review what is known about single scalar multiplication so just to be perfectly clear the single

scalar multiplication problem is basically an MSM where N equals 1 so you're just given a single scalar and a single group element and you just have to multiply that group element by the kind of stand easy method for this is double and add the cost of this method increases with the Hamming weight of a that is the number of ones and the binary representation of the scalar so some examples here if the scalar 128 has a very low hemming weight so I can compute an MSM using only seven group ops but you see as the Hamming weight of my of my scalars increases so does the number of group ops required to compute it so if I get up to 255 let this very high hemming weight it takes twice as many group ops to compute it so the idea that has been explored extensively in

single scalar multiplication is to use different encodings for scalars that have possibly lower average Hamming weight in the hope that that will reduce the number of group watch that I have to do so let's look at a couple of ideas here so one example that you may have heard of is the non adjacent form so basically this is like a binary dog decomposition except for the digits can be plus or minus 1 this requires you to be able to do the group subtraction at least as fast as you can do group addition fortunately since we're working with elliptic curves we can do that ok so the idea with the naf is that there is a canonical form where the nonzero digits are never adjacent that means

whenever you have a non-zero digit you're guaranteed to have a 0 on the left and right so you can see that maybe that is going to reduce the average Hamming weight of your scalars and indeed the average Heming density of scalars written in this Naf form is 1/3 of course if you compare this to standard binary encoding the average Hamming density of a random binary number is going to be 1/2 because each bit can be 0 or 1 with equal probability ok so here's some simple examples of Naf encodings of the same numbers I had before of course if you started with a number like 128 that has low Hamming weight well it's also going to have low nef weight but for other numbers like 255 that had very high binary Hamming weight it is very low and they have

Hamming weight because you just have two nonzero terms here so you use eight group ops and sorry eight group of plus operations and one group subtraction operation and that's compared with 14 group plus ops if you just use binary encoding so that's a pretty against being up there okay another example of crazy stuff you can do there's this thing called the double bass number system so if you think of by nonny is writing a number as a linear combination of powers of two well you can imagine that I throw some other things into the mix there so maybe I can have other bases I can write my numbers as linear combinations of powers of two and say free why not of

course your digits can be vinyl e or something larger if you want so the first observation you could make is that this is a very highly redundant number system there are many ways to encode any given scalar using this in linear combinations of powers of two and three so for example I just took this from a paper the number 127 has 783 different representations with only binary digits and if you take the ones with minimal Hamming weight there are three of them and they have a Hamming weight of free so by comparison the number 127 has Hamming weight seven in ordinary binary encoding so here's three different decompositions of 127 in this double based number system and I believe it was

proven that the Hamming density for B bit scalar scales as 1 over the log of B in this double base number system and again compared with 1/2 for binary so this actually gets better the larger the scalar is ok so we've really beaten that to death so I guess the question is can we make use of any of this for multi scalar multiplication um so I thought a lot about this and I couldn't come up with a good way to do this although again it's just me by myself so if anyone else is thinking about this I'm very happy to talk to you about it but some observations I would make is that um the cost of the bucket method increases not with a Hamming weight of say one

individual scalar but instead it increases with a number of possible scalars so if there are two to the C possible C bit scalars then you're always going to need 2 to the C buckets regardless of how you encode those scalars right I mean you could choose a bunch of encodings that reduce the Hemingway of each individual scalar but of course a lot of those encodings will you say many different Basie's or something and at the end of the day you will still need at least that many buckets in an information theoretic sense you you could maybe pre compute for the buckets that I'm more likely to yes [laughter] you could of course if it's a totally random instance then you don't have any guarantees on which buckets are more likely to occur but

if you're using non-adjacent form and you you expect the weights to be less than average sorry yes you know we'll be fine right yes well okay okay yeah yeah so okay coincidentally I'm not sure if you're reading ahead on this slide but I have written here the cost of the bucket method could be reduced if we have a guarantee that some scalars are never or rarely occur in which case you can you know kind of tailor your algorithm to favor those scalars that are likely to occur of course a scalar encoding by itself like such as naf or double bass cannot

provide such a guarantee on the distribution of inputs you might have to instead use more advanced techniques to do that and you know one could argue that this is kind of like Pippen ders algorithm does it gives you you know it's kind of a recursive algorithm with where each level of the recursion kind of restricts the the the space of possible scalars that you have to worry about and so you could possibly use that to reduce your bucket accumulation of course the big question is whether the cost of establishing such a guarantee outweighs its benefits and that's a discussion for another talk on Pippen ters algorithm I do note that Pippen ders algorithm was kind of the granddaddy of all of these algorithms in the sense that it subsumes them all and

it is asymptotically optimal yet I have not seen anything more complicated than the bucket method being deployed in practice for the specific case of MSM and there's probably a reason for that okay any further comments on that before we move on to the next topic it was so I guess so dairy your your point in the chat you actually do get a chance to share that I guess oh that that's already what I said okay all right thank you okay so let's uh let's move on it's a good

thing we have 90 minutes how are we doing for time anyway can see well okay perfect perfect I think we might even finish it my throat is getting sore but well we're at thirty two out of 57 so I think we'll be okay a lot [laughter] of these slides you slip flip through pretty quickly because they're animations and I didn't want to fiddle with anyway whatever let's move on okay so yes okay so now I want to talk about new ideas that we've looked at for this so as Darren mentioned at the very beginning with elliptic curves we have

cheap group inversions so let's see what we can do with that so just to be clear what what I mean by that is given a point on an elliptic curve group it's cheap to compute it's negative you just take it in its coordinate representation and you negate the y-coordinate so so the observation is that currently the MSM scalars are written with this standard digit set in base 2 to the C all right so let's suppose instead we allow negative digits so basically we're kind of sliding our digit set from 0 to 2 to the C down to centering at 0 so you have 2 to the C so minus 2 to the C half and plus 2 to see how roughly so then the idea is that when you're doing the

bucket method if you encounter a scalar that's positive then you just add it to the its corresponding bucket as usual but if you sort of digit I guess this should be digit instead of scalar so if you encounter a digit that's negative then instead of adding GE to the corresponding bucket you add negative G to the corresponding bucket and since it's almost free to compute negative G this adds very little overhead so the idea that that by doing this you have eliminated the need for buckets with large labels so basically any digit that's larger than 2 to the C minus 1 you don't need a bucket for that now so basically we've eliminated half the buckets by doing this okay so let's dive

into this a little bit more clearly here so I have a specific example this is actually the example from earlier in the talk on the bucket method but here instead I've just translated all the scalars so that if they were large they're now small negative numbers so 6 becomes minus 2 here so you'll notice now that instead of having 7 buckets I only have 4 buckets and even though this is still 4/3 bit MSM so the first point G 1 has a scaler of minus 2 so G 1 goes into bucket 2 but since it's minus 2 I actually put minus G 1 into bucket - all right similarly for the rest the scaler here is positive 2 so just plain old G 2 goes into bucket 2 again we have a minus

2 for G 3 that one was positive 6 before so minus G 3 goes into bucket 2 and so on so if you redo that computation with all 14 points from the beginning you will end up with buckets that look like this only for buckets a lot more points in each bucket now and from here on out it's the same thing you just sum up all the points in each bucket right so here are those for sums written explicitly ok so like before the desired output is just equal to this linear combination of bucket sums except for now this sum only goes up to 4 instead of 7 so instead of 2 to the C minus 1 buckets we now have

only 2 to the C minus 1 buckets doesn't sound as good when you say it as opposed to looking at it written down I guess of course bucket accumulation works exactly as before except with half the buckets bucket accumulation costs drop from 2 to the C to half of 2 to the C ok so what do you get from this so the total cost of the bucket method if you do it in this way the approximate number of group opps looks like this I guess I shouldn't just say plus here should also have - so and then again this is for your choice of C so given this you have two options available to you at least two options you can use the same C as before and

simply bask in the glory of your 50% savings and bucket accumulation costs or you can put that to work and absorb it and increase your C by one all right so this keeps your bucket accumulation costs the same but it reduces the scalar multiple of n of the front here by putting a +1 in this denominator and that of course reduces the overall asymptotic cost okay so how much of an improvement do you get from this so if you use option two then the multiple event improves by a factor of c over c plus one so to just take some silly example with knifes convenient numbers if you started with c equals 19 then 19 over 20 is a 5% improvement and again this is ignoring

bucket accumulation costs this is just improvement in the scalar multiple event but of course this also ignores the stuff that we discussed last time there might be practical reasons not to change C but again we're just kind of staying at a high abstract level for the moment although I guess that moment is now ended because I have a point on concrete improvement here so I actually implemented this stupid ass stupid proof of concept in ganar k-- where i kept seeing the same so i employed option 1 here and even so i observed a 5.7 percent speed improvement for 1 million points this is actually a little bit surprising to me because as i mentioned earlier in connect the c is a little bit less than

the theoretical optimum so the bucket accumulation costs are a little bit you know are a little bit less than they would otherwise be in the optimum case and so I expected roughly a 5 percent improvement for the optimal C and yet I observe the same thing even for a suboptimal C so that was kind of a pleasant surprise ok ok ok [clears throat] so there's a pro so actually the two options end up giving you about the same improvement because 16/17 subtract from 1 that gives you a 5 point 8 something improvement in theory so it's about the same is

it always the same though I thought it would only be the same as thirds it's only approximately the same okay and I would just depend on the choice to see Yogi's yeah yeah I would think the more you know see diverges from optimum the farther apart these things would be would be my guess but I confess I didn't think too deeply about that okay okay so yeah so there's one problem that I've swept under the rug so far so let's talk about that so I just so far all of this discussion has kind of assumed that I somehow magically have my scalars written with these negative digits but I don't I have to do that myself and there is a cost of doing this so so by comparison for the bucket method it was

really easy to partition scalars into the normal not non-negative digits we just saw that because you're given these numbers in binary so they're right there but so yes so in general we are given for free this decomposition in this digit set here but what we want is a decomposition in this digit set here so I put a prime on all these digits so we want to write a like this instead of like this okay so how do we do that so I guess here's some pseudocode because I don't know how better to explain this it's actually not that difficult at least for this specific case of sign digits so the idea is that you go through each digit and if you encounter

a big one like if you have something that's larger than to the C minus one then you you shift it down by to the C and that will put it in the correct range and then in order to compensate for that you have to add one to the next subsequent digit which gives you another multiple of 2 to the C so you're kind of borrowing like you know grade-school subtraction or I guess lending from the next digit okay otherwise of course if your digit is not too big then you don't have to do anything you can just keep it and that's it but then of course there's this problem where like well what if my highest digit is too big and I need to borrow from the next highest digit which doesn't exist well I'm just kind of like going to

assert that that's never going happen here and just kind of wave my hands and wash myself with this problem but I'm allowed to do that at least in some cases because in many of the cases that were interested in this never happens so for example so just to be clear this this method of converting to sign digits works only if the group order fits comfortably into B bits so for example the BLS 12 377 curve its group order is actually roughly 253 bits which is typically stored on the computer using 256 bits so there's three unused bits in the final digit which means that even if we do the worst that can happen we still cannot have an overflow in the final

digit so it's okay okay so that's nice and convenient but the point is then that this conversion to signs digits does have a cost fortunately this cost seems to be negligible it doesn't significantly affect the runtime so how do you actually compute these sign digits well I mean I guess I gave pseudocode I don't know what the most efficient way to do this is in my stupid proof of concept I did basically the the dumbest thing I could imagine and I just allocated a completely separate memory for all of the scalars and I just computed them once and stored them there so you know if you know there that means you're allocating n times B bits of

additional memory so if you have a million points and you're scalars are 256 bits that's 32 megabytes Fram I guess so I mean 32 megabytes isn't that much but maybe there's a better way of course this memory could be saved if you instead compute these sign digits on the fly but it seems to me that if you do this you kind of need to compute the first the preceding sign digits first and so if you don't store them then there's a lot of repeated computation here I don't know whether that's significance or whether the trade-off or how it trades off with memory use I simply didn't matter my intuition is there's an in-place algorithm for this that doesn't require recomputing all the digits

I don't know yeah yeah I have seen now that you mention it I remember reading about in place algorithms for converting to different yeah so it might be possible okay okay but there's something I would like to flag for later in this talk and that this problem of conversion to the correct digit set becomes much worse when I attempted to generalize this idea and this will lead to an open problem that I would really like other people to

help me with Dara COFF COFF okay [clears throat] okay so I will move on here then okay yes so let's okay yes sorry so let's let's move on so let's try and generalize this I think the link I just posted has to do this in place that could be wrong excellent thank you it's it's targeted to memory constrained environments excellent thank you okay

okay so I would like to generalize this idea I mean it's it's great that we can use group inversion to reduce bucket accumulation costs but is there anything more we can do so I guess the the observation that you want to generalize is that we've used the ability to cheaply compute minus 1 times G to reduce bucket accumulation by a factor of 1/2 so maybe I can pose the question this way suppose we have K different scalars and you know for ease of accounting we'll just include the scalar 1 in that list so we have K different scalars for which we can cheaply compute those multiples of G if we have this can we reduce bucket accumulation cost by say a factor of 1 over K so with just plus or minus 1 we

have 2 different scalars we were able to reduce bucket accumulation by a factor of 1 over 2 so if it's K can we reduce by 1 over K that would be awesome if we could do that then the approximate cost in group operations again I guess this should be not just group Plus operations anymore it drops to this so you're dividing the the bucket accumulation cost by K or if you want you can reabsorb that into C so you you change your multiple of n by c plus log k so the multiple of n improves by this factor c over c plus log k so say that you can do say that you have a method to do 16 different scalars and if c is 16

then you get 16 over 16 plus 4 that's a 20% improvement for multi scalar multiplication that would be pretty awesome that would be significant but so i know how to do it for k equals 4 using endomorphisms yeah yes i will show you that in a second ok but [laughter] but but but unfortunately though there is a there is the problem of writing an appropriate digit set to exploit that and that's getting in the way and as far as I know that's currently a blocker so if you know how to write clean note very very recently actually I just tweeted a couple of days ago there are certain calves for which the lattice basis production and becomes trivial okay

but I think this loudest basis reduction you're referring to is from what does it glv paper yep that works fancy for single scalar multiplication but I'm it's not as well okay okay excellent that's it maybe well how time can shape excellent I am so glad you're on this call this is exactly what I was hoping for okay well I will plow through with my slides anyway okay so assuming we can do all this magically then you know you can get say up to a 20% improvement for MSM using this method which would be awesome okay okay so so let's dive into how exactly this

would work okay so so suppose for example we can do one extra scalar multiple for free all right so we already know how to do minus one times G and let's suppose magically we can somehow do lambda times G for some lambda that will be specified later so if you can do that well then you can just combine the two and you can also get minus lambda times G so that gives us a total of four different scalars that we can multiply by quickly plus minus 1 plus minus lambda so now suppose and here's a big suppose suppose we can write the scalars using this digits X whereas before we just had plus and we had negative digits so just the top two

rows here but I'm going to add a couple more rows here I'm also going to allow lambda 2 lambda 3 lambda all the way up to 2 to the C lambda minus lambda minus 2 lambda minus 3 lambda all the way up to minus 2 to the C so [clears throat and cough] this digit set in this example has size roughly 2 to the C divided by 4 and yet it still requires only two digits sorry that should be two of the C times for not divided by four and yet it still requires only two to the C buckets okay so in this particular case by adding this new scalar lambda we've doubled K the number of scalars by which we can cheaply multiply points so hooray that's amazing that seems like we might get an

exponential improvement for you can use scalar that we had but you know cool your jets because that doesn't always happen some you know this only happens when each new scalar is completely independent of all the others so we'll see an example shortly where you don't necessarily get to double the number of scalars that you get but you still get to increase okay how are we for time twelve ten okay okay we're getting close okay so just to kind of fully generalize this example suppose we can cheaply multiply by these K scalars and suppose we can somehow write these scalars using this digit set where you just have every possible combination from the two lists this digit set has size roughly two to the C times K and requires only two of

the C pockets okay so how can we where do we find magic lambis okay so this is finally where I'm gonna talk a little bit about endomorphisms I'm certainly not going to go into detail I'm just going to because that's not the point of this talk I just want to kind of give you some inspiration for where this comes from so so we're gonna dive into elliptic curves briefly here so we're gonna work with an elliptic curve of this form so this is a very common form of curve used in zero knowledge proof this is the BLS curves of this form and we're going to consider a prime order subgroup of this curve over a prime field and if you let beta be a cube root of 1 modulo your base field then for any point if you simply

multiply the x coordinate of that point by that cube root that transformation acts as multiplying that point by a scalar lambda where lambda is a cube root of 1 modulo the group order now so that's kind of a long way of saying computing this specific scalar multiple of G can be implemented with a single multiplication modulo P that's only slightly more costly than computing the negative of the point and much much cheaper than computing a full group plus operation so basically these endomorphisms give you a way to compute specific scalar multiples for specific lambdas okay so so what about what about more cheap

scalars all right so this this these endomorphism [clears throat] gives us at least two new scalars we have lambda and of course lambda squared lambda cube you can do again but that's just 1 ok so we can combine each of lambda and lambda squared with -1 to yield a total of 6 cheap scalars so you a plus minus 1 plus minus lambda plus minus lambda squared so just to observe here here by adding the new scalar lambda squared we did not necessarily double the length of our scalars up to 8 we only got up to 6 why is that well because lambda and lambda squared aren't fully independent because you know if you combine them you don't get a new scalar that you haven't seen before instead you just get one which is not another new scalar okay so far so good so I guess the question

is this is great how many of these endomorphisms of how many of these endomorphisms exist and how easy are they to compute so the original [clears throat] paper on this that I mentioned earlier to Dara had really just exploited a single endomorphism giving you these there was a follow-up paper in I guess it was originally posted in 8th where Galbraith Linscott they found a bunch more and more fizzles but in their paper you had to work in an extension field instead of a prime field in order to get access to these guys also believe it may be patented the the glv patent is expiring in the US in September it's already expired outside

the US the I haven't really researched the GLS patents but they're gonna be longer just because it was like ok so I was aware of the GLD patents and I was aware that it's expiring I was not aware that GLS it was also patented I'm a little surprised I could so I could I could be completely wrong there I'll just check I think that I think that the patent involves any endomorphism based computation so GL v and GLS and every endo morphism you need to do for example for clearing cofactor or sub objects but it is already expired all over the world except the users AR say yeah I mean I'm not I'm not I'm not making

any assumptions on patentability in this talk but of course you have to take that into account if you're doing this but you know we're just we're just I refuse to comment on that issue I agree ok ok yes yes so um my understanding of this GLS paper is that you can find more endomorphisms but you need to work in an extension field instead of a prime field now I might might have missed some something here but it seems to me that if that's the case then if we were to if we were to try to exploit these into morphisms then you need to convince everyone to switch to a different base field I think you can still stick with

the same VLS curve you just have to work with a different field you know I don't think that's necessarily a problem in fact if to speed things up but but it does require kind of the whole community to come to a consensus on that change but I think anyway I'm sorry trying to actually but I think that anyway in VLS curves if you want to work or if you want to do multiplication in G to go then you already work in an extension in a quadratic extension as the the twisted untwisted for veneers by Galbraith in sports yeah so that would only work for g2 computations yes but what I'm thinking is like your g1 like your your base

field would no longer be prime it would actually also be an extension field and if I understand correctly the idea is that instead of working in say like a 256 bit or 384 bit prime field you chop the bit length of your prime in half and work in a degree 2 extension for example so that the total bit length of your base field is still 256 or 384 or whatever you need except for is just chopped into multiple components of the extension so that's what you would need to get everyone to agree on is the change in the prime modulus that you're using if I if I've understood correctly I think that's correct I'm by the way I think Len is spelt ly mm oh okay thank you if

it's the right if it's the same Len that I'm thinking of I will look into that okay so we'll just one other thing I would flag on this is that there's a paper [clears throat] by Hugh longer in zoo that actually implemented this using a quadratic extension so they got what they call a four dimensional glv implementation and they demonstrated a significant speed up for a single scalar multiplication so that is I don't know that's a positive and inspiring result that you know that it could be useful here okay okay

yes okay so next I'm going to talk about I think this conversion two digits s so before we go there are there any more comments that anyone would like to make you can't you can't resist era I'm [laughter] sorry I was someone else was talking at me so so what I was going to say is yeah it's it is actually for some curves easy to convert the scales you might already have it on this slide and because it for some curves the lamda is only half the length

of the scale yeah okay okay well we're about to get into this so this is where I'd really like your input here okay so let's talk about this conversion into the appropriate digits at them so we observed earlier that the scalar minus one is well behaved in the sense that it is cheap to convert scalars into sine digits overflow is very easy to quantify and easy to avoid okay we saw that but other scalars might not might not be so nice right lambda could be very large so for example for BLS 12 377 this lambda is I believe of the order of 129 bits so the question is

how do I convert scalars to digit sets containing such large numbers as this where the digits are actually larger than the radix of your scalar representation so that's it's kind of weird and I don't know if this has really been considered before so bate so basically the the digits that you're splitting it into they don't have to be contiguous so you can consider say the lowest three digits the three digits that are from so you first of all you decompose your

scaler into say a lambda plus B and then you take a number of bits from B and a number of bits from a you treat those as being in the same book you see how that works I'm not totally sure I see that okay well let me move on and like I saw I do have some slides on this and you can tell me how closely okay I'm coming to what you're talking about okay okay yes so I guess to finish off this slide then my worry is that overflow might kill us in this case so but maybe

there's an asterisk there okay so here's a first attempt to generalize this signed digits method that we saw earlier so suppose we have a scalar whose five digit is large it's too big and we want to kind of map it into a smaller a smaller scale smaller digit so we want to map it to a small bucket label so suppose we can write in this way so this is kind of a generalization of what we saw earlier with minus one all right so we found some integer D and some label AI prime that's in the correct range such that this holds so earlier with minus one we saw that like D was just negative one that was just borrowing two to the see from the next subsequent digit right

so suppose we can do both of those things then we can do the following we can just kind of repeat this borrowing trick all right so we map our current digit to an a prime here by adding this D times two to this C to it and we subtract that D from the next digit pray that we don't overflow and then during bucket accumulation we can add the point lambda times G to the bucket with this label instead of adding G to the bucket with this label okay and of course lambda times G is easy to compute so there's no extra cost the problem though is that if lambda is large then in order to compensate in order to make this equation hold here you also need D to be

very large so your digits start becoming very large and I it just kind of becomes unwieldy as your number as you do this conversion your digit start becoming really large and I don't know how to deal with that now there's a bit of a mitigation you can do for this where instead of just borrowing from one subsequent digit you can borrow from subsequent digits and that way at least you can keep these amounts you're borrowing in some small reasonable digit set right so in this case if you do this you're actually you need to set several digits instead of just one so instead of just borrowing from one subsequent digit you borrow from else subsequent digits but other than that it's the same idea so okay so that seems fine except for what

if I don't have L subsequent digits to borrow from anymore I'm screwed right then I have overflow so just some examples here if if you're working in 256-bit group like like BLS and you have a lambda that is roughly half the bit length like 128 then this optimization can be used only for the lower half of digits because only for those lower half do you have enough subsequent digits to borrow from as soon as you get to higher digits you run out of things to borrow from so you cannot apply the optimization anymore so you lose the ability to use that scalar lambda at least if you're a try of trying this particular trick that I've described here and even worse if you encounter a lambda

where the bit length is actually close to equal to the bit length of the whole group order then you can't use this optimization at all because you need more digits than you have 12:23 okay we're almost done well unless you unless you do lots of space reduction right because then you can always express it as it it looks like a similar problem if lambda was half length because you're expressing it as a plus B lambda were a and B are each 128 bits yes okay unfortunately I don't have a slide getting the point that I want but I

think this isn't just a vanilla lattice basis reduction because yeah okay okay so yeah we'll talk about this offline but I'd be very curious to hear how this differs from a vanilla that is a lot of spaces reduction okay okay in the meantime I'm [clears throat] just gonna make a few notes here before I end so so I talked before about pre-computation and I kind of gave you a really bad trade-off in terms of precomputed storage that looked like this so if you store K times endpoints you get only this benefit but instead if you use this trick with writing things and better in a new digit sets then you can actually

instead of subtracting Kait you divide your bucket cost by K here which is really good so for the same cost roughly of extra storage you get this benefit instead of this benefit and I have to thank Alex Belling for pointing this out to me when I presented this in an earlier version to him at consensus this didn't even occur to me and he had to point it out yes okay and an advantage of this pre-computation is that we don't have to worry about unwieldy 128 bit lambdas anymore we can choose the Landers to be whatever we want so we can choose them to play nice with sign digits so we can choose it to be two three four or five whatever so there's a simpler conversion to the new digit set less worry of overflow of

course so yes so each new precomputed multiple significantly increases the number k of cheap scalars at our disposal so for example if we start with six scalars maybe these were obtained from endomorphisms then each new multiple we add adds six new cheap scalars because we can multiply each of those by six okay so on slide 45 we estimated that you have approximately a 20% improvement if you have 16 scalars this is ignoring the cost of convert digit sets of course so you can actually hit this K equals 16 target with only 2 times n extra storage if you have these six points originally cuz you know 6 12 18 you've exceeded 16 but you know if if we haven't figured out

how to properly account for all these lambdas and we're stuck with just plus minus 1 well we can still hit that k equals 16 target with 7 times an extra storage so that's a lot but it's you know at least tractable I did not implement this improvement they didn't have time okay so on the final slide here so just to summarize the open problems so the big one is to find an efficient way to write scalars using the digits set without overflow there's prior arts based on shortest vector problem lattice reductions it's not clear to me how that can be generalized to MSM but there are things it could which is awesome and of course you want to find more scalars that admit cheap scalar multiplication I mentioned some work on new endomorphisms there's

some follow-up work to this that's the only way I know how to do it okay and with that I will close and I guess the remaining time and we can discuss thank you very much for your attention does [laughter] anyone have any questions or comments or thoughts okay can you go back a few slides because I you went past that slide very quickly with the extra optimization allowed you to increase K this one I think is this one yep I was

like okay so sorry how are you choosing lambda here I may have missed something well oops I would want to choose it to play nicely with my existing digits and to make signed into conversion easy so up here for example I just say maybe I can just store multiples of two or three or four of the points and that would make that naive design digit conversion algorithm I have convenient oh yeah okay so see the using storage you

don't have any other cheap way to multiply by yes that's exactly right that's exactly right okay that makes sense so maybe in the one or two minutes we have left just for the sake of recording so I think Dara you said you there might be a solution to this problem but just to just to clearly articulate what exactly the so you want to write your scalars using a digits that that looks like this but once you get beyond minus one you have a non contiguous digits right there's a lot of numbers between you know two to the C and lambda right so you have an interval here and then a big space than an interval here and you want to find you

want to decompose your number into digits using these this weird disjointed scalar set and moreover if lambda is very large then you know these digits can be much larger than the radix now as you mentioned there are lattice reduction methods to do this but as far as I'm not let's let's simplify the problem imagine that lambda was equal to exactly who's the one to wait you're not going to be able to find that but but it if we consider that then we'll see what the essence of the solution is so then what you're basically doing is selecting

two different bits according to whether you use with which of these four possibilities you choose right so you can either add a bit from the lower half of the scalar or a bit from the scalar yeah I mean I think if you wanted to generalize that it sounds like you would write it not in radix two to the C but in like radix lambda yes yeah okay well

okay so one independent remark that is relevant is that I guess my biggest problem is that you can use basis reduction methods to you know have your basis be like like each contiguous region would have a basis but then if you just use them as a black box you will get in general nonzero coefficients for each of those bases whereas really you want all but one to be zero in this digit set right so I don't know if I'm articulating that very well but like you cannot have a multiple of like say one multiple of one and a multiple of lambda in the same digit because that requires two group operations to handle instead of one so you only want to have one of

those to be nonzero maybe I maybe I should just stop talking because I'm not sure if that's making any sense so that was my that was my stumbling block with the lattice basis reduction methods what why would that be true why wouldn't it be okay to just discharge and say what we're going to deal with this in a different bucket um so I'm not sure if I understand your question correctly but I guess the point is like you can still do that but then in order to do the to place this in a bucket you have to place it in multiple different buckets that requires multiple group operations so you're not really saving anything then I have a feeling that I'm not getting your

question properly so so halo does something similar to this but we have a simpler problem because we're not trying to multiply by arbitrary scalars you just need a random scalar so basically what we do is we pretend that we already have the recoded scalar and then we prove that the the recoded scalar has enough entropy so [clears throat]

we just need to multiply by something that has enough entropy so that's one way of doing it but it doesn't really solve the general case so yeah I do know that if you choose if you try to choose scalars in like this weird basis you do get a biased outcome so you do have to do something to post-process it to make sure you don't end up with biased scalars but it sounds like you've accounted for that we we have a proof and one of the appendices of the halo paper that this mapping from the recoded scaler back to the actual scaler well multiplying by it is

one-to-one and so it's preserving entropy okay that only works if you only need to think about the general problem my intuition is that it's possible but it's going to take longer than we have thank [laughter] you everyone for staying on so long I really appreciate the extra time thank you oh you're very you're very quiet on them oh I

think my microphones over here sorry thank you very much have a good day everyone and I guess if maybe we find a place to continue this conversation if anyone wants to follow we can definitely coordinated in the study club so thanks again everybody great thank you