# The Rated List

- Speakers: [hopinheimer](https://streameth.org/speakers/hopinheimer), [Chirag Mahaveer Parmar](https://streameth.org/speakers/chirag-mahaveer-parmar)
- Channel: [Devcon 7 SEA](https://streameth.org/devcon_7_sea)
- Date: 2024-11-13
- Duration: 17:32
- Watch: https://streameth.org/watch/6734828d9dbb7a90e1dd808a

## Description

The Rated List construction aims to minimise the number of requests required to complete sampling in Data Availability Sampling (DAS) for Ethereum. This optimisation becomes especially critical in the context of Full DAS, as data production per slot is anticipated to far exceed the current Deneb-Cancun (Dencun) specifications. The Rated List attempts to improve rate of successful sampling against unfavourable network conditions there by reducing the bandwidth consumption of the overall network.

## About the speakers

### hopinheimer

Hi! I'm Manas aka hopinheimer. I'm currently a grad student at NYU and really like to geek out about math, crypto and distributed systems!


## Transcript

. Hello, guys. Thank you for coming for the presentation. Okay. I think I . So we are presenting the Rated List. We were mentored by Dankrad on this project. It was his idea originally. What we did was to formally specify the rated list, take it out from a blog, and have a proper set of Pythonic specs for the rated list, build a simulator against which we can test the rated list, write some unit tests so that we have some basic sanity checks test the rated list, write some unit tests so that we have some basic sanity checks of the rated list so that it does not perform worse than just randomly pure sampling, and collect some metrics against known attacks on existing DHTs. So just to give you a quick intro to rated list. Sorry. So, this was the idea proposed by Dankrad, which is instead of having a DST, you form a tree of all the nodes that you know. You ask for, in kind of a peer exchange manner, you ask for nodes of the nodes, and you build out a tree, and you start your peer sampling. based on the peer sampling if a node replies or does not reply you propagate those scores back to all the ancestors right so as you can see the red node is malicious node or a node that does not respond and because of that the scores of its direct parent and its Great-grandparents are affected So this is the basic idea of the rated list This was what was defined in the blog. We went on to further define how you would use filtering over it which is Sorry scoring. Yeah, so once you have every node's descendant score, so if a set of nodes are serving a sample, their descendant scores are not the actual scores that we use for filtering. What we do is we trickle, not trickle basically, but we kind of follow the paths of that node existence in all the subtrees because a node has many peers and it would exist in different subtrees. We take the level one peers scores, which are the best for that node's path, right? So it's the best path score of that node. We use that score, we filter out using a threshold. If the threshold does not work, like if it does not filter out any nodes, we switch to an average score for the same. And basically because we want to complete sampling even though we cannot filter out using the rated list. So that's average filtering. And after filtering, we can apply different querying strategies, which is we can use random querying strategy, we can use the highest score first, we can use the lowest score first, and we can use the average score first. Average score first and lowest score first does not make a lot of sense in the start, but if you think about it, parent node can have a perfect score because none of its children are contacted yet, right? A parent node can have a perfect score because none of its children are contacted yet. So a higher score first wouldn't be the most successful strategy in some cases. You would want to go for the average score because you know that there are some honest nodes balancing out the malicious nodes in that subtree. So there are different squaring strategies that you can apply. And for the rated list, we have defined a default score of 1.0, which is the perfect score. Which is slightly optimistic, but it's fine. Because we do scoring on a per-slot basis. So for every slot, we get all the peers, off-peers, and build a tree, and we start scoring. And we delete the scores for the next slot. We start again, right? Ideally, what we could do is we could propagate these scores into the Gossip Score V1.2 to persist over slots. So we could have that kind of a scoring mechanism as well. Why do we use the rated list, right? The main attack that we are going towards is to defend against a local key space flooding attack through Sybil nodes. We also want to reduce the amount of requests that we sent out for actually completing peer sampling which can be avoided if we can defunct an entire subtree of malicious nodes. I would say that the per-slot tempo matches very nicely with the pure sampling requirements because you can have honest acting malicious nodes, which is default on one particular block. So the entire objective is to complete sampling for that particular slot. honest acting malicious nodes, which is default on one particular block, right? So the entire objective is to complete sampling for that particular slot. So a per-slot sampling sets the tempo right. And lastly, it removes dead subtrees. So if there are any inactive nodes, they would already be removed. And you could assume that we reach a global stability point, like where everyone removes their defunct subtrees. So then coming to the simulator and the simulator's design, we had to play around a lot because for graphs, there are libraries out there, but the ones that are usually used are not that optimized. So we started with the NetworkX library, but it was really slow at generating a random graph with a high degree at number of nodes at 10,000. Right now for all our simulations, we use the degree at 50 and the number of nodes at 10,000, which is like a good assumption for a peer-to-peer sampling network, right? And we use RushWorkX because, as you can see, the benchmarks for graph generation is just the best for all the libraries that are there out there right now. And for querying strategy, we used all four querying strategies, highest, average, lowest, and actually random as well. But we also refilter nodes with a different threshold if we cannot complete sampling, because our objective is to complete sampling at the end of the day. So coming into the architecture of the simulator a little bit, we wanted to modularize everything so that this simulator can practically be used for other kinds of implementations like the rated list in the future. So having it modularized gives you an attack framework because we have written a lot of attacks right now. So you could test against these in the future. So yeah, everything's modularized. We spec convert the rated list spec into a Notepad implementation for all the simulations. I'll give it to Openana. So yeah, that's the simulator. Let me just quickly, I said it's not working. I think it's working. Okay. I mean, just since the slides are off, let's turn the attacks on, I guess. So yeah, I'll quickly brief you guys about the sort of attacks we try to use against our construction. Okay. Yeah. So basically what we try to do is poison the entire network with a lot of randomly picked nodes and mark them as malicious. The only problem with that is that the conditional probability of finding the parent being malicious with the children is almost same as just randomly picking any malicious node from the network. So just randomly marking any node doesn't make sense, and there's not a lot of difference because of the rated list. Although the only attack vector that might cause an issue would be basically trying to attack on one local key space, and that's what we tried to simulate. So yeah, basically trying to mark and enter a subtree to a malicious node, which then gave us the results where we were getting far more better results in terms of rated lists as compared to just randomly. Yeah. There you go. Okay. So yeah, there's a graph plot where we get to see where the rated list performs much better than just randomly picking out nodes and trying to sample. It's in terms of the number of requests that go out. Like for 90 percent of, 70 percent of civil nodes gives us almost double number of requests when doing a random sampling. But in case of a greater list, it's like the lower number. So is it? Okay. Okay. Got it. Okay. Yeah. So there are graphs showing those results and that there's some future work that needs to be done. We are currently researching on this new topic of trying to score the pens in a probabilistic way. Right now, it's just averaging out. So we are trying to take the probabilities of each and every children nodes and then finding the score for the parent based on those scoring for the children. So yeah, that's the scoring mechanism we are trying to work on. And I mean, oh yeah, awesome. So yeah, this is what I was talking about, where we were just randomly poisoning the nodes in the network. You don't really see a massive difference between rated list on and off. So as you can see, there's not a lot of difference, but there's a small difference. But still, this is where we shine, is the rated list performs much better than just randomly sampling from the network in case of 90 percent poisoning. So this is where there was a entire subtree marked as malicious. I think I have a small, yeah. So those are the sort of future work we are trying to do is that, since our implementation is still in like super native like primitive stage right now, so we would like to implement a better simulator. Yeah, I think this probably sums up. Yeah. Yeah. So can you go back to the graph? So just want to point out that all these graphs were done over like 100 runs at different thresholds. Sorry. So all these metrics were plotted over 100 runs with different thresholds and different strategies straight out. And for the rated list, we picked the best score among all different strategies. So best score first, average score first, and everything. Where the rated list off is just plain old naive, randomly sampling from the network. Probably just for visualization, this is the graph that the big blue ball is basically a network, but then it's all pulled out and those are the malicious nodes here. So yeah,, guys. Any questions for these two on the rated list project? Just trying to understand the Sybil graph that you had. You injected lots of Sybil nodes into the tree. And how do you determine which ones were Sybil and which ones weren't? Or have I misunderstood? Are you asking about the implementation detail? No, kind of in general. So a Sybil node would basically not reply for any peer sampling requests coming to it. We can definitely test for more cases where the attacks are more nuanced, as in the adversary can be adaptive, where the Sibyl node only responds to a certain number of nodes but not other nodes. If you want to actually eclipse a particular node, you would flood its local space and not just reply to that particular node, but reply to every other node. So you were detecting the Sybil, you didn't just assume that they were Sybil, right? You didn't just say these ones are malicious, you actually based on their responses, you determined that they were Sybil attacks. Yes. The parent-child relationship that you showed in the graph, how do you come up with the peer parent-child relationship? Is it like if this peer told you about the other peer, then it's child? Yes. So it's much more of a local view rather than a global view, where it's basically just like peer exchange where we just ask for peers from particular node. So first I ask from the nodes that I'm connected to for their peers, and then I make a list of those peers and ask for peers from them as well. I can cap this. Basically, in the rated list, we have it capped at 100 max children per node. So any node could randomly send for every slot, randomly or maybe probabilistically send a certain set of 100 nodes to us. Is this a candidate for replacing CAD-based discovery? It wouldn't replace CAD-based discovery per se. So rated list assumes that you already have a libP2P network. And for discovery, it's not really... You would need bootstrap nodes to actually form this thing, so it becomes a little more complicated over there. But what we are definitely planning on is, like if you think about it, per slot scores, they make sense if you assume that malicious nodes are honest acting until that slot, but then you can also have malicious nodes that start acting honest after that slot, and a per slot score wouldn't really help at that point. But the good thing is the version 1.2 Gossip scoring provides these application scores that you can inject into them, and they are persisted with DK parameters and everything. So we plan on just injecting the rated list score into the Gossip v1.2 scoring. All right, thank you. Let's give it up for these guys one more time.