# The rated list DHT proposal based on having a "list" of all nodes, but with some rating added in for protection ## Construction Choose a constant $T$. Compile a list of all current peers. These are the level-1 peers. Ask each of them for a list of their peers. These peers are level 2. A peer that has already appeared in a lower level cannot reappear in a higher level. Do this up to level $T$. For all peers, additionally maintain a list of their "children" (peers with a higher level) and "parents" (all peers that have this peer as one of their peers and have a higher level). A peer can have multiple parents. ## Maintainance Peers at all levels are periodically queried for their current peers and the parent/child relations updated. Peers that have zero parents are removed from the list. ## Querying/scoring Sample numbers are mapped into the node ID space. All peers within a radius $d$ are expected to maintain a given sample. All peers start in inactive status. Any peer that responds to a sample request positively is moved to active status. Any peer that does not respond to a sample request is marked as inactive. Every peer has a score that is composed of the list of all active descendants of that peer (children, children of children etc.) As a client starts querying the table, they will identify peers with low scores. Peers with very low scores will be marked as defunct, and all their descendants will now longer be queried unless they are also descendants of non-defunct peers. ## Reciprocity Membership of two nodes in their respective rated lists should be mutual after a suitable convergence time; that is, if node A is in node B's list, then node B should also be in node A's list. Nodes that are in each other's rated lists (and not in a defunct subtree) can prioritize their mutual requests in times of network congestion. ## Depth Assuming peer degree 50 $T=1$: Only direct peers, equivalent to PeerDas One node should cover 1/12.5th=8% $T=2$: Ca. 2,500 nodes One node should cover 1/100th=1% $T=3$: Current max useful for Ethereum, enough to cover 125,000 nodes One node should cover 1/400th=0.25% (at 2^18 samples: 655 samples / 367 kB) $T=4$: 6,250,000 nodes # Attacks ## Flooding the full table (random malicious nodes) Attacker seeds the table with only malicious nodes. These nodes later execute a withholding attack: Question is, how fast can the withholding attack be identified and the offending subtree be removed? ## Flooding a local keyspace Attacker adds many nodes with very similar node IDs to flood one particular key space. Withholding attack -- seems imilar to previous one ## Combined flooding to occupy one particular key space, but add enough active nodes Example: attacker adds 90% active nodes all over the keyspace, but sprinkled with 10% in a particular key space that later start a withholding attack. All the malicious nodes's scores will still be pretty high since 90% of their descendants are still active, so it is hard to identify the original malicious nodes causing this. Example: With $T=3$, attacker adds 12,500 nodes to one sample keyspace, where there are only 125,000/400=312 honest nodes. The querying node will on average have to query 40 malicious nodes before finding an honest node in the subspace. Potential remedies: 1. Construct the system such that it can tolerate a small amount of local failures 2. When querying nodes for samples, use an additional diversity metric to rank them, to e.g. prioritize querying nodes with maximally different ancestors first 3. Scan the list for any unexpected clustering of nodes with common ancestors. When such a cluster is identified, mark their common ancestor as defunct. (Problem: This could also be used to attack good nodes by flooding their tables with bad nodes) # Bandwidth to maintain the list Assuming updating the list at an interval of once per 30 minutes, 100 bytes per peer = 5 kB for querying one peer's list of peers $T=2$: 50*5000/1800 = 139 b/s $T=3$: 2500*5000/1800 = 7 kB/s $T=4$: 125000*5000/1800 = 350 kB/s Up to $T=3$ seems practical currently Bandwidth can potentially be reduced by only transmitting abbreviated node records first, and only sending the full record when the querying node hasn't seen the node in question yet.