Lotteries vs. Auctions: Prover Market Design for Ethereum’s ZK endgame

Transcript

kit design for um provers in Ethereum ZK and game. This is joint work with Mikey. Okay, so ZK has always been part of Ethereum's endgame. Um, we've been talking about it for many years and it was a long-term plan, but real time ZK proving is accelerating and here faster than we thought. So, it might look like a medium-term plan now. And this is a screenshot from a Berlin last week or two weeks ago uh citing the payment and alignment of provers as one of the big open problems. and we don't really understand market design and incentives

and economics of integrating provers into the L1 very well. Uh in particular, think of all of the research on transaction fee mechanisms. There is a lot of work that's been done. But for approvers, the design space is just as rich if not richer, but uh there is very little work done so far. And of course the same questions also apply here around incentive alignment, how to find the efficient allocation, how to price things, how to make sure that uh provers are accountable, uh more long-term, how to think about specialization and roles and centralization. And basically most of this we don't understand very well.

So that's the broader motivation. Um maybe a good starting point for thinking about provers is PBS. Um so PBS has a similar goal as what I'm calling PPS PS proposer proveration uh where both try to delegate a complicated task to third parties. In the case of building it's the task of finding the most valuable highest me block. It's a complex task. Uh and in the case of proving it's of course the task of generating a zk proof. Um and there's similarities. Both of them have to run an auction to accomplish this.

But there are also crucial differences. So one difference is think of the direction of the cash flow. With builders, they are essentially buying blockspace because they value it a lot. So they are willing to pay for access to blockspace. Whereas with provers, they're essentially selling the service of proving. So they have to get paid. And this difference is pretty deep because it makes accountability much harder in the provers's case. So here's a more concrete example of how accountability is harder. Um so in the case of PBS, we have to solve the fair exchange problem because there are two parties involved and we have to make sure both of them respect the terms of

the sale. And the way PBS solves this is using trusted relays. These relays are intermediaries that um sit in between the two parties. Builders submit bids as well as the entire block content to relays and then the relays can make sure that the block is valid. They can verify it and they make can make sure that the block content is revealed uh eventually uh to the chain. So basically a relay fully solves the fair exchange problem in the case of PBS. So let's think of a similar architecture for prover markets. You can think of again a relay sitting between provers uh and the protocol and it can collect bits from provers and select a winner. But we're not done because then the winning prover should

hopefully run the proof and deliver a proof or otherwise it can sherk. It can just not show up. Um so in summary a relay can guarantee that the block is valid and delivered and everything goes according to plan in the case of PBS. But with provers a relay fully trusted relay cannot guarantee that the prover will deliver unless of course it requires that the provers submit the proof with their bid which is a huge upfront cost.

Cool. So the big motivating questions here are how to design live prover markets that provers are accountable for delivering if they're allocated and whether we have to use taking and slashing to accomplish this and if so how much and the quick outline um we'll first give a model of procurement auctions with a livveness penalty then we explore two candidate classes of mechanisms uh the first one is proof lotteryies that that are permissionless and don't need any stake. The second one is a normal procurement auction with stake and then we do some analysis of how each of them do and leave some time for

discussion in future work. uh I think a useful paradigm to have in mind throughout the talk is this trade-off space this that I'm calling the accountability trillemma uh between computational efficiency meaning how much redundant work are provers doing like how many uh different proofs how many copies of the proving task are getting done per block um and liveness livveness insurance which is basically kind of the risk that we fail at procurement that no one delivers a proof and in that case, do we get some monetary compensation for it? And the third axis is capital efficiency, meaning how much upfront capital or stake are we requiring from provers to participate in our mechanism.

Okay, so we can start with the model. Uh it's a normal uh procurement auction setting where there are n provers and if the protocol is permissionless then n is unknown. But I'm introducing it here just as a variable for analysis. And the protocol has a task. The task is there's a a block that it wants proven. And it wants to procure this task by um but then so what is the protocol objective is to minimize this cost and this cost has two components. One is capturing the capital efficiency requirement and the other is capturing the livveness requirement. So concretely the protocol loss is um the total

payment to all of the provers if the protocol succeeds at getting some proofs and if the if there the protocol fails and there are no proofs then the protocol incurs this livveness penalty that we're denoting by C. So what should C be? What is the value of C? um conceptually C represents the economic loss the missed opportunity from having a missed slot. So if we are um in the endgame requiring for validity that a block has a ZK proof if the protocol doesn't manage to procure a proof then that slot is missed. So any economic activity that would have happened

doesn't happen anymore. So what is the economic value of a slot? A very good estimate for that is the MEF boost winning bid. And here's a screenshot of in the last week some very high winning bids can get up to a couple hundred ETH. Of course, the average value is much smaller, but still there are is a highly variable value and um probably the very var val valuable blocks are the ones that we're most worried about getting liveness attacks on. So the liess penalty can be kind of large.

Great. So let's look at the first class of mechanisms proof lotteryies. So in these the protocol first announces a bounty a prize X and provers will submit proofs as tickets for a chance to win X. It's kind of a lottery. The proofs are tickets for entry to this lottery to win X. Um I'll note that you don't need any randomness to implement this. You could distribute X equally among all submitted proofs and the analysis and the properties of the mechanism will be the same but the lottery is maybe a simpler mental model to think about. So X will get allocated uniformly at random to one of the proofs that are submitted.

And this might uh this has a proof of work flavor or like proof of useful work flavor might remind you of uh mining pools. I'll say that Alio's coinb coinbased puzzles have also a similar flavor flavor of distributing a reward amongst some submitted provers uh some submitted proofs. Um and you can read this ETH research post for an actual formal model and an and an analysis of this game. But here I'll just give an overview um enough to compare it to auctions.

Cool. So let's say we have the lottery game set up. How do provers behave in this game? In equilibrium, each prover will participate, meaning submit a proof with some probability P depending on how big the prize is. And the protocol can vary the prize size X to target whatever participation rate it wants. So specifically, it can choose a price size to minimize the protocol cost. Cool. So, how does this lever of price size affect participation rate?

Here are maybe some two useful plots. Um, here I've normalize the cost of producing one proof to one. This is a plot of the expected number of proofs as a function of the prize size, the bounty size. So, what does this purple point mean? It says if the protocol wants an expected or on average two proofs per block, it has to post a bounty of 2.3. That means 2.3 times the cost of generating one proof will result in an average of two proofs per block.

The second plot is probability of livveness failure as a function of participation rate. Notice that I've switched the axis from the left one. So it's saying that if I target some expected some average number of proofs per block, what is the chance that no one delivers a proof? So the blue point is can be interpreted as if I target two proofs per block on average it corresponds to a failure probability of 13% that no one delivers a proof. Cool. So this is how the protocol can vary the bounty size and affect the participation rate. So what happens if the protocol chooses the optimal bounty size? So notice how these two plots are one is

increasing, one is decreasing. It's kind of capturing the fact that this protocol cost has two components. The first one, the total payment to provers is increasing in the participation rate. If the participation rate is high, there is a lot of redundancy. Many proofs are getting generated and the mechanism has to compensate all these provers for their efforts. The second term, the liveness penalty is decreasing in participation rate. If a lot of people are joining, the chance that all of the coin flips uh come against us, come up against us and no one joins is higher. So there's an increasing term, a decreasing term. The protocol balances these, you can solve the optimization problem. Turns out you do the math, it's in the post. These are kind of the asmtoics that you get. Um turns out the

optimal bounty size is something that scales logarithmically in C, the livveness failure penalty. Um, and let me just highlight this term. That's the optimal protocol cost. And it's the it's an LNC log log C term plus some lower order terms. And I think this should be exciting for two reasons. One is that log C is a pretty slow growing function. So even if the livveness uh penalty C is really high, a couple hundred ETH, you can run a lottery and incur an expected loss of much smaller than that. The second good news is that this doesn't have any n in there. So the protocol

doesn't need to know the number of potential provers. It can permissionlessly just look at the participation failure rate sorry participation failure pro uh penalty C and as a function of that set its bounty and get some loss. Okay. So to wrap up lotteryies um on this trillemma how is the computational efficiency? Well, we get an LNC number of proofs per block.

How is it in terms of livveness? There is some risk of livveness failure. It comes from this coordination risk where all of the so all of the provers are randomizing and there's a chance all of them happen to choose not to join. Of course, that probability um depends on the participation rate and at the optimal rate that probability is around one over C. Um, but there's also the worry about adversarial livveness attacks. And the good thing about lotteryies is that there is nothing an adversary can do to cause a livveness issue because there is no staking or allocation and there's no sherking possible like there's no bidding stage and allocation and sherking. So it's good on that front. Finally, it's really good for capital efficiency reasons

because it doesn't need any stake. All right. So maybe one critique of lottery is that it doesn't do a good job of price discovery because at no point did provers say anything about what their cost was. We didn't collect bids. So the price signal is very weak. And the counter uh design that is very good at collecting a price signal is an auction that elicits bis from provers. they will actually specify how much they have to be paid for each specific proof proving task and then uses that to figure out which prover is cheapest and which one should win. So concretely uh in an auction we again have provers.

There's an auctioneer. The provers submit bids to the auctioneer. The auctioneer selects the winning proverb the lowest bid or the cheapest prover and then that prover will have to deliver in order to get paid some payment. You can think of it as they get paid their bid for this talk. But this design has a big flaw for proving specifically uh because it can be liveness attacked for free. Like an adversary can come in and bid zero and say I can make it proof for free. It will win because it's very cheap and it will not actually deliver.

So of course you must be thinking it. We might need some accountability here. So we can ask provers to stake and then we can slash that stake and use that as an insurance against the risk of livveness failure. And the natural question is okay how much stake should we ask for? Uh well it will depend on C how much we care about liveness failure how costly that is if the stake is equal to C which is a large value but if it's equal to C then that's definitely enough for us we're fully insured. If the stake is C, it means if we assign the task to approver and they don't deliver, we can slash C, which is all the economic value we could get from the block anyway. So a stake of C is definitely enough. But

let's think about what that means. That means we're asking provers to stake couple of hundred ETH to participate in an auction to then do proving for the chain. That is not going to that C is very big. We can't do this. So what if we can only ask for a smaller state uh stake. So let's consider a stake of C over two. The problem is if the stake is C over two then in order to have enough insurance against the live liveness failure we have to allocate to two provers because then if both of them don't deliver we have a total of C stake to slash to be fully insured. So in general to be fully insured against the livveness failure if the stake is C over

key K then we have to allocate to K provers so we're getting more uh redundancy of compute back at as a trade-off with capital efficiency. Um a nice site comment is that as the state goes to zero uh the auction allocates to everyone so we converge back to the lottery. Um so just highlighting that here we see the trade-off between computational efficiency and capital efficiency. As the capital constraints or like provers's budget for staking is smaller then we need to overallocate to multiple provers um and vice versa.

All right I'm not sure when I started. Did I start on time? Two minutes. All right. So there's a table of all sorts of things you can compare these two mechanism classes uh across but maybe the rule of thumb here is use lottery if the livveness penalty is high if the provers are very budget constraints constraint and if um livveness failure with monetary insurance is not acceptable you might just say like I think it's a bad bad optics or bad user experience to just keep having missed slots it's no amount of money compensates for that then lottery might do better.

Cool. So maybe some future work directions. Uh one obvious one is how to set the lotteryies bounty x. Um a natural design is EIP59 style controllers. Basically the protocol can look at how many proofs showed up in one slot and adjust the bounty accordingly for the next slot. Um, I'll point out the dynamics here are kind of more complex than transactions in AIP559 because these strategic provers are also reacting to the bounty updates. You can like you can basically ask what if the provers are running some no regret strategy by updating their participation rate um as a function of the bounty changing over time and like

ask about the equilibria that this game converges to. It's just like a whole rich area of theory you can do about it. Um more practically there are onchain implementation challenges around credibility and griefing and collusions. So like these proofs have to end up on chain in an censorship resistance way to make sure that the proofs the provers get paid for their work. So for example in a lottery if uh somehow the proposer and assessers collude and only include one approver uh then they will get the full lottery prize and they can distribute amongst themselves. Um so all of these are important. Maybe a more macro met question that's in the meta now is how to pay for the proofs. You

can think of them as a common good and say uh we should use issuance or maybe we can think of it as fully delegated to builders in the builder market and then they can pay for it and so in effect MEB is compensating for it somehow. Um so that's completely open and I think more broadly the direction of understanding accountability gadgets different accountability gadgets whether it's reputation risk or uh staking and slashing or KYC and how exactly they contribute to what like guarantees you get about good behavior is something that's not well understood and it would be great to see more research on it. So, I'll pause here. Happy to answer

questions. [Applause] Um, thank you so much, Miam. Um, we're running really short on time. I know Mr. Lee is going to speak here in a bit. Um, did you already email your presentation? I I think so. Okay, then. Do you mind if we have one question before or two questions uh before you speak? Yeah. Okay. That's what I said. you're going to ask a question. Uh thanks for the talk. Uh but for the the auction approach, can you go to the slide?

So I I think the the proving cost can be deterministic. Right. Then it implies that one pro one prover has the lowest cost to make zk. Then then I think he will if he will constantly win the auction then I think the other provers will be demotivated to stake and the join this auction then finally one or only one or two provers will remain for the auction. then that it consequently there will be very big dependence to very uh few provers 100%. Very very good point. Um so that's people I've been talking about uh more proportional

allocations or allocation rules that uh don't always give the task to the lowest bidder. So succinct for example h uses these proof contests that does exactly that that like sometimes tries to allocate to not the lowest bid. Uh so there is some like trade-off with efficiency. You lose some efficiency but then you get more uh maybe equitable or fair or proportional participation. Uh so I will say that regardless of the axis of how uh proportionally you're allocating the task versus how aggressively to the lowest bidder, the accountability piece still stands. So I would say so here you can plug in any auction you want for this auctioneer.

you still have to make sure that everyone delivers and specifically an adversary can't attack you. So I think basically there are like two orthogonal directions of research to answer. One is about how to make sure provers are accountable and the other one is how to balance efficiency with risk of long-term centralization. Okay. Um yeah one quick question um in the lottery case. Yep. What happens if the prover post like posed as many provers and just post the same like proof? So I'm I'm no ZK expert but I'm told there is a way to make sure that proofs can't be cheaply replicated. Uh so I think you can run a server and then

people send you a request and you issue them a number and then they generate a proof for that number. So basically that means every submission will actually incur the cost of generating the proof and I guess it's fine if you want to generate the proof many times um you will have more tickets but that's okay. Uh great talk I had a question uh is the lottery trustless and if it is how are you managing an onchain randomness? Good question. So on the second front uh you don't have to run the lottery randomly. you can just distribute the prize equally deterministically and equally among all the submissions and

the guarantees of the mechanism will be the same. Um and in terms of trust I guess I am assuming this lottery is a black box that will correctly figure things out. I think you can use the smart contract that will assuming you have censorship resistant uh ways of collecting all of the proof submissions. Assuming you have that, then the lottery function is simply take all the proofs, make sure they're valid and on time and distribute the prize accordingly. Unifor Thank you so much. Um, thank you so much for Sorry. Sorry. It's not really a lottery.

True. What I'm describing is not I just think people are familiar with the concept of a lottery, so maybe it's easier to think about that way. Thank you so much, Miriam. Of course. Thanks for listening.