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