Rethinking Censorship Resistance: A Rateless Sharding Txs Approach

Transcript

All right. Well, hello everyone. I'm Alejandro and I'm going to talk about censorship resistance. Uh at the core protocol level. Okay, um We're a lean team at the moment. Just last day. So, thank you for coming. Um [snorts] Okay, so who thinks here that Ethereum is censorship resistant? I see. I I like I like You see lean team, but you guys know what you guys are talking about. Uh yeah, it depends, right? It depends. I'm going to argue that not enough. It's not censorship resistant enough.

So, Ethereum looks a little bit like Uh bear with me here, you know, big differences, but it kind of looks a little bit like the protocol at the bottom, right? We have a four proposers here. Um but there is one that per every uh slot of time controls ordering. Right? So, this one can decide not to include some transaction just deliberately or front run it as well deliberately. There are some proposals to alleviate that with Fossil, with uh Braids, uh which are interesting. And actually the Braids one is uh kind of an analogous of what we uh what I'm showing in the top protocol, which is what we call multi-concurrent proposers. So, in the top protocol is also a BFT protocol.

Um what we have is four proposers, but they're proposing each uh [snorts] one value one block, if you like. And then they propose it concurrently. There is [snorts] in the case of this protocol four binary consensus instances to decide whether we include that block or not. And then a super block is what is decided in this uh slot, right? In this round of consensus. So, no single proposer controls ordering in one single slot of time. So, even if one proposer lights up uh sensors a transaction, you can still include that transaction if other proposers don't censor it. And if you have sent it to those other proposers.

This is what is called uh MCP, multi-concurrent proposers. And um this is what the you know, what the Sui guys are doing at those. Hedera uh what Braids is for Ethereum. What we're doing at Saygega. Um I'm sure you know what the Pod guys are doing. I'm sure I'm missing a few more. And it's supposed to be the holy grail for censorship resistance. But I'm going to argue that this is not actually real-time censorship resistance. The reason is because of this three-way trade-off. So, actually let me go a bit forward. So, there's basically three things that you can do as a user right now in these MCP chains. You can either send a transaction once and if it gets censored, uh you know, I got censored, so I'm just I lost the arbitrage opportunity or whatever, so I just I give up, right?

I can instead keep sending the transaction to other proposers one at a time. And then I do not get censored, but in every single slot one single proposer can censor me, so I might get um not the expected latency that I was expecting if I if I wasn't being censored by some proposers. Or I can just send it to more than one proposer, say all proposers to get the highest level of censorship resistance. And in that case I'm guaranteed to be included this transaction in one slot, what they call real-time censorship resistance. But somebody's got to pay for that, right? Um so, this transaction might appear n times in the chain and somebody's got to pay for that. And so, MCP chains are facing a difficult question.

Uh who pays for that? Is it the system absorbing the cost or are users going to pay for that? And actually in production, we already have some MCP chains that are facing this problem and they some of them are facing it differently from others. So, on one side, uh I know for a fact that Filecoin, Sui or Aptos are just subsidizing the cost. So, uh in the case of Sui, a transaction appears five times in the chain. Um it's a replication factor that they target. But the users pay for it once, which means that the throughput if it the throughput is 100,000 transactions per second, the goodput, the useful throughput, is actually 20,000 transactions per second, 20% of that.

In the case of Hedera, they're actually uh they actually explicitly say that if a user if a user sends a transaction twice, if a transaction appears twice, the user pays twice. And it's interesting that they pay twice even for execution, which uh the transaction is definitely only executed once. But they pay twice for that. Um for ordering they pay twice and that's rightfully so. Um but what that means is that if a user wants to tolerate deterministically 99 proposers censoring, let's say, then he he needs to pay for the transaction 100 times. So, it's not really affordable censorship resistance, right? Another note is that the reason why this is not a real problem, cuz the problem with the the chains on the right is that this could be exploitable, right? It's an attack vector because users don't pay for the duplication, so they could just

keep sending the same transaction concurrently and really decrease the goodput without really paying The reason why it's not a problem is through is because of trusted RPCs. So, in the case of Sui, for example, the user sends the transaction to the trusted RPC and the trusted RPC targets five proposers. And so, in a way, I like to see the evolution of providing censorship resistance in uh Web3 in this way. So, first we have leader-based consensus protocols, right? We have one proposer per slot. Great, we have a trust uh you know, a decentralized system. We have some level of censorship resistance because eventually one of the proposers includes my transaction. Then we realize, okay, you actually many applications you want low latency for this, right? There's always some time sensitivity to when a transaction is included. And that's why

MCP is proposed. Then you go one step further. Sorry. [clears throat] You go one step further and you realize somebody's got to pay for that. Um and it shouldn't be the system because then it's not it's an attack vector. And that's what Hedera does. And finally, the work that we have been doing at Saygega with uh with the Sui folks, is uh to try to alleviate this cost. And to alleviate this cost, what we're doing is sharding the transaction. So, we're dividing transactions in chunks and sending different chunks to different proposers. Uh we do it with rateless codes. It's a not a very complicated uh protocol to understand.

Um but let me uh show you with an example compared to the naive application. So, on the left right here is what MCP systems do at the moment, right? A propo- a user who sends a transaction with k bits. And uh if he wants some level of censorship resistance, it sends the same transaction to three proposers, let's say. >> [snorts] >> And what that means is that the tolerance to n proposers censoring translates in a fee multiplying by n as well. And also in the goodput of the system decreasing by n. By the same by the same uh factor. Ins- If instead you shard the transaction to get the same uh level of censorship resistance, you actually only have a constant increase in fees.

And you also got a constant decrease in uh goodput relative to the throughput. The way the protocol actually Let me go forward a little bit. So, the way the protocol works is uh is not that complicated. You basically the user um attaches some metadata to each shard. So, it it uh rateless codes the transaction, it erasure codes the transaction. Uh I'm going to I'm going to show different It's a user-facing protocol, so the user can decide how to shard the transaction. And we have both variants. But basically there it sends some metadata to each shard, which is a commitment to the uh transaction. It identifies the shard to a particular transaction.

Um then it in this in this in the main version of the protocol, it sends some rateless some symbols that uh from rateless from fountain codes in each shard. And uh it The advantage of rateless codes is relative to erasure codes is that uh you can keep sending new symbols, whereas in erasure codes you cannot have to commit to how you uh uh partition the transaction in different chunks. And uh the what multiple symbols is what we call a bundle. And so, each each shard basically contains a bundle of symbols and each symbol contributes to reconstructing the transaction.

And uh then, you know, we have with this protocol calculated what is the probability of single slot inclusion in the presence of some uh size of an adversary that's trying to censor. Um also, what is the theoretical lower bound? So, if we had the best protocol with no metadata added whatsoever, what would be the overhead to provide censorship resistance in the best case for any protocol? And we show that we asymptotically approximate that. I'm going to show you that in a minute. And uh and then uh yeah, to determine the execution order, that's also an interesting question. How do you determine the order of a transaction if it comes in kind of like shards, right?

And the way we do it is the intuitive way in which we the moment the transaction is reconstructible, that's the order of the transaction. So, the moment the the the last shard that is needed for the construction, which is that a deterministic uh event, comes ordered, that is the order in the chain of that transaction. And so, th- this is entirely a user-facing protocol that is orthogonal to any MCP uh chain. Actually, it's even you know, you can have a single leader chain. You just don't get the advantages because at some point there's one leader that just can reconstruct the transaction and decide the ordering.

Um but yeah, so it's entirely user-facing and the user has a bunch of parameters that he can decide. So, that's the other nice thing about this protocol. The system doesn't need to commit to some kind of like generic notion of censorship resistance. It's the It's the user that can really tweak what is the parameters that make sense for him in terms of what's the adversary that it assumes. What is the cost that it's willing to pay? What is the admissible latency in the worst case given the censor um the censoring size. What is the probability that the adversary cuz another nice thing that you get with this is for some definition of privacy, you get some privacy because uh you proposers don't really get the transaction until they reconstruct it.

The censoring leaking there and where one of our future um work that we're working at the moment is to get non-linear leaking in the number of shards that you get for the construction. So, basically not be able to reconstruct the transaction to any leak any information about the transaction until the proposers have so many shards that they basically are close to reconstructing the transaction. Uh but the point is if you cannot reconstruct the transaction, you cannot even extract MEV. So, that's another parameter that the user can decide, which is different from censorship resistance. And uh on Tuesday I presented the analysis, the economic analysis of that.

How much MEV What basically was the cost to protect a transaction from MEV depending on the extractable value of the transaction with uh with this sharding approach. And yeah, so then we provide some um safety properties that which are intuitive non-malleability [snorts] unique decode, and the deterministic order that I was talking about. And uh what we see here at the bottom is some uh probability of the transaction being reconstructed in the presence of an adversary that controls one out of every eight proposers and all uh at least one is censoring.

So, 12.5% of the proposers are censoring. Depending on how many uh on the x-axis is basically how many proposers you send a shard to and how many symbols per proposer. So, how big of a shard you send. There's a difference on the left axis, the left plot and the right plot. On the left plot is because the transaction size is bigger. So, you actually send um you need to send more symbols per um per proposer in order to reconstruct the transaction with less lanes. That's why the the kind of like sigmoidal increase happens later when you contact more lanes.

Um but of course on the on the right side what we see is uh Well, on the left side what we see is the more lanes you send per shard, obviously the easier it's going to be to reconstruct the transaction as you send to more proposers. Like as you send more shards cuz you're just sending more symbols in the network. On the right side what we see is obviously that the naive replication case pretty much has a success probability that is overwhelmingly high, but you need to pay for each duplicate. And I'm going to show a little bit more of that later. I already talked about this. Okay, this is probably the most interesting plot of the of the talk, I think.

And uh this is exactly what I was talking about on before on the cost of providing censorship resistance. So, this is for again, for a census uh censorship size of 12.5% of the proposers trying to censor the transaction, but we don't know which ones. And so, we're sending duplicates or in the case of the sharding solution, shards at random to some of the proposers. And on the x-axis is the size of the transaction in bytes. And on the y-axis is the metadata overhead. So, what how much extra data are we sending just to provide censorship resistance.

And we're comparing it with the naive case, you know, which is what we do now in the in MCP chains, what you can do in Aptos and Sui, just replicating the transaction. In the case, for example, of the highest blue point is a replication factor of 5.5. Um and and then as the payload size increases, how this alleviates the uh cost, the overhead cost to provide censorship resistance through sharding. And how it approximates actually the information theoretic lower bound. Um which is quite nice. Um and already, you know, for a transaction size of just 10,000 bytes, it already is a dramatic decrease in cost for users to actually tap into censorship resistance.

And And And on top of that, also get MEV protection. Of course, uh this is now it's just a sharding proposal. And of course, depending on how big of an adversary you want to tolerate censoring you, you are going to need to send more shards. But the important bit is that this cost also alleviates dramatically and in all of them for whatever adversary just asymptotically converges to the information theoretic lower bound. And now latency. So, how much does this add as well because you need to reconstruct the transaction? Well, uh intuitively for some of the people in in the in the room, for sure, actually

um sharding a transaction can help with latency because you are using multiple channels. And so, you're not overloading a particular uh networking channel. And actually, that's what we have experimented in our test that uh for some cases when the transaction is big enough, it's actually better to shard the transaction for latency than it is to just send the the transaction naively to a number of proposers. But anyways, this is like ridiculous latency. And it's ridiculously parallelizable as well, you know, what we're talking about. 1 to 3 milliseconds in all cases. So, it's really This is a strong advantage of sharding a transaction compared to threshold encryption and decryption because as I was saying, this is not just about um censorship resistance, but also MEV protection. And so, we and privacy

or until decode privacy. Um and so, there's there's like some interesting comparison with threshold encryption. But threshold encryption increases a little bit more the latency. Apart from one more problem that we have found with threshold encryption is that in many cases it relies on non-standard cryptographic assumptions. We actually I don't know if it's out yet, but if not, it's going to be out soon. A paper in which we prove that um some of these standard assumptions are actually broken. So, the threshold encryption schemes are not safe. They don't provide the properties that they say they provide. I already mentioned as well that part of the future work we're working on is providing non-linear leaking per shard that you obtain.

And the other one is uh also the first economic model on how to price the amount of data that each proposer is distributing in this multi-concurrent proposer design. And so, yeah, that's uh that's Sedona. I hope you agree with me that current chains are not in an resistant or MEV protected in an affordable way and a trusted way. And that something like uh sharding transactions are just necessary to provide real trustless censorship resistant systems. >> [applause] >> We have 5 minutes for questions and answers.

Uh Yeah, thanks for the talk. I'm wondering if uh you can say a bit more about potential drawbacks of this uh solution. For example, I'm wondering if there is potential scenario where many transactions uh become decoded at the same time deterministically or if the deterministic rule that I said that might create like a huge burst uh of loads that has to be executed very quickly. Is Could this be a problem? That is an interesting interesting question. Yes, so you're saying that one block where suddenly you have Right. So, in the in the typical Imagine, you know, you send the transaction If I'm understanding what you're saying, it's like in the typical case, if you had no duplication whatsoever, then maybe your transaction

throughput would be 200,000 transactions, but because now the shards divide the um the like divide by some fraction the size, then you can have actually If you divide it by five, then you can have actually a million transactions per second in one instance. Right. Um that is a very interesting point. I have not thought about that. Um but that's the funny thing something to think about. That could create a bottleneck on the already bottleneck execution. >> [laughter] >> So, yeah, that's a very good point. Another another threat another disadvantage that that is immediate is is shown here. Like you need like if your payload size is very very small, uh you you might be better off just just duplicating your transaction, you know, because there's some metadata that you have to add.

Yeah. >> [snorts] >> By the way, this is again That's a good point because that affects the system. The other point I said is as I said, it's completely a user-facing protocol. So, it's not about forcing down the throat of the user anything. It's just giving more options to for the users to choose what are the properties that they want to tolerate. Thanks. What sort of thing would be in the metadata? Would that allow censor resistance? Would it be data that could be used to Excuse me. Say that again.

Sorry. What sort of thing would be in the metadata attached to the shards? Would it be something that would enable censorship or could be used to decide to censor? Um well, it would be something that allows you to identify Okay. Depends how you do it, right? Like this is more um researchy yet. It's not engineering yet. Um so, it does depend on how you do it, but what Basically, what you put in the metadata is a way to identify to link together shards. So, like some commitment that links them together to the same transaction. And a way to prove that someone has enough balance to pay for the ordering of this.

And then how much you want to leak or are you uh admissibly leaking from that is uh is something that we haven't thought about, but of course, there's different approaches that will leak more or less information on the metadata. Also a very good point. Yeah. Thank you very