Scaling Ethereum by Optimizing ZK Prover Networks

Transcript

works nice. I can go back. Yeah. Okay. So, I'm going to present you the result of a research that has been done in collaboration between Y University and my company LR labs. Uh that is related to how to build uh double action mechanism for efficient resource allocation in the context of a proven network. So, let us wrap up a little bit. The general plan to put it in more layman terms is to find a mathematically sound way to broker fair and mutually benefiting conditions in a market between sellers and buyers and in this very specific case uh given that my company is a company geared toward

towards the K proofs uh but we do not want to do the proving oursel because we are not AWS or GCP and we don't have any special hardware capacities The goal is to basically put in a relationship between sellers. So people who have a lot of compute power and are ready to take on proving tasks and buyers which are clients that do want to generate Zika proof for whatever use case they are using. So uh this is a theme that has been quite widely explored in more traditional financial system when it comes on to for instance market making or basic auctioning. But in this case uh we have a very specific uh slight

difference that is actually not really well covered in the literature and this is a fact that for the clients all of their offers are all or nothing right like for instance on the stock market if you want to buy 50 actions 50 shares of a given society at a given price you would probably accept if I can only give you 45. But in this case, if you want to generate a zika proof and you need a given amount of compute cycles, if I'm saying okay, I can only provide you 95% of them, you're not going to accept the deal because you want to finish the proof. You don't want to have the computation stop in the middle. So this is where we are deferring from the more classical application on explor theoretical exploration of the of the

domain. So uh now to dive down a little bit deeper in the the application of the system in our company uh we are running a couple of prover networks that are running different proving system for different applications but all of them are following the same global uh the same global organization. So we have clients clients are the people that want to have ZK proof run proved and returned back to them. We have operators. Operators are entities that are running one or more on many many many uh computers and they want basically to make a margin between the cost of exploitation on the money that they will get when they run the proofs and finally

we have the auctioneer and the auctioneer is ourselves. So we basically want to nurture the ecosystem that we developed and we want to put these people in a relationship so that they can use our ZK systems. So this is the global uh the global overview and now we will focus u quite closely on how to have clients putting up offers with for a given amount of computation at a given price and operators proposing uh proving computational power at another given price on how to match between them.

So uh to start with a little bit of definition there is like the the pinfecta of a good auction system that has been defined in the literature and for a proving system to be efficient and to be smooth and for everyone to actually have an incentive to run into it. These five uh criterion have been uh retained. So you have the truthfulness. It means that uh every people basically taking part in the system do not have any advantage into lying. So it doesn't make any sense as you don't get rewarded for instance as an operator to overestimate your running cost. Uh you have the weak group strategy proofness.

Basically if you are trying to conspire with a group of people to to to act on the prices, there will always be at least one person in the group for which it is more advantageous to leave the group rather than to maintain the click and to maintain conspiracy. Then you have welfare maximization. Basically we want to extract the maximum amount of value for everyone. So we want to to find the the global global maxima of value generated which is basically uh paying as little as possible for the clients and getting as much money as possible for the the operators. Then there is a weak budget balancer which is saying that the actioner does not lose

money of course because otherwise if you're what if you're losing money you're not running not really running a long-term system and finally you have the computational efficiency which is not really critarian but more limitation of the real world which means that the algorithm must run in a polinomial time which is a fancy way of saying that you cannot really find galactical algorithms that would take months or days to find the optimal solution. to given options that wouldn't be realistic. Now uh the thing is that uh the what the theory is headbutting against is that that kind of this of uh of problem. So the development mechanism problem is actually very similar and in some way yeah kind of yeah very similar to the

napsac algorithm napsac problem. So what is a napsac problem? The NPAC problem is what you hit when you are trying to fit all you can in the hand luggage that you can take on the plane. Right? So you have a given luggage, you have a lot of stuff of variable sizes on the weight that you want to take with you on your trip, but you are limited to I don't know 15 kilogram on a small carry carry bag. So what do you do? You have to find the optimal solution to find to to take on as many item as you can while respecting the limitation of the napsac and this is a problem that is unfortunately nplete which means that basically if you want to find the

optimal solution you have to try every single other solution. So when you have three items that's pretty simple when you have 45 of them your combinatorial combinatorial complexity is already through the roof and so that kind of problem is not really solvable on a maximal global maxima uh in a reasonable amount of time as as soon as you are leaving like the the most basic of precincts. So what we are doing uh because exactly the same limitation are applying to our system which is some kind of a very complex knapsack. So what we are doing is that we will be basically loosening some of the criterion and we will reach what I would call a tetra and the half factor of a

good option. So we are keeping the same criterion but we're going to change some of them. So for instance uh the welfare maximization which is the hardest one instead of maximizing the value that is extracted from the auction we are just going to make sure that it is positive and too bad if that's not the optimal solution but at least we will have a solution where everyone will be making money on the system as a whole will behave in a probably not optimal but at least acceptable way. So following that uh the global strategy that has been established is to uh define a parameterized family of algorithms. So basically you take building brinks and

you will be building uh according to a single recipe and algorithm from all of these bricks. Then you will prove that this uh algorithm recipe is actually fulfilling the criterion of the tetron and a half factor of the good auction. You will choose parameters that are adapted to the application. So you will change a little building bricks before running your recipe and finally you just have to cook that thing and you get what you want for for your use case. So here we are going to describe what are the parameters of the family of algorithms that we define in this paper.

So the first thing that you need is a ranking that has to be consistent and monotone for clients and provers. So what this part of the algorithm do is that it will uh rank the the offer from the provers and the offer from the clients in a way that will be used then by the other pieces of the algorithm. Then you must have an asymmetric composition rule which will determine whether uh client pro match. So the uh whether a match between a given request for proof on a given offer for computation is actually useful or not.

So for instance, you need to be sure that the computational power is bigger than what is required to run the proof. You have to ensure that the prices between the offer between the bid and the offer are compatible and so on and so on. Uh you need an asymmetric composition between the clients and the prover. So this is the part of the algorithm that will be um generating this matching to be accepted or rejected by the composition rule. And finally you need a payment rule which will be there to price the matches between the pro the proof request and the computational power that has been offered by the clients. So in our specific case uh the the the rule that we're using is that we are

ranking the proof of in decreasing order of profitability for the for the prover so that we are running first the one where the let's say cost by cycle is the highest and for the prover we are ranking them in decreasing order of uh computational power. So this way we have the biggest one running first on the smallest one at the end to take anything that couldn't fit in the biggest one. So what are the application for that? So uh the problem of course is that this is a very nice and very fine uh theoretical design but then you you you hit your

head against the wall of reality and this is exactly the thing that happened here. So for instance uh the the paper only defines what happen in a single round of an auction at a given point. But when you are running a proven network then the the thing must run in a continuous way right you have always incoming request for proof and you have always incoming machines on the operator side or machine living and so on and so on. So you need to introduce a dimension of temporality which is not necessarily something that is trivial to do if you want to maintain the maintain the characteristics of the algorithm. So this is something that we are working on closely with our mathematical department. Uh you have to in some way only let partner truthful partners

within the the develop. So for instance, you don't want people who will provide you with computational P that will fail or that will take a very long time to run proof or that will have a lot of more technical issues. And this is not even talking about people that are actually trying to to damage your model. But this is another completely already another question. uh you also need to implement sometime client specific uh criterians because when you are interacting with other companies of course other companies won't always have a whole set of requirements uh that they will that they will reveal to you in due time and they will want for instance to fize some kind of

operators because they may have previous deal with them or anyway you have to let's say add all of these meta information within your system so that you can let's say satisfy the the two parts in the in the business deal. Uh you also have to discriminate between a homogeneous hardware this way is a very big issue of course because uh in the real life computational cycles are not all the same. Right? If you have a proof that can either run on a GPU or a CPU and you have proof that can only run on CPU and proof that can only run on GPU, how do you balance all of that to maintain uh to maintain all of these

criterions? Because for instance, you cannot if you were to have completely separate cues for CPU and GPU, you probably would end up with some unoptimal use of the total compute power. uh if you mix everything together then do you want to prioritize dual machines or do you want to prioritize GPU machine or whatever I mean that's a very complex set of issues that are also quite interesting to solve I would say and sometime unfortunately add another combinatorial factor to the final complexity of the algorithm which ends up with something being close to close to well virtually unsolvable in a reasonable development of time and once

again you have to to rely on huristics to actually be able to address that kind of issues. So yeah that was it. Thank you for attention. I hope this gave you a glimpse on the technical difficulties and the challenges that come from taking up your research paper and actually porting it over to a final product. And thank you for for your attention.