Episode Description
Corey and Jessie teach themselves the basics of ZK cryptography by going through the ZKDL Camp book by Distributed Lab.
Watch Episode
Transcript
Click to expand transcript
It’s a Bitcoin podcast. The only one that’s making your money you listening to the Bitcoin market. So hold on. Hell yeah. >> Welcome to the live stream about teaching ourselves some cryptography on the weekend on a Saturday at >> in the afternoon. >> What are you guys doing on your Saturday? Come join us. Learn some uh learn some cryptography. Learn some maths as the Europeans say. Uh for those who are new, we’re streaming to multiple platforms at the same time. We accidentally recorded the first episode instead of going live. Uh so this is the second episode. In the first one, we went over uh essentially the book that we are going through, which is called ZKDL lecture notes from distributed lab, a Ukrainian group uh that does uh applied cryptography for various different projects in the web through your crypto industry. Uh, right now we are I don’t know if I’m on the right page that we’re on because I don’t remember where >> I’m on. It’s No, the page that I’m on is 14. It’s a It starts with the mathematics crash course. >> Okay, >> that’s where we left off last time. >> All right, cool. So, what we’ve been doing is uh try trying to pre-eread a little bit uh during the week so that when we record on Saturdays, we’re not looking at the content with entirely fresh eyes. that helps us kind of parse things a little bit faster and helps us have conversations about the actual content versus just um getting stuck on things. So, with that said, um I don’t know if you want to kick it off and read the first part, Corey. >> Yeah, I’ll do that. Let’s see. As any cryptography sub field, cryptography requires a solid knowledge of mathematics. While the practical development of cryptographic protocols might not include the need to understand the whole underlying theory, much of it typically still arises. For example, one might need to implement the elliptic curve pairing operation verification in a zero knowledge proof system or RSA encryption and decryption methods in circum circuits. In case you specifically develop a zero knowledge system from scratch, there is no need to explain why you need to understand underlying theory. This part of the book is dedicated to the mathematical background required for cryptography. Namely, we will cover essentially specifically t essentials specified in table one. So section three will handle number theory which is modular arithmetic. Uh ring was that zspace and field z I don’t know how to say that formats little theorem. I don’t know what that is. uh four abstract algebra groups subgroups fields prime fields um fp isomorphisms automorphisms I’m aware slash comfortable most of that five polomials quite comfortable with those divisibility lrange interpolation and schwarz zipple lema I don’t know that one >> I don’t know that one either >> six linear algebra basics this is a strong suit of mine basic operations over vectors and matrices seven field extension definitions of FP of M, FP to the M, F of P to the M, field, multiplicative subgroup, and algebraic closure. Um, so we’re all going to learn that. Not today. Probably go through like 10 pages, I imagine, today, right? We’ll figure it out. That’s our goal. 10 pages, 10 pages an episode >> where we uh yell at each other about what’s wrong and what’s right. >> So, this is not a mathematics book. So we will not prove every mentioned theorem or lima but we do provide reasoning for some key facts. We focus on the practical side of the theory providing examples and exercises for the reader to solve. Moreover, the solutions to the exercises can be found in part five for the reader to check their understanding. That’s interesting. We should try that. Um >> yeah, I did that already. >> Okay, great. Awesome. The reader should already be familiar with the very basics of the first four topics. So they will be covered for the sake of completeness in reminding the reviewers of the key concepts. The last topic field extensions is less frequent in the mathematics curriculum. So we will cover it in more detail. In case you feel comfortable with the aformentioned topics, feel free to skip them and move to the next part of the book. Finally, you are unsure about your knowledge, you should open the corresponding section and se and check whether you can solve exercises in the end without any help. I am not comfortable solving probably any of those except for the linear algebra part and most of the polinomial I think I bet let’s see how it goes okay I’ll read the next part so introduction to number theory as you can recall from high school math typically real world processes are described using real numbers denoted by uh how do you how do I say this just uh >> R space real space >> r space real space okay >> I mean r is real or not calligraphic but like I don’t know like double >> I’ll chat GPT it I’ll I’ll cla it asking how you supposed to say that while you’re while you’re talking >> I’ll say real space R because that that makes sense to me but uh for example to describe the position or the velocity of an object you would rather use real numbers instead of fields groups or paddic numbers uh however uh when it comes to working with computers real numbers become very inconvenient to work with the primary reason is that the set R is uncountably infinite. So the computer can only store the approximation of a real number as a precise interpretation of the real number would require the infinite number of bits. For example, different programming languages might output different values for quite a straightforward operation such as an addition 2.00001 + 2.000000. This becomes a huge problem when dealing with cryptography which must check precisely whether two quantities are equal. This is why the cryptography must work with integer-based formats. One of the earliest and most fundamental branches of mathematics is number theory which deals with the properties of the integer set Z. Although, as we will see later, we will primarily need notions of finite fields and groups further, the basic concepts of number theory will be used extensively nonetheless. So just a little bit of context in case people who are listening aren’t uh people who program um this is actually a really huge thing um in terms of having enough bits to represent like a floatingoint number. So if you think about like most modern systems now everything is like 64 bits and I don’t know if we should go into like what bits are just for people >> floating point precision. >> Yeah. So like just just for people who don’t know anything about computers who are just like listening because they see people talking about something that looks like Google deuke >> um >> bits are zero and one like your computer is basically parsing everything in terms of zeros and one ones at the end of the day >> um there’s a number of optimizations that are done by your computer processor that take uh programming uh languages that are like um let’s say business logic written in various different programming languages whether they’re more human readable which are generally the higher level programming languages uh to the lower level more machine code looking um business logic that gets encoded. So like in in the old days when the computers were not so smart, uh they had to write in low-level programming languages where it’s really it doesn’t read like a book. It reads more like um a bunch of commands in a bunch of places where you store things. So what I mean by that, you have a lot of go-to labels, jump statements, registers that you’re throwing values in. And these >> registers actually emulated punch cards in a lot of ways. I never played with punch cards. Did you? >> No, but I I I programmed in for 77. So like I’ I My parents taught me a lot about them. I’ve I’ve I’ve seen them and held them and played with them, but not like actually put them into machines. That was my parents job. >> My dad said he he ran a computer lab in college. He was a a chemistry major in the Philippines back then and he used punch cards and I >> My parents both both were computer scientists that were that were like punch card people. >> Interesting. That’s cool. Okay. So, yeah, that’s why we need um we need integers when whenever we’re doing cryptography. computers uh they like integers especially when you’re going to do like as I I’ll do a little bit bit of foreshadowing here but we’re going to have to do a lot of um modulus operations on integers essentially because what we need is we need really big numbers that are impossible to calculate especially in cryptography when the goal is to encrypt something in such a way that a computer cannot reverse the encryption um you’re trying to hide in plain sight and to do that you need really big numbers that can be turned into uh small numbers for computers to I guess verify things are being done correctly. That’s that’s kind of like the most high level explanation I can give. Maybe it makes sense to you, maybe it doesn’t. But if it doesn’t, just ask for clarification. >> It was interesting to me like something I I ran into was with like the concept of machine machine precision. And so like depending upon the bit size of your number, you then have a certain precision on how what what the difference is between any given number. >> And if you do a lot of um algorithms that are iterative, meaning they have multiple multiple steps in order to get to the end end solution and you need accuracy that is really really really high. You can re that you need to care about how machine precision adds up for every given calculation of the iteration. Otherwise, you end up with something that’s so far off base because you’re rounding at machine machine precision and then that that error accumulates over and over and over and over and then grows to be larger than the discrepancy that you need it to be once you get to the final answer. It’s like certain weird things that come into play when you’re doing with computers trying to represent numbers. >> Yeah. Because all the business logic essentially turns into math at the at the at the gate logic gate and transistor level. So like if you have math that that doesn’t make sense, your output of your computer program that you’re trying to run is not going to make any sense. And so like >> this gets into like >> buffer over >> even the representation of the math, right? And so like you your math can make sense, but if you don’t represent it well in the code >> um and care about some of the things on how like the math turns into like op codes. >> Yeah. >> Then you can end up with the wrong number even though your math’s good. >> Yep. Yep. There’s so many different and and then back in the day when error correction in in computers was worse uh like you you you want um you want deterministic output from a processor. You and and this goes beyond my depth because I’m not somebody who makes computer processors but computer processors are expected to be deterministic in output by everybody but they actually don’t operate deterministically under the hood. And I I don’t know how that works because those are that’s beyond me. Again, it’s for the those are for the big brains at Intel and AMD who make the chips. >> Look at that. Got to ask. >> Okay. >> You want to read the next section? This one. Division. >> Me too. >> Yep. >> Go for it. Let me put this back in. Trying to play with the the vertical stuff. the people who are watching vertically on like X and uh Instagram aren’t going to be able to see the text based on what we’re showing here, but it’s fine. >> Oh, should I like I can full screen. I can go like this. I can remove my notes. Let me see. >> Yeah, just do that, I guess. >> Just try and No, hold on. >> Let’s see. Division GCD LCM. We start with the most ba the most basic definition of number theory, divisibility. So definition 3.1 integer A is divisible by a nonzero integer B denoted B bar A or B is a divisor of A um if and only if there exists an integer K that exists within the integer numbers or the numbers such that A equals K * B. Um let’s see. Okay, that makes sense. Example three. Let’s consider the following example. 41 bar 1 2 3 since 1 2 3 is equal to 3 * 41 and then two was that not bar like >> so you just read it >> is not a divisor >> 41 is a divisor of 12 >> is not a 20 divisor of 29 since there’s no integer k such that 29 is equal to k * 5 >> that make sense I’ve never seen the shortand for that though >> yeah me neither I didn’t know that >> now explore some more basic probabil properties of divisibility So lema so bas given that that definition of lima 3.2 to divisibility properties for all ABC that exists within the numbers or the integers. Um see one is divisible by a any number is divisible by one. Oh is a divisor of one is a divisor of a for any number. I say a is not equal to if a is equal to zero then a is a divisor of a. Obvious a can divide itself. A is not equal to zero then A is a divisor of zero. Um and B is a divisor of A and C divisor of B then C a divisor of A formula called transitivity. So okay so divisibility is transitive. That’s the property you get. Uh five B is a divisor of A and B * C a divisor of A. What is that back and forth symbol there? I forget uh uh which one >> number five. >> What is that? >> Forgot. >> Uh it’s the same thing basically. That’s how I read it. It’s the same thing. >> Or like what is the what is the property there? Didn’t list it, but I get it. Basically, you you can do the same thing with a constant. >> Yeah, I think it’s also like trans >> multiply constant transitivity. This looks like transitivity. If C is a divisor of A and C is a divisor of B, then C is a divisor of A * A plus or minus B * B or alpha* A plus or minus beta* B for any alpha beta that exists within the integers. >> Yeah, I can I can look up what’s this called because it looks like transitivity. >> Uh here, let me >> fine. Okay, I get that. Basically, six follows from five. It looks like but it just it’s also transitive. So like six is a property of 4 + 5 it looks like in my head intuitively speaking. Anyway, we can keep going >> this way. We have a and b with b is a divisor of a. We can safely divide a by b. However, in the majority of cases, it so happens that a is not divisible by b making it hard to define the division of such cases. Um for that reason, consider one of the central theorems of number theory, the division theorem. Theorem 3.3 the division theorem says for any integers a and b that exist within the numbers there exists unique integers q and r that also exist from the numbers with zero less than or equal to r less than equal to b. So r within the boundary of uh zero and absolute value of b such that a is equal to b * q plus r. So that means basically like you get a remainder. So the >> there’s a number of there’s a number of uh divisor like there’s a there’s there’s a multiplicative you can add that will then give you the a number that’s smaller than the original number plus some remainder. This is basically the remainder theorem if you will um you have this this gives us two more operations which are useful. The floor operation which is a slashb or that those symbols whatever a divided by b is defined as q. This operation is a standard dividing operation. Um oh look at spelling earlier commonly used in programming languages. You can make a you can make a PR to the programming or to the the source. >> Yeah, I already did. >> Oh >> yeah. >> Mod operations. A mod b is defined as r. So this operation is a standard mod operation commonly used in program. So that’s the mod operation I think is where you’re going to spend a lot of time in especially in cryptography because you’re always used energy fields. >> Mhm. >> You’re the the >> Yeah, I’m trying to fix it actively as you’re reading. >> I can do mine. >> It doesn’t look like that on the tablet. >> I can do mine. >> Yeah, if you want to do yours. Yeah. >> So we’ll just blow this up. So that’s central >> where I zoom in. Yeah, nice >> remark. Uh there is one caveat with programming languages though. Often times the quotient Q and remainder R obey the aformentioned condition A= B * Q plus R but with the difference that the absolute value of R is less than the absolute value of B allowing two possible values for R including negative. Okay. Um, so an example of that we know that five is not a divisor of 29. However, definitely we can express 29 as 5 * 5 + 4. So 5^ 2ar + 4. Similarly, it is evident that 34 is not a divisor of 123 but 3 * 34 + 21. Okay. Compare the results. So, you have some code here. Let’s look at this. This >> I just ran this in a in a WSL instance. Uh, >> a what? >> Yeah. >> WSL instance. What’s that? >> Yeah. Yeah. Yeah. Because I’m on Windows, right? So, I just popped open VS Code on the computer that the tablet is streaming to and then I ran this. >> Yeah. >> Just just uh cuz there not not this one, but there’s another one where actually I didn’t I didn’t know. Um, there’s a there’s a way of a succinct way that’s Pythonic that I didn’t know before and I had to look that up. Not in this one, but the next example. >> I don’t have IP Python. What the Might be actually good to show. Yeah, I’m I’m installing a few things. >> Okay. I don’t know if I can spin it up real fast. All right, I got IPython going. Let’s see. I’ll change my my screen over to it. Stop screening window. share. See? Um, how’s that? Well, I just killed it. That’s neat. Some reason this does not like to be maximized on the screen. Wonder if I can just grab this. Nope. Cannot. Interesting. There we go. Let’s try this now. Add a stage. So, let’s pull a code. I don’t know if it’ll copy and paste from a a uh PDF very well. Let’s find out. I don’t like the indentions. I think I need to Yeah. 54. So it worked. So a divided by b is five. No the remainder. So yeah. So q is just going to be how many what is the divisor of a into b. r gives you the remainder. So a mod b. And so there you go. >> Interesting. There’s another error. Pupil is not supposed to be capitalized. >> Huh. I got mine. >> Oh, you’re doing on yours? >> Yep. I cop it. Copy and paste nicely. I didn’t do the indigents of the of the definition. >> Wonder if I’m running on a different No, I’m on 3.10.12. I don’t know. I didn’t like capital T and Tupole for the output. >> I’m 3.14. Anyway, moving on. Use yours. We’ll have to get used to the um what’s it called? The start using the scenes here. So we can like have scenes for various types of things we’re going to show. >> Mhm. That could be useful. >> Yeah, I haven’t used it. I assume it’s like stream labs. >> Yeah, you just set it up. It’ll All right, so we got that going. Division operations. It is common to check for any shared factors between the two numbers. This is where concept of greatest common divisor or gcd is short comes into play. Um greatest common divisor gcd of a and a b is defined as the integer d exists within the natural numbers such that d is a divisor of a and d is divisor of b. d is a maximal integer that satisfies the first condition. Um, one might write one might write the above definition. That’s a okay that’s the incorrect way of saying right. Uh, wrong. Right. One might write the above definition more consciously as GCD of A of B equals the max of D existing within N parameterized by D um, D advisor of A and D advisor of B. Okay. So there could be multiple divisor of both but you take the max as the greatest common denominator. There’s an example few pairs integers GCD 14. That makes sense. >> Oh, whoa, whoa, whoa. It went way further. >> Well, I’m reading offline. >> Okay, good. >> There you go. >> Okay. So GC to the one means doesn’t have a common common divisor other than one. This trivial two definition 3.5 integers a and b exist within the in the the integers are called co-prime if gcd of a and b is one. So three and four are co-prime in the above example. Mhm. Let’s see. As with any fundamental concept, let’s explore some basic properties of the GCD operation. So given that we have uh greatest common denominator, let’s see the greatest common denominator of a and b is equal to >> greatest common divisor. >> It’s the same thing. >> No, it’s not. >> Greatest common denominator and greatest common divisor. >> Oh, yeah. Yeah. Yeah. Yeah. Sorry. It is. Yeah. >> B is the same as dividend. Yeah. Yeah. Okay, I don’t understand one’s uh greatest common denominator divisor of A and B is equal to B interchangeable with is that what that means? Like B is a divisor of A. So if I guess yeah, you just read it like you just said it. So if if the greatest common denominator of A and B is B, then B is a divisor of A. Yeah. Like basically B will go into A. >> Okay. >> Yeah. These are like these are like things that we take for granted. >> Okay. Blown out math. >> That makes sense to me. I was just reading it. >> Yeah. >> Strangely. >> Yeah. Yeah. >> Okay. Um if a is not not equal to zero, then greatest combinator of a and zero is equal a. That makes sense. >> There exists a delta within the natural numbers such that delta is a divisor of a and delta is a divisor of b. Then delta is as a divisor of the greatest common denominator of a and b. Okay. If c is greater than zero, then the greatest common denominator of a and c and b and c is equal to c times the greatest. That makes sense. It’s just this transitive. I think it’s transitive like transitivity. >> It looks like it, but I’m not going to call everything transitivity. >> Yeah, >> because sometimes like more formal math like the other one was called cancellation law or cancellative property, which I didn’t even know that was a phrase. >> So, I’m not like matrix algebra. >> Yeah. Well, what I mean is I’m like it looks like transitivity, but I’m not going to be like, yeah, transitivity everywhere. >> That’s fine. That’s true. >> Matthew is going to like get in our comments be like >> Oh, good. Yeah, mad people. You say something wrong. Don’t be a Say something. >> Yes, please. >> Let’s see. Now, from the programming standpoint, you might ask how to implement the greatest common computation in practice. Consider the following lema, which as of now might seem quite abstract. For any integers a and b exist within the numbers, we have greatest common denominator a and b equal to the greatest common denominator of a of b a minus b. Uh this is interesting actually the this implementation is is interesting because I didn’t know I I’ll I’ll read this one. Uh so after Corey read the lema 3.7. So it says how does this help or how does it help here is how instead of computing gcd of a and b directly we reduce the problem to a simpler one where one of the one of the numbers is smaller. We apply this recursively until at some point one of the integers is zero. The other one will be the GCD result as follows from the second property of definition 3.6. Surprisingly, this can be written in a couple lines of code. >> And so the question that I had here was like I’d never seen this format of the fourth line a comma bals, a so. So this is um what is I’m gonna I’m gonna look up the chat GBT that I did earlier this morning because I don’t want to mix words. Oh, wait. Hold on. It’s probably in here. So, they called it Yeah. Python’s tupal unpacking trick. So, it basically swaps A and B. And I didn’t know that. >> So, that’s that’s pretty cool. Yeah. So, >> so it wants to put basically if a is a is less than b, >> we want to put the larger number first. >> Yes. >> We want to make sure that we’re in descending order basically. >> Mhm. Yep. >> Okay, that’s fine. So, make sure that these two numbers are in descending order is the first line. Yep. Then subtract them so you end up with a positive number. >> Yep. And then when it hits zero then the remainder is essentially the gcd which is going to be a. >> Um if you’re in descending order a minus b will be a negative number. >> It’s uh a no it will it will be a positive number because it’s going to reorient a and b. What what what you should do is uh use your tablet and then do full screen on walking through this code handwritten with the print gcd 36 and 14 then you’ll understand. >> Okay, then let’s do that. >> Yeah, I was doing this on the treadmill. I was like, “Oh, okay. >> Let’s do that.” Let’s see. share my screen. I show like multiple windows. Blow this up. All right. So, let’s see. Probably need both then. Yeah. Yeah. I mean you could just copy you can you can copy paste into miro. Just grab the grab the code and then paste it in there and then just work the >> the second print statement. So we have definition. So given a and b I’m just going to write it out. If A is less than or equal to B, swap A and B. Return A. If B is equal to zero else GC D it’s recursive B A minus B. Okay, let’s do a example of this. So given A equ= 36. >> Yep. and b equals 14. So a is less than a and b. Don’t need to do that. So don’t need to swap. >> Yep. >> And we’ll return b is not zero. So we’re going to do the same thing. >> Yep. We’ll do GC D of 14 and 36 - 14 which is equal to 12 >> which is going to be >> what? >> 22 >> 36 - 14 is equal to 22. Wall which is going to be so A is now less than B. So we swap them. So now >> just do it vertical so you don’t have to pan around so much. >> Yeah, it’s fine. Just trying I’ll get used to doing this on whiteboard. I’ve worked on whiteboard a long time. So now this is equal to let’s do the swap here. Swap AB. A is now equal to 22. B is equal to 14. And then B is not zero. GCD of is it A or B of 14 and A minus B. So 10 2 - 14 is equal to 8. once again. So, we’ll do a swap. A is equal to 8. B is equal to 14. No, that’s not right. Don’t need a swap. You don’t need a swap. That’s going to give us So B is not equal to zero. So we’ll do GCD of A 14 and 8 and 14 - 8 is equal to six. >> Yep. >> This just keeps on going, huh? >> Yep. Well, only for a few more lines or like >> now we’re going to do same thing GCD because they’re in descending order again six and two GCD of two and four GCD of two and two and GCD of two and zero. So two go. >> Yep. Interesting. >> Yeah. Work with odd numbers. I’ll try that. That’s cool. That doesn’t have work. interesting way of doing a nice short like um concise way of representing a function that does that. >> It gets better. >> Wait, there’s more. >> Yeah, hold on. If I hit the power Yeah. Okay, watch. Uh so, however, such an approach in the worst case scenario still requires linear time in the size of the numbers. For example, when computing gcd of n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n n in one uh the following lema will be extensively employed in the so-called uklidian al algorithm which will reduce complexity down to logarithmic time. This is where it gets cool. Uh corlary 3.8 for any a uh a or b uh that exists within the uh integer set z uh we have gcd of a and b is equal to gcd of b and a mod b. Now this is much better. Let us apply this idea again but with the modulo operations of sub uh subtraction uh and then this Python code def gcd then it declares it it’s just type setting a and b as ins output type set it as int uh return gcd b uh and a mod b if b is not equal to zero else a and then it’s got a few different print statements for running through that gcd functions output. Uh but yeah, this is even more, you know, it’s it’s like now it’s one line and it’s pretty it’s pretty uh what do you call it >> um >> concise? >> No, there’s it’s it’s it’s like when you when you get like it’s like it’s like ASMR for your brain when you when it like Yeah, it’s concise, but like it’s like it’s like concise and efficient, but like it’s called something. >> This is like a word that mathematician Yeah. like getting closer. It’s like in that ballpark. Yeah, it’s math sexy, but like anyway, notice that the if I remember it, I’ll I’ll bring it back up. Notice that the algorithm can be easily implemented in a single line. Moreover, the complexity reduced down to logarithmic time. No, no, no, >> but I alluded your attempts. >> For computing gcd and b, we need uh o of log max time. Um, example 3.4. Let us find the gcd of 535 and 230 manually. We will use the uklitian algorithm for this purpose. 535 = 2 * 30 + 75. So this follows the same um structure as was given like in one of the previous I think lemas where it’s just um it’s it’s uh a is equal to uh QB + R. Uh and it’s just doing the same format for the subsequent two lines. So 230= 3 * 75 + 5 75 = 15 * 5 plus 0. Once you have a remainder zero, you know that uh your um your b is five. Yeah, your yeah because it’s it’s it’s the it’s the b is it’s it’s uh a is equal to qb plus r. So gcd is five. Uh while the greatest common divisor GCD focuses on finding the largest shared factor between two numbers, the least common multiple LCM deals with finding the smallest multiple that both numbers have in common. Uh the LCM is particularly useful when we need to synchronize cycles or work with fractions. So this is what I was telling you before like I don’t know what synchronize cycles means. I I’m sure we’ll understand that later. Um I I have >> I imagine we’ll get to that later. That’s like kind of like a foreshadowing. Yeah, exactly. Um, okay. Definition 3.5 or 3.9 LCM. For any A or B that exists within an integer set Z, the least common multiple LCM, A and B is defined as an integer. M exists within the natural set of numbers N such that one A is a divisor of M and B is a divisor of M. Two, B is a minimal integer that satisfies the first condition. Uh, one might write the above definition more concisely. the least common multiple of a and b is equal to the minimum of m of m that exists with a natural set of numbers n uh I don’t remember how you read the colon how do you read the colon >> divisor that >> no no colon not a bar this >> parameterized by uh a is a divisor of m and b is a divisor of m uh example 3.5 let us again find but now uh least common multiple of multiple for few pairs of numbers. One LCM of 12 and 4 is 12. Two, LCM of 13 and 17 is 221. 3 LCM of 13 and 18 is 234. 4, LCM of 42 and 28 is 84. Um, scroll on this lema 3.10 least common multiple properties. Uh, we consider LCM of A and zero to be undefined. LCM of A and B is equal to uh Do we know how to read this? Did you chat GBT this one? >> Where you at? You’re not you’re not scrolling. I I’m I’m doing Where are you? >> Uh I am on lema 3.10 second item. And it’s the it’s essentially like the same as >> it’s like interchangeable with like >> Yeah, that’s how I read it. But like Okay, I’ll just say it like that. the same as. I’ll look it up while you >> That’s how I re read it. Like the same as because it’s just keep it simple. >> I’ll look it up while you do that. >> All right. Least common multiple of a and b is equal to a which is the same as b is a divisor of a. If a and b are co-prime, then least common multiple of a and b is equal to a * b. Um any common divisor delta of a and b satisfies delta is a divisor of least common multiple of a and b. >> If and only if >> if and only if. Wait, really? Yeah, it says the least common like according to uh Claude Haiku 4.5 the least common multiple of A and B equals A if and only if B divides A. >> Oh, okay. I didn’t know that. That does Why don’t they just put the iff? Because that’s how I usually see if and only if written. >> Me, too. >> Why do they have two symbols? It’s >> that that’s that’s part of why this is complicated for people is because you have to like learn the jargon because white papers like cryptography white papers there is no unifying symbol set. So you have to know all the different like essentially synonyms of a given symbol and how they can be parsed. But anyway, problems down the road. Any uh or for any C is greater than zero, we have uh LCM of A time C and C * B is equal to C * least common multiple or LCM of A and B. Integers is LCM A and B divided by A and LCM A and B divided by B are co-prime. >> Okay, >> these are really important constraints and I’m sure that there’s like really >> like optimizing circuits, this becomes like really important information, right? This is like >> right >> like because you want to optimize a circuit. You want to try and find the least amount of operations required to >> Yep. >> uh complete the circuit. >> Yeah. >> And you can use a lot of these tricks in order to make it minimal because you can start to do like you can do the algebra on all these things and say because this this and this we can then rearrange things and then we have this thing which equals this thing and now it’s now it’s like two operations, right? >> Yep. Because at the end of the day is like if you can reduce the operations you increase the speed and time is money. >> Yeah. >> So theorem 3.11 for any A or uh is it A or B for any A or B belong to set >> for any a A and B in the natural numbers >> for any A and B belonging to the set of natural numbers N we have GCD of A and B times LCM of A and B is equal to AB. One interpretation of the above a theorem is that no additional algorithm is required for LCM of A and B if we already have an algorithm for GCD of A and B. Indeed, we can simply use the formula LCM of A and B is equal to AB / GCD of A and B with a previously computed GCD A and B. Excuse me. The reasonable question is how to generalize the GCD and LCM operations to more than two arguments. For that reason, we provide the following definition. Definition 3.12 GCD and LCM for multiple arguments. We define the greatest common divisor GCD of uh a sub1 to a subn and the least common multiple LCM of a sub 1 to a subn for any set of integers a sub1 to a subn exists within the integer set z as follows. GCD of a sub 1 to a subn is equal to max of d exists within the natural number set n uh parameterized by d is a divisor of a one a sub 1 uh d is a divisor of a sub 2 and on to d is a divisor of a subn. LCM of a sub one to a subn is equal to the minimum of m exists m that exists within the natural set n parameterized by a sub1 is a divisor of m a sub 2 is a divisor of m up until a subn is a divisor of m theorem 3.13 computational properties of gcd and lcm for multiple arguments the following two statements are true uh there exists an oh no not there exists for all a and B that exists within the natural set N G uh is parameterized by GC GCD of A B C is equal to GCD of GCD of A and B and C. I guess I that that if you’re hearing that it’s hard to visualize that because technically there’s a parenthesis within the parenthesis because you’re doing a GCD operation on A and B. >> Yeah. Out kind of. >> Yeah. So the the the output of the GCD of A and B is the first parameter of the second GCD. >> They’re commutative as well. So it’s like it’s like transit transitive and commutative. >> You can you can apply the operations kind of like >> at will >> uh and move them around >> which is nice. >> Yeah. >> Hold on. Hold on. >> There’s no C in that last one. >> Yeah. I just I just I just saw that. >> How’d they get rid of the C? >> Maybe because it’s a common a common factor for both. So you can just remove it and you just need to find some conant. >> Yeah, but it doesn’t >> Hold on. It’s factored out >> because this is natural number set. Yeah, it does factor out. >> It didn’t It doesn’t say what the C is. It just says constant. It’s a factored out constant, >> right? It doesn’t specify >> and C are natural numbers. C is any constant apparently. >> Would C be would what would C be? Would C also be potentially a natural number? >> I need an example. >> If you have >> it could be apparently doesn’t need to be. >> I mean, it could be anything as long as you can factor it out. >> Uh I I think this will make more like it it we’re we’re making guesses. >> Yeah. But it would be nice to just see the worked example. But that makes sense that C somehow factors out. >> I’m sure there’s one of you. No, there’s no there’s probably one at the end. We can ask tragic for one. In conclusion, from these two theorems, there is no conceptual necessity for specific algorithms for GCD of anything and LCM of anything when dealing with more than two arguments. It is worth noting that there are more effective algorithms for more than two arguments, but such a topic is well beyond the scope of this book. Interesting. Uh I can read this or you want you want to go? >> I’ll go. >> All right. Extended uklitian algorithm. So in this section we will intro introduce the extended uklidian algorithm. An important lema related to the GCD. So greatest common denominator you might have reasonable question. You might have a reasonable question. You might have reasonably questioned oddly worded. Why do we even need an extended version? One of the primary reasons is that this algorithm will help in finding inverse modular elements introduced in the subsequent sections. Uh inverse modular elements. Interesting. Lema 4 314 the bezout identity for any two given integers. >> I had to look that up. >> Basu. >> Yeah, it’s French. >> Sure. I’m American. >> I’m American. Bout out. >> Bees out. the B’s out. And for any given two integers A and B that exists within the natural numbers with D equals to the greatest common of A and B, um there’s just such a U and V that exists within the integers such that D is equal to A of U plus B * V. Interesting. So let’s see here. Example, it is evident that the greatest common denominator of 125 and 93 is 1. So we can find such uv existing in the integers that 1 is equal to 25 125 * u plus 193 * v. One such example is u equal to 32 and v= 43 since that >> so it’s so nice to see a worked example. >> We call the tupal 32 43 as the basu coefficients. >> Yeah like that makes sense. >> Interesting. >> We’ll explain and show how to find these coefficients concretely a bit later. What are the purpose exist? I wonder if there’s another >> I’m also curious as like what are the what are the what are the benefits of knowing these things like why would we care, right? Because like previously if you if you’ve watched this whole thing like you can see some of the benefits of knowing maybe you haven’t yet you will probably get to the point of understanding why we need to like you know in math right they’re always like why why should we care about this and it’s always because it’s useful for doing something and a lot of the stuff we’ve learned so far we’ll learn later that it’s useful for optimizing circuits right doing algebra to get to a point where you have you have the minimum number of operations within the circuit to then provide a proof which makes it more efficient and you can you know require less resources to get it done etc etc. Um I’m assuming this is also useful for that but I have like no intuition as to why or how. See corlary um from the basil identity integers u and v are of different signs excluding the case when either of bas coicient is zero. Um okay interesting generalization for multiple integers. Suppose d is the greatest common denominator of a through n. Um a of one sub a of one to a of two a all the way to a of n. Then there exists such integers uh u of 1 2 u of n that exist within the integers that d is the summation from i to n of ui ai. Okay. So they’re linear combinations of each other. >> That’s interesting. >> Yeah, >> that’s going to be useful for polinomials I imagine. >> Yeah, it looks like it could be. The integers u and v are called baso coefficients. Uh the first corlary can be understood intuitively. If all coefficients are non- negative, the result will be much larger than necessary. Similarly, if they are non-positive, the result must be negative but the greatest common nator was defined to be positive. The second consequence follows from the fact that we can decompose the greatest common denominator thus sequentially derive this sequence. Also note that we can find basil coefficients in each uklitian algorithm step. I would be curious to see the the like a geometric representation of this. You know how like >> if you were to watch like three brown one blue or three blue one brown animations of >> Yeah. He does a lot of really good visualizations uh >> of these types of things. I bet there’s like a really >> does he work alone? I think so. I mean, he’s done a lot of collaborations lately as he’s gotten bigger, but like for the most part, I think >> the animations of the n dimensional space because like Veritasium that one like I >> using so he built that whole library called manom which is a mathematics visualization tool. >> You know what would be interesting if we tried to use like chat TV or AI or claude to like >> do a manom visualization of these things. >> We we we could do that. We >> that could be fun. That would be awesome. Yeah, >> unless someone in the audience who watches this wants to do that. >> No, there’s zero >> zero. I know I know one person’s watching and I’m talking to her. So, uh you can go do that. >> Oh, there’s somebody watching. >> Yeah, Maya is watching. >> Oh, okay. >> Hi, Maya. D has entered the room. Hey, let’s get rid of your your second screen. for watching mine. >> Okay, hold on. Let me get rid of it. >> Sup, bro. Audio only. Anyway, Deacon, listen. Uh, let’s see. Now, we introduce the extended the extended uklitian algorithm, which is uh besides calculating the greatest common denominator itself finds the baso coefficients efficiently in the poly logarithmic time. For example, as we will see for calculating the modular inverse element, one would rather use the extended ukarian algorithm than the naive approach which shows whether inverse exists at all. The time complexity of the extended uclear is O of log max a and b minus the same as for the classic. Okay, so the it’s the same. So it’s the extended is the same order of polinomial time complexity. What is this QR code you’re putting up? That’s not me. >> D’s doing something. Discord. What is this? >> Say something, bro. >> That would actually be useful. >> Yeah, we should Can we Can you stream to Discord? >> Uh, >> and then we just take we could like we we could like funnel people to the Discord who want to who want to like participate in this. >> Yes. >> Or something. I don’t know. I could share screen to Discord through OBS. That has to be a So I can run SLOBS on my end and then screen share that into a Discord channel that we are both in. Yeah. Yeah. That’s just this is a lot. We’re streaming to a lot of places at that point. >> Hey, it. Whatever. Who cares? Maybe somebody’s learn if one person learns some math then it’s fine because I’m learning. This is a fun way to treat my Saturday. >> I’m going to be honest. I don’t care about anybody else. >> No, I’m I’m having fun like learning this stuff myself. >> Yeah. >> I hope we get like balls deep into it and someone’s like, I I learned ZK through watching you guys. >> That would be funny. Be like, wow, >> you must be really bad at GK. >> No, they just like sometimes it’s it’s it’s it’s better to have company because learning something that’s really this boring, >> it’s it’s painful if you just do it alone. >> Yeah, I’ve done that before. Yeah, I’d be cool to have We got some comments, by the way. Um, coming up here, >> let’s see. Uh, cheat viewers streamboat. That That’s garbage. Join the Discord. D’s got Discord stuff. I think that what he put up is the Discord. >> Okay. >> Okay, that makes sense. D is typing for us. You just said, “Ignore me. I can’t hear you.” And my bro, okay, D is D is is producing while we uh do content. >> Okay. Algorithm one extended uklidian algorithm. Input a and b parameterized by a and b exists with a natural set of numbers n without loss of generality. A is greater than or equal to b. Output gcd of a and b is the first input. U and v are the second and third inputs. R sub0. So a is going to r sub z. B is going to r sub 1. One is going to r uh u sub0. 0 is going to u sub 1. 0 is going to u uh v sub zero. one is going to v sub 1. Uh well r sub i + 1 is not equal to zero. I is equal to 1 to two. >> Uh this is this is um what do you call it? Um pseudo code. So like instead of somebody actually writing the code, they’re just writing essentially how functionally how the I’m going to keep calling it business logic, but essentially how the function should be written. So this is as close as you can get to like human readable code. I suppose you probably get no you can get >> yeah pseudo code is like >> it’s pseudo code is useful for implementing something in any language usually that’s why people like using Python because Python is very like the like the the syntax of writing Python is very close to writing pseudo code. >> Yeah. Uh and so people usually when they do like specifications which are supposed to be as close to implementation generic code, they write it in Python because it’s close to pseudo code more often than not. >> Yep. There’s also languages like that are newer like Ziggb which I haven’t taken a look at but I heard that >> like Quint is a is a spec specification language. Um, that’s something that got put on my uh radar the other day when I was talking about specs. It’s made by the the team that did um um Cosmos and um what’s their what’s their consensus algorithm off the top of my head? >> Oh. Oh, no. I I’m not going to remember that one. >> Why have I forgotten that? Doesn’t matter. Anyway, um it’s very BFT, right? So, I think PBFT, but they they made a >> I look it up. Tenderint. Yeah, >> Tinder. Yeah, Ethan. >> Yeah. >> Uh, created Quint in order to help verify a bunch of to-do like executable specifications and writing specs. >> He says it’s he says it’s nice. I haven’t tried it out yet. I’m thinking about giving a giving it a go on like taking one of our specs and writing in Clint and seeing what that process is. >> Interesting. I mean, specs are already pretty like the way that IETF pushes out specs. They’re pretty readable or like the EF. It depends though, right? Because I’ve been I’ve been diving into a bit of a a bit of a a tangent. I’ve been diving into the difference between the Ethereum Foundation process of what it is today, which is executable specs and the EIP process. So like EIP are like the process for changing specs and introducing new things. >> Whereas the final is for people who don’t know, Ethereum improvement proposal, it’s how you submit changes. >> Yeah. And then though then what that then generates is like this canonical document at least when it comes to like code of an executable specification meaning that becomes like the reference implementation for how you write the software in any language. And so that then allows you to do a lot of automation like writing like generating tests and frameworks and stuff like that. And then so when someone so someone’s like I’m gonna write this in go or rust or nim or whatever like C or whatever >> or like it’s like it’s agnostic and so >> they should all they should all if I if you do a function if you write a function like this it should give you the same answer every time >> and if if it doesn’t >> then up problems. That’s like that’s why like uh shout out Mammy uh writing Constantine which is a cryptographic primitives library in Nim. Like that’s that’s that’s all it’s been something everybody’s been impressed. >> Pretty hardcore. Nim is great. >> Yeah, it’s pretty hard. >> There’s a cool repo I’ll share with you later in terms of how to build everything from scratch. Anything you want. It’s pretty interesting. >> What? Constantine? >> No, no, no. Uh I’ll show you later. But anyway, we’ll we’ll finish up this page because it bleeds into a new This page is the 10. So we’ll just we just go up to prime numbers and we’ll start there next time. >> Yep. >> Okay. Go ahead. >> So although we already know how the extended uklitian algorithm works, this method is still not very intuitive. Let us consider an an example to better understand how it works. Example 3.7 extended uklitian algorithm example. First we need to uh first oh okay I’m going to have to correct some more typos. First uh you need to find d is equal to gcd of a and b. Then knowing the sequence of expansions quotient Q subi at each step, we can find the basu coefficients. Um 1 uh 125 is equal to 93 * 1 + 32. 93 is equal to 32 * 2 + 29. 32 is equal to 29 * 1 + 3. 29 is equal to 3 * 9 + 2. 3 is equal to 2 * 1 + 1. 2 is equal to 1 * 2 + 0. Uh let’s see what is going on this table here. So you have I >> the multip the >> the dividers >> are the first row. Those are the Q’s, >> the quotients. >> Yep. >> One, two, one. >> Uh >> this is the iteration step by the way. So >> zeroth 1 2 3 4 5 6 right here. >> And then what the >> So it’s just it’s just tracking. So like this is Q. Uh so Q is 1 2 1 912. Yeah, that matches. And then U is an invisible one. Then uh cuz it’s what is the U is next to Q. So one. Why is this zero? >> So what is the what are we getting here? Um >> it’s asking you to do five and six so you can calculate V subi. It’s an example in this table here each corresponding cell is calculated with the following formula. So they’re giving you the formulas. So you can calculate V subi of I is equal to 5 and six. So you can fill out the rest of this table. >> But essentially they’re showing you how the table is populated based on uh the iterations of this example. 125 is equal to 93 * 1 + 32 all the way down to when you have a remainder zero. >> Yeah. >> Uh I’m I’m we should spend a bit of time outside of the this recording and then just work through some of this if because like this is still a little bit not so intuitive for me. So I’m going to do this one. I never got to this. Um but yeah so exercise finish this example by filling in the missed cells marked by the question mark after finding v sub6 be sure to check yourself. So this is something that we could code >> and then just you know verify like do it by hand then write the code and then just >> you can post the python code in the in in the discord server or the comments section in the YouTube or whatever. >> Yeah. >> Cool. Sweet. Well, that is it for this weekend’s next 10 pages of the ZK book. Oh, hope you turn tune in for next time where it will get even more mathy. Yes, >> while my kid while my kid takes a nap, we will do ZK or primitives of ZK. >> Can’t wait till we actually get to write Circom stuff. >> That is gonna be neat. Yeah, it’s gonna be fun. >> All right, see you guys in the end of stream. >> Later.