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 in protocol.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 first 3 bits equal to 000,
• the second Bloom filter would contain CrdsValue(s) whose hash has its first 3 bits equal to 001,
• ...
• and lastly, the eighth Bloom filter would contain CrdsValue(s) whose hash has its first 3 bits equal to 111.

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 the CrdsTable index of the hash.
• And the values of the HashMap are of type u64 which represents the hash value represented as a u64.

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 a u64 (hash_u64 = @as(u64, hash[0..8])),
• compute the first shard_bits bits of the u64 by computing shard_index = hash_u64 >> (64 - shard_bits),
• get the corresponding shard: self.shards[shard_index], and lastly,
• insert the CrdsTable index along with the u64_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.