Paying Nodes That Actually Execute: Proofs a Free-Rider Cannot Copy From a Peer

Transcript

[music] [music] >> Uh thanks for the introduction. Today I'll be talking about full notes and their role in optimistic roll-ups. My goal by the end of the talk is to convince you that full notes or the notes that don't participate in consensus are quite important in the roll-up ecosystem and they should be compensated for their work. So, let's get started. So, just to give some context, uh in optimistic roll-ups like Arbitrum, validators play a crucial role.

Uh they execute the all the transactions that happen on the chain and they post the final state to L1. And the safety of optimistic roll-up depends on the assumption that there is at least one honest validator. Now, consider this scenario where there's a full node and it has the following dilemma. It can either faithfully run all transactions, in which case it has to spend quite some computational resources, which we estimate it to be dollar an hour.

But uh disputes on optimistic roll-ups are quite rare. So, they never receive any reward. So, the net profit for this honest validator is negative $1. Now, consider the other uh aspect of this node. Uh it decides to do uh run nothing, in which case it doesn't spend anything and at the same time it doesn't get anything. So, the net here is zero. So, in this example, we show that we see that uh skipping is a better strategy for full node in optimistic roll-ups.

But, this is obviously a bad outcome for the chain. So, what optimistic roll-ups typically do is they use something called attention mechanism, which is not related to the machine learning attention. Uh What the attention mechanism is supposed to do is it it pays full notes that execute the chain. And there are two reasons why attention notes are important. First, as there are more attention notes, meaning as there are more uh full notes in the network, they the chances of a false assertion being produced or a uh

going unnoticed on the chain is drastically reduces. The second aspect is the data aspect where uh the full notes provide valuable uh data for light clients and wallets. So, they play these two important roles and they should be rewarded for these uh job. But, there's a problem here. If you announce a reward for full uh for full notes, the node operators can manipulate this uh mechanism.

Let's see how they can do it. First, they could register a First, they could register multiple identities, but in fact, run a single instance of of the node. Or even worse, they don't even run a node, but yet uh claim some attention rewards. The fundamental issue here is the chain or the roll-up can't see whether a node is actually executing. Let's see some solutions on how to address this problem.

Consider this uh straw man solution, which is uh at regular intervals draw a lottery among all uh registered parties and assign a reward to one of these parties. Now, consider an honest node. It is faithfully executing the chain and it gets a reward whenever it wins the lottery. There's another set of nodes which are called the free riders. They never execute the node, but the moment they see that um they they win a particular lottery round, they claim uh they claim the reward.

>> [snorts] >> That was the basic uh straw man solution. Um couple of years ago at AFT, uh Sheng and co-authors proposed an improved protocol called proof of diligence. I won't explain the details of it, but the main intuition here is instead of a random lottery that the chain generates, um each node by themselves generate a lottery ticket using a verifiable random function. And if that ticket has certain properties, which is pretty similar to how hash challenges in proof of work work, then they win uh the reward.

So, this is slightly better than the straw man solution, uh but it still has the free rider problem that I mentioned. Earlier this year, uh we proposed Trace, which is an improvement over the proof of diligence protocol. It has a similar structure as uh proof of diligence, but it varies from proof of diligence in one key aspect. In proof of diligence, the the node is proving that they know the state root and the execution root as of a certain block height, but that is something that can be copied

from others. What we do in the Trace protocol is instead of relying on the state route, we need a proof that the node has a full information of the execution trace, which a node can get only if they actually executed all the transactions. And this has quite uh uh advantages properties over over the proof of diligence. Taking a step back, I discussed a straw man and two uh solutions, um but let's look at what attention mechanism all actually needs.

The chain wants to know that uh each attention proof or whenever somebody is claiming a reward, it is based on some independent uh node execution. And the chain also wants that the attention proofs that the nodes are generating cannot be amortized. Meaning, if there are n attention proofs, it means there are uh n independent proof generations. Moreover, we don't want the nodes to skip generating these attention proofs, uh especially when they don't win the lottery.

So, trace that I described earlier has three of the four properties that I mentioned, but uh one of the key property that it doesn't have is uh we don't formally prove the non-amortizability of these uh uh attention proofs. And moreover, what the attention proof uh gives in trace is is a knowledge of the execution trace, but the there's a slight nuance here, which is that the knowledge of execution trace doesn't necessarily mean uh uh independent node execution.

And that is what a chain operator uh actually wants. So, to summarize this line of work, uh what the chain operator wants is independent node execution so that there is less chance of a false assertions being produced. In a follow-up work which was published very recently, we improved on trace in three key aspects. One is cryptographic formalization.

Then an improved construction over trace and a game theoretic analysis. I have the QR code here for more details. In the rest of the talk, I'll give a brief tour of all these three improvements. So instead of showing you the cryptographic formalization which is sort of more academic, I wanted to explain why we need this cryptographic formalization. If you look at all the recent research in SNARKs, they are mostly dedicated to things like batching proofs or aggregating proofs and IBC and recursion. All of these are related to compressing proofs.

But what we want in the case of attention proofs is the opposite. We don't want the proofs to be amortized across different identities. So that's the reason we introduced this new notion of designated proving in the as a cryptographic formalization of attention [snorts] proofs. Then the second is an improved construction over trace. So the the baseline is each honest prover, uh, uh, if the execution trace is of length n, uh,

pays uh uh, order of n computational resources. That's the honest prover's baseline. What we showed in this recent paper is uh we can formally prove that uh a lower bound on the work that is required by any node, not just the honest prover. Then we also showed an upper bound on uh what is the worst an adversary can do or how much uh advantage can an can an adversary get when they uh try to cheat the system.

And the construction I mentioned is based on using per uh per node challenges, which Trace doesn't have. Uh I won't go into the details, but uh you can think of that as um each node have each node having to prove a different thing, so that uh there is no way that they could reuse work across different identities. Now, coming to the last part, which is on the economic analysis of this uh protocol.

So, here is the setting. Uh the players in this game are the node operators. Each of them have different costs. One is to operate a node, which is the cost C. Then there is the cost uh for attention and validation. Both uh we assume there's a reward for both attention and validation uh roles. Then the strategy space for each uh validator is they can either sit out, meaning they don't participate in any of these uh roles, or they can do only attention, or they can do attention plus

validation. So, this is the the main result. We showed that for any non-decreasing uh reward function, the necessary condition is is this. I won't go into the full equation, but the intuition here is if the if the cost of generating attention proof is is quite high compared to the cost of running a node, then there is less incentive for somebody to spin up multiple attention identities.

Whereas if if the cost of attention proof is closer to zero, then as you can see the number of independent executions that this protocol can get us close to one. That was a necessary condition. Uh We also showed that um we can actually realize that condition under under these conditions. Again, I won't go into the details in the interest of time.

Uh But the basic idea here is you want the reward to be such that it covers all the attention costs, meaning nobody would participate if they are not compensated for their uh at least for their cost. So, that becomes the left-hand side of this equation. And the two conditions on the right are regarding you want uh a condition to deter new identities under same operator. And you also have a condition for deterring uh new operators.

An interesting aspect of this uh research is we use real numbers from Arbitrum node uh to see what kind of independent executions we can realize and what are the corresponding costs. So, on the left here we have N, which is the the trace execution length on which that attention proof is based on. On the the right-hand column is the number of independent node executions the protocol can realize.

The second to the last column is how much each attestation proof costs. As you can see if a chain wants to realize more independent executions, which is on the bottom bottom most row of 29 independent executions, the execution trace has to be quite high. And the cost of generating each attestation proof is also quite high. But the chain maybe they the chain doesn't want to spend $14 to realize 29 independent executions. Is there a better way here?

And we show that a chain can realize the same number of independent executions when when the reward curve that it uses is not non-monotonic, but it has this bell shape, meaning beyond a certain number of identities, the reward pool reduces. And here I show particular example of max of zero and and this quadratic form here.

And we show that this reward function gives you the same number of 29 entities 29 independent executions, but at a much lower cost. So, to to give you the main result here, we showed that if if the reward pool is is a constant reward pool, the chain has to spend around $465 per hour to to realize 30 independent operators.

But if it is okay with reducing reward curve, it can realize the same 30 operators using $90 expense. But this has some limitations. We show that the equilibrium that this game reaches in the case of of this decreasing reward function is not very stable. And it also has this property that if there are irrational operators, they can disrupt the entire attention mechanism and bring down the policy the the total available pool to zero.

And this raises a broader policy question, which is how does in general reward curves affect independent participation? And this is something that has discussed in the case of L1 as well in this EIP 8363, which is about tapered issuance. So, the main takeaways from this talk are that attention notes play a crucial role in rollups. And they provide deterrence against false assertions, and they also provide valuable data for

light clients and wallets. So, they should be incentivized to run. And we show that certain class of cryptographic attention mechanisms prevent the so-called free riders, which don't run the node, but it's but try to claim the rewards. And finally, with the economic analysis, we show that certain reward curves determine the type of equilibrium one can achieve in this uh mechanism.

That's all I had. Uh, I have the QR code for our paper here. And this is my email and uh, feel free to reach out for more discussions. >> [applause] >> Great, great, great. Uh, thank you so much, Pranai. And uh, yeah, I hope that now all of the free riders will be eliminated just because of that, but let's dig a little bit deeper into it. And the first question we have, what exactly is execution trace and how is it implemented?

>> Yeah, that's a good question. I kind of uh, pushed it under the rug for this talk. Um, so you can think of execution trace as as the snapshot of the node uh, during the execution of a block. Uh, like most of the optimistic rollups have uh, an arbitrator machine that that records the state of the um, state of the node after each and every instruction. So execution trace is is just a vector of values in one particular pre-decided uh, uh, state of that arbitrator machine.

It's like a snapshot of uh, of the node, um, of the memory of a node. >> All right, seems pretty clear. The next one is why rewarding attention and not slashing inactivity for stake validators? >> Yeah, so if I understood this question, um, so this is mostly for rollups um, where um, where there are very few um, uh, incorrect assertions that are posted. For example, Arbitrum never had a false fire uh, assertion that was posted on mainnet. Uh,

so there the main problem is it's difficult to detect uh, inactivity of uh, validators. >> All right. Uh, up next uh, without running the node, how can I guess rewards be claimed? >> Yeah, if the reward mechanism or the attention mechanism is similar to a straw man where to claim a reward you just show a state route as of a particular block height, then that uh, mechanism is is doomed to fail because anybody can get a state route from querying a RPC node and uh, that's the whole point of this talk

is uh, how do you make uh, claiming rewards more expensive, meaning you want them to claim only when uh, when they run the node. >> Okay, and I guess the final one unless someone of you will scan the QR code and ask more, but while you are doing that, is it only for rollups and not for L1 chains? And I personally also very interested in that. >> Yeah, that's a good question. So, um uh, coming from Offchain Labs and thinking more of uh, rollups, that was the natural uh, thing to target um

in general this whole mechanism of uh, having um, using a cryptographic proof to to ensure that a node does certain things is is widely applicable not just in uh, rollups but also in uh, L1s. And um, the other important aspect is the is the importance of this reward curve that that reduces beyond certain point and that analysis that we did is particularly useful for uh, EIP 8363 which is about tapered issuance.

>> All righty, and on this bombshell we are done with the questions. Thank you so much. >> [music]