GossipSub: PubSub Extensible Protocol | Rajat

Post

editor-img
Rajat
Dec 27, 2022

GossipSub: PubSub Extensible Protocol

GossipSub is a protocol that extends existing PubSub implementation to make PubSub more efficient. Since GossipSub is an extension of PubSub, it makes sense to know about PubSub before directly jumping on to GossipSub.

media

PubSub

It is a form of communication among services through a common topic of interest.

Let's take the example of the WhatsApp group to explain PubSub

PubSub comprises of

1. Provider: Provide data that is expected & received by the subscribers E.g Send a message in a group

2. Topic: Group the related data. E.g. Group name

3. Subscriber: Recieve data related to the topics they are subscribed to. E.g. All participants of the group

In the standard PubSub implementation, whenever a publisher publishes a message on a topic, it is flooded to all clients which have subscribed to that particular topic.

From this point onward I'll use some terminologies which I'll explain now itself

1. Peer - Client who wants to send and subscribe to messages on a topic

2. Peering - Process of connecting one peer to another peer. It is bidirectional & needs to be acknowledged by both peers to be called a successful peering

Design Goal in PubSub

1. Reliability: Successful delivery of every message

2. Speed: Quickly delivery of every message

3. Efficiency: Remove redundancy of messages & reduce network bandwidth

4. Resilience: Subscription/Unsubscription to a topic should not affect the whole system

5. Scale: Handling multiple subscribers to the topics

6. KISS - Keep it stupid simple. A basic design principle

Since we are clear with the basic things we needed to know, we can now learn about GossipSub.

The first part is discovering peers before subscribing to the topic. Peer discovery is not part of PubSub, it relies on the application to do that.

There are certain methods for that

1. DHT - (Distributed hash tables)

2. Local network broadcasts

3. Exchanging peer lists with existing peers

4. Centralized trackers or rendezvous points

5. Lists of bootstrap peers

Explaining each of them is out of the scope of this article, but rest assured they are standard algorithms part of the ambient peer discovery process

Types of Peering

In GossipSub there are 2 types of peering

media

1. Full Message Peering (FMP)

In this peering, the full message content is sent to peers throughout the network. Full Message peering creates a sparsed network, not every peer is connected with Full Message Peering.

Purpose: Reduce network bandwidth since full message content is not forwarded to all peers

2. MetaData Only Peering (MOP)

In this peering, only the meta of the message is sent to peers throughout the network. Whichever client is left out of full message peering is then connected using MetaData Only Peering.

Purpose: Gossip about which message is available and not yet received by certain peer

GossipSub combines both the peering strategy to devise a new protocol which is quite efficient and scalable. Now each peer has to maintain a network of Full Message (Generally few & configurable) & MetaData Only Peering connection.

The number of Full message connections is called Peering Degree. For simplicity's sake, let's say 5 is the ideal value for this.

Grafting And Pruning

Grafting: In case the Peering Degree goes below the value of 5, it converts random MOPs to FMP

media

Pruning: n case the Peering Degree goes above the value of 5, it converts random FMPs to MOP

media

In libp2p’s implementation, it performs heartbeat checks every 1 second & this grafting and pruning are internal parts of that process.

Subscriptions

Now each peer maintains a list of topics to which their directly connected peer is subscribed.

Every time a peer subscribe or unsubscribe from a topic, that peer sends a message about that to all its connected peer (Even though that peer is not subscribed to that topic, it doesn't matter to that peer)

Subscriptions & their relation to Grating & Pruning

On Subscription: Peer along with sending the message about subscriptions also grafts some connections to become FMP

On Un-subscription: Peer along with informing about it, also prunes their connection for that topic to MOP

Send Message & Gossip About Message

Send Message

When a peer sends a message

it stores & forwards to all FMP connections

these peers then store & forward it to their FMP connections

media

These peers maintain the list of messages they have seen & avoid retransmission if already seen.

Gossip

Each peer gossip about the message they have received to randomly selected MOP n (Let's say 6) connections.

media

Now this allows peers to cross-check & see if they have received the message, if they haven't received it, they request it from the peer who gossiped about that message

Fan-Out

Peers can send messages to topics they are not subscribed to

Peers can randomly pick n (Let's say 6 again) peers of such category & fan out the messages. This type of connection is unidirectional, The other 6 peers don't know if they have been selected.

These particular peers cache the list of such peers for a certain amount of time

State

Each peer maintains a state of their own

1. Subscriptions: List of topics subscribed to.

2. Fan-out topics: These are the topics messaged recently but not subscribed to. For each topic, the time of the last sent message to that topic is remembered.

3. List of peers currently connected: For each peer connected, the state includes all the topics they are subscribed to and whether the peering for each topic is full-content, metadata-only or fan-out.

4. Recently seen messages: Cache of recently seen messages. It is used to ignore retransmitted messages. For each message the state includes who sent it and the sequence number, which is enough to uniquely identify any message. For very recent messages, the full message contents are kept so that they can be sent to any peers that request the message.

That's it, This is GossibSub.

I'll post about the security context of GossipSub in the next article. Stay tuned!

Reference: https://github.com/libp2p/specs/tree/master/pubsub/gossipsub