Sig Engineering - Part 1 - Solana's Gossip Protocol

This post is Part 1 of a multi-part blog post series we'll be releasing periodically to outline Sig Validator's engineering updates/milestones.
This blog post marks a major milestone completion in Sig's journey: Initial implementation the gossip protocol for Sig. We outline the technical implementation here.
A gossip protocol propagates data to nodes across a network efficiently. It is a core component of a distributed system and acts as a node’s entry point to the network, allowing it to identify other nodes in the network and to receive and sync metadata about the state of the blockchain.
A gossip spy is, in essence, software written to do two things: store data and send/receive requests. Doing each of these efficiently is the goal of a well-implemented gossip spy.
In line with our dedication to transparency, we've detailed below the Sig implementation of the Solana gossip protocol.
Storing Data
What is the CrdsTable?
Solana’s gossip data is stored in a Cluster Replicated Data Store ( CrdsTable
for short).
There are two main data types we store (defined in crds.zig
) which includes CrdsData
and CrdsValue
data structures. A CrdsData
enum covers various gossip data types including LegacyContactInfo
for node details like public keys and addresses, Vote
for block validity signatures (being phased out for lower bandwidth), and more. Secondly, CrdsValue
holds a CrdsData
struct and a signature over its data. When processing incoming gossip data from the network, we first verify the signature of the CrdsValue
and then insert it into the CrdsTable
.

Inserting Data
ValueLabels and VersionedValues
To store this data, we use an indexable-HashMap in a struct called the CrdsTable
located in crds_table.zig
.
For each CrdsValue
type we store, there is a corresponding CrdsValueLabel
which is used as the key for the HashMap and a CrdsVersionedValue
structure for the value of the HashMap.
Cluster Replicated Data Store keys: CrdsValueLabel
To understand how the CrdsValueLabel
defines how data is stored, we start with an example.
One important data type we care about is the LegacyContactInfo
struct which includes the public key of the node and socket address fields that are used to communicate with the node. However, its corresponding CrdsValueLabel
is only its Pubkey. This means we'll only store one LegacyContactInfo
per Pubkey
in the CrdsTable
(i.e., if we assume that each validator corresponds to one Pubkey
, then this means we'll only store one contact info struct per validator).
// the full contact info struct (including pubkeys, sockets, and more)
pub const LegacyContactInfo = struct {
id: Pubkey,
/// gossip address
gossip: SocketAddr,
/// address to send repair responses to
repair: SocketAddr,
/// transactions address
tpu: SocketAddr,
//...
}
// the corresponding label (only the Pubkey)
pub const CrdsValueLabel = union(enum) {
LegacyContactInfo: Pubkey,
//...
}
When inserting a CrdsValue
, if an entry with the same corresponding label exists (i.e., a duplicate), we keep the value with the largest wallclock time (the newest value).
Cluster Replicated Data Store values: CrdsVersionedValue
The CrdsVersionedValue
structure contains the CrdsValue
inserted along with other related information including its hash, timestamps, and more.
pub const CrdsVersionedValue = struct {
value: CrdsValue,
value_hash: Hash,
timestamp_on_insertion: u64,
cursor_on_insertion: u64,
};
Reading Stored Data
We’re also interested in reading all stored data of a specific type. For example, when broadcasting data to the rest of the network, we need to retrieve all the contact info values stored in the CrdsTable
. This is why we use an indexable HashMap as our main data structure.
To do this:
- we insert the value into the
CrdsTable
and receive its corresponding index (crds_index = crds_table.insert(&versioned_value)
), - we store these indexes in an array corresponding to the specific type we’re tracking (
contact_infos.append(crds_index)
), and - when we want to retrieve these values, we look up all the indexes stored in the array to get the corresponding values (
versioned_value = crds_table[crds_index]
).
We follow this approach for the LegacyContactInfo
(s), Vote
(s), EpochSlot
(s) and DuplicateShred
(s) data types.
Reading New Data
To efficiently retrieve new data from the CrdsTable
, we also track a cursor
field which is monotonically incremented on each insert/update (which is stored on the CrdsVersionedValue
structure using the cursor_on_insertion
field).
For example, a listener would track their cursor and periodically call the getter functions (such as get_votes_with_cursor
, which allows you to retrieve vote CrdsVersionedValue
(s) which are past a certain cursor index) to retrieve new values.
Note: This is how we produce new push messages - talked about in a later section.
Bounding Memory Size and Removing Old Values
The CrdsTable
is also periodically trimmed to maintain a max number of unique Pubkeys (the max number of Pubkeys is set to 8192
in the codebase) and remove values with old timestamps so that memory growth is bounded, preventing out-of-memory errors.
We use the field CrdsTable.pubkey_to_values
to track all the CrdsValue
(s) in the table associated with a specific node’s Pubkey and periodically call CrdsTable.attempt_trim
to remove all the values associated with the oldest pubkeys when close to capacity. CrdsTable.remove_old_labels
is called to remove values with old timestamps periodically as well.
In the solana-labs implementation, the gossip pubkeys with the smallest stake weight are removed first, however, we don't have stake weight information yet in Sig. This will be future work.
Note: Since we are using an indexable HashMap struct, when removing values we typically use the removeSwap
function (defined as: "The entry is removed from the underlying array by swapping it with the last element and pop-ing"). Since we are tracking the index of values across multiple arrays, when we removeSwap
, the last value is now at a different index than how we recorded it. So, we need to account for the 'swapping with the last element' and update our indexes. The full logic can be found in CrdsTable.remove()
.
Sending/Receiving Requests
We receive new messages from the network as bytes. Before processing these messages, we:
- deserialize them into
Protocol
messages (defined inprotocol.zig
), - verify their values are valid, and
- verify the signature is correct.
If any of these checks fail, we discard the value. Otherwise, we process the protocol message.
Note: This logic can be found in the GossipService.verify_packets
method in gossip/gossip_service.zig
.
There are 4 types of Protocol messages to describe:
- Pull
- Push
- Prune
- Ping/Pong
Pull
Pull messages are used to retrieve new data from other nodes in the network. There are two types of Pull messages: PullRequest
and PullResponse
.
Building Pull Requests
Pull requests are requests for missing data. A pull request includes a Bloom filter over the values stored in the node's CrdsTable
to represent the CrdsValue
(s) it currently has, which the receiving node parses and uses to find CrdsValue
(s) which its missing.
Note: The majority of pull request code can be found in pull_requests.zig
and bloom.zig
.
Since the CrdsTable
can store a large amount of values, instead of constructing one large Bloom filter, we partition the data in the CrdsTable
across multiple Bloom filters based on the first N
bits of the CrdsValue
(s) hash.
Note: When constructing pull requests, in addition to all the values in the CrdsTable
, we also include values that were recently overwritten (which is tracked in the crds_table.purged
field), and invalid values that were received from a previous PullResponse
(discussed more in the 'Handling Pull Responses' section).
For example, if we are partitioning on the first 3 bits we would use, 2^3 = 8
Bloom
filters:
- the first Bloom filter would contain
CrdsValue
whose hash has its first3
bits equal to000
, - the second Bloom filter would contain
CrdsValue
(s) whose hash has its first3
bits equal to001
, - ...
- and lastly, the eighth Bloom filter would contain
CrdsValue
(s) whose hash has its first3
bits equal to111
.
If we are tracking a Hash
with bits 00101110101
, we would only consider its first 3 bits, 001
, and add the hash to the first Bloom filter (@cast(usize, 001) = 1
).
To implement this we use the CrdsFilterSet
struct which is a list of CrdsFilter
(s). Throughout the codebase, the first bits: N
, is called mask_bits
. mask_bits
is a field that is computed based on many factors including the desired false-positive rate of the bloom filters, the number of items in the CrdsTable
, and more. It will likely be different for each pull request.
After we construct the CrdsFilterSet
(i.e., compute the mask_bits
and init 2^mask_bits
Bloom filters), we add all of the CrdsValue
(s) in the CrdsTable
into the set, and construct a list of CrdsFilter
(s) to send to other random nodes.
## main function for building pull requests
def build_crds_filters(
crds_table: *CrdsTable
) Vec<CrdsFilters>:
values = crds_table.values()
filter_set = CrdsFilterSet.init(len(values))
for value in values:
filter_set.add(value)
# CrdsFilterSet => Vec<CrdsFilters>
return filter_set.consumeForCrdsFilters()
class CrdsFilterSet():
mask_bits: u64
filters: Vec<Bloom>
def init(self, num_items):
self.mask_bits = ... # compute the mask_bits
n_filters = 1 << mask_bits # 2^mask_bits
self.filters = []
for i in 0..n_filters:
self.filters.append(Bloom.random())
def add(hash: Hash):
# compute the hash index (i.e., the first mask_bits bits of the Hash)
# eg:
# hash: 001010101010101..1
# mask_bits = 3
# shift_bits = 64 - 3 (note: u64 has 64 bits)
# hash >> shift_bits = 001 (first three bits) = index 1
# == filters[1].add(hash)
shift_bits = 64 - mask_bits
index = @as(usize, hash >> shift_bits)
self.filters[index].add(hash)
To build a list of CrdsFilter
(s) from a CrdsFilterSet
, each CrdsFilter
will need a Bloom filter to represent a subset of the CrdsValue
(s), and a field to identify the hash bits that the Bloom filter contains (using a field called mask
).
For example, the mask
of the first filter would be 000
, the mask
of the second filter would be 001
, the mask
of the third filter would be 010
, ...
When a node receives a pull request, the mask
is used to efficiently look up all the matching CrdsValue
(s).
For example, if you received the 010
mask, you would look up all hash values whose first 3 bits are 010
and then find values that are not included in the request's Bloom filter. These values would then be included to build a pull response.
def consumeForCrdsFilters(self: CrdsFilterSet) Vec<CrdsFilters>:
for index in 0..len(self.filters):
crds_filter = CrdsFilter(
bloom=self.filters[index],
mask=CrdsFilter.compute_mask(index, self.mask_bits),
mask_bits=self.mask_bits,
)
To compute the mask
of a given filter index, the logic is similar to the bit operations above:
def compute_mask(index: u64, mask_bits: u64) u64:
# shift the index to the first `mask_bits` of the u64
# e.g.,
# index = 1
# mask_bits = 3
# shift_bits = 64 - 3 (note: u64 has 64 bits)
shift_bits = 64 - mask_bits
# shifted_index = 1 << (64 - 3) = 001000000000000...0
shifted_index = index << shift_bits
# ones = 000111111111111..1
ones = (~@as(u64, 0) >> @as(u6, @intCast(mask_bits)))
# result = 001111111111111..1
return shifted_index | ones
Notice how the result will be ones everywhere except for the first mask_bits
bits, which represent the filter's index. After getting the vector of filters, we then send each filter out to a random peer weighted by stake weight.

Building Pull Responses
Pull responses are responses to pull requests and include missing data that was not included in the pull request.
To build a pull response, we find values that match the CrdsFilter
's mask
, and respond with values that are not included in the request's Bloom
filter. To find values that match the filter's mask
, we use the CrdsShards
struct which is located in crds_shards.zig
.

What are CrdsShards?
The CrdsShards
struct stores hash values based on the first shard_bits
of a hash value (similar to the CrdsFilterSet
structure and the mask_bits
). Whenever we insert a new value in the CrdsTable
, we insert its hash into the CrdsShard
structure.
To store these hashes efficiently we use an array of HashMaps (shards = [4096]AutoArrayHashMap(usize, u64),
) where shards[k]
includes CrdsValue
(s) in which the first shard_bits
of their hash value is equal to k
.
- The keys in the HashMap are of type
usize
which is theCrdsTable
index of the hash. - And the values of the HashMap are of type
u64
which represents the hash value represented as au64
.
The struct allows us to quickly look up all the CrdsValue
(s) whose hash matches a pull request's mask
(compared to iterating over all the CrdsValue
(s)).
Note: shard_bits
is a hardcoded constant in the program equal to 12
, so we will have 2^12 = 4096
shard indexes.
After inserting a new value in the CrdsTable
, inserting its hash value into the CrdsShards
struct is straightforward:
- take the first 8 bytes of the
CrdsValue
(s) hash and cast it to au64
(hash_u64 = @as(u64, hash[0..8])
), - compute the first
shard_bits
bits of theu64
by computingshard_index = hash_u64 >> (64 - shard_bits)
, - get the corresponding shard:
self.shards[shard_index]
, and lastly, - insert the
CrdsTable
index along with theu64_hash
into the shard.
def insert(self: *CrdsShards, crds_index: usize, hash: *const Hash):
shard_index = @as(u64, hash[0..8]) >> (64 - shard_bits)
shard = self.shard[shard_index]
shard.put(crds_index, uhash);

Using CrdsShards for finding hash matches
To build a Pull Response, we need to retrieve values in the CrdsTable
whose hash matches a mask
(i.e., their first mask_bit
bits are equal to mask
).
To find these matches there are three cases we need to consider:
shard_bits == mask_bits
shard_bits < mask_bits
shard_bits > mask_bits
When shard_bits == mask_bits
, we look at the shard corresponding to the first shard_bits
of mask
and return its values.
For example, if shard_bits = 3
, mask_bits = 3
and our mask is 001
, we can find all the CrdsTable
values whose first 3
bits of their hash value is equal to 001
by looking up shards[1]
.

def find_matches(self: *CrdsShards, mask: u64, mask_bits: u64) Vec<usize>:
if (self.shard_bits == mask_bits) {
shard = self.shard[(mask >> (64 - self.shard_bits)]
crds_indexes = shard.keys()
return crds_indexes
} else {
# TODO:
}
When shard_bits < mask_bits
, the mask is tracking more bits than the shards are, so we can find the shard corresponding to the first shard_bits
of the mask
, and iterate over the values to find exact matches.
For example, truncating mask
and looking up the shard gives us hashes that have a matching first shard_bits
. We then need to check to make sure the last shard_bits - mask_bits
matches the mask
, which we do through iteration.
In another example, if shard_bits = 3
, mask_bits = 5
and our mask is 00101
, we would first find all the CrdsTable
values whose first 3
bits of their hash value is 001
by looking up shard[1]
. We would then iterate over those values and make sure the fourth and fifth bits of the hash are equal to 01
.

def find_matches(self: *CrdsShards, mask: u64, mask_bits: u64) Vec<usize>:
# ones everywhere except for the first `mask_bits`
mask_ones = (~0 >> mask_bits)
if (self.shard_bits == mask_bits) {
# ...
} else if (self.shard_bits < mask_bits) {
# truncate the mask
shard_index = mask << (64 - self.shard_bits)
shard = self.shards[shard_index]
# scan for matches
crds_indexes = []
for (indexes, hash_u64) in shard:
if ((hash_u64 | mask_ones) == (mask | mask_ones)): # match!
crds_indexes.append(indexes)
return crds_indexes
} else {
# TODO
}
When shard_bits > mask_bits
, the shards are tracking more information than the mask, so we'll need to look at multiple shards to find all the values that match mask
.
For example, if shard_bits = 4
, mask_bits = 2
and our mask is 01
the possible shards we'll need to lookup are: 0100
, 0101
, 0110
, 0111
(i.e., there will be 4 shards that match the mask represented by the difference in bits). We know we'll have to look up 2^(shard_bits - mask_bits)
number of shards (which can be computed using count = 1 << (shard_bits - mask_bits)
). The largest shard value would be the mask
followed by all ones at the end (i.e., 0111
in the example above) which can be computed as end = (mask | mask_ones) >> shard_bits
. Since we know the largest shard and the number of shards we're looking for, we can iterate over them from index = (end-count)..end
.

def find_matches(self: *CrdsShards, mask: u64, mask_bits: u64) Vec<usize>:
# ones everywhere except for the first `mask_bits`
mask_ones = (~0 >> mask_bits)
if (self.shard_bits == mask_bits) {
# ...
} else if (self.shard_bits < mask_bits) {
# ...
} else if (self.shard_bits > mask_bits) {
shift_bits = self.shard_bits - mask_bits
count = 1 << shift_bits
end = (mask | mask_ones) >> shard_bits
crds_indexs = []
for shard_index in (end-count)..end:
shard = self.shards[shard_index]
indexes = shard.keys()
crds_indexes.append(indexes)
return crds_indexes
}
After we have all the CrdsValue
indexes that match the mask
, we then check which values are not included in the pull request's Bloom filter (i.e., values that the node is missing). These values are then packed into a PullResponse
message and sent to the peer who sent the corresponding PullRequest
.
def filter_crds_values(
crds_table: *CrdsTable
filter: *CrdsFilter
) Vec<CrdsValues>:
# find crds values whose hash matches the mask
var match_indexes = crds_table.get_bitmask_matches(filter.mask,filter.mask_bits);
# find the values that are not included in the requests bloom filter
values = []
for index in match_indexes:
entry = crds_table[index]
if (!filter.bloom.contains(entry.hash)):
values.append(entry)
return values
Handling Pull Responses
When receiving a PullResponse
, we insert all the values received in the CrdsTable
. If any values fail to be inserted (due to having an old wallclock time, or being duplicate data), we track their hash in an array failed_pull_hashes
. These failed hash values are then used when constructing the next Pull Request so that the values are not sent again. To ensure memory doesn’t grow without bounds, the failed_pull_hashes
array is periodically trimmed to remove old values.
We also do the same thing for values that are pruned in the CrdsTable
(i.e., values that are overwritten) in CrdsTable.purged
.
For each CrdsValue
that is successfully inserted in the CrdsTable
, we also update the timestamps for all the values from that origin pubkey. We do this so that when we are trimming old CrdsValue
(s) in the table, we don't remove values from an active pubkey.
Push
Sending Push Messages
Push messages are periodically generated to send out new data to a subset of the network’s nodes. To implement this, we track a push_cursor
variable which represents the cursor value of the last pushed value, and use the getter function crds_table.get_entries_with_cursor()
to get new CrdsValue
(s) which have been inserted past this value.
In Sig, a PushMessage
is defined as struct { Pubkey, []CrdsValue }
: a source Pubkey
, and an slice of CrdsValue
(s). The source pubkey will be the same pubkey on the local node's contact information. And the array of values will be the new CrdsValue
(s) that are being pushed.
An important note is that all messages sent through gossip should be less than or equal to a maximum transmission unit (MTU) of 1280 bytes (which is referred to as the Packet
struct throughout the codebase).
Because sometimes there are more CrdsValue
(s) to push than can fit inside one of these packets (i.e., bytes([]CrdsValue) > MTU
), the CrdsValue
(s) are partitioned into packet-sized chunk PushMessage
(s) instead of one large PushMessage
.
These PushMessage
(s) are then sent to all the nodes in the local node's ActiveSet
.
Data Structures: Active Set
A node's ActiveSet
is a list of nodes in the gossip network with a shred version equal to the local nodes (i.e., a variable used to track hard-forks), with valid gossip ports, and other details. The ActiveSet
is a key part of the PlumTree algorithm, which enables data to be propagated in a tree-like structure instead of a full broadcast.
The ActiveSet
is periodically re-sampled to reduce the chance of eclipse attacks.
Note: See the “Receiving Prune Messages” section for a more detailed explanation of how the ActiveSet
is constructed on a per-crds-value-origin basis.
Note: The solana-labs rust implementation uses stake weight information to build their active set. However, since Sig doesn’t have stake weight information yet so we chose to randomly sample the nodes.

Solana-Labs' Active Set
For completeness, the solana-labs client's active set implementation is also worth discussing. Their PushActiveSet
contains multiple PushActiveSetEntry
structs where each entry corresponds to a different probability distribution over possible nodes to be included in the active set.
The entries distribution is ordered by decreasing entropy over stake weight. Entries at the start of the list (with a low index - e.g., 0, 1) are a uniform distribution over the possible nodes (with high entropy) and entries at the end of the list (with a large index - e.g., 24, 25) have a distribution weighted strongly by a node's stake amount (with low entropy).
When building the active set, the local node's stake weight decides which entry to sample the nodes from. For example, if the local node has a large stake, its index will be large which corresponds to a distribution that has a higher probability of selecting another high-staked node to be included in the active set.
This means, high-stake nodes are more likely to send push messages to other high-stake nodes, while low-stake nodes send push messages to random nodes.

Receiving Push Messages
When receiving a new PushMessage
, the values are inserted into the CrdsTable
, and values that failed the insertion (due to being a duplicate) are tracked. The nodes who sent those failed values are then sent PruneMessage
(s).
Prune
PruneMessage
(s) are used to prune duplicate PushMessage
(s) in the broadcast tree (i.e., sending a Prune message that effectively says: “stop sending me this data, I’ve already received it from another node").
Sending Prune Message
A Prune message is defined as struct { PubKey, PruneData }
where PruneData
is defined as follows:
pub const PruneData = struct {
/// Pubkey of the node that sent this prune data
pubkey: Pubkey,
/// Pubkeys of origins that should no longer be sent to pubkey
prunes: []Pubkey,
/// Signature of this Prune Message
signature: Signature,
/// The Pubkey of the intended node/destination for this message
destination: Pubkey,
/// Wallclock of the node that generated this message
wallclock: u64,
}
The comments explain most of the fields in the struct. The prunes
field is a list of origin
pubkeys (pubkeys of the node which create a corresponding CrdsValue
). When inserting the received values from a new push message, if a CrdsValue
fails to be inserted into the CrdsTable
, the origin
of the value (i.e., the pubkey of the node that created the value) is added to the prunes list. And lastly, the destination field is set to the node which sent the push message.
def handle_push_message(
from_pubkey: Pubkey, # received from
values: []CrdsValues, # values from push msg
my_pubkey: Pubkey, # local nodes pubkey
crds_table: *CrdsTable,
) {
pruned_origins = []
for value in values:
result = crds_table.insert(value)
if result.is_error():
origin = value.id()
pruned_origins.append(origin)
return PruneMessage {
prunes: pruned_origins,
destination: from_pubkey,
pubkey: my_pubkey,
}
}

Note: In the solana-labs client, to compute what nodes to send a prune message to, the client uses the number of duplicates sent, along with the node's stake weight and a minimum number of nodes to keep. Since Sig doesn't have stake weight information yet so we follow a simpler approach and send prune messages to any peers which send a value that fails to be inserted in the CrdsTable
.
Receiving Prune Messages
When a prune message is received, we track which from_address
pruned a specific origin
using a HashMap(from_address: Pubkey, origin_bloom: Bloom)
where from_address: Pubkey
is the address which sent the prune message to a Bloom
filter which the pruned origins are inserted into.
When constructing the active set for a CrdsValue
:
- we find the
origin
of that value, - iterate over the peers in the
ActiveSet
, - look up the peer in the HashMap to find their corresponding Bloom filter, and
- check if the origin of the
CrdsValue
is contained in the Bloom filter.
If the origin is not contained in the bloom filter, we haven’t received a corresponding prune message, so we add the peer to the active set. If the origin is contained in the bloom filter, we don’t add the peer to the active set.
Ping/Pong messages
Ping
and Pong
messages are used to health check nodes quickly and easily. The corresponding logic is defined in gossip/ping_pong.zig
.
Ping
messages are periodically sent to all of the nodes in the network (by parsing the contact information in the CrdsTable
). For each of these Ping
messages, a corresponding Pong
message is expected within a certain amount of time. If we fail to receive the corresponding Pong
message, then we don’t send that node any other protocol messages (i.e., we don’t include them in the ActiveSet
so we don’t send them PushMessage
(s), nor do we respond to any PullRequest
(s) received from them).
We track the nodes that have responded to Ping messages with a corresponding Pong message as well as which nodes we are still waiting for a corresponding Pong message for using the PingCache
structure.
What is the PingCache?
The PingCache
holds important data including the amount of time a received Pong
message is valid for (i.e., when the node should send a new ping message) which is set to 1280
seconds by default and the rate limit for how often to send Ping
messages which is set to only send Ping
messages every 20
seconds.
When building certain messages (i.e. Push
, Pull
, etc.) we verify the node is valid using filter_valid_peers()
func. This returns a list of filtered valid peers along with possible Ping
(s) that need to be sent out.
Overview Diagram
The following diagram shows the overall implementation design of the GossipService
of Sig which handles receiving, processing, and sending gossip messages.

A working Gossip implementation is crucial for the node as it enables communication with other nodes in the network and facilitates the construction of a chain of valid blocks. We have endeavored to provide a technical summary of the gossip spy above.
We welcome comments and feedback from the Sig community.