Write Circuits: Practical Optimisation Strategies

Transcript

Good morning GMGM. Thank you everybody here for taking choosing [music] to spend your time at our third inaugural noon. >> Hello. Thank you for being here. Um so I'm going to present uh trying to give you ins on how to write efficient code. Uh but first let me explain the title because you should not write circuit. So I I did that because when we uh when we were developing noir our moto was write code not circuit and uh [clears throat] so that like anybody can generate zonage proof and you don't need to be a

cryptographer just need to know how to program. So that was the idea but knowing so what do I mean by circuits? So like circuit is the output of the compilation of a no program. [clears throat] So no is writing the circuit for you. You don't have to care about that but it's important to know what it is doing so that you can write efficient code. So we need to know what is a circuit basically. Okay. The good news is that a circuit is a very simple thing. It's sorry.

Okay. Uh [clears throat] so it's just a set of equations like living in a in a field and this equation describe the computation that you want to prove. [clears throat] So it just just literally just literally just a bunch of equations. So it's very simple in fact. uh in the context of Noir we have also more in in the output of the compilation what we call gadget or what in in the context of noir we call blackbox functions uh which are stuff that is implement it's a like it represent a small computation that is implemented by the proving system and it's implemented like much much more

efficiently if you wanted rather than doing it like using a generic circuit [clears throat] So these blackbox functions usually they are done uh using lookup tables. So lookup tables are a very uh important primitive of cryptographic cryptographic primitive [clears throat and cough] and this is how you can access to to this uh kind of primitive using noir. We will see some example of that later on. Okay. So this is a very simple example when I want to do to to multiply a matrix by a vector or 3 * 3 matrix.

So like the multiplication matrix vector multiplication is very simple. So like you say okay this is an equation uh I can do the same for the second coordinate and so on. So I already have my circuit. Well, not exactly. Uh the trick is that in your equation you need to have only one multiplication. [clears throat] So we call this uh equation with only one multiplication. We call it a gate. And uh so how do you come from this to this? You need to create intermediate variable for each multiplication. Then you can sum the result. [clears throat] Okay. So what we learn here that a multiplication costs one gate.

Okay. Uh so yeah [clears throat] if you want you can try the example. It's very easy to install noir. I put some QR code but [clears throat] you cannot uh install it on on your phone. So just for just because it's nicer with a QR code but no you really need to to follow the follow for the link follow the follow the link and it's very easy to set up if you are using Linux or a Mac if not then I don't know it will be not be easy uh so this is fware but you need also our proving system which is Bartenber we call it BB and but installing it is also very easy [clears throat]

okay so This is a matrix multiplication example. So if you're not familiar with noir, you see that it's very straightforward to to code with noir. So it's uh yeah, it's it's a rustl like language. [clears throat] And here I added um a common line that we will be using. Uh it shows you um the the circuit size. So the result of the compilation, the number of gates that you have. So it it also tells you the number of ass codes which is an intermediate compilation step but what really matters is the circuit size at the end. So 66 here in that case and you can see that

[clears throat] also we have just three coefficients. So the number of up code is only three uh but in reality because of this uh like one multiplication perate and so on we have more. I don't know why it is 66 frankly should be like less than 30 but uh I didn't investigate I think 66 is a good number okay [clears throat] so we have seen what we can do with a circuit now what cannot you do with a circuit well you cannot do integ arithmetic like if you want for instance to compute the average of two numbers you say oh good I've got my equation I don't need I can

just use this in my circuit well no this uh this computation is not the average of the x and y and the reason is because one over two is not 0.5 it's a big integer number we are doing uh we are in a prime field remember okay [clears throat] another thing that is not easy to do is a comparison uh because it's not an arithmetic operation. So like everything that you cannot do in a circuit you need to emulate it and this uh this is very costly. Uh so fortunately for comparison we can use blackbox

functions which is which call it run check. It's a very [clears throat] very well-known cryptographic primitive. Uh so run checks allows you to assert the bit size of of a number. So [clears throat] in case of comparison you will need like two to do two run checks and a few arithmetic operations. So uh what you need to remember is that the run checks costs between one and 10 gates depending on the bit size. Okay circuit also doesn't have any memory because it's only like numbers in an equation.

So also this needs to be emulated and this is horribly costly but we have also a dedicated black box for that. So I and yes you don't really need to worry about the black box because like noir will uh lay down the correct black box for you but what you have to remember is that memory operation are costly even with the black box. So if you want to do a read a read it would be two gates more or less on a right would be like in average four five gates. Uh hello okay. Um [clears throat] so why do I say dynamic read and dynamic

right? Uh it's because like if you have a if you want to access your memory at a constant index index as you know like five eight whatever usually it can be optimized out and one more thing uh you need to we need to to pay for some initialization costs which correspond to the array size. So even even if you you have only one dynamic grid it will be to get plus number of element in your array and also these numbers are only for uh arrays of simple type like numbers but uh if you start to use composite type it will not

be the same number. would suggest that you want to avoid that [clears throat] and of course what you don't have in in a in a circuit is control first statement like using if loops uh break continue function calls okay so all this needs to be emulated and it then it will be costly okay so [clears throat] what we have learned here is that uh writing circuit is difficult on error our phone and circuit are not really efficient. So um like one of the reason also is that uh this uh integer arithmetic versus uh prime

field. So when you want to do like normal computation with integers, it needs to get emulated by the field. But then you need to remember that you are executing this on your computer which is like a binary computer like using bits uh for instance like register of 64 bits but our field are very are much much bigger like around two 256 bits. >> [clears throat] >> So then this will need to be emulated again by uh binary computer. So you have to do this kind of double emulation that is at the end very slow.

Okay. Okay. But the problem is that in a we want to use noir uh for private smart contract that means contract like programs that run on your device because you don't want to give your data to anybody anybody else. So you just want to generate a proof and then say okay my transaction is correct. Uh you can check the proof. Uh so it must run on a personal device like a phone. So it must be efficient. So we need you to write efficient no code. And how to do that given that uh noir is write is creating circuits that are slow.

Well the answer in fact is quite simple. uh if writing a circuit if using a circuit is slow let's not use a circuit and for that for this we have uh this concept of unconstrained functions in uh so I say it's a unique feature but like okay it's not it's not unique like it's it existed existed well before noir so like it's not unique at all but I think that the implementation we did in is very good like very well integrated It's very easy to use and uh yeah you just add unconstrained keyword in front of your function and and that's it.

[clears throat] So what can you do with this unconstrained function? So an unconstrained function is uh is saying to noir that okay this computation do not put it in a circuit put it outside the circuit. So that means that the cost is zero like in term of number of gates. Okay. Then what you need to do of course is to validate the result that you get that is computed offline like outside the circuit. I mean you need to validate this in a circuit of course. So you need still need noir.

Okay. So we'll see a very simple example like the classical one like how to do a division. So if you want to compute a division in inside a circuit how you would do like a division in a we are in a prime field remember so division you need to multiply x by its inverse the inverse of y and the inverse you can get it using little theorem very easily easily so here p is a prime number of the prime field like the characteristic of the field [clears throat] uh so it's a very big number like 200 more than 250 bits. But fortunately this can be computed efficiently using the

like famous uh square and multiply algorithm. But still it requires log p multiplication. So to compute this you will need at least 250 multiplications for just one single division. So it's kind of costly anyway. So can we do better? So yes, of course with unconstrained functions, which is kind of straightforward, but maybe not. So uh yeah, this is something I'm trying to explain to my daughter for so many times and she still doesn't get it. But yeah, if you move the y to other to the other side, then you have a multiplication.

Come on. Okay. So how can you do it in one? So yeah, you don't need to do it in Noah because Noah is doing it for you. But still if you want to [clears throat] you can still do that. So you can use an unconstrained function. You just say that it's unconstrained uh call it divide and then this is doing the real computation and then we just check uh in your circuit. So main is your like is the circuit that you are going to to compile.

uh to use the unconstrained function you need to specify that with this unsafe keyword to tell that tells you that uh the result of this function is not proven so it's can be anything okay no problem because I will assert that this relation is true so this is happening in a circuit and uh when you use uncontra function you must be very careful because you need to think about all the edge cases in that case the h case is when y is zero because you are not able to divide by zero. So okay no problem I just assert that y is different than zero and that's it. So this cost one multiplication this is another

multiplication as well. So and maybe another one to return the another gate to return the result. So like it cost three gates and that's it instead of 250 multiplications. Okay. So quite nice now. Uh so now I'm just going to give you like trying to give you some intuition on how to do that with more example and that's it. Uh so another example [clears throat] which is also simple is what if I want a function that find an element inside an array that is sorted. Okay.

So [clears throat] like the simplest solution will be to do a linear scan and when I get to my element I just return it. Okay. [clears throat] So and that doesn't work and the reason is here you are we are doing a early return which is a control for statement that uh doesn't work in a circuit and that we do not emulate because if we would do it it would add a cost and it will be like a kind of invisible cost. So we don't want we don't want that we want you to be aware that okay this is not possible how to do it differently.

Uh so [clears throat] one way to do it differently is to go over the wool array and then just check when we uh reach our elements start the result and then return the result. So but that means that there is no um like even if my element is the first one you will process the wool loop. So this is an important point when you uh use an algorithm in a circuit in war you must remember that the cost will always be the worst cost of your algorithm.

Okay, [clears throat] we know that we can do better and the classical way to find uh an element in an array is to use binary search which will be a login um cost. Then [clears throat] if you try to do that what will happen like because here we have recursive function calls uh this doesn't work in as well. So functions calls are emulated that means that they're in line into uh into your circuit and if you call yourself then of course it doesn't work well. Uh okay that's not a very big

problem because you can always write an iterative version of a recursive function but even if you do do so here the benefit of the binary search is that you have your array you split it into two and then you only search in the revelent part but uh remember that if is a control flow so it's emulated and how do you do we emulate is by you need to process the two branches. If you process only one branch and it would not be zero knowledge because you will know in your circuit oh we are only executing this branch. So we need to execute the two branches.

Uh that means the gain that you do by this trick is completely cancelled because you need to process the two. So like this binary search will be uh will be linear time. it will not be login and because of all this overhead uh it will be worse than the previous linear scan. Okay, still can we do better? Yes, with unconstrained functions. [clears throat] So here the idea is to do okay no problem I will do my B binary search outside the circuit using an unconstrained functions and then I just assert that the result is okay. So I assert it here. I hope you can you can

read it. I'm not sure you can read. Yeah, more or less. Okay. So I just assert that the index given by uh the unconstrained function on correspond to uh the element I was searching for. But here again we need to pay attention to the [clears throat] edge cases. So this is fine when x belongs to the array. But what if it doesn't belong to the array? So yeah, in that case is we need to handle this case as well else it will not be safe.

Uh so this is I this is what I do. Uh uh this is why I need all this. So like basically either X is outside completely the array. So I check this or it's inside. And then if it is inside it must be between two element of the array in term of the range. Okay. So this is what I do here. [clears throat] But it's still like doesn't change. This is there is no loop here at all. So I just do a three like one two three four assertion some comparison and that's it.

So it should be like a constant cost right. uh but it's not what what what I wrote here. So do you know why it is not constant cost? Why why is it a linear cost? So [clears throat] remember what I what I told you here we are using an array. We are reading at a dynamic index in into the array. So that means we have to pay for the initialization cost which is n in that case. But still this is better than the linear scan because in the linear scan case

like [cough and clears throat] for every step we do all this which is a comparison and if so this will cost at least three gate per uh step. So the cost will be like o of 3N something like that. uh whether here the initialization of the array is exactly n and then we have a constant overhead. So it's better. All right.

Uh so now we know how to find an element in a sorted array. But my next question is how do we sort an array? So you may remember this interview um with Obama. So what is the most efficient way to sort an area of big with lot of numbers and yeah you should not use bubble sort because bubble sort is quadratic. The good point about bubble sort is that um it is very simple.

So for instance [clears throat] if I do try to do a selection sort which is also quadratic here the cost will be uh bigger. Uh we will see this uh maybe I can uh Where can we find it?

I don't know. [laughter] Okay, we'll see later. So what I wanted to show you and I don't want to break the the setup uh like is ping the profiler with this and the previous one and then you can see the number of gates and what type of gates there are and in the previous one here [clears throat] you don't have any uh dynamic memory operation so all the array access are optimized

uh and the cost is I think it's 50,000 gate for 100 array an array of 100 elements that you want to sort and here the cost is three times more and because of like here you are doing a dynamic access on your array okay so again we can say okay but we can do better we can use uh n login sort Uh so here I took the example of merge sort. Merge sort is very simply sorry is very simple. So you you you divide your array in two. You recursively sort each part and then you can merge the two

because it's there sorted in linear time. Uh recursion doesn't work well as we know. uh so we will need to get to an iterative algorithm and then it will not fit on screen. So I just wrote here the linear merge. So the like the first the first layer so we need we will need to do log n of of this operations and still you can see oh there is a lot of if >> [snorts] >> uh there is access and so on. So here like a good idea would be okay to to see what it what do you get with uh with the no profiler and what you would get here is uh I

think the cost is around 10,000 gates but just for one layer so doesn't compare well to even the bubble sort okay so obviously the correct way to do a sorting is to use unconstrained functions so let's Okay, [clears throat] so the idea is that you sort your array outside the circuit and in the end you check that the result is correct. Now how do you check that the result is correct? [clears throat] Well, one part is easy is to check that the result is sorted. This is very easy and we can see that this is linear. I just check go over all my element and check that one is bigger than the next

one. uh the previous one. Sorry. All right. [clears throat] But that's just half of the story. We still need to know that the elements in your result correspond to your initial array. Uh and what does that mean? Is that that means that your initial array and the the new one the certain one must have the same elements. So the that the elements may have been permitted but they are the same. They come from the same set. Okay. So, so this is a kind of permiss permutation checks that we need to do. So, how to do that?

[clears throat] So, for this I'm using this unconstrained function that that gives me what I call the sorted indices. So, what I mean by that is that if my smallest element is index three for instance, then this array will start by three. If the second one second smallest one is index 8 then the second element here will be eight and so on. Okay. Uh but this is totally unsafe for now. So what [clears throat] I need to do here I check that every element of this sorted indices correspond to one 0 one to up to n minus one.

So here using another unconstraint function I prove that this array contains all elements between zero and n minus one and since its size is n then it must it it is exactly this. Okay. So sorry. So what I have proven here is that this array is a permutation of element from zero until n minus one and that's it.

Okay. Now I need to compute in circuit the result using this sorted indices which I do here. Okay. [clears throat] And this prove that my result the element of my result correspond to the initial array. All right. And then the final step that as we already saw it is to check that um it is properly sorted. Okay. So now we you you can see that we have three loops over my uh over zero zero n and like inside we just do a small assert just three assert.

So the cost here is is linear. So we are even better than quick sort merge sort or whatever which is kind of cool. No, I think okay of course [clears throat] uh there is no magic there is no free lunch like even at the connect you have to pay for your lunch now so [clears throat] uh you need to sort at some point your really and this is done in inside this function get sorting index so [clears throat] how does that work in like in the stack so you have [clears throat] uh your program you compile it with no which gives you the circuit

uh and it will also give you the bag the kind of assembly code of all the your unconstrained functions that you are using and then you need to execute to get your witness assignment. You need to execute your program and [clears throat] at that time you will no will run your unconstrained function. So it will sort the array at this time using the the code that you provide. So you need to [clears throat] like here don't do not use bubble sort because the execution will be very slow. It will be quadratic again. So you need to use a uh efficient sorting here. Okay. So you need also to pay attention to that even if it is outside the circuit it has some impact during execution time.

[sighs] Okay. Yeah. So this is uh this graph are uh was done using uh the result of the pro profiler that I didn't show you. [clears throat] So you can you can see that the this a logarithmic scale. So like bubble sort of course is very very big and this is not much short but only the first layer. So in reality it's more than that and this is what I wanted to show you but here like we don't see much uh like [clears throat] so believe me with

the bubble search we only have run checks uh and arithmetic operations. So it's very simple and cost uh it costs 50,000 gates. Uh for the merge if you look in detail you will see that [clears throat] we are using a dynamic memory operation. We are doing run checks we are doing arithmetic operation. So it's very complex and the cost here is 10,000 more more or less uh but just for the first layer and with this unconstrained version the cost is 700 gates so much better uh and we have a lot of

memory operations a few arithmetic operations and we should have run checks as well. Okay, here we have unchecks. [snorts] Okay, so it's always a good idea to check with the profiler what you are getting. Uh try different alternative, see which one is better. Okay. So in conclusion, what have I learned here in this workshop? So if you have to remember one thing is when you want to write a noir program then you use noir to write a circuit that validates

a result that has been computed in an unconstrained function. This is what you try to do. It doesn't always work. I mean it always work but it doesn't it is not always uh the most efficient thing but usually it's very efficient. you need to check and validate with the profiler. So in more details we have learned that circuit are inefficient. Yes, multiplications cost one addition are cheap. Uh no blackbox they're good. Uh there are um lookup tables.

Uh with the profiler you should focus on the circuit size the number of gates. uh when you have an algorithm uh in a circuit it will be the worst cost that you need to take into account. Uh dynamic memory comparison are costly. Uh and for memory operation do not forget the array initialization cost. Uh if is not what [snorts] you think it is. So use it with caution. Uh keep it simple and smart. So smart I mean like you need to validate all all the cases all the edge cases when you use unconstraint functions.

Uh and also last one when you are using unconstraint functions you should also try to optimize them but this time using like normal programming uh language strategies like normal stuff. You can use early return, use them. Uh you can use if without problem it will be good and so on. Okay, that's it. [applause] Thank you. So if you have any question >> Yeah. about the unconstrained space.

What is the language actually executed? What is available for you? It's not Rust. It's still noir but compiled to native byte code. What are the features of the language in this specific uh context? >> Yes. So it is still noir uh but it's no with more feature like you can as I said for instance you can use an early return. If you use early return syntax in a noir program not in an unconstrained function it will give you an error. If you use it in an unconstrained function it will be happy.

So it is no but with more features. Uh this program [clears throat] yes you but it will be no liib but you can import and then it's part of yeah it will be part of your library as well. So like it's fully native in Noir. In fact like that's that's why I was saying that it is very well integrated uh this concept of constraint function in Noir it's very I think it's well done. So it completely transparent uh you are just you continue to write nowhere and uh in term of like [clears throat] more technical detail. So after so you write it and then it gets

compiled to some assembly level uh code which is like only our own assembly and the reason is because uh in a tech we have private execution but we also have public execution and then for public execution we need to run in a VM just to in case of something goes wrong we need to prove pro that the result is is failing rather than having a proof that you cannot that that does not verify. So that's why we need a VM and so to have a VM we need to have some by code and this B code is the same as the one that we have have for unconstraint

functions. So it's our c our own ble let's say >> thank you it is very interesting um I had a question about uh you mentioned with the division example that that is actually already optimized in noir is there a way for us to know when it is already optimized uh by compiling it. >> Uh, not really. [laughter] Like the basic stuff you can expect it to be optimized

basically. Uh, more complex stuff probably not. >> Okay. >> And then you can check on the profiler if with the prof profiler if it looks good or not. >> Um, thank you. I I wanted to ask um from someone that has some but little knowledge uh of noir, you showed some examples of um very complex functions that you've used it unconstrained followed by asserts. So is it a good way of using that to run away from very complex and costly functions or is it not?

>> So yes, so that was the point of my presentation. So you uh it will not remove the complexity the complexity will still be inside the unconstrained functions. So you need to write this code. It's just that this complexity will not run inside the circuit because we have seen that inside a circuit it's much slower. So that's the idea like you move the complexity outside the circuit and you just check that the the result is okay using this assert. Yes, >> I had another question about the unconstrained part. Is there any privacy concerns um because you're outside of the circuit?

>> No, no, no concern at all because it is done by the prover. So like there is no there is no problem. It's done by the prover. When you execute your program, you are still the prover that doing that is doing that. And this will uh generate all the witness which means the results of your unconstraint functions will become a new witness but a private witness not a public witness. So it's it's fine. Uh and then these witnesses will be used to generate the proof and in your proof you you don't have them anymore. You don't leak any any data. There is no no privacy problem at all.

>> The only problem should be forgetting about the The only concern I get that you doing will be the only sorry that will be the only possible issue from the side of the developer like that that you execute the constraint function but you don't do the assert that the computation is valid. >> Okay. Yeah. If you miss some assets then it's it's a then it's a problem but not for from your privacy. It's a problem for the verifier maybe the like Yeah. So yeah the verifier like is not verifying

the correct thing. >> So the and constraint execution environment is optimization and it happen at runtime. I think in other ZK systems the padding was more like to execute everything entirely before end and put the result or the pieces you want as public or private input of the circuit you are building. It's kind of different but similar purpose way of doing things. Is it still useful like this way of having another implementation of your program and compute it beforehand in like regular Rust environment or Python environment and then like give the interesting part

as public input? >> Yeah. So it it's it's yeah it's similar concept it's the same uh the benefit of doing like using a rust for instance program it will be speed it will be faster than executing it in our uh assembly code our own assembly code because then it's another layer like uh we have we need to execute it to read the code to execute etc. It's not like it will not be native compilation of of the constraint functions. So it's a kind of a VM that we use for that. So the only difference will be speed, but then it's much more easier to use and it's well integrated into Noah.

So [laughter] uh, sure. I guess yeah, we need we need to see who's with the organizers, but Okay, thank you then. [applause]