ZK Study Club - Bulletproof implementation with Oleg Andreev

Transcript

good alright so I think it's kicked off this is the study club this is where we get together and we talk about paper a protocol a video sometimes and we kind of dig into it today we're gonna be talking about bullet proofs and an implementation of bullet proof Oh like I feel like you can introduce this even better so I'm gonna pass it right on to you hello everyone so my name is Oleg Andrea and I was extremely lucky to work with brilliant folks at my team at chain interstellar on the bulletproof

implementation in rust so if you can see the screen this is our you know the documentation page so today I'd like to gonna walk through the design of bull truce why why they matter and how how they actually work and gonna be the basis material for it would be the denotes that we wrote as a sort of expanded the condition for our library we dab into the paper and this is what we'd begun to so this will be the topic of today's conversation sounds good I'm

gonna meet myself okay yeah I'll try to kind of make several pauses so people could ask questions also I don't mind interruption so if someone feels that you know something was gonna glossed over then please come forward by the way do we do use the chat or do we have some like you know signal those things yeah I would say like what we actually need people to do is just unmute and actually jump in but sometimes we do also like if you if you

have a question but you don't feel like jumping in put it in the chat and like I'll definitely be checking in on that as well great okay yeah I I don't mind being interested in it anytime soon please do all right so what do we start with so what what about Bruce are the blood probes is a framework for zero knowledge proof and specifically it's a field for composing the rank one constraint systems which means that you can form certain arithmetic constraints and prove them into your knowledge and I call it a framework because it has it's

sort of it's a low-level protocol but also it contains certain building blocks so you can build your your own application kind of layer protocol with this building blocks and the build process is pretty cool because it has if you can a cool features that you could call what batteries included so one feature is that you could build constraints on the fly so it means that you can you not only use it for you know some static constraint system or so-called circuit that you can design it look once and then reuse many times but

you could also build those constraints on the fly with some custom parameters which allows you to do you know some kind of pretty cool you know protocol so that are not typically covered in literature on zero knowledge proof and another thing is that all troops come with the commitment skin right away so you don't need to implement commitments as a part of your circuit these come for free and form of Petersons commitments so these are kind of two notable features so the framework to keep in mind if you have some background on you know what the rank one for a system is so the the whale can in a structure there's this first say few

words about you know the what the constraints are then we'll dive a little bit into how they how it transformed them in a certain form that that allows us to build there this is the actual zero knowledge proof and finally if we have time we could drill into the inner product protocol which is the core piece of the Boutrous that allows us to get those compact compact proofs the the log log sized proofs so this is a kind of cool part and it's a separate probably construction so we can you know

kind of review this version so how to like think about this so what is it what is the rank one constraint system if you if you could open the documentation that would be great so we had this project called Dalek a bunch of 2d graphic libraries written in the rest and you should go to this URL Doc internal the Dalek dot RS and this will show you internal documentation for all the Dalek libraries and the full plan would be curve for 250 519 but you should click on the left to the bulletproof great if

this just one thing is this one of the links that you actually shared in the study club already yeah I did so maybe I'll just go find it and I'll stick it in a little higher up or like a little lower down so people can actually find it oh oh that's ok but you keep going and you go ahead a like so yeah if you go this bulletproof sedation's it covers both API and some code examples and the notes so if you scroll to the bottom there is the list of modules and one module is kind of special it doesn't

have any code at all it's called notes so if you click on the notes then will see this description of the bullet proofs which are like gonna melt on the math behind blue proofs and it consists of this front page talks about my notation so cover this just for a second so we're all comfortable with the notation and then there are three sections there's inner product proof in the table of contents there is rage proof description and there is rank one constraint system so let's start with just a few words on notation first thing if you open up the original

2017 paper from boons and others there are some changes in the petition that we deliberately make so they are more consistent and match our tone so will you use it first of all additive notation and second we consistently use uppercase letters for group honors or for the points and we use lowercase letters for the scalars also you may notice the that bold symbols like this bold why so bold is always used for

vectors so anything bald is of lectured and also the tilde means the blinding factor so things with so scalars would the tilde means some sort of a blinding factor and the generator B with the blind effect is simply means the orthogonal kind of secondary generator so that's that's our notation also we have the stable so if you if you want to really gonna compare our nose with the original paper there is a translation table that shows which letters are replaced you know overall the structure should be easy to compare now so what is a ring coin constraint system proof so

in the library we have tubes of potations one is specifically for the range proof when you want to prove that some number is in specific arrow range and separately there is a more flexible API and actually the underlying math is a little bit more you know connects extended for the arbitrary expressions so we're not going to spend time on stocking this you know specific instantiation for the range proofs but it would be informative to kind of show it a couple of four dots of Rangers to understand what we want to do in the Canon general sense so let's take a look at the restroom just to have a

feel of what are we talking about so if you click on this bulletproof notes range proof module this is the description of the ratios so as I said again we're not going to dive too much into this but this will begin like a setting in which you would can understand what the wrinkles face is too much so this would be start with with me this in a little bit we start with a statement that some number lowercase P belongs to an interval from zero to certain power of two so let's say 2 to 2 to the N typically it's like a 16-bit number or

low since 64 bit number or 32-bit numbers inside and as I said the bulletproof provides you with the commitment scheme so this number is immediately represented or is going to be represented as a Pederson commitment denoted by the uppercase P so we start with this very simple statement we want this secretly represented by a commitment to be in a certain range so to understand what the Raekwon constraint system is let's see how do we represent the statement in in a form of arithmetic expression we do this by breaking down the number into individual

bits and we represent as effective list powers of two by letters a from 0 to n minus 1 for each position and the binary representation of in other words we can use this angle bracket mean the inner product of two vectors so the vector of the bits and the vector of powers of two so we're kind of working towards expressing the the original statement in arithmetic form and since we need this vector of bits to be not any scalar but specifically zeros or one or ones we

should add an additional condition saying that the pairwise product of each bit minus 1 should be equal to 0 so this is like country-wise multiplication so now we you can see that now we have one statement where we kind of break down the V into the bits and now we also have an statements about the bits themselves gonna say that these bits should be actually bits finally so this is the list of the conditions that we have and there's one

extra step that we need to do you may notice that you have the in the top statement you have the multiplication of a clear-text value which is a power of two with a secret value which is a bit so this if it is effectively a linear constraint between the secrets a and V and we call it clear because all the like factors are in clear text so everything that is in clear text we gonna a conventionally call a constant and things that are secret would call variables because from the point of view of the verifier these can can vary even

though they're fixed with commitments but yeah but the can be chosen in secured by the improver but the second set of statements and these are all involved so this is not a single statements actually a vector of statements here you can notice that we have a multiplication of a secret by a secret so this is interesting so this is no longer a linear constraint between the secrets now it's can elevating the ranks is now not a rank zero system but rank one because we have a multiplication of a secret by a secret and in the rank one constraint system API we would have this set of

multipliers or multiplication gates that are effectively the constraints that have their special place in their voters where you have a secret input on the left secret input on the right and secret album and so to kind of fit in the framework we need to have separate commitments to the to the left and to the right inputs and that's why we have to introduce two sets of secrets instead of just one so instead of just having the vector of bits will have the a left which is a vector of actual bits and the

F R which is can a complementary vector of the bits with one subtracted from them this allows us to express the multiplicative constraints clearly that fit in the framework so we should have wealth secrets multiplied by the right secrets and in this case they should be equal to zero and the connection between the left and the right which we just getting just introduced this the set of third can I write bits complementary bits this again is a linear constraint and it's it's a vector expression so there's

there are n linear constraints in this third line so this is how you this is how we're going to build towards the rank one constraint system we want to have a set of multiplicative constraints which is this middle part I'm sorry and we want to have a set of constraints between any of the secrets so the the rest of this nodes are focused on this specific statement to build the most efficient instantiation of blue proofs for the range proofs but we are interested in going to the more generic ring in a ring quantum streets so we'll go back to the in a more generic one and

gonna continue there but at this point I'd like to gonna give it a little pause and if anyone has any question or or maybe a like comment that oh this is all clear we all know it so please don't waste their time please go ahead and and ask your questions right now does that mean that you can only build rank groups for powers of two I mean I mean for the limits of power soft or is it possible for a betrayer numbers great this is a great question so this you can think of this as a building block so this building block allows you to build rito-san powers of two but you can have

some number of those to express our which ship is whole range by constant you can adjust the expressions my say all the addition this set up these prepares to - you know something or you can kind of construct an arbitrary range with smaller power of two rich fruits does this make sense you cut off your leg I don't know what I mean to say you can construct the

arbitrary ranges with combination of differently sized binary range crews all right I think Peters asking a question I would like to ask about like what kind of developer to say you have to build a bulletproof so and what like gadgets and we have now or we do how deep when the low-level stuff do we need to go to build our zero knowledge groups on electrics thank you so the the only tool that we have so far is the arrest API to

build the low-level constraints and I can be shoot like guys thriller to which we discover so open the source code ensure to you so at the lowest level you have as API to multiply not all let me just some things where you allocate a multiplication constraint and you can form this linear combinations of existing variables also you could delegate individual variables and add

those linear constraints between the variables to the constraint system so these are very low-level building blocks and on top of that you could build gadgets kind of progressively in a fire in higher order an example of these gadgets is our cloak protocol which is implemented in a library called spacesuit for confidential assets so it has a rich proof implemented as a gadget and it has gadgets called split and merge and in zkv M which is another project that uses cloak you have even can higher-level tools to build boolean

combinations of an arithmetic expressions and these are automatically arithmetics and compiled to Lisa VI so it's it's just gonna stack or frost api's that we have so far and the there's gonna plenty of code to look and see how this all composes together I city can't what about like for Bri images of for some different kind of pressures isn't some leverage on top of that to check these things we have a great like to request from from that plot some kind of generic GK interface

back-end here it is still in the PR so you could look at this pull request number 279 I haven't got time to you know do proper review of this but this introduces kind of like at adapter API to to plug into some other as you know their system so if you have some code that implements like a hash per image that works with this back-end that you could get it use it with bloopers however there is there is a problem with in a very complex circuits in relation to bloopers

because unlike zeeky zeeky sucks for instance the verification time is linear and the proof size is logarithmic so for instance the sha-256 preimage would probably like a single round would be producing a pretty large proof maybe you know 10 to 20 kilobytes and also verification time would not be pretty sure it would be no maybe up to minutes so we can like be the particles that we were focusing on are those that are getting more lightweight where we could avoid building a gigantic circuits so that that's why we don't have a very

good you know in a simple code to do those things but I'm pretty sure that you can pretty nice in a Google built in a collection of gadgets to to to many people eat you know hashes and do the left/right shifts and source and stuff like that so I'm pretty sure that should be easy to yeah thanks so pull requests looks really promising and the first question that I would like to ask you almost answer about verification improving time in operation with snarks so and you say szeliga I think the proving sighs since Knox it's constant time so yeah I would like to know you can you get the drift operational

verification proving and calculation time in some kind of benchmarks or maybe Santa bees yes sisters very dramatic difference and between City Starks and and bull proofs we were not really spending time on you know comparing them on on in the same load because it doesn't make much sense you would not be for instance you would not be deploying you know watch a system doing the NSE cash like accumulator implemented a bulletproof that that's just like this is what the CT snacks agree is the different approach hand you Bobby

yeah so it's gonna the difference is so dramatic that it completely influences and drives your whole architecture so is the key VM architecture is completely different from zag Z or Z key snacks are easy cash for instance and you can do things in the KVM that you cannot do in Z cash with you know different trade-offs so so that's why like this way there is no gonna accurate head on had benchmarks showing that okay this circuit is performing this well and you know that's Ricky's prior that so the range proof makes sense to do in boot proofs and we have like remember

something like six hundred bytes for 64-bit right proof and it verifies on the latest Intel instruction set in under an millisecond so that's gonna the fastest bulletproof implementation by itself would get a fastest curve implementation behind it but and this is like a linear verification cost thank you very much cool alright so so back to the get a rank one constraint system so you you're gonna got a glimpse of how we transform our original statement into

a bunch of linear and multiplicative constraints so now let's take a look and how it's gonna work how come for generically in in a constraint system VI so I'll go back to the notes and specifically to the rank 1 constraint system proof notes so here we are so a Raekwon constraint sister API gives you not a single in a high-level commitment the V the value that you want to have a proof about but a list of those we have M high level variables so we call them and we have also like in the ratio for example and

low level variables which will be our inputs and outputs to the multiplication DS now here I'll make a little pause and explain the difference between those kinds of variables the high level variable is something that has a separate individual pitterson commitment and the blood groups so think of this as your external fact so if you if you build a system with like like I do with confidential assets then each individual asset will have one or two of those high-level variables in my case it's one for the quantity and another one for the

asset type if you if you have a single kind of asset versus it's a confidential transaction and Bitcoin for instance you would have a signal variable for one secret value secret financial amount and another for another one etc so you would have an individual Pederson commitment for each an external external providers commitment that already exists outside of the boot process let's say someone created a previous transaction and stored some value under some commitment this is your external fact and we call it a high level variable and in blue proofs that they have their own special place and they are denoted by the letter

V at the same time the bull provides you with rank one constraint system which means that you have the multiplicative constraints where you effectively have linear constraints in in addition to that you have a bunch of multiplication gates where you have this extra secret that that are connected through multiple key multiplicative relation and the cool thing of Boutros is that they provide you with a commitment scheme that allows you to commit to all these multi multiplicative wires to the multiplication base in a compact vector

Pedersen commitment so I'll explain what this means you when you create the proof you start with those high-level variables that you have up front but your facts that you want to prove some relation some statement about and then when you've going to form your statements you would find yourself needing can a helper [Music] variables to those we started with just one external fact the secret be and then we found ourselves in need for those

extra bits zeros and ones that we need to break the V down enter and when you have to do that then you so to speak allocate their multipliers in in the in this bulletproof constraint system and you have to choose those inputs to the to the multiplication gate so in case of the race proof you have to choose where the wish of those are once and we should those are zeros and all of these variables have sort of low level because they they were not provided as external facts you just create them as a sort of helpers and the cool thing you don't need separate individual Peters and

commitments for shook those worth fact it would be a linear in size because you would be wasting space for all these individual Pedersen commitments so what Boutros gives us is a single compact commitment for all this kind of wires sticking out of the multiple multiplication gates which are called left-right and output with the letter A and this is pretty cool so you have a in a very compact commitment told this multiplication gates so these are types of the variables that we have this is the one half of the relations that

bullet-proof provides us with it which is the multiplicative relation between the left right and output kind of wares and finally the big list of linear combination of all the variables that you have and in bullet proof so you have left wares for all the multiplication dates right where's output where's the external high-level variables and things that are called constants because the O's are clear text clear text values that I've been a constants from the perspective of the verifier and these bold uppercase W terms those are mattresses with weight so

effectively this statement says that we have some number of linear constraints that connect arbitrary combination of left-right and output wires on the multipliers the external B's and some constants and these are all linear constraints okay so that's that's gonna our set up and and the this is this provides the general general purpose rank one constraint system and I'll make you probably have a you know a little bit of glimpse how the range proof would work

in this but III could go gonna gonna one short round explaining a little click so in case of rage proof you would use one of the wire as a bit another one as the bit minus one and set the third one to zero and then you would create the necessary linear constraints between all the swears to describe the relationship between those so if you want the the left to be sorry if you want the right to be the left minus one then you would have a linear constraint just for that

where you would have something like weight one on the Left where plus weight I guess minus one on the right where plus nothing on the output equals minus one so the C would be minus one and then separately you would have another linear constraint saying that the corresponding output wire should be zero so you would have weight one on the output with all the other weights being zero equals zero and one extra linear constraint would be for the V expressed as powers of two of all this left where's where each

software is a corresponding bit in the binary representation of U so if you have a 64 bit range proof then what you would have is the 64 multipliers and 129 linear constraints so you have one linear constraint for the binary representation sixty-four linear constraints between the left and right where that can elements it to be a to be 0 1 and 60 for linear constraints setting the output wires to 0 so is the like it is the studying so far can I

clear before I move forward seems like yes cool or maybe I lost : s then medicine alright so okay so what with this in mind will oh yeah I talked about that we can allocate the multiplier we add the constraints we also have the such yeah oMG scalers talk about right now but this is also gonna cool accession to Boutrous well gonna come back to this as a media bonus point so let's go down into the kind of death valley

so I will I will not actually go much gonna deep into all this like everything gonna conversions but I will explain the the idea behind them as so so issue but I really feel like that you you could go and repeat the out and I oldest algebraic transformations but they're really in a very boring and at the same time gonna not much and not very interesting so the idea behind all the rest of this the foundation is to do and a three things what one is to what we have all these multiple constraints we have linear

constraints we want them to combine into one or two non vector statements so we can I need to flatten them and one a jazz thing so that's one thing that we need to do second thing is that we need to blind the secrets in this statement so we need to kind of transform that statement that is a term of pure pure secrets to transform it in a statement of the secrets that have some blinding factors apply and third we need this final statement to be in a form where we have the inner product of two vectors and a one giant inner product of two

vectors on one side that involves all these low-level variables so we could use the very efficient inner product argument and the sufficient vector commitment together on one side and on the other side or the linear combination of the high level variables V so we kinda need to transform and do some kind of super annoying but pretty kind of straightforward transformations of our statements to come to this form and once we get to this form then we could can easily turn this into kind of homomorphic we turn it into a statement all over Peterson commitments and then

separately apply the inner product argument so to do that we'll use basically a single cryptographic trick which is sampling a Fiat Shamir challenge variable for instance if you have the vector so this is where the trick is explaining and we use this trick three times so whenever you have a list of statements in a form of something must equal zero and you have the vector of those then you could flatten it by multiplying by the powers of certain random challenge variable and setting the the result of this inner product year so

now you have a single statement effectively saying that shouldn't polynomial in this random variables should be 0 and if this is true for each of those random challenges then certainly it implies that the original statements are all true of course we cannot you know test every challenge so we'll use the Fiat geometric where would kind of force the prover to commit to the to the inputs of the original statements and then we'll use the random challenge scalar to to compute this product and then we'll have

a you know very low chance that the the cheated and meet the resulting statement to be true so we'll use the statement to flatten first the multiplicative relation with the powers of challenge y and then we'll be [Music] where is it yeah so this is like the first one so our statement in terms of this ah sorry I missed it so we'll do this for the multiplicative relations and then for

the linear relations will you will do the same trick with the powers of Z so we'll have two challenges y&z so we'll flatten to them next what we're going to do so so far we're going to have to do two of those next the super annoying part is to rearrange the terms so that we could form the one giant inner product of all this like well level variables so this is super annoying and we'll just gonna scroll down to that but this really doesn't use any cryptographic tricks is just an algebraic transforms one algebraic trick is to L sorry actually like the Kanak cryptographically starts in the very end

where if we have the sum of two inner products and we want to combine them to one then we construct yet another polynomial in terms of a third charge scalar that we call X and we construct this very artificial polynomial so if we have like a by B plus C by D then we have this one here and the second degree of this polynomial will be exactly what we need so then using this trick we go back to our terms that we have at hand [Music] be sure you can see that on the left side you have the linear combination of

all the external factors with some combination of the challenges and end constants so the only secrets here are the high-level variables and on the right side we have this artificial polynomial and we only care about the second degree but the whole polynomial is a one giant inner product of two vectors with horrible mix of the Y challenge exchange and there's a charge I'm sorry there's a challenge is completely outside the school all right so this is our kind of first step there the second step is to blind the terms of

this [Music] a proton that we'll be using later is not Tara knowledge so it's made much more efficient by not caring about hiding data in Planet factors so you just prove that multiplication of two vectors is such-and-such without in a very efficient space to do to do that and zero knowledge you have to care about blind factors one step before inner product protocol so this is what we are doing it doing here so we are effectively expanding our polynomial which like second degree of

we care about with this extra blinding factors for each of the low-level variables so for the left worse we have the SL blinding and a vector and for the right wires we have the SR and those are so to speak separated from the original values with the second degree second power of the challenge X that we introduced in the previous step where we when we constructed this polynomial so it turns out that if we do the substitution with this extra blinding factors then our vectors in the similar product are properly blended and and and

we can expose them and they will not like information but the second degree of this polynomial will still be the statement that we originally needed to get a two steps before here all right so that's that's our second step so we have this left and right vectors there are this big polynomials and if we multiply them and take the second degree this would be exactly what we need which is what is described here in the section but the vectors themselves have properly blinded so it's easy to see right here that the the secret AR has the Arkana mix enough sr and the left and output

wires are blinded by SL in their left factory so this is our like first step so sorry this is our second step when we blinded the vectors and get the final step before the inner product part is to gonna combine all the pieces together to express the statements in terms of Peters and commitments instead of just just the scale much because so far we were just just talking about the scalars I'd like to make like another ball so if someone you know you know what lost the thread of discussion somewhere please these last question I'm dumb question there was a the wider Zed popping around

what was that about oh yeah yes is the remember that we have two vectors of constraints the multiplicative ones will scroll up here and the linear ones so the multiplicative flows are left by right equals output and the linear ones are those stuff with weights so to flatten each of this sets we need separate challenge variables so for the first one we'll use the powers of Y which is just we would call the challenge variable Y and to flatten the second set a world uses variable called Z so the samples

will be flattening the linear constraints you which is over here so you can see that the multiplicative constraints are flattened with the power of white and the linear constraints are all flattened with these powers of Z and there is just one quick you could see that we have this one extra that sticking out this is just for the it doesn't really change things but allows us to Afghan up in a cleaner formulas elsewhere because we would be using some extra linear

constraint without the power of 0 and and our notation this is gonna bold that in power Q that means that we start with 0 so it's all 0 is your index so set Q the first the first element of the vector would be the 1 and then that 2 power 1 and then 0 2 etc so the set would actually be separating later this statement from the first one we have two statements so we will be kind of merging together the oh yeah you can see it here so we'll be just adding

together the flattened multiplicative constraints with flattened linear constraints and then they themselves are separated by this extra power of Z so does this make sense so far yeah cool all right yeah so after this form we just have this one single non-doctor statement which is then transformed into this horrible you know like inner product construction with the second degree in blend factors all right so the third step is to make the statement terms of the commitments now let's break this down in two halves so

we have one half that has the sir product second degree of this point and the other half which doesn't have any inner products it's just a linear combination of the higher-level variables so let's zoom into this left part with just high level variables if we remember that Peterson commitment is this construction where we have the value multiplied by one generator plus some blinding factor multiplied by their terminal generator then we could build this in a diagram where we have original statement multiplied by the primary generator and of course we'll remember

that we have the polynomial so we have a bunch of terms that we don't care about so the this central part will be the second degree of sample interval that we care about and all the other degrees will be think of this as committed away right so we just want to form commitments to all the other terms of the polynomial but we don't really care what they are what the prover has to compute them the verifier doesn't care then we take this statement with appropriate manufacture smart multiplied by the secondary generator be Tilden and correspondingly for those terms that we

don't care about but we don't want to lick them so so there are plenty factors for them and finally we'll add those two statements together and we can add them because the generators are talking also if the resulting sum is true then the individual portions are also true and this allows us to use the homomorphism of our group to extract the Pedersen commitments from this G's and maybe Tilda's into the Peterson commitments in in the first column in the second column we don't need to apply the blinder factor to all this in a constant and clear text values so there's just

zero added this these are all variables that are known to the verifier and you can see that we have this commitments ti2 all these other terms of the polynomial that we don't care about but these are proper Pedersen commitments that we have to transmit so we commit to to the whole polynomial and then we get get a chance to squeeze the challenges and finally as a result of adding all this blinding factors we have the t tilde which is the synthetic winding factor which is not really by de factor is just our artifact that we need to have so things are balanced right so if we are adding some plain factor over

here then to make the equation work we need to add a corresponding value on the on the other side and these t TI tilde would be blinding those blenny factors over here so this whole T T tilde X is not going to be secret it's going to be transmitted but it by itself will not gonna look any information so if you look now on the left most column kind of transition to the bottom row now this is our statement from the verifiers perspective in terms of the commitments not in terms of the secrets which is pretty cool right so we now have the

statement to check where we don't show any secrets anymore we just have the commitments so that's first half of the first step the second half of the third step is the other side of our original equation which is the inner product and this is this also requires some preparations before we get into the unit for each argument so remember that we have this left and right lectures that are blended here there they're a little bit ugly because we have all these powers of Y and powers of X sprinkled all over the place and we need to make some transformation to have clean commitments to those

low-level variables if you remember I said that all these wires onto the multiplication gates they are all nicely committed to using vector Peterson terminus where no matter how many you have you just have a constant number of points representing the commitment to them so we'll do a little transformation will begin a factoring out this powers of Y to get a-movin there on the other side so that we could have a clean commitment to the left and right worse before we even know their challenge 1 so we're effectively what is happening here we want to move

this for a fly on the other side and oh I'm sorry this is the this is the definition of our vector peterson commitments so we have a bold g which is a list of generate some generators the ball h which is another list of generators for the the the right wires and all of these generators are all orthogonal so all the generators including the be detailed the list of g's and the features they're all orthogonal to each other so the they cannot like mess with each other right so the electro peterson commitment is the commitment to in our case its commitment to two vectors plus the

spline effector will be children and it's kind of like arbitrary shows but it really mattered we have a three sets of vectors so we commit to the lesson rights in one we call it a inputs and to the outputs we commute as a output so this way we'll have a kind of clean construction also we have some additional help or a notation to you know minimize the amount of noise and this is the thing where we can factor out the powers of voice on the other and a side of the right right factor so we're going to do the similar kind of diagram construction as we did in the

first half where we take our description of the left lecture and the right vector multiply them by corresponding generators and add together to form the statement in terms of the commitments so we want to the goal here is to take the commitments to our low level variables which are AI and a Oh including this S which is the commitment to the blind factors and get to the form where we have the the vector like the left factor and the right vector

expressed you know clearly so this allows us to can a bind the our can it artificially constructed vectors of scalars to the commitments of our low level variables so will like it will be a little bit clearer how we use it in the inner product argument but the gonna take away here is that we we have all these lower level variables we need to have commitments to them and then somehow tie them to the to this to artificial vectors that we'll be multiplying in the format that would be friendly to the inner product argument

to kind of finish up the the proof so let me pause here for a second so if anyone has a question or maybe a gonna glossed over some things still here yes yes I don't know if you see participants there's a little button called participants you can actually see are you going but unless that was quite

hardcore so we need time to process this yeah so yeah the good thing is there's a you know all the details are in the in the documentation so if you want to can it really slowly could get through all the all the steps they're all you know carefully preserved but the canal you know the big takeaway is that we have these original you know vectors of statements we flatten them now we have this you know horrible flat statement which we want to rearrange into this inner product on one side and some you can a linear this statement about the high level variables on the other side

and then we for the photos like horrible part on the on the inner product side we need to extract the commitments like better commitments to all the small little variables and tie them to our vectors and then as a final part we need to prove indirectly that these vectors when they multiply they give us the proper left side which we had love without wasting linear space so that's like the final in a cool part of the book process that can it gives the you know compact comforters okay so so if you're gonna you know

take my word that this lesson right vectors are tied to this vector commitments to the low-level variables in this shape then we end up with this statement where we have some point P which is the inner Procera which is this connect the combination of the left and right vectors and this H is now connect transform it has this hat because we moved the powers of y2 it's sort of like transmute of generator but doesn't really change the semantics of this so this equal to this combination of the

commitments to the inputs and outputs of the multipliers and the blen effectors and at the same time we have this TX which which is the evolution of this blinded at the flattened polynomial from the from the previous step now the thing to keep in mind is that L and R can be simply transmitted to the verifier and the verifier could check this relation to to that statement and then simply multiply the l and r to get the TX so they could do that and this would be completely safe and in zero knowledge

because the L is flying it R is blinded and if you multiply them and get this property X which you for future kebab over here into the high low levels and Ebisu the the only gaucho is that l and r are vectors of the size of number of multipliers so if you have let's say 64 multipliers then you have to transmit two times like 128 scalars so that's gonna win your size of the proof so that wouldn't be very nice and to going to compress down this proof and avoid

transmitting the left and right vectors Sinclair attacks we need the inner product protocol which is the final step so this is the step where we say the we have an indirect kick commitment to this left or right vectors and we have their result of the on the multiplication of those and we simply want to prove to you that we we know those lectures and we committed to them but we do not need to transmit them as a whole so we can transmit some you know get a smaller small amount of data to prove that so that would be our final step the inner product protocol which is oh this is

work group for all it the link is that is over here so if you go back to the notes this is the inner product proof a separate link where we start with this a little bit kind of abstract annotation to to kind of keep things clear so we forget about the powers of Y powers of X powers of Z all those weights all the stuff we just focus on the one thing that we have two vectors of scalars and we have some result of their multiplication and we have this commitment to those vectors with

generators G and H and we want to prove this relation so what can I simplify things we'll have just a notation of vectors a and vector B and so we have the C as their multiplication so he is eight times be like in a product and the point P would be the kind of unblinded commitments to the vector of a and vector B all right so we need to prove the knowledge without zero knowledge so we assume that a and B already you know are not not having any sensitive sorry detail clicking information so we need to prove this relation that P is this this commitment to to the vectors a and B and

that's lowercase e is their inner product now to kind of do that we first do the flattening right so we have two statements one statement and another and we need to flatten them and we'll use exactly the same trick as we did before so we have yet another challenge w which would be applied to the second statement and remember that the first one is in terms of the group elements and second one is in terms of scalars so we also need to bring it to the to the group elements with the orthogonal generator in our case it would be B so it's sort of analogous to to G and H so we'll use

the challenge W and also throw in the generator B so now adding everything together we get to kind of this form doing it gonna a little bit of renaming so so we don't have to worry about extra know kinda clear-text others we see this nice form where some point be a prime that we know is sum of a spy generator G B's by generators H and they are in a product by some extra point Q which is just the this you know can challenge multiplied by the orthogonal generator B and finally there is kind of one can a

compression trick and the inner product for are called easy recursively until we compress things down to the vectors of the length one so so I will just gonna explain this and this will be basically the end of the of the story tying things together so we'll look at this we'll start by splitting each of the vectors a and B into two halves so the a will be consisting of the low half and the high high half so if you have for instance 64 elements then you will have lower 32 elements as slow and higher 30 elements is a high high and we would be

easy err evil that go to you and since we like a recursive algorithm it will be UK because at each I said because the United Kingdom it's because each step it would be like case step from the can will be kind of splitting in half those vectors in K steps and K would be of course logarithmic because we are having having the vectors so it's a logarithm of our number number of elements so let's take a look so if we can choose the powers of this challenges and deliberately confuse this get a flattening of the halves of the vectors

onto themselves with these powers plus 1 minus 1 minus 1 plus 1 etcetera and compose our original statement then we'll see very cool thing if we open the parentheses then the cool part would be that we'll get a new point P K minus one we can in a new group element which we don't know what its meaning is but we'll see that the low and high have some nicely kind of jumping out together that are exactly the same as they were in the previous step

so this is a low by G low plus a high by G high so we're kind of kind of split in half they're those generators and this is exactly this same as a by G in the previous step while all the cross terms like low by high and high by low all the cross terms are sort of separated away by this and nonzero powers of this random challenges so what does it mean it means that we now have the original statement with a new point that is it is produced with shorter vectors remember

that we can flatten the vectors who took the low half x challenge and added a high half x another power of challenge so we can have flattened those vectors and we could consider this point but at the same time this point is exactly the same as our original point plus a lot of garbage-can across terms multiplied by the powers of this challenge so this means that we could repeat the step until our vectors to compute the resulting point are of length 1 and we would have the logarithmic number of garbage with the logarithmic number of charges added to it so this is how it looks like a you after first step of

doing that you would see this original point here plus the garbage plus it more garbage and this would be a new point so you could compute this new points through bite by using the shorter but you would not do this right away until you do the step once again and get down to vectors of length one so that you could construct this p0 through just one scalar a one scalar B and one multiplication of the single scalar and single scalar B so this you could compute with just you know can a constant size part of the proof which is simply this kind of 64 bytes of the

proof and you would have to add those commitments that we call it left and right L and our commitments to all these cross terms with like properly multiplied by the challenges you Jade right who so this is gonna tell the inner product works so to reiterate you you do this trick by compressing vectors onto themselves and commit to the cross terms so you only transmit the resulting just tiny we've been a pair of scalars and the verifier would be gonna hashing

those cross term commitments to generate the challenges and then simply verify that this statement is correct and gonna do to how the those challenges were computed the verifiers convinced that the prover has properly compressed the vectors on there and so they had to originally have proper proper long vectors that they did not receive and this concludes the proof so now we can plug in this proper P from the rank 1 constraints for this horrible you know flattened statement about the high level

variables and the low level like low level wires after the multipliers to apply all those things have this extra overhead of the inner product protocol which is committments L&R so this will be like logarithmic number of those plus the scalars and B as the final cut breast vectors and that's kind of how it's going to ties together the whole can a bulletproof system so in the end if we go back we'll end up with this one statement as mascara a pro not here but in the

hey Oleg I think we're gonna have to look pretty soon we've had a couple of euro to bounce but are you yeah yeah I think no this and now I have just opened to the questions so you show you the yeah I'm just saying that after you plug all the things together you end up with this giant one verification statement where we have the parts from the inner product protocol and all these kind of hanging pieces from the like other statements that we formulated so far so you just check this one giant multi scalar multiplication that's and that's

the end of it huh yeah yeah so anyone who survived so far could ask questions I think so actually put a question in the chat is bulletproof still the state-of-the-art protocol for range proofs well it depends on the years case oh by the way why can't they just switch to hear this so it wasn't a telegram it was in the chat in oh yeah yeah so what do they mean by the state-of-the-art so if you if you need to do the range proof with

well I guess if you just need to do the range proof then the bulletproof freely compact and fast with gonna probably even faster than Ziggy snarks maybe I'm not sure and the proof size is pretty small maybe it is but maybe if you have some other you know proof surrounded then can i if you don't just have the range property you need something you know other things to check then you probably would can consider portals for other reasons so I'm gonna not cut sure

how to just say whether it's just there but if you just need for the range Bruce it's kind of it's very fast and it's [Music] like doesn't have the trusted set up so you don't need to know set things up you just you just construct your statement and here you go with it like like a like Russian or signature or something so should be pretty convenient for that for the purpose oh and he just said thank you do you see the news yeah there you go alright see the friendly alright so deep

yes our our imputation state of the art in terms of all this canon own Zeki snark a politician so with that non paring like an a traditional curve so if you if you're not comparing with any new and I like city snack type of post and our application state of the air I mean thanks for one question was more about how would it compared to something like the green paper or the green implementation of words or how does that compare to what we just learned today and what you implemented so the green green you mean the remember one blurry yeah exactly I didn't appreciate how

detailed it was thank you for your time today cycle yeah so I'm sure where the green uses the in a Bitcoin curve or the I corrupted 519 or a strata note I'm gonna not up to date but our comparison with gonna get a second best implementation for the sec p duties by 256 K 1 we have something like you know 2 X verification improvement and would if mice like 3x and Manero has implemented the range proof so we're sure she's fine ante and the didn't do

this safely so they don't they don't build it over there ristretto group do you think oh it's like all over the kind of group for the cofactor yeah so it's not quite safe but we're like 7 times faster so I'm not I'm not sure which one Green Jesus another perfect not wolf thank you yeah I would say if there are any other questions feel free to put them in the chat I'm gonna sort of sign off now and to everyone who's participated so glad you're here and to those look and are

listening or watching actually oh like how can they get in touch with you yeah you can ping me on the on the group I have they're all icons of Twitter and github and - telegram handle so here is so you could just use that very good cool so thanks everybody thank you yeah sorry for taking too