ZK Hack Study Group – MoonMath Manual 2024 – Week 7 Part 2

Transcript

okay let's let's go over this week's uh material um yeah again uh reference from from a rare skills CK book okay so uh last week uh we talked about R1 CS in Grass uh 16 I think it's important to mention that R1 CS is no more the def facto industry standard right now so for snark right now the most part popular framework is uh for arithmetization is uh a Plage right so yeah plish Works a little bit different but I think if you understand rmcs you can you can just Google um

plish um there's an article called like plank by hand three-part uh article you can read that pretty easily um also in Stark you will use air right so a IR stands for bre uh inter intermediate representation so different Pro protocols they have different ways for arithmetization so so you need to beware that R1 CS is not the only thing so you can Google that right so plation err um after that part we are going to do the qap step right so qap basically just Lo range

interpolation uh we going and cuz from rncs we had uh like three matrices right called r l r and O we have three huge matrices with a lot of like zeros in between so that thing is not sucin uh obviously so how to make that uh succinct uh we want to squeeze that Matrix into polinomial that's called qap and also this encrypted polinomial evaluation is uh we can evaluate polinomial in a at a single point therefore we don't have to compare all the coefficients of the polinomial so in that way we just reduce like the Matrix

computation into polinomial and then into evaluation at some random Point therefore the proof is pretty short and the verifier has easy time to to to verify that right so in Grass 16 I think it it can be verified in like o1 time or o Logan time I'm I'm not sure which but it's actually sublinear of course so probably like constant time I think right pretty easy to verify um today we going to cover some the details behind uh the ideas right so last time we had three matrices l r and O uh the first step is uh we can take

out all the column vectors and uh do L range interpolations on them right so how to do that first for example I take this column vectorizing example um we have this we use them as a Y coordinates right so what are the x coordinates we can just use 1 2 3 4 like how many constraint you have you just increase this linearly okay yeah just plus one and we call this uh them labels so the label for for like the first entry is one so 1 1 2 0 3 0 and blah blah so we have a list of points right so seven points um we can do log range

interpolation on these seven points um recall that uh L range interpolation if you fed into that end points you're going to get a degree and minus one polinomial right so right now we have seven points we going to have six like a degree six polinomial out of this column Vector so we going to do the same thing for the for like every column Vector in The Matrix uh recall that we had five column probably last time yeah last time we had like um seven rows and five columns for each Matrix and we have three matrices

right so for each Matrix we can do this five times and then three matrices totally like 15 times of L range interpolation so how to do that I recommend you to watch this video I'm not going to go over the ideas behind the right now so yeah this graph is pretty clear actually so you going to do that four times right like each time you have three zeros and one one non zero point something like that and then you add this information together in the end yeah this is a the interpolation phase so yeah yeah just watch the video please so how to do that in Python

right we can use this uh Library called galwa it handles um finite field operations and also nonp we're going to use the nonp np. array to represent vectors and mates Okay so um I think this is self-explanatory you can you can understand this right these are the x coordinates these are the Y coordinates right so yeah basically just we are turning this points we write all the the x coordinates like here on the left as the

first input and also all the Y coordinates at the second input here okay so it's not like seven points is like two arrays these are the all the X in this uh x coordinates these are the the the Y coordinates okay and then we have to wrap them into nonp array and then wrap into GF this GF is some uh some U Prime field so so I'm picking some uh small Prime to make this computation easier so in practice you're going to use um py e. BN 128. curve order so that thing is going to take a few minutes to to process so I'm not using that here I'm just picking like a

random some random Prime small and to speed this up okay uh do lrange poly this is a lrange interpolation it's called lrange poly uh just do that you're going to get a degree 6 polinomial as expected and over this Prime field okay cuz we are feeding seven points into that um the degree of that is uh the number of points minus one so degree six okay pretty easy to understand this um how to implement this part in Grass 16 um this is the code I wrote um I think I think is not that easy to

understand at first clance um how to approach that let's look at this this function okay so nonp that apply along AIS you can see from the name that we are applying some function this is a function as input okay so this is a function the first input is a function we are going to apply this function along some axis so the second input is Axis if you say zero here is apply for every column if you say one here is apply for every row right so like a Tuggle here uh we are going to do like ration for each column so 0 0 0 apply which function this is the

function we we Define okay so apply to V Matrix uh to r l r and O right so this is basically like encapsulation of what I did here okay so this is yeah I think is pretty easy to understand this uh the confusion here usually is what is zero represents uh simply it represents each each column right so in the in the documentation I think it's not very clear so just remember zero is for every column and one is for every row and we are doing this for every column so 0 0 0 okay we have questions so far

[Music] no question so far right okay okay I got to continue so uh we had done L range interpolation for each column Vector uh we squeeze the matrices into 15 polinomial right um so right now we can build a qap formula so qap this part is pretty hard to explain [Music] um so this U is the result we got from last step so this U poly is the U here

so it is a vector consisting uh five pols I think right yes I think the yeah this is a vector of five polinomial because we had done this for each column and there are five columns in the problem right so V similar and W similar so they are the result form last step and this a is a secret witness generated by the by the prover right this is a pro secret uh this looks very similar to qap formula but it's not balanced yeah I going yeah yeah I'm going to explain

this later but just remember this is kind of the qap formula but it's not quite like there are some some other terms behind this yeah so so this is a general idea but but not the final version of the formula okay so how do we get this um yeah this part is very hard to explain so recall that in rncs we have this formula right so so the Matrix is like we got from arithmetization the the huge Matrix L * a and handar product is R * a = o * a so this was balanced and so the idea is there exist a

homomorphism from the RCs format into this qap format but I don't find like a formal definition in anywhere so I going to use the term loely so probably quote unquote homomorphism not going to appr uh like prove it uh but you get the idea like we have a an algorithm to turning rncs into qap using using this program right so we can do the same thing for for like every matrices no matter what arithmetization we have done we can do the same algorithm and turn that into this format so it works like

homomorphism but if I claim this I you have to prove it by but I don't want to prove it so so so you got the idea so like five five is a homomorphism five of L five of L it turns into U and turn this R into V and turn this o into W okay so this is the idea and don't don't don't blame me for not proving it please um so to expand this formula bit uh you see this U * a is actually inner product right because U is a is a polinomial no is a list of polinomial right so probably five here in our

problem uh five polinomial times like entry five uh witness Vector right so basically the length of U and the length of a they must be equal in order to computer the the inner product right so we call that uh A1 you our problem it uh stands for one which is the constant term so 1 comma X1 X2 X3 X4 I hope you still uh remember the problem we were working with right it was the the bipartite graph proving so there's no output so this uh the first term is uh the the constant uh term one and

these are the coloring for each node and there are four nodes and therefore this is a lens five Vector witness Vector secret one right and this is uh five polinomial so so lens five lens five we can do inner product uh between them so just yeah A1 * U1 and plus A2 * U2 and plus blah blah blah okay so this is the inner product and uh it is easier to understand this in in written form but in Python is a little bit work right so so to implement this uh the idea is to

use I think I can minimize okay the idea is to use uh some functional programming strategy from python right so python has these two methods uh first is called map second is reduce so this is the map reduce uh pattern right it it exists in many many programming languages so in Python they work in the following way so how does map work right for example we have a list of polinomial in polinomial and the weakness Vector is um is n right so lens n and and lens n uh if we apply like

map parentheses uh multiply like most multiply uh multiply is a should be a function right so the first input is multiply and the second input is a is a Polish and third input witness what we get is we are going to apply this this function input into like every pair right so for for for this to work you have to pass in two two iterable um elements so in Python there are list right you pass in this list and uh python is going to okay I got to map that function onto like

this pair and then the second pair and blah blah blah and until the last pair okay so the result is just multiply I going to multiply all the pairs and then store the result into a a separate list so this is map in Python okay so basically I'm mapping a function onto every pairs of some intervals okay so reduce is a yeah reduce is a little bit harder to understand than map so reduce is not actually a good term for this I I think is easier to

understand if you call this like like folding like folding a a an iterable into one element something like that right so if I do reduce reduce sum so the functional input is sum so what I'm doing here is okay I going to take this and do the sum between the zero element and the first element okay I going to take the sum of these two so so I got a result here right so this the result of the first step and then okay I going to have P3 * W3 and I going I'm going to have

some appli to the previous result like again so you just keep adding the stuff so the final result is you are folding a list an itable into a single element because I'm doing some for this two I got to so this is the result I'm going to do some again and again and then repeat till the uh the last entry right so I'm folding a list into a single variable by applying this function many many times basically this will reduce me yeah uh yeah pretty easy to understand map maybe

takes a little time uh to understand reduce but I think the idea is pretty clear that this is very similar to what we had done here okay so this inner product is perfectly represented by we do map M uh multiply first and then to to reduce some so this is is exactly what is happening in inner product formula so if I want to uh improve this code a bit I think I GNA add some something like a lens check here to check police and vitness they have the same lens in order to to to make this more more like

engineering part you know okay so they should be have having equalent okay uh question so far no question kind of continue so um where am I um oh yeah this is um an example for map yeah just map this Lambda function also Lambda function is like inline function

without function name so we're going to use this once and then just drop it okay um Lambda function I going to I going to apply this addition onto every pair of the the elements okay this and this yeah and reduce is just keep adding this and folding folding a list into into a single it okay nice pretty easy to understand nice nice so the question we left was um I I told you that the qap formula looks good but is not balanced okay so why is not balanced because um

UV W they are all arrayed with u five polynomials of degree 6 so look back to this formula uh we were having like a list of pols of degree 6 degree 6 and it's still degree 6 on the right hand side so immediately you can tell something is wrong because on the left hand side we probably having a polinomial of degree 12 because we are multiplying two polinomial with degrees six okay so right now left has a degree 12 and right has degree six so it's not balanced we had to plus some

term with a degree 12 polinomial to balance this out right so yeah I uh I can give you some ideas here so why I said the left hand side is a degree 12 because you can express this final inner product as uh C1 x to the 6 power plus blah blah blah okay so similarly we got C2 * X to 6 so after multiplying this to polinomial uh the highest term you get if C1 * C2 is not is non zero you will get some uh High term of x to

12 for sure okay so this is degree 12 and this is degree 6 therefore we have plus some uh some polinomial some like artificially crafted uh polinomial of degree 12 because yeah because this is addition um so after addition the final degree is Max of this and this okay so so we have to do a degree 12 here so how do we construct this uh some poly oh oh forgot to mention that uh why is not balanced can be view in this way

because remember that from the R1 CS equation although the formula is this part right but we can view that as uh we have additional zero Vector here so we can plus like an additional uh zero Vector but doesn't change the the result right so what does it look like um so just a bench of zeros seven zeros as a column Vector okay so recall that we were doing this homomorphism five on everything right so 5 Z turns out is non zero in Q

formula okay so so what does it turn into it turns into some this some po okay uh question I heard something uh if you don't have question please just yeah just mute your mic please uh thanks uh where am I uh I'm saying I'm saying what oh I I'm here I'm here um yes so right now we have to artificially construct this some poly right so how does it work um so in the graph 16 paper it says uh this

polinomial is is having the form HX * TX so so this TX is a public knowledge is known before um The Proving process because is corresponds to the size of the constraints so in this problem we we are having seven constraints right so we are doing x -1 * x - 2 until x - 7 and for example imagine you have uh like 100 constraints then you can just keep adding terms here like multiply minus uh - 8 - 9 and yeah to minus uh 100 right so this is some public

knowledge it always work this way uh so why does it work I'm not sure about this part okay this is my my understanding so so how do I understand this problem is we can do L range interpolation through like these are labels right so so basically we are interpretting this uh the zero Vector so the labels are 1 27 so 1 2 3 4 5 6 7 the labels are fixed and the Y coordinates are always taken from the vector so so one Z two 0 blah blah blah to 70 uh we have to find a polinomial that goes through all the

points at the same time therefore you can see that basic Bally this say so this point is saying one is a root okay so two is the root and blah blah blah 7even is root and the easier I mean the easiest polinomial you can come with come up it is this one okay so imagine plug one into this the polinomial becom zero PL plugging two into that okay so um yeah so um after we know what is TX we can compute this HX so this HX is deduced

polinomial from from like the the entire equation right so right now we have everything we have we know what is U * a we know what is w * a and we know what is uh V * a so and also we know what is T So this T is always public knowledge therefore the only unknown here is H and you know what to do right so when you have only one unknown in a in an equation you just move it to the other part and then just solve for it like simple simple algebra middle school algebra maybe okay so yeah just solve for H and

then you get this formula I I want to make a comment here is when you having too many constraints this operation is pretty is pretty time consuming actually it's pretty hard to do this um polinomial Division I think there is some uh like faster way to do this probably like Fast folate transformation fft you can speak this up but yeah I need to do more research cuz I haven't implemented that in my code um yeah uh I think if you do this division like like in in like a stupid way like

me yeah if you do this uh this is going to take a lot of time to compute okay so there's room for for improvement on this computation and so how I implemented uh this part is is uh yeah I just type in t uh like manually uh here I'm saying like the polinomial like the the the coefficient for X term is always one right you can see the coefficient for each X is always one so the constant term uh I handle the negative number in like a St yeah yeah I just manually say curve order minus one

this is is a like equivalent to to the to the negative number minus one right cuz we are working in a finite field of this order so so basically we are working in scalar field therefore the order is curve order right recall that if we uh we are working in base field the the order is field modulus is a different constant okay I got T here I'm going to explain this later because it's not qap part is related to um to the to the zma so so we're going to discuss this

later and we can compute H here using naive approach okay just just yeah do the formula here this uh sum Au is uh comes from this inner product okay you already computed them so yeah yeah so so this formula is this one okay yeah I computed H * T just for for easier programming okay so yeah and you assert your math is okay so this is uh this formula so you

assert this is uh true okay okay question so far no question no questions nice nice nice yeah so that's qap that's everything for qap okay so you already have qap formula so what's next is um we can do the Su part right so so why we need to improve this protocol because imagine that if you are asserting no I mean if you are comparing the equality of two polinomial right for example um here if like a verifier comes

in and checks the equality of this equation imagine you have like a milon constraints in your circuit then this is going to take a lot of time from the from the verifier right um so so to make this succinct or also you're going to have a long proof okay so it doesn't follow the definition of a Nar so to follow the definition we going to use show zma which says okay we are going to evaluate two polinomial as some random point if the result is the same we

can uh deduce that with high probability that two polins are equal okay so yeah if you want to study the idea behind this uh similarly to LR uh interpolation please watch this video uh they are both a visual approach uh which I prefer it's not very formal but yeah but I like it okay so if you don't want to know the proof behind it it I have an easier way to understand that okay so we are discovering sh polymer here by in an informal way okay so observation suppose we have a degree D

polinomial over a finite field of uh modulus p and our job is to guess is root so you take a random guess um theoretically you are generating a random number here just okay so your job is to take a random guess and um we only record your first guess so you only have one shot okay so you have one chance to to make this guess and then I claim that the probability of uh you got the correct result in first try is less than or equal to uh D over P so what is D recall

that D in the definition is the degree of the polinomial uh by fundamental theorem of of algebra we know that the number of rules is kind of bounded by the degree of polinomial right so when do you have exactly D Roots that's over complex number c but right now we are doing this over finite field P but uh I know that the number of roots is bounded because you can do better because in C you have the most like the ultimate form of factorization of polinomial you have like this number

rules uh so D rules right so in over fite field you can only have less than the rules so this is like the upper bound of the all the rules we can get and over P what is p because we are taking random gas from a finite field of uh modulus P which means we have P elements uh P field elements in the field okay so this is all the possibilities there are P possibilities and the the the answer there are potentially bounded by the answers okay so I'm saying that the uh the probability of in first shot I got the correct result is bounded by by this

number so uh recall that over this finite field P for example in Grass 16 we are working with the scaler field the the modulus ending in 617 that one right that uh that number is huge okay so when this peak gets huge this uh fraction is approaches to zero okay so you can kind of say okay the probability of I take this random guess and I uh I got the correct result in first shot is almost zero yeah that's what it says here okay so so this is the observation um yeah uh I I'm probably

making this informal and if you want to figure this out please just read Wikipedia okay so so like something like can do better you can write this in like a math book okay so so so this is my my personal understanding don't don't quot me on that okay so yeah uh so this is how I learn math very informal um so this uh observation you can turn that into another form because right now we only care about comparison between polinomial we don't care about this this like the root equals zero okay we uh we don't

care about this form we what we actually care about is the pro the probability of Po one evaluate at this point minus poly2 evaluate at the same point is zero so you can see there is a connection here so basically we are breaking this polinomial into two but mathematically they are equivalent you know yeah because poly one minus poly 2 is is another polinomial for example okay I say poly 1 minus poly 2 equals poly and for each poly I can always come up with this two polinomial so no matter what okay so

they are they are equivalent um we are turning this this formula into okay this one this one okay um say this is degree D and then we say Okay poly one is degree D and po two is degree D also so so the probability of poly 1 minus poly 2 equal Z is the same as poly one equals poly 2 okay so we are turning this statement so here we are saying okay the pro the probability of I make a random guess I get the the correct result on on the first try is

very close to zero and here we are saying okay yes oh no question uh I was saying um so this is equivalent to saying okay I evaluate two polinomial at a random point and I got so this uh this result is the same like the pro the probability of I got the same result on the first try is very close to zero in other words if we evaluate two polinomial at some random

point and the result are equal we can kind of deduce that they are the same polinomial okay because this this prob uh like the probability is so low okay so the most likely scenario is we have okay poly one equals poly 2 so this is the idea behind schma but I still recommend you to watch this video because yeah he use a a visual approach uh very interesting here very interesting okay um but that's the uh the the main idea okay so why we were talking about this

because we want to make our ZK proof suing right so before this we were having qap formula where we have to compare every coefficient of two polinomial imagine we have like huge number of constraints and therefore we have huge degree of the polinomial then we have to do the comparison for each coefficient like many many times but right now since we have this observation we have deduced kind of deduced the the schma we can say okay we are going to let some trusted third party generate this random point and then we only

evaluate two polinomial at this point and we are only verifying if the result is the same so we turn like o n comparison into o1 right this is very easier to compute compared to um comparing two polinomial Okay so so we are making ZK proof Su sync in this way so this idea is pretty important so almost like in almost every single ZK SAR you have to use this okay so it's not like uh like some special thing for grass 16 is very Universal okay so please understand this okay this is

called schma uh very important to understand okay uh how to evaluate polinomial we're going to talk about that next time uh that thing is another story because we can just say like tell Pro and verifier like about this point because this point is supposed to be some random point which is secret so we are going to let some trusty set up ceremony uh generated this point and then we are going to evaluate them um based on the it's called powers of tow okay so we going to we're going

to let the trusty setup to that part and we're going to talk about that next week probably because we don't we don't have enough time obviously okay so uh we still have 10 minutes uh let me quickly go through the circum the the actual code okay so we that last time we we saw how circum Works behind uh behind Hood okay so this week we are going to read some real circuit from uh circum lip I think this is very beneficial okay so I mean compared to pseudo code uh you can just read the the real code from Real World libraries okay this is um so comparators

do circum this is probably the most commonly used uh library in cir okay so we going to figure out how it works uh I think and can of uh went through this uh in one of the exercises but but yeah let's see how circum Works wait hold up okay so in like a normal programming language you probably want to say okay how do I compare something to zero right um is very easy to do for example python you will say okay if the input is zero I

going to Output one one for True right if uh else if the input is one or two or three whatever the output is false which is zero okay so this doesn't work in in circum it's not that easy why because you cannot uh use this uh variable input in if statement or in statement or in for Loop okay because this in is a variable and we have to generate the circuit first right because we have to generate the circuit we have to know like every

single things here therefore we cannot say like for uh like comparing a variable to zero or comparing a variable to like in a for Loop right so for in a for Loop we have to tell circum that we are working for how many iterations before before the actual proving process okay so this makes uh comparing a number to zero very complicated actually so this is the wrong way okay in circum how to do it um you can find that decode here okay so in this file uh this template is called E zero uh takes an input in and

output out uh this signal in like without the uh marking it as input this is the intermediate signal so this is like a helper helper signal but in a witness we are including this in the busness but we don't have to provide it uh the value for in in our input Adon okay so this one exists in witness but not in input this is called uh intermediate signal so we are assigning the value uh yeah just be aware that um this uh how do I call it like like

like single single aror Double Arrow yeah yeah I think you guys understand like single arror means uh you are assigning this this statement to some signal okay so if you do like like double error this double error uh means uh you are assigning this value to a signal and also create a constraint so the difference is single error does not have I mean does not create a new constraint so yeah this can be pretty dangerous because you want to you want your circuit to to be to be fully constrained in the end okay so why do we have this single error because we

can do division in it right recall that if you uh if we create a new constraint we can only limit ourself into a rncs scenario and therefore we can only do plus and multiply but if we do this we can have more flexibility here to say okay if in is not zero then I assign in this one over so so we can do this operator here this question mark here also the division here so it's not possible if we do that in double eror okay so um here we are saying okay so if in is zero we assign one over in into in otherwise we assign zero into so

basically here we are checking that uh if the input has a multiplicated uh inverse in the in the field uh because every nonzero element should have that inverse based on the definition of field so if it's zero then it it does not have the inverse so that's how we dis uh distinguish um the the the the zero zoness of the input okay so yeah and also here you have to flip the result because um for example if if we have like nonzero element we are going to do in is 1/ in and then negative in * 1 / in this is 1 and + one is zero means

the thing is non zero because zero means uh false okay so yeah we have do some manipulation here but yeah I think the most important part is to distinguish um why we have single error and why we why we have double error yeah okay that's is do you have question on this one no nice nice nice no question um that was a zero so so you can kind of think this as the in end gate as in like traditional digital circuit right so a zero is the most fundamental gate in in this file because

we are going to use it a lot okay so for example in is equal so why we why introduce you the this template first because it is used here okay so we have to cover a zero first understand is equal um is pretty easy to understand now because we can just take the difference if the difference is zero we can say oh okay they are equal okay so if the this is uh not equal then the the output is is false here okay so we are using this template to distinguish the the equality of the two inputs and yeah the

the thing to learn here is if you have multiple inputs in circum uh usually you want to do that in in Array okay so input two means the input array has you should provide two elements here okay so this yeah this is pretty uh pretty easy to understand um the difficult thing is is less than yeah this one is pretty confusing to me like half an hour to to understand this properly going to walk through uh two examples um yeah just notice that n two Bas is used in less than so we want to go over non to Bas first so basically this template the the

functionality is to use um this template to convert a field element to is binary representation okay so yeah is pretty hard to understand the code but if I give you an example it would be easier okay so just remember that lc1 is used as an accumulator so this is like the sum of of something I going to show you later okay so this E2 it is 1 12 48 so basically 2 to 0 2 to 1 2 to2 to to three you I think you understand this right uh basically we are converting binary to decimal right like this corespond to the to the

rightmost bit and the second rightmost bit like this okay so let's go through an example how this works uh consider a decimal five so like a field element or decimal whatever five equals 01 01 in binary right so we are feeding in as five this is binary representation and in this for Loop uh first at the the very beginning we have E2 equal 1 you see this V oh forgot to mention that this V is uh is not included in the final output of the proof so this is like a helper um variable right you declare

that as war and you can do like normal like programming thing on that so so they are helpers right so in the final like when you generate the proof or generate the witness whatever uh these War variables they are not included okay so so they are just making this math uh easier for you okay so initially has E2 = 1 lc2 this is the accumulator equal Z okay call 0 equal 1 and uh we first do like right shift but uh remember that I Cod zero for the first iteration so we are not doing anything here okay so we

are not right shifting because we are uh right shifting zero so so no effect and and one so the result is one so recall that when you end one to something um very likely you are extracting that bit okay so here we are extracting the rightmost bit this which is l SB okay so the we are extracting the LSB and store that in out zero now I is zero okay out zero is one and uh we do we we check that the output of that bit is either uh either one or

zero makes sense okay um we increment the accumulator by out I which is out0 1 * E2 E2 is one now so the accumulator is one and then the increment E2 uh we added to itself so E2 now equals 2 because 1 + one okay so that's the first iteration here and we go into the second interation you can see okay we are red shifting input by one bit therefore CU we already work with the the LSB here we just do right shift and to to discard hard this bit so so now it becomes 0 0 1

0 also the uh the end one we are extracting the bit here so you only have two cases right if this is one you got one if this zero so you got zero so so the way I understand N1 is you extract this bit okay so recall that E2 was two lc1 was one uh this was the initial state of the two two vs okay so extract the LSB at this moment which is zero we assign that to out one um increment the accumulator so since this bit is one we

are not incrementing the accumulator so no effect accumulator is still one and E2 equals four okay so we are just repeating this process and then okay so in iteration three we do something like okay I shift this by by one bit and then extract the the last bit which is one and then I increment the accumulator based on what my current E2 is so in third iteration it should be eight so I have this final oh no no no I mean no in in the next iteration I increment the accumulator by four so 1 + 4 = 5 which

matches our initial uh input so why we were tracking this accumulator because we had to constrain this uh circuit to say okay the accumulator equals the input in the end therefore our computation is correct okay so that's why we keep track this accumulator okay so yeah I think this is easy to understand after I provide this example uh should be good now um and we understand how to turn that into binary now we go back to this uh this uh last step template okay so this was pretty confusing at first glance um so let's take a four bit example uh say 5 equal 0

1 0 1 and 7 equal 0 1 1 1 okay so um we are taking this four bit uh numbers take the binary and so what we we are doing here is we take the first input in our case is 0 1 0 1 we add uh 1 0 0 to it why because this is one left shift by four bits that's that means we add one to the left so we we scale this number up by one bit that's what is doing here okay so after the scaling um we do a subtraction

we take the diff uh the uh the difference of this scaled number we subtract that from U now I mean we we subtract the second input from from the scale number so in the end we got something like this so how do we distinguish the if it's like greater than or less than so if the the the MSB the most significant can be at a zero it should be a less than b because if we have this at zero it means okay we don't have

enough values to subtract this number therefore we we borrow this carry uh like this carry bit okay so if we got zero here means we don't have enough values here in the original form to to subtract the second input there therefore the first input should be less than the second input okay so if we have one here that's another story right so we if we have one here that means okay we have enough number like here in the last four bits already to subtract the second input therefore we don't even have to

borrow anything from this Carib B uh so in that case the the end result is MSB equals 1 that means the first input is greater than second input okay so this is um a universal way in in circuit to comparing numbers yeah like usually it's done in this way so pretty important to figure out how it works so the idea is just I have this Carib bit here I just subtract this scale number with a second number right and then I see if my carry bit has been

changed if change uh it means the the first input is is smaller right yeah and there are a few other templates uh pretty easy to understand because they are all using this less than template V Vis cover yeah I think the the difficulty is understanding lesson if you understand this uh pretty easy to understand the other time okay okay so that's everything for today