The PlumTree Algorithm (PTA) in the Solana Gossip Protocol: Some Thoughts

Glossary

INV (Inventory): A message sent to nodes in the network to depict the availability of data each node requires.

GETDATA: This is a message sent to a node that queries for the data specified in the inv message.

Spanning Tree: A spanning tree of a graph is a subset of the graph that connects all its vertices with the minimum number of edges without forming any cycles.

Introduction

Blockchain is gaining massive attention as support for cryptocurrencies due to the rapid growth of memecoins and the celebrated launch of cryptocurrencies. However, one key challenge in blockchain networks is the efficient propagation of messages between nodes, which leads to communication resource consumption. In traditional gossip protocol, a key problem plaguing it is the latency issue—a node must wait for the next cycle to transmit a message.

The Plumtree algorithm is designed to reduce latency and redundancy in message transmission, particularly in peer-to-peer networks and distributed systems where reliable and fast message dissemination is important. It can achieve this by finding the shortest path to send the message to the next node in the spanning tree. By doing this, each node participates in forwarding messages without relying on a central source.

This article delves into the implementation of the Plumtree algorithm in the Solana network and its role in increasing the speed of message propagation in the network. Furthermore, a comparison between Plumtree and GossipSub, a gossip-based epidemic broadcast algorithm used in Ethereum.

Solana Broadcast

In Solana, a gossip-based block propagation method is as follows: when a node receives a new block, it sends a BROADCAST message to other nodes in the network. This broadcast includes information about the new block, such as the block header, transaction data, state changes, and other metadata like compressed data, etc. Upon receiving the BROADCAST message, the receiving node checks if it already has the block in its ledger history. When the nodes check its history and have no record of that block, it sends a QUERY request back to the broadcasting node, querying for the block data.

When the node receives the data of the queried block, it verifies it and adds it to the network. This ensures that the node does not share the block data with every other node in the network repeatedly.

Plumtree Algorithm

Origin

The plum is a fruit of the Prunus species, Prunus domestica, a genus of trees that also includes peach, cherry, nectarine, almond, and apricot trees. Plums have a lot of health benefits. They contain a lot of nutrients, are rich in antioxidants, promote bone health, and help lower blood sugar. China and Romania are the two largest plum producers.

The main sources of inspiration for the Plumtree algorithm are as follows:

• The flowering of the plum trees in the early spring.
• The transformation of the pollinated flowers to plums.
• The plums drop before maturity by 20–30% due to various reasons or diseases, such as diseases caused by plant viruses.
• The plums have a shelf life of around 2–6 weeks, even when they are stored at 0 °C.

The Plumtree algorithm implements these sources of inspiration as follows: the positions of the flowers and the positions of the plums are represented as matrices; the dropping of the plums before maturity is represented by a fruitiness threshold (FT), and the shelf life of the plums after they are collected is represented by a ripeness threshold (RT). The two thresholds lead to the development of three types of equations to update the positions of the flowers.

How Plumtree Works

Plumtree is a broadcast method that combines tree-based and gossip-based approaches to reduce redundancy while maintaining high message reliability. In a tree-based broadcast, each node transmits and improves efficiency by forwarding messages only in a tree-based manner. It also uses gossip-based links between nodes to properly handle inter-node failures.

In a tree-based broadcast, a tree consisting of all participant nodes is constructed, and messages are transmitted only along the tree, which reduces the redundancy of messages. However, if the number of nodes increases or decreases or if a network failure occurs, the tree becomes incomplete, and a message may not reach all nodes. For instance, the block is broadcasted, and a spanning tree is constructed using the Plumtree algorithm. In subsequent broadcasts, the constructed tree is used. If the exchange of inv and getdata messages is omitted, the blocks are not sent directly to the child nodes of the tree and hence fail.

In Gossip-based broadcast, when a node attempts to broadcast a message, the node randomly selects nodes to send the message. The node that receives the message for the first time repeats this process to send the message, which not only provides high scalability but also makes the system more resistant to network inadequacies and node failures.

For instance, when a node broadcasts a message, it randomly chooses a node to send it to. The node that receives the message for the first time repeats this process. This property allows the system to respond flexibly to network failures and increases or decreases in the number of nodes.

The following approaches are utilized in the Gossip-based broadcast to disseminate data:

• Eager push: In this approach, once a message is received, it is sent to the neighboring nodes immediately.
• Lazy push: In this approach, when a node receives a message, it sends the message identifier to the neighboring nodes. If the node has not received the message, it makes a pull request to the neighboring nodes.
• Pull: Once a node has not received a message, it makes a query to its neighboring nodes—pull on recently received messages to update its state with that particular message.

Plumtree uses a combination of an Eager push mechanism for sending a small number of messages and a Lazy push mechanism for assisting transmission.

Plumtree in Solana Network

Solana utilizes a peer-to-peer communication approach combined with a Plumtree tree-inspired algorithm, allowing for efficient dissemination of data throughout the network of nodes without depending on a central source. This structure enables messages within the network to be disseminated hierarchically, with nodes directly interacting and making each node in the network operate autonomously in relaying messages to the subsequent node in the tree.

A spanning tree structure is constructed using the Plumtree algorithm for the nodes in the Solana network, allowing for a more scalable approach to broadcasting information throughout the network. In basic terms, every node shares messages with its direct neighbors, who in turn, propagate the information across the spanning tree.

Differences Between Plumtree Algorithm and GossipSub in Ethereum

The differences between the Plumtree algorithm and GossipSub used for information broadcasting in Solana and Ethereum, respectively, include:

• Solana Tree-based PTA uses a tree-based broadcast approach where nodes are connected in a hierarchical manner where the parent node is connected to the child node. The focus is on building an optimal routing path over time through message duplication handling, while GossipSub utilizes topic-based P2P overlays, where nodes subscribe to specific topics related to validator duties and communication within the Ethereum network. These overlays self-optimize to find the shortest path for message dissemination.

• Solana Tree-based PTA uses epidemic broadcast but focuses on handling message redundancy by downgrading peers with suboptimal message paths, while in GossipSub, messages are disseminated via a random epidemic broadcast.

Wrapping Up

In this article, we examined the Plumtree algorithm in Solana's Gossip Protocol, highlighting its tree-based and gossip-based approach to efficient message dissemination. We also compared it with Ethereum’s GossipSub, noting its differences.