No-Tag-Back Gossiping

Version: 0.1.0 (Draft)

Authors: Antoine Toulme antoine@whiteblock.io, Dean Eigenmann dean@status.im

Table of Contents

1. Abstract
2. Motivation
3. Specification
   1. Prerequisite
   2. Ratelimiting
   3. Message Path
   4. Blacklisting
   5. Last hop
   6. Origin and Last Sender

Abstract

In this specification we highlight a series of simple improvements that can be made to gossip protocols improving their reliability.

Specification

Prerequisite

For purposes of this specification we assume that nodes initially take part in a handshake where they exchange secrets, and share identities that will be used to sign messages.

Ratelimiting

Nodes MAY ratelimit their peers. Ratelimiting information SHOULD be exchanged in the handshake. The information that SHOULD be exchanged is the following:

• epoch length
• number of full messages
• number of headers
• max hops for full messages
• max hops for headers

All the numbers MUST be for fixed period of time, designated as the epoch.

The number of headers allowed SHOULD be much higher than full messages. Peers SHOULD prefer communicating headers only.

Message Path

When a peer receives a message it MUST verify the validity of it. A message is valid if the previous sender has signed it along with the original sender.

Upon receiving and verifying the message, a peer SHOULD send it to all eager peers and send the signature to all lazy peers.

All peers MUST perform verification and add their own signature. This creates a path of headers that can help trace how a particular message transited through the network.

When receiving a message destined for itself, the peer MAY then opportunistically perform optimizations of routing to reduce distance to the sender, if necessary.

Blacklisting

If a peer sees a blacklisted node as part of the message path, it MAY choose to stop propagating the message.

Last hop

Messages

Using the path (or if using last sender, a number of hops), the peer MAY decide to propagate a message if it has a maximum number of hops.

To finish the propagation, the peer MAY send headers instead of the full message to all its peers. The peers MAY request the full message if they don’t get it in time (per Plumtree algorithm).

Headers

The headers are propagated further. Since the full message is no longer available, the path of peer headers is signed instead with new headers, which allows peers interested in the full message to request the full message from their immediate peer, or to perform a routing optimization to connect to one of the peers in the path with the full message.

Origin and Last Sender

For scenarios where packet size may be very critical and network edges may be far apart, encoding an entire path could be problematic. We therefore encode the origin meaning the first sender of a message, and take note of the last sender, when retransmitting the message we MUST ensure that it does not get sent to the last sender or the origin.