Improve Gossamer Gossip Algo

[dutterbutter]

Overview

Some of the properties to consider when optimizing gossip algo:

• Reliability: All messages get delivered to all peers subscribed to the topic.
• Speed: Messages are delivered quickly.
• Efficiency: The network is not flooded with excess copies of messages.
• Resilience: Peers can join and leave the network without disrupting it. There is no central point of failure.
• Scale: Topics can have enormous numbers of subscribers and handle a large throughput of messages.
• Simplicity: The system is simple to understand and implement. Each peer only needs to remember a small amount of state.

Currently, Gossamer doesn't use gossipsub. A peer sends messages to all peers from whom it hasn't received the message or previously sent to.

No benchmarking available as of now.

Requirements:

• Message congestion/duplication improvement (Efficiency)
• A better gossiping algo than current implementation which is a simple floodsub
• Look into substate as to what has been done there
• And come up with simpler version of that or gossipsub or maybe even use them with custom parameters

Substrate

Substrate's networking crate: https://docs.rs/sc-network/0.9.0/sc_network/

(Substrate uses Noise protocol for connection establishment: https://noiseprotocol.org/

Uses Kademlia for p2p DHT during discovery phase)

Substrate uses 'polite gossiping'. The network-gossip crate implements this. The idea is that there is a Validator whose goals include:

• Decide to keep or discard incoming messages and if a re-broadcast is required. Messages are identified with the hashes of their content in order to not have an attacker send a different message with same ID (Message Silencing).
• If a message is allowed to be sent to a peer.

While looking at the code for all the implementation of the Validator trait, there is no specific check as such to which messages to keep and propagate to peers and which to discard. All of the implementations (except for DiscardAll) return ProcessAndKeep (code link) enum value from ValidationResult enum, which sends all messages to all peers subscribed to that topic.

But given that it is a trait, if we want to use that we can have custom validate function implementation.

All messages, categorised by topic, are stored in HashSet (message content hash). This includes own list of messages and a list of messages known to specific peer, for each peer.

While propagating messages to peers, a check is performed if the peer to send the message to, already has a particular message sent by the current peer by looking at the HashSet If yes, the message is not sent**. (code link) The messages are discarded only when the receiving peers already has that message. This check is performed on broadcast_topic (all messages in a topic), rebroadcast (all message to all peers) **and multicast (send a message to all peers)

In conclusion, substrate implements a similar logic as we have in gossamer. And as we are also using the sc-network crate from substrate, the discovery and routing process are also the same. Meaning that if the routing is structured in an optimised manner, and a node knows only a required subset, then the message congestion can also be optimised in that way. Afaik, Kademlia is already a great implementation with complexity of O(log n) for searching from n nodes.

Substrate also uses a peer scoring mechanism which gets updated based on gossiped messages but the gossiping itself does not use the score for relaying messages. (code link)

Randomsub

Randomly selects a subset of peers i.e square root of the network size of peers, with a fixed minimum number of peers (6) to propagate the message to. Part of libp2p-pub-sub.

Code Link

Could be a middle solution with a tradeoff between reliability and efficiency. Won't be deterministic, not possible to mimic behaviour for comparison.

Gossipsub

Spec is available here.

GossipSub proposes to forward metadata of the messages they have “seen”, instead of the entire content of the message. In addition, GossipSub implements Lazy push in which peers that are interested on a message for which they have received the metadata, request that message explicitly. Given the difference in size between message data and metadata, using this technique it is possible to save a non-negligible part of the network bandwidth, improving scalability.

Gossipsub v1.1 evaluation report is available here. The report gives an evaluation that was performed on Filecoin nodes and Eth 2.0 (Pages 5-6). Depending on the number of nodes that Gossamer is targeting to have, this can be an ideal solution for us. There are implementations available which we can use directly and given that we are also using lib-p2p, there shouldn't be major conflicts.

Epidemic Broadcast Trees

Flooding combined with efficiency of Tree model.

The EBT paper

Although this approach looks good, I'm not sure if this can be directly adapted to the networking mechanism we have implemented using sc-network. I still need to read the paper. And I also didn't find a matured implementation that we can use right away.

Metrics for analysis

• Residue. the remaining nodes which didn't get the message. It should be as small as possible.
• Traffic. The average number of messages sent between nodes. m = total message traffic / number of nodes.
• Convergence.
  • tavg: average time it takes for all nodes to get a message.
  • tlast: time it takes for the last node to get the message.