Protocol Berg v2: István András Seres - Forking the RANDAO Manipulating Ethereum Distr. Randomness

Thanks. Uh, thanks a lot for having me and thanks for coming to the talk. Let's see if this works. Okay, cool. So, I want to play a game who wants to be a millionaire.

So the question is that what percentage of the blocks a validator with 25% of the stake should propose if we look at the blockchain slice of say 10,000 blocks or slots. So who votes for and the validator is honest. Who votes for A? Hands up. Who votes for B?

30%. Okay. Who votes for C? 25%. Okay.

Who votes for D? 26.6%. All right. So the correct answer is 25%, if the Rando and Ethereum would implement correctly the this distributed randomness beacon, then as a validator you should expect to have if you have 25% of the stake, then also you should expect that you own you you are able to propose the slots and the blocks 25% of the time.

But sadly this is not the case. So the next question is 4,000 bucks. uh so what happens if this validator is economically rational and it exploits all these vulnerabilities that I'm going to describe to you uh so you have again just as a toy example 25% of the stake uh in expectation how much percentage of the blocks you can propose a 20% all right B 30% the round is not this bad C 25% Okay, D. Okay. Yes, you're right.

So, this is the right answer and this is how I'm going to show you that how you how we can arrive to this number at the end of the talk. Okay. And at the end of the talk, there will be a million-doll question. So, uh pay attention. So, um if you need to go and you need to run to other presentation, the TLDDR is that um there was a paper that also identified manipulation technique.

the way you can modify and manipulate this rando lottery if you wish that selects the validators and this is a nice paper presented at last year AFT by Kaia Alur and Matthew Weineberg from Princeton University and we introduce a new class of strategies that allows us to manipulate the rando even further and so basically the the truth is that the rando is even more manipulatable than people thought. So for instance, if you have a coalition or if you think of Lido or a coalition of stakers that control 30% of the stake in Ethereum, then and if they would manipulate the runo um systematically then they would be able to propose almost 33% of the blocks. Okay, so just to be on the same page, uh let me just give you um a quick rundown on leader selection in Ethereum. But first, why do we need randomness in consensus? So, um there's a very famous FLP and celebrated result, the FLP theorem, which says that permissioned traditional consensus u needs randomness is without randomness, it's impossible to have consensus in the asynchronous setting.

But the good news is that once we have randomness, then we can have consensus um in constant expected rounds. If you are interested, if you don't believe me, if you want to check out the FLP theorem's proof, then you can do so um at this link, this is a nice blog post. I suggest you to have a read. Okay. Um and there was a similar result that showed that we need also randomness in the permissionless consensus setting and there even in synchrony without randomness consensus is impossible.

This was shown by Louisis Bay and Raf Garden. Okay, so we need randomness and now let's see how Ethereum computes and outputs randomness. So in Ethereum we have epochs. Each epoch is divided into 32 slots. One slot is u lasts 12 seconds and at each slot we select a validator that has the right to propose a block and each valid block needs to contain a so-called randow reveal which is a randomness contribution to the output of this beacon.

And this rando reveal is nothing else just a BLS signature on the epoch number. And it's important that it's a BLS signature because BLS signatures are unique and deterministic. So just like RSA signatures, I guess all of you know what's an RSA signature is. So the validator can the only thing that the validator can do is just publish a valid block or not. They cannot grind this rando reveal field of the block.

And what we do in an epoch, we sort all these rando reveal values and that's going to be the output of the rando. Um so we have um and and we we take the output of the rando, we feed it into Absuda random permutation and we permute the list of the validators. So currently there are 1.1 million validators in Ethereum. Once we have the output of the beacon, we feed it into a PRP serum permutation.

We permute the list of the validators and the first 32 uh validator indices of this permuted list are going to be the validators in epoch plus two. The whole protocol is a little bit more complicated but that's the gist of it. Um and this is how it looks like this run reveal. It's um it's a BLS signature. This is how it looks like in our favorite blockchain explorer ether scan.

Okay. Um, so what's selfish mining? Interestingly enough, selfish mining. So the ability that you can manipulate the rando output was already known even before the merge. But the EF was saying, okay, you can manipulate the runo, but it's just a tiny bit.

So imagine that you are this adversary denoted as red and you own the last slot in epoch E. So what you can do since you are in epoch E, you've already seen all the rando reveals in that epoch. So you can rec so you can compute the output of the rando seed right and now what you see is okay I'm going to own three slots in epoke plus two but wait a second you can also do um you can also refrain from publishing this last slot right and that also gives now a different rando output which results in a different seed and this different seed will create another permuted set of validators but this time you will end up with six slots in epo plus2. So overall you are better off by now currently not publishing this block but overall since okay you throw one block to the dust bin but in the future you will obtain three more. So overall you are better off.

So in in certain cases if you have these tail slots so from the random manipulation point of view these tail slots are the most important ones. um they allow you to pre premputee the output of the beacon and we can generalize this. Imagine you have k tail slots. Now for each tail slot you you have a binary choice either publish the block or withhold the block. So this gives you altogether two to the k possibilities to two to the k different outputs of the rando seed and then you can rec premp compute all these two to the k different uh configurations in apple key plus2 and obviously an economically rational validator would choose the setting which gives more slots to the validator.

Um and this is just an example that happened uh in 2022 November. Um, Lido had a tail had eight consecutive tail slots. And basically in this particular case, Lido was honest because they published all the slots, all the blocks. Um, and what you can see in the left hand side is that in reality, Lido had two to the eight possible decisions, right? For each tail slot, they could decide publish the block or not.

This results in 256 possible random outcomes. And these 256 different outcomes also define 256 different configurations in epoke plus 2 which results in different number of slots and but we need to adjust. So on the left hand side we see the different number of slots in epo plus2 but we need to adjust these numbers by the sacrified slots in epoke. Um, and what you can see with this red column on the very right end of each of these figures is that Lido could have been better off in this particular example by selectively proposing and withholding certain blocks, but Lido was nice to the Ethereum users. They didn't they did publish all their blocks.

Another objective that a validator could take is the so-called target slot utility. So imagine that you know a priori you know beforehand that in slot two in EO plus2 there will be a there will be an NFT launch or airdrop or some high MEV activity then maybe the validator doesn't care about maximizing the number of obtained slots but they care about just grabbing that specific slot in the future and um so this is also this was identified by Tony Veter in an E3 research post but we analyzed in the paper. Okay. And this was all kind of known before our paper. And in our paper, we describe a new strategy uh that allows the validator to even to have even more power, manipulative power over the output of the runde.

So I have two assumptions for this setting. The first is that the adversary controls at least 20% of the stake. And the second is that this is the configuration of the slots next to each other. So honest is the blue, the malicious is the the random manipulator is the red. So imagine there that we have these slots honest malicious honest malicious.

Then what the adversary can do? The adversary can fork out the middle guy uh in slot n plus2. How? So in slot n plus1 the adversary just builds this block secretly and votes for it with all its validators and the rest of the n rest of the network didn't see this block being proposed. So they just vote on top vote for the slot vote for the block coming from slot n as the head of the blockchain.

What happens in slot n plus2? Um, now the honest validators will build their block on top of the block coming from slot n because they didn't see the block coming from slot n plus one. And again the honest validators uh will vote for this honest block. But the malicious validators will build on top of the secret block coming from slot n plus1. And finally in slot n plus3 now the adversary will publish its fork containing these two blocks coming from slot n plus1 and n plus3.

And if we do the math this upper branch of the tree has two alpha plus 0.4 40% of votes. That's an idiosynchrony of the ethereum protocol. So if you publish a block on time then you get a proposer boost which is currently 40%. And so on the upper branch we have two alpha plus 40% of the votes.

On the lower branch of the tree block three we have one minus alpha votes. So if alpha is larger than 20% then the upper branch will be accepted as the cononical chain. And so basically the adversary if they wanted to then they can fork out this honest guy. And there are many such configurations where you could fork out uh an honest guy with even less stake. And how can we use this?

So why is this useful for um in the context of run manipulation? Imagine again this is the setting. Uh if you don't know forking then what can the adversary do? Just a binary choice. The adversary can either publish a block in the tail slot or not publish a block.

Uh but now so that's just two binary just it is just a binary choice but since we can fork the blockchain we can do more so the adversary might decide to fork the blockchain so not publish a block so this is a secret block u but since the honest guys don't see it they publish a block and if the now the adversary can decide whether to finish forking meaning that the adversary in slot 31 will build its block on top of the secret block and publish that branch. Or the adversary could decide because now the adversary sees the rundown reveal coming from slot 30, the adversary could give up its forking plans and act honestly. And one important thing here is that the only Rondo reveal uh Rando output of the epoch that's visible to the adversary corresponds to the uh upper uppermost branch of the tree because that doesn't include the output of the honest run. Um so that's the only visible at the very beginning of of the attack. So if it gives an unusually high number of slots in epo key plus two then the adversary will fork and the regular selfish mixing happens could happen.

So if we don't if we only know selfish mixing then the adversary only sees the the last two branches of this decision tree. But since we have forking this is just to build up your intuition. Since we have forking now the adversaries strategy space is much larger. So also the adversaries manipulative power increases. Okay.

Um I'm not going into the details how we evaluate it. It's just some mark of decision process in stoastic tools. The main idea is that if the run would be cryptographically unbiasable then what we would see is just this blue line. So if you have alpha portion of the stake then you should you should only be entitled to propose alpha portion o of the blocks as well in expectation. But since you can manipulate the runo um if if the adversary only uses selfish mixing strategies then the adver that's the brown line then the adversary can increase its fair share.

If the adversary reads our paper and uses our proposed random manipulation strategies, then the adversary can increase even further uh its fair share and we also evaluate this target slot probability. So uh if you look at this graph at let's say Lido has roughly 30% of the stake. If Lido would wanted to have a specific slot in in a future epoch, they can do it roughly with 20%. Um okay if the run would be completely unbiasable then what would we see in this graph uh it would be completely blue right so there was nothing you could do the only thing you you would need to do is just publish a block whenever you have the chance to publish a block but since this randomness beacon is biasable the adversary can do nasty things and the adversary is more incentivized to do nasty things is also the uh the staking power increases because now it has more choices to to do nasty things. So it's kind of pretty alarming that this figure is not entirely blue, but you also see forking, selfish mixing and so on.

Um, so all these techniques that I described so far are good for the adversary, right? Because they get richer and richer, they have more blocks. Um, but it's good for me and you and for us regular users. So it's a negative externality for everyone because now the the throughput of the blockchain decreases as more and more people and coalition of adversaries uses these random manipulation strategies also the blockchain throughput decreases because now we will see a lot of missed adversarial slots and a lot of fork lot of honest blocks that are forked from the canonical chain. um a natural question that we also analyze in the paper has the rando been manipulated.

Um so we identifi so we have these two adversarial strategies and in in the case of selfish mixing we only see the one reveals that has been published. So we don't see the entire uh entire history that we would need in order to recomputee all the possible run configurations that the adversary sees. So with selfish mixing it's a little bit tricky whether manipulation happened or what's the real reason why the adversary didn't publish those blocks because as the public we cannot recmp compute all what the adversary sees but the situation for forking is different because with forking even though an honest block is forked from the blockchain the runo reveal is there so we can recmp compute every possible state and if a forking happens for the reasons of frontload and it's completely visible for everyone. Um we made quite a large uh experimental analysis. So we uh we collected all the data since the merge up to two 2024 uh October 1st.

There are we use some public validator pool mapping. So a lot of we know which validator belongs to which entity. Lido, Binance, Kraken. And the way you need to read this graph is that for instance six times Lido had uh sorry 67 times Lido had six tail slots in at the end of an epoch and out of these 67 times Lido missed at least one of these tail slots only once. Um, so what you can see from this figure is that all these wealthy entities already had dozens of opportunities to mess around with the randomness and and manipulate it in their favor.

Okay. Um, what you can see here is that when all the validators proposed all their tail slots, then actually a lot of times this is the worst column. a lot of times they could have been better off by not proposing one of these stair slots. So actually the bottom line here is that hundreds or thousands time thousands of times like in case of Coinbase almost 5,000 times they would have been better off by manipulating the rando whenever they had the chance. So they leave a lot of money on the table like millions of dollars.

Um I'm not going into the details and describe the statistical tests that we use. they are quite classical tools like Z tests, t tests. The bottom line is that um there's an expected uh there's an expected uh empirical distribution. There's an expected distribution and an empirical distribution that we we gathered and they match pretty nicely. So with strong statistical tools, we cannot reject the hypothesis that they are uh they are not manipulating the rando.

But again this only this only this is only valid the statement for a very particular type of random manipulation which which manipulates the rando consistently. So maybe they are doing it once every day or once every month but what we could say and what we do see that they are not doing it like all the time and this is what also the statistical tests say. Okay. Um there were two forking reorggs u executed by Lido and in both cases Lido was better off by forking um poor home validator or who knows who um out from the canonical chain was it on purpose or not only only they know. Um okay so wrapping up food for thought uh why don't we see random manipulations yet?

uh can we tolerate this level of manipulatability? Is it going to be part of the MEV tool chain? I would guess in the long run because people are leaving millions of dollars on the table. So I would expect that sooner or later this vulnerability and the weakness of the randomness generation protocol would be exploited. This is just a personal opinion.

Um shall we just rely on social slashing as a fix? I would say no because otherwise we wouldn't be here. We would be on Wall Street in New York, right? So I would say that we we need cryptographic guarantees for unbiasability to to not have this rich gets richer uh phenomenon and we know how to do it right so we know verifiable delay functions weighted threshold VRFs there are many tools and we know how to build uh unbiasable randomness beacons uh feel free to reach out uh wherever you want and here's our paper which was accepted at CCS this year. So maybe we will see you at Taipei Taiwan CCS25.

Here's the GitHub where you can access all the code and scripts that we wrote. And now is the million dollar question. What should we do as a community? Should we fix the run? We sent an academic grant to the EF.

It it got rejected. Or we should just go back to New York City and Wall Street and and pray social slashing or some vitalik saves us or I don't know let's exploit this me. Yeah. Or we should just chill and have a clum mate. I don't know.

So that's a question for all of you. I don't have answers. Thank you. [Applause] Okay cool. Thank you.

Uh, now I actually have some questions for you if that works. Yeah, sure. Um, cool. So, the first one, doesn't missing a slot mean that the proposer gives up all fees and me revenue? Is that considered here?

Sure. Um, that's absolutely considered as in the toy example at the very beginning of the talk because in the future you might have much more than just this one missed slot. So in the end in total it will be better for the for the manipulator validator. Okay. Um then the next one I think you also touched um upon it a little bit.

Um isn't this kind of attack easy to detect? Wouldn't it harm the attacker's reputation? Uh so for selfish mixing uh I mean for forking it's absolutely visible. Can't see your slides. Oh okay.

So anyways for forking it's absolutely visible because all the rando reviews are on chain but for selfish mixing by definition some of the rando reviews are missing because the adversary didn't publish them. So if you don't have access to the runo reviews you cannot recomputee all the rando outcomes that the adversary sees. So in that case we we can only rely on statistical tests. And then maybe last one. Um, what if an attacker tries to maximize the number of tail slots they can they control in the next epoch so that they attack can be more easily reiterated?

Have you done this analysis? Yes. And interestingly enough, the optimal strategy to so this is not the optimal strategy. So um this code like in the paper we call it like tail maximization strategy or something like that and intuitively this is what you should do if you want to op optimize the number of slots overall but as it turns out this is not the optimal strategy. So you can do better than that and u what what you could see in the slides were the optimal strategies and not the tail maximization strategy.

So yes I think we have time for one last one. Um should we should we or can we address these vulnerabilities as part of the beam chain design? Yeah, I mean uh so there was this academic grants round for Ethereum and there was this there was a wish list where they were saying please let's fix the rendo because we know that there are vulnerabilities and um so we thought that they want to fix it in the upcoming beam chain update but uh it seems that uh other more important things like ZKVM I don't know has pri more priority so uh I don't know what are the plans for people at the EF uh but it seems not fixing though I mean it's it's not an issue until it will be an issue and exploited but that's just a personal opinion. Okay.