Ed Felten 🛸 Improving Deadline Protocols via Censorship Detection

[Music] thanks everybody thanks for your time um I am um I'm sorry I couldn't be there with you in Istanbul or or Prague today um but I want to talk about um improving deadline protocols via censorship detection so this is a little bit different to talk about censorship detection as opposed to prevention but I think it's an important and uh and useful thing to be doing uh and the reason is simply that of course obviously we'd like to prevent censorship but even in systems that prevent censorship the worst case censorship uh time that you that you see is longer than you'd like it to be so ethereum being a good example right ethereum has a certain resistance to censorship and you know and I'll dig into this uh a little bit uh a lot of it repeats earlier earlier talks from today um but you in practice usually on ethereum you can get much faster inclusion than the worst case guarantee so the idea here is that by being able to detect censorship on chain that is a chain to be able to detect whether it's being censored that you can actually uh make protocols more efficient but let me let me talk a little bit more in detail about what I mean by that so I'm talking here about deadline protocols and what I mean by a deadline protocol is any protocol that requires part to act before a deadline so a classic example of this is something like an onchain auction where parties have to submit their bids before a deadline or some kind of interactive protocol that has some default thing that happens if a party doesn't act or if nobody does anything by a time of course the example that is of most direct interest to me is a fraud proofs and optimistic rollups right where a party has where some party might make a claim on ethereum about uh about what is the correct outcome of execution on arbitrum and other parties have uh have to respond by a deadline if they think that's wrong um similarly The veto in an optimistic side chain kind of design that's a design that's like an optimistic rollup except instead of having fraud proofs you just have some kind of committee veto in all of these cases you have some kind of deadline if a party misses a deadline then um either that party will be disadvantaged or the protocol will not work as well so any protocol that assumes an honest party will be able to act before a deadline is a deadline protocol and these are these are pretty common um so um sure okay so that's what we're trying to um that's what we're trying to uh protect okay so our threat model here is the idea that there's an adversary and the adversary wants to is targeting some particular deadline for protocol and they want to censor transactions in that targeted deadline protocol not necessarily all the transactions in that protocol but the transactions that are submitted by certain honest parties or certain kinds of transactions that um uh or certain kinds of transactions that uh will advance the protocol in a way that the adversary doesn't like so we assume in um that that the adversary will be trying to compromise ethereum block proposers or block Builders and compromise them either by becoming um a proposer or Builder on at scale or by paying proposers and Builders to behave in a certain way or by attacking them some other way so we're going to assume the attacker has some control over some fraction of the proposing or building um uh um activity and the adversary's motive here will be taken as financial gain that is the adversary has the the idea that they can corrupt the operation of the deadline protocol by using their proposing and building power um and if they can do that they can get some financial gain within the protocol or that they can discredit the protocol in order to get financial gain so in an online auction they might bid low and then try to keep other bids from getting in in some kind of a an optimistic L2 protocol they might uh try to put in a false claim about the execution and then try to censor any one uh any attempts to disagree with that and so on so that's our basic threat model OKAY common responses to this are basically two things in a low stakes protocol or in a protocol that's not carefully designed you might just ignore the the issue or make deadlines a little bit longer um now that might be a rational thing to do if the stakes in your protocol are low you might figure either a that no attacker is likely to find it worthwhile to attack your protocol in this way that an attack would be too cumbersome or expensive to do given the low value in a particular protocol um you might also decide that well there is a risk of an attack but we would choose to make our protocol more responsive by having faster deadlines and that's a good trade-off but in a high stakes protocol that's really not going to cut it and the usual approach in a high stakes protocol is to make the deadline longer than the worst case assumed censorship um and of course the extreme case of this is something like an optimistic rollup where uh on arbitrum and other similar protocols the uh the deadline for action in the rollup or dispute protocol is is conventionally set to seven days um because seven days is the worst case assume censorship attack on ethereum that would not trigger some kind of of a social response Why seven days well it's basically a social cons consensus and it's it's kind of thing that vitalic and other people say is safe to do um in public and so um the worst case assumed censorship there is seven days obviously we would like that to be to be shorter but in a protocol like arbitrum where an attacker could plausibly steal billions of dollars by carrying out a successful attack of this sort um the um um this um we really do need to uh work with the worst case assume censorship time okay so the key idea in this talk as I hinted earlier is that we're going to design an onchain test for sensorship on ethereum with one-sided error and what I mean by that is that the test will say one of two things um it will say either that there has not been significant censorship since sometime t0 that's in the recent past or that maybe there has been censorship we don't know right so um the uh so and the test is designed to be correct um when it g when it says U no significant censorship correct in his statistical sense that we have extremely high statistical confidence that uh that the result is correct and then the idea is that in a deadline protocol we can shorten the deadline um if and only if the test says no censorship so we might say for example that the the deadline in some optimistic rollup is seven days but if the test says that there's been three hours with no significant censorship then uh then we can declare that three hours to be enough right and so we're going to it's it's a sort of another form of optimistic protocol now of course the challenge is how do we do that how do we build an onchain test for censorship it seems it it might seem a little paradox toxic well how can a chain know that its input has been censored um in fact I don't know of any way of any example where it's possible to build a test with one sided error in the other direction where the chain can know it's been censored but um but but it turns out it is possible in many cases to build a test that allows a chain to know that it is not being censored so let me talk about how to do that in AUM so uh so just just by way of review because I know ear speakers have talked about this and to establish the terminology I'm going to use we can talk in censorship attacks on ethereum there are basically two uh different levels or strengths uh what I'll call weak censorship is uh an attack against a particular transaction where some block proposers refuse to include The Unwanted transactions in their in their blocks um strong censorship uh which typically by the way is applied on top top of weak censorship the idea is not only to attack particular transactions to try to keep them out but to attack blocks so if an unwanted transaction unwanted by the the sensor is included in a block then the attacker either refuses to attest to the block with their proposers to try to prevent that block from getting um accepted or if the block does get enough attestations the attacker will reorg the chain to exclude that block so weak censorship um as um you know as is pretty well known um as long as uh you can avoid be as long as some um block proposers um are are not participating in the censorship but strong censorship has the uh has the undesirable feature that if the attacker does control enough of the proposer or Builder power they can sustain a strong censorship ATT attack for a long time okay so defeating weak censorship and this is just well known again um again review and setting up terminology for uh for later um if we suppose that some fraction F of proposers are honest which means that they build blocks that are not deliberately excluding or the blocks they propose are not deliberately excluding um a transaction and we're assuming here that the transaction that is the target of censorship is um has gas parameters um that um uh and other characteristics that make the transaction valid so it could be included and also that it includes a generous tip so that a rational um proposer or Builder who's not trying to censor would include it but suppose some fraction F of proposers are honest in the sense that they're going to build blocks that are not deliberately censoring this targeted transaction and then if we say well let X be the number of honest slots that is the number of slots in the um in the consensus protocol call that are built by Honest proposers out of n total slots then uh we have this result that says basically the probability that the number of honest slots is less than or equal to some number K is this a binomial sum and this is essentially just the formula for flipping a weighted coin right we're flipping a weighted coin which with probability f u comes up as honest and with probability one minus up comes up as dishonest so this is basic stuff right all right against strong censorship again the assumption is that the attacker adversary is doing weak censorship but when the weak censorship fails they'll somehow suppress the honestly produced block and we'll assume the adversary we have to assume the adversary controls enough proposers to do this so the key observation here that makes the task possible is that the attacker if they're going to carry out a successful attack they have to turn every honest slot in the consensus protocol into an empty slot a slot that does not include um a block in the canonical chain uh right so they can do that either by uh either by uh uh arranging that there are not enough attestations to the block or else by reorg away but either way in the eventual canonical chain um any slot built by an honest uh proposer uh will need to be made empty by the adversary in order for the attack to succeed so then it follows that if the attack was successful the number of honest slots during the attack time is going to be less than a Rec to the number of empty slots right because every honest slot will be empty but of course some um slots might be empty for other reasons and then of course the other nice thing is that we can measure the number of empty slots on chain over some interval of time we could look at how uh we can look at how the time stamp advances divide that by 12 that gives us the number of slots and then of course we can also see how many blocks were added to the canonical chain during that time subtract and that gives you the number of empty slots so we can tell the number of empty slots and that's an upper bound on the number of honest slots okay next step now let's go back say again propose suppose a fraction of f of proposers are honest and non- censoring and as before we'll let X be the number of honest slots out of n total slots and we'll let y be the number of empty slots out of the same end total slots now we know from the previous slide that X the honest slots or less than equal to Y the number of empty slots and so the um uh and so this uh uh this bound on on probabilities follows that the probability that the number that why the number of empty slots is less than some uh is less than some bound can't be bigger than the probability that the number of honest slots was less than that Val and so that that it follows that if a strong attack has occurred that we have this equation at the bottom that the probability that the number of empty slots was less than K given that an attack has occurred is upper bounded by this binomial uh formula which is just the probability that X is less than or equal to K copied over from the previous slide so now we have a statistical property um that um will uh we we have this statistical property that um will hold if a strong attack has occurred right and so now we can say this allows us to build a statistical test of the hypothesis that a successful attack has occurred um so in other words it says if an attack we can build a test such that if an attack occurred that test will detect it with high probability so if we can reject the hypothesis the successful attack occurred at a very high confidence level very strong confidence level say p equals 10us 6 meaning that the probability that the test would miss an actual attack is less than one in a million um that is if Cas slots were missing out of n total slots and this equation holds then the test can say that there's no sensorship okay so now if we if we're given values of K the number of actually empty slots and the number of slots that elapsed and it assumed value of f the the fraction of proposers who we assume will behave honestly then we can actually implement the test and the way to implement this test is in practice we'll choose these parameters in advance and we'll precompute that summation off chain and then build a simple test that we can do on chain so for example just running the numbers if we assume 10% honest proposers we can report no censorship if at most 34 out of 688 slots are empty that's about 2 hours and 18 minutes 688 slots or with the same assumption we can report no censorship if that most four slots out of 225 were empty that is no more than four empty slots out of 45 minutes and by the way these tests would always have passed in the entire history of ethereum up to now well since the merge which was the first time that a test like this was possible all right now there's a couple of annoying issues that we need to get past in order to make this real um annoying issue number one is the adversary gets to know in advance the next uh few proposers uh worst case the adversary might know the next 64 proposers and so they can wait to launch the attack until it knows that all of those will be its friends um and so we need to tweak the test a little bit the mitigation here is to just add 64 slots to the end of the test assuming that there will be no evidence that there will that the the attacker can arrange that there will be no empty slots out of the first 64 the second issue is that if the test fails uh we'll be tempted to do it again over the following end blocks but that's actually UNS that's an example of what in applied statistics is called packing um basically um that if there's an Epsilon chance of failing each time and we do the test over and over until it succeeds then we don't have an Epsilon um chance of error so the mitigation here is if we're going to do up to let's say R repetitions we can do each one to a confidence level of Epsilon over R then we'll have overall an Epsilon confidence um or at worst that we ever get it wrong or alternatively we can set a total budget of Epsilon and spend that over a set of repetitions taking advantage of the fact that we probably won't need more than one uh either way we need to make sure that we don't um pack by trying to test over and over till it succeeds okay next steps here what can we do for optimistic Roll-Ups or optimistic side chains you can decide on what value of f um is safe to assume I think you could reasonably do do the test assuming f is 5% or 2% or 1% it's kind of a policy decision you can then Deploy on ethereum a censorship orical contract with some wired in values of these parameters and we've actually built a test version of this on I forget either gorle or sepolia and then you can update the timeout in your protocol to be adaptive based on the censorship Oracle result and that's it thanks everybody uh please if you have questions please put them in the uh in the chat um in the in the in the chat room that people are seeing in the uh in the event