Skip to content
blockchain-compression cargo add →

← back to notes

Reading the algorithm: how we exploit chain-specific structure

blockchain-compression team · ·
architectureengineering

The shortest honest version of how this library works is: it is Zstandard, with a hardcoded dictionary of common Solana byte patterns, exposed through six named presets that map to specific Zstd compression levels. Nothing in that sentence is novel. The interesting question is where the line is drawn between “general-purpose compressor” and “Solana-specific compressor,” and how much of the work the dictionary actually does.

This post reads the relevant source. It is structured as a tour, not a tutorial. If you want the full code, it is at src/presets/solana.rs in the GitHub repo.

The trait

Everything in the library implements CompressionStrategy. The trait is small:

pub trait CompressionStrategy {
    type Error;
    fn compress(&mut self, data: &[u8]) -> Result<Vec<u8>, Self::Error>;
    fn decompress(&self, data: &[u8]) -> Result<Vec<u8>, Self::Error>;
    fn metadata(&self) -> CompressionMetadata;
    fn stats(&self) -> CompressionStats;
    fn reset(&mut self);
}

That is the entire contract. compress takes bytes and returns bytes. decompress takes bytes and returns bytes. metadata describes the encoder. stats reports counters. reset clears the counters. There is no streaming API in the trait, no partial-block support, no chunk boundaries. Those exist in the implementations but are not part of the abstraction.

The trait is what makes the Solana preset interchangeable with the more experimental algorithms in src/algorithms/ — EnhancedCTW, MultiPassCompressor, PracticalMaxCompression. They are all CompressionStrategy implementations. We benchmark them against each other behind the same trait, and the one that wins in production is the one that ships.

The Solana preset

SolanaCompressor is the production path. The struct is four fields:

pub struct SolanaCompressor {
    compression_level: i32,
    preset: SolanaPreset,
    dictionary: Option<Vec<u8>>,
    stats: CompressionStats,
}

The preset enum has six variants — FastCompression, Transactions, Instructions, Accounts, Mixed, MaxCompression. Each variant maps to a Zstd compression level by a simple function:

fn preset_to_level(preset: &SolanaPreset) -> i32 {
    match preset {
        SolanaPreset::FastCompression => 3,
        SolanaPreset::Transactions    => 3,
        SolanaPreset::Instructions    => 6,
        SolanaPreset::Accounts        => 6,
        SolanaPreset::Mixed           => 6,
        SolanaPreset::MaxCompression  => 19,
    }
}

That is the entire preset_to_level function. There is no per-preset dictionary tuning, no per-preset chunking strategy, no per-preset Huffman table. The presets differ only in the Zstd level they pass to the encoder. The ratio differences between Transactions and Mixed — both at Zstd 6 in the case of the latter, Zstd 3 in the former — come from the level and from the data, not from a different code path.

This is on purpose. The complexity-to-ratio curve has a knee, and the knee is “Zstandard with a custom dictionary.” Adding more knobs above that floor does not pay for itself in the ratios we observed during development.

The dictionary

The dictionary is built once, at compressor construction, from a constant array of byte patterns. Here is the full list, lightly abbreviated for the post:

const SOLANA_DICTIONARY_PATTERNS: &[&str] = &[
    // System and core programs
    "11111111111111111111111111111112",              // System Program
    "TokenkegQfeZyiNwAJbNbGKPFXCWuBvf9Ss623VQ5DA",  // Token Program
    "ATokenGPvbdGVxr1b2hvZbsiqW5xWH25efTNsLJA8knL",  // Associated Token
    "9WzDXwBbmkg8ZTbNMqUxvQRAyrZzDsGYdLVL9zYtAWWM",  // Serum DEX
    "BPFLoaderUpgradeab1e11111111111111111111111",  // BPF Loader
    "Config1111111111111111111111111111111111111",  // Config Program
    "Vote111111111111111111111111111111111111111",  // Vote Program
    "Stake11111111111111111111111111111111111111",  // Stake Program

    // Common instruction discriminators
    "00000000", "01000000", "02000000", "03000000",

    // Common amounts (as bytes)
    "00e1f50500000000",  // 1 SOL in lamports
    "00ca9a3b00000000",  // 0.1 SOL in lamports
    "0010270000000000",  // 0.01 SOL in lamports
    "00e40b5402000000",  // 10 SOL in lamports

    // Transaction structure markers
    "0100", "0200", "0300",
];

Twenty-or-so byte patterns. That is the whole dictionary. The construction logic concatenates them with null separators, appends the Base58 alphabet at the end, and hands the resulting byte vector to Zstandard:

fn build_solana_dictionary() -> Vec<u8> {
    let mut dictionary_data = Vec::new();
    for pattern in SOLANA_DICTIONARY_PATTERNS {
        dictionary_data.extend_from_slice(pattern.as_bytes());
        dictionary_data.push(0);
    }
    dictionary_data.extend_from_slice(
        b"123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz"
    );
    dictionary_data
}

This is the entire chain-specific intelligence in the library. It is a constant. It does not depend on the input data, it does not change between releases without a code change, and it does not require any per-customer state. Decompression is deterministic because the dictionary is a deterministic function of the build.

The compress path

The Zstd encoder is constructed with the dictionary at compression time:

let mut encoder = zstd::stream::write::Encoder::with_dictionary(
    Vec::new(),
    self.compression_level,
    dict,
)?;
encoder.write_all(data)?;
let compressed = encoder.finish()?;

That is the entire encoding path. Three calls into the zstd crate. The dictionary parameter tells Zstandard “treat these bytes as if they had just appeared in the stream.” When the encoder sees TokenkegQfeZyiNwAJbNbGKPFXCWuBvf9Ss623VQ5DA in the input, it finds the same byte sequence in the dictionary, emits a back-reference, and moves on. The encoded output contains a tiny token where the input contained 44 bytes of Base58-encoded program ID.

Multiply that across every transaction in a batch and you get the ratio table from the README.

The decompress path

Decompression mirrors compression. It builds the same dictionary, constructs a zstd::stream::read::Decoder::with_dictionary, and reads the bytes back out:

let mut decoder = zstd::stream::read::Decoder::with_dictionary(data, dict)?;
let mut decompressed = Vec::new();
decoder.read_to_end(&mut decompressed)?;

The dictionary is the same constant on the decompress side. This is the load-bearing reason the dictionary is hardcoded instead of learned: a learned dictionary would be a separate artifact that would have to ship beside the compressed data, or be embedded in a header, or be downloaded at decompression time. The hardcoded dictionary travels with the library binary. As long as the major version matches on both sides, the round-trip is exact.

What the experimental algorithms taught us

There are three other compression algorithms in the codebase that do not power the Solana preset: EnhancedCTW, MultiPassCompressor, and PracticalMaxCompression. They live in src/algorithms/.

EnhancedCTW is Context Tree Weighting, a prediction-based scheme that learns a model of the input as it goes. On highly structured data it produces excellent ratios — better than Zstandard at the high levels, on some workloads. The reason it does not ship as the production path is that the encoder is slow and the model is sensitive to input distribution shifts. For the kind of mixed Solana traffic real customers send, Zstandard with the dictionary was within a few percent of CTW on ratio and many times faster.

MultiPassCompressor applies compression in passes, stopping when an additional pass does not improve the ratio by a threshold. It is most useful inside the more aggressive algorithms; in isolation it tends to oscillate around Zstandard’s output size on Solana data.

PracticalMaxCompression orchestrates the pattern engine, CTW, and multi-pass. It is the most aggressive ratio target in the codebase. On archival workloads it can beat MaxCompression modestly — a few percent — but at a substantial CPU cost. It exists as a research path and as a reference point. If you have an unusual workload where the marginal ratio matters more than CPU, it is worth trying. For everyone else, MaxCompression is the answer.

The summary

The library is not trying to be clever about compression theory. The clever part is choosing not to be clever, and instead being correct about what makes chain data different from arbitrary bytes. The difference, source-code-wise, is a short constant array and a single with_dictionary argument. The difference, ratio-wise, is in the README’s preset table — and it is the difference between vanilla Zstandard on chain data and Zstandard that knows what an SPL program ID looks like.