Consider adding a network overlay

This is a summary of some prior discussions related to network overlays.

Message stratification is an idea to help reduce overall network traffic in various scenarios. In essence, each node is assigned a persistent node ID (a large random number that survives node restarts) and then a network overlay, such as Kademlia [1], is used to efficiently route messages to relevant nodes.

For instance, once durable votes are implemented, a network overlay enables propagation of votes with far less network traffic. Durable votes would be stored on partitions of the ID key space (the possible permutations given the size of the node id, typically 160 bits). A light node would then query votes in this key space, allowing it to be connected to just a few nodes - the Kademlia distance metric ensures that any key/node can be reached within log(n) steps where n is the number of nodes. A network overlay reduces load on representative nodes since other (partial) nodes store durable votes.

[1] http://pdos.csail.mit.edu/~petar/papers/maymounkov-kademlia-lncs.pdf

What is the focus for the network overlay, is it just for durable votes or also bootstrapping, or live block/vote broadcasting?

While the current fanout of sqrt(peers) is fast and redundant to ensure delivery it results in a lot of duplicated messages, on average around 8-11 duplicates on the live network with 325 peers, and as the number of nodes increases the number of duplicate messages will also increase.

If the network overlay will not be changing live broadcasting should the fanout be reduced now that TCP is implemented and message delivery is more often guaranteed? Even reducing the fanout by 1/3 (eg 12 instead of 18 for 325 peers) would result in a 1/3 reduction in overall messages and bandwidth while still maintaining similar propagation metrics.

Another option could be to increase the fanout from the sending node for blocks by 3-4x and then reduce rebroadcasting blocks by other nodes by 1/2. This would reduce the overall network bandwidth requirements by almost half for block propagation while putting a higher bandwidth requirement on the sender which would help disincentivize spamming.

Also since the network is organized into Principle Representatives and non PR nodes, the faster blocks get to PR nodes the quicker they can be confirmed and can move on to other blocks. With that in mind, having a sender broadcast to a large portion of PR nodes would help speed up the confirmation process. PR nodes could also partially focus on sharing their votes with a predetermined amount of other PR nodes in order to keep the PR nodes relatively in sync with each other during higher load instead of relying on random peer selection.

Thoughts, comments or questions? What can help or needs to be done to analyze this further?

Yes, fanout is probably on the conservative side (at least with tcp) and there's an issue discussing that (https://github.com/nanocurrency/nano-node/issues/993)

Are they considered 2 separate/independent topics or will fanout be impacted by the network overlay? Is DHT primarily for data lookups like bootstrapping and durable vote lookup?

When fully implemented, an overlay would connect a node to a few "neighbouring" peers (with a preference for peers with long uptime), which would replace the ~sqrt(n) flooding. I suppose you could imagine a transitional phase using a kademlia-style DHT to support durables votes first, with normal fanout for other messages.

Thanks, that really helps to understand the focus and direction!

I guess the number of neighbours is less than sqrt(nbr of peers), thus, the messages will be sent to fewer peers, and hence requiring more jumps before the messages reach all peers. It seems that this will increase the time it takes for a block to get propagated and confirmed. Do you have any intuition about this?

Seems like it would depend on how many neighbors you have in the DHT, it should be much more efficient if contacts are more organized than current fanout. With 325 nodes if you have just 9-12 or maybe even fewer contacts and there is sufficient organization it should be similar to the current sqrt(325) fanout. With more organization you really only need just a few fanout to get to all nodes in 2-4 hops like it is now.

While kademlia gives clear upper bounds, the actual hop count in a given network configuration is apparently hard to analyze. There's a large body of research and I think studying those and doing simulations is going to be important (see for instance https://pdfs.semanticscholar.org/8f1c/cee9698e6aefcae07013e86fad47bea4254d.pdf regarding hop distribution)

Some (somewhat dated) research suggests even large overlays like Mainline DHT (bittorrent) can have lookup latencies as low as 2-300ms.

1 Like

Note that Kademlia is vulnerable to the following:

  • Spartacus attacks: Any node may assume the identity of another node and receive some fraction of messages intended for that node by simply copying its node ID. This allows for targeted attacks against specific nodes and data. Spartacus attack mitigation is addressed in S/Kademlia by implementing node IDs as public key hashes and requiring messages to be signed. A Spartacus attacker in this system would be unable to generate the corresponding private key, and thus unable to sign messages and participate in the network.

  • Sybil attacks: involve the creation of large amounts of nodes in an attempt to disrupt
    network operation by hijacking or dropping messages. While Kademlia is vulnerable to Sybil attacks, an adoption of S/Kademlia proof of work identity generation reduces the vulnerability to a degree.
    Further, a node reputation system can be implemented with a prolonged initial vetting period where nodes must complete before they are trusted with significant amounts of data or membership in Kademlia routing tables. This vetting system, can prevent a large influx of new nodes from taking incoming data from existing reputable storage nodes without first proving their longevity.

  • Eclipse attacks: attempts to isolate a node or set of nodes in the network graph by ensuring that all outbound connections reach malicious nodes. Eclipse attacks can be hard to identify, as malicious nodes can be made to function normally in most cases, only eclipsing certain important messages or information. Eclipse attacks can be addressed by using public key hashes as node IDs, signatures based on those public keys, and multiple disjoint network lookups as prescribed by S/Kademlia.
    The larger the network is, the harder it will be to prevent a node from finding a portion of the network uncontrolled by an attacker. As long as a node has been introduced to a portion of the network that is not controlled by the attacker at any point, the public key hashes and signatures ensure that man-in-the-middle attacks are impossible, and multiple disjoint network lookups ensure that Kademlia routing is prohibitively expensive to bias. To avoid an eclipse attack, all that remains is to make sure new nodes are appropriately introduced to at least one well-behaved node on the network during the bootstrapping process. To that end, Nano could run some well-known, verified bootstrap nodes.

S/Kademlia addresses some of the above:
https://ieeexplore.ieee.org/document/4447808

Also, Storj describes how they use S/Kademlia:

1 Like

Thanks for the input @funkspock! I believe all of the suggested methods of mitigating these attacks are in the current plans. In addition, from my research the recommendation is to limit the number of connections to the same ip or /24 subnet which helps significantly against eclipse attacks.

The routing tables can also be setup to favor connections to existing nodes that have been online longer and only add new nodes when those drop or go offline for an extended period of time.

I think there can also be a mix of the existing network structure and a Kademlia DHT for vote lookups. For example if other nodes are storing votes from PR nodes if you fail to get results from other nodes, then a node could request votes directly from the PR node instead.

What’s your general opinion of Kademlia as a network overlay for more efficient message propagation and storing votes for later vote requests?

@Srayman I would be cautious for message propagation and storing votes and take into account risks and attack vectors because Kademlia is intended for exchange of transient data between peers in an untrusted network. This is key and should always be considered for all the operations performed on the overlay network.
See for example below which demonstrates that DHT networks (among other attacks) are vulnerable to the index poisoning attack and the routing table poisoning attack: http://sourcedb.ict.cas.cn/cn/ictthesis/201103/P020110314768421277389.pdf

The popularity of Kademlia over other DHTs is likely due to its relative simplicity and performance. It has a number of core features that are not simultaneously offered by other DHTs, such as:

  • The number of messages necessary for nodes to learn about each other, is minimized.
  • Nodes have enough information to route traffic through low-latency paths.
  • Parallel and asynchronous queries are made to avoid timeout delays from failed nodes.
  • The node existence algorithm resists certain basic distributed denial-of-service (DDoS) attacks.

Source: https://tlu.tarilabs.com/protocols/dht/MainReport.html
Above link also provides a nice comparison between CAN CHORD Kademlia Koord Pastry Tapestry Viceroy protocols.

These protocols can achieve similar performance if parameters are sufficiently well-tuned. However, parameter tuning is a delicate business; not only can different parameters interact within a protocol to affect the cost versus performance tradeoff, but similar parameters in different protocols, such as base and stabilization interval, can behave differently.
Source: http://www.news.cs.nyu.edu/~jinyang/pub/iptps04.pdf

This is a study on the connectivity of the overlay network Kademlia in multiple simulated scenarios.

Abovementioned are examples of Structured P2P overlay networks, there also Unstructured P2P overlay networks: Freenet, Gnutella, FastTrack/KaZaA, BitTorrent, Overnet/eDonkey2000. This source provides a nice overview of all protocols:

Careful (risk) analysis and thought must be given in choosing the right protocol. For example. a recent attack has been demonstrated on Ethereum which also uses this protocol: https://arxiv.org/pdf/1908.10141.pdf
While Kademlia is a prominent contender, it also has some issues and risks that need to be addressed.

1 Like