brine-tree

A fast, low-overhead, Blake3 Merkle tree library for the Solana programs.

Features

• Zero-copy
• Support for add, remove, replace
• Low compute unit (CU) consumption
• Can be stored in account state
• Includes proof generation and verification
• Includes cached proof generation

Quick Start

use brine_tree::{MerkleTree, Leaf};

fn main() {
    const TREE_DEPTH: usize = 18;

    let mut tree = MerkleTree::<{TREE_DEPTH}>::new(&[b"empty_leaf_seed"]);
    let data = &[b"hello", b"world"];
    let leaf = Leaf::new(data);

    tree.try_add_leaf(leaf)?;

    // Off-chain proof generation

    let db = &[leaf, ...]; // your database of leaves
    let leaf_index = 0; // index of the leaf you want to prove

    let proof = tree.get_merkle_proof(db, leaf_index)?;
    
    assert!(tree.contains(&proof, data));

    Ok(())
}

Returns Ok(()) for successful operations or Err(ProgramError) if invalid.

Use Cases

• State compression for large datasets
• Whitelist or access control verification
• Off-chain data integrity checks
• Cross-chain state proofs
• Decentralized identity claims
• Oracle data validation

But why?

Q: Why not use an off-chain Merkle tree?
A: Solana programs often need to verify inclusion or manage state on-chain efficiently. Off-chain Merkle trees require additional infrastructure and trust assumptions.

Q: Why not use something else?
A: There definitely are a few other implementations worth looking into, like concurrent merkle tree, but this one is simple and easy to work with.

Contributing

Contributions are welcome! Please open issues or PRs on the GitHub repo.