The Rated List | Devcon SEA

[Music] uh hello guys uh thank you for coming for the presentation um okay I think I Buist click so uh we are presenting the rated list uh we were mentored by danrad uh on this project it was his idea originally uh what we did was uh to formally specify the rated list uh take it out from a Blog and have a proper uh set of uh pythonic specs uh for the rated list build a simulator uh which against which we can uh test the rated list uh write some unit tests so that we have some basic sanity checks of the rated list so that it does not perform worser than just randomly pure sampling uh and collect some metrics against uh known attacks uh on existing dhds so uh just to give you a quick intro to rated list sorry um so this was the idea proposed by danrad um which is uh instead of having a DST uh you form a tree of all the nodes that you know you ask for uh in kind of a pure exchange manner you ask for nodes of the nodes and you build out a tree and uh you start your peer sampling and based on the peer sampling uh if a node replies or does not reply uh you propagate those scores back to all the ancestors right so as you can see the red node is a malicious node or a node that does not respond and because of that the scores of its direct parent and its Grand great grandparents are affected right so this is the basic idea of the rated list uh this was what was defined in the blog uh we went on to further Define how you would use filtering over it uh which is uh sorry scoring yeah so once you have uh every node descendant score uh so if a set of uh nodes are serving a sample uh their descendant scores are not the actual scores that we use for filtering what we do is uh we trickle uh not trickle basically but um we kind of follow the paths of uh that node existence in all the sub trees because a node has many peers and it would exist in different sub trees uh 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 uh 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 uh for the same and um basically because we want to complete sampling even though uh you know we cannot filter out using the rated list so that's um that's average filtering and after filtering we can apply different quering strategies which is we can use a random quering 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 uh parent note can have an a perfect uh score because none of its children are contacted yet right so uh highest score first wouldn't be the most uh successful strategy in in some cases right you would want to go for the average score because you know that there are some honest nodes balancing out the uh malicious nodes in that sub tree right so there are different sing strategies that you can apply uh and for the rated list we have defined a default score of 1.0 which is a perfect score uh which is slightly optimistic but it's fine because uh we do scoring on a per slot basis so uh for every slot we uh get all the peers uh of peers and build the tree and uh we start scoring and we delete the scores for the next slot we start again right uh ideally we could what we could do is we could propagate these scores into the gossip score uh v1.2 to persist over slots uh so we could have that kind of a scoring mechanism as well uh why do we use the rated list right uh the main attack that we are uh going towards is to defend against a local keyspace uh flooding attack uh through Cil notes uh we also want to reduce the amount of requests that we sent out uh for actually completing pure sampling which can be avoided if we can defunct uh an entire subtree of malicious nodes um I would say that the P slot Tempo matches very nicely with uh with uh the peer samp sampling requirements uh because um you can have honest uh 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 up per slot sampling sets the tempo right uh and lastly it removes dead sub trees so if there are any inactive nodes they would already be removed and you could you could assume that we reach a global stability Point like where everyone removes that defunct sub trees uh so then coming uh to the simulator and the simulator's design we had to play around a lot uh because for graphs uh they're not uh there are libraries out there but the ones that are usually used uh are not that uh optimized so we started with the network X Library but uh it was really slow at generating a random graph with a high degree uh at number of nodes at you know 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 p sampling uh Network right um and we use R Rush workor X because uh as you can see the benchmarks for uh graph generation is just uh the best for all the libraries that are there out there right now uh and for quering strategy we used all four quering strategies highest average uh lowest and actually random as well uh but we also ref filter nodes with a different threshold if we cannot complete sampling uh because our objective is to complete sampling at the end of the day right so um uh coming into the architecture of the simulator a little bit uh 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 uh having it modularized make uh gives you attack framework because we have written a lot of attacks right now uh so you could test against these um in the future uh so yeah everything's modularized we spec convert the rated list uh spec into a notep implementation for all the simulations I'll give it to open so um yeah that's the simulator let me just quickly set I think it's okay okay um um start explaining the attack um I mean just since the slides are off let's uh turn the attacks on I guess so uh yeah I'll uh quickly brief you guys about uh the sort of attacks we try to um uh use against our uh construction uh okay uh yeah so uh basically what we Tred to do is uh poison the entire uh network with a lot of Random picked uh nodes uh and mark them as malicious uh the only problem with that is that uh the conditional probability of finding uh the parent being malicious uh with the uh children is almost same as just randomly picking any uh malicious node from the network so uh just randomly marking any uh node uh doesn't make sense and like the there's not a lot of difference because of the rated list uh although uh the only attack Vector that uh that might cause an issue uh would be uh basically trying to attack on one local key space and uh that's what we tried to simulate uh so yeah basically trying to Mark and anise subre uh to a malicious node which uh then gave us the uh result results where we were getting uh far more better results in terms of uh rated list as compared to just randomly yeah there you go okay uh so yeah uh there's a graph plot where we uh get to see where uh the rated list performs much better than just randomly picking out notes and trying to example uh it's in terms of the number of requests that go out uh the like for for uh 90% of 70% of uh civil uh nodes gives us almost double number of uh requests when doing a random sampling but in case of rated L it's like uh um the lower number so is it okay okay got it should I okay yeah so there are graphs uh showing those results and uh that there's some future work that needs to be done uh we are currently researching on this new topic uh of trying to you uh score the parents uh in a probabilistic way right now it's just averaging out uh so uh we are trying to take the probabilities of each and every uh CH children ndes uh and then uh finding uh the score for the parent based on those uh scoring uh for the children so yeah that's the uh scoring mechanism we are trying to work on and uh I mean perfect the graph oh yeah awesome uh so yeah this is uh what I was talking about where we were just randomly poisoning the nodes uh in the network you don't really see a massive difference between rated list on and off uh so as you can see like there's not a lot of difference but there's a small difference but uh still yeah this is where we uh shine is uh the rated list performs much better than just randomly sampling uh from the network in case of 90% um uh poisoning so this is where there was a uh entire subtree marked uh um marked as malicious and I think I have a small yeah so the those are the sort of future what we are trying to do is that uh since our implementation is still in like super native uh uh like primitive stage right now so uh we would like to know Implement uh a better uh simulator and uh yeah I think uh this uh probably sums up our uh that's yeah yeah uh so um did we can you go back to the graph yeah so just want to point out that all these graphs were done over like uh 100 runs at different thresholds sorry um so all all these um uh metrics were plotted over 100 runs uh with different thresholds and different strategies TR out and for the rated list we picked the best score with uh in all among all different strategies right so best score first average score first and everything uh where the rated list off is just plain old naive randomly sampling from the network I just for probably just for visual visualization uh this is the sort of graph that the uh big blue ball is basically a network but then it's all pulled out and those are the malicious notes yeah so yeah thanks guys all right any questions for these two on the rated list project uh just trying to understand the Civil graph that you had you you injected lots of Cil nodes into the tree and how do you determine which ones were CBL and which ones wer or have I misunderstood um are you asking about the implementation detail or like uh no kind of in general so like okay so um a civil node uh would basically not reply for any P sampling requests coming to it right uh we can definitely test for more cases where the attacks are more nuanced uh as in it can the adversary can be adaptive uh where the Cil node only responds to a certain number of nodes but not uh other other nodes and if you want to actually Eclipse a particular uh node you would you would flood its local space and not just reply to that particular node but reply to every other node so yeah so you were detecting the sibl you didn't just assume that they were sibl right you didn't just say these ones are malicious you actually based on their responses you determined that they were attacks yes yeah yeah the parent child relationship that you you've showed in the graph like how do you come up with the peer parent child relationship is it like if this peer like told you about the other peer then it's its child yes so it's a it's much more of a local view rather than a global view where we it's basically just like peer exchange where we just ask for uh peers from particular node like so first I asked from the nodes that I am connected to for their peers and then I make a list of those peers and ask ask for peers from them as well I can cap this uh basically we in the rated list we have it capped at 100 uh Max children per Noe so any node could like randomly sent for every slot randomly or maybe probabilistically send a certain set of 100 nodes to us is is this a candidate for like replacing CAD based Discovery it wouldn't replace CAD based Discovery per se it would so rated list assumes that you already have a P2P network uh so and for Discovery it's not really like you would need bootstrap nodes to actually form a this thing so it becomes a little more complicated over there uh but yeah but what we are definitely planning on is like if you think about it uh per slot scores uh they they make sense if uh you assume that uh 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 so uh but the the good thing is the uh version 1.2 gossip scoring uh provides like 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 uh Gossip V2 v1.2 scoring yeah all right thank you let's give it up for these guys one more time