Binary Trie Store

A high-performance Rust implementation of binary trie data structures optimized for key-value storage. This crate provides both a full-featured trie store and a zero-knowledge compatible witness-based variant.

Features

• High Performance: Optimized binary trie implementation with fast insertions, lookups, and deletions.
• Distinct Flush Operation: Recomputation of the trie intermediary nodes and root hash is delayed until an explicit flush function is called (improves performance).
• Witness Generation: ZkBinaryTrieStore variant that generates compact witnesses for ZK proofs (a minimal binary trie for use when re-executing in zkVMs).
• Parallel Processing: Uses Rayon for parallel hashing on large tries
• Fast Serialization: Very fast serialization (simple memcpy operations) which allow for quick snapshoting and trie copying.
• Memory Efficient: Optimized memory layout and operations for running in a zkVM.

Core Components

There are actually two implementations of a binary trie in this repo. One built for the needs of normal operation on a typical machine with lots of memory (BinaryTrieStore), and another built for short term existance that can be pruned to only the bare minimum needed for execution (BinaryTrieWitness).

BinaryTrieStore

The main trie implementation which trades higher memory consumption for better performance:

• Fast [O(1)] key-value operations (load/store)
• Efficient batch operations with delayed flushing
• Cryptographic root hash computation
• Parallel hash computation for large tries

BinaryTrieWitness

A zkVM friendly implementation which expects a very specific order of load/store ops:

• Contains only the minimal set of nodes required for proof verification
• Fast [O(1)] key-value operations (load/store) through replay "advice" during witness generation
• Supports all trie operations (get, update, validate) on witness data
• Optimized memory layout for zero-knowledge circuit compatibility

ZkBinaryTrieStore

A wrapper around both BinaryTrieStore and BinaryTrieWitness that tracks operations and can generate witness data during a flush:

• Operation tracking for witness generation
• Compact witness format for ZK circuits
• Seamless switching between full store and witness modes (write code once that just interacts with one object whether in zkVM mode, or normal execution mode)

Usage

Basic Usage

use binary_trie_store::{hash::Sha256, types::{Bytes32, U64}, BinaryTrieStore};

// Create a new trie store
let mut store = BinaryTrieStore::<Sha256, Bytes32, U64>::new();

// Store key-value pairs
let key = Bytes32::from([1u8; 32]);
let value = 42u64;
store.store(&key, Some(&value.into()));

// Load values
if let Some(retrieved_value) = store.load(&key) {
    println!("Value: {}", retrieved_value);
}

// Flush changes and get root hash
let root_hash = store.flush();
println!("Root hash: {:?}", root_hash);

Zero-Knowledge Usage (Witness)

use binary_trie_store::{hash::Sha256, serialization::ByteSerializable, types::{Bytes32, U64}, ZkBinaryTrieStore};

// Create a ZK-compatible trie store
let mut zk_store = ZkBinaryTrieStore::<Sha256, Bytes32, U64>::new();

// Perform operations (automatically tracked)
let key = Bytes32::from([1u8; 32]);
zk_store.store(&key, Some(&100u64.into()));
zk_store.load(&key);

// Generate witness and flush
let witness_store = zk_store.flush_with_witness();
let root = witness_store.root();
println!("Root: {:?}", root);

// Serialize the witness
let serialized_witness = witness_store.to_bytes();

////// Pass to zkVM //////

// Deserialize the witness
let mut witness_store = ZkBinaryTrieStore::<Sha256, Bytes32, U64>::from_bytes(&serialized_witness);

// Validate witness
if !witness_store.is_valid_witness() {
    panic!("Witness is invalid!");
}

// Get witness initial trie root
let initial_root = witness_store.root();
println!("Initial root: {:?}", initial_root);

// Re-execute the same operations (in same order)
let key = Bytes32::from([1u8; 32]);
witness_store.store(&key, Some(&100u64.into()));
witness_store.load(&key);

// Flush changes and get root hash
let new_root_hash = witness_store.flush();
println!("New root: {:?}", new_root_hash);

Architecture

Binary Trie Structure

The trie uses a binary tree structure where:

• Internal nodes store prefixes and have left/right children
• Leaf nodes store actual key-value pairs
• Proxy nodes store just the hash of the node for proving purposes (BinaryTrieWitness only)

Memory Layout

• Nodes are stored in vectors with index-based references
• Memory-efficient node representation using #[repr(C)]

Serialization

• Trie is quickly serialized through few memcpy operations
• Can take advantage of improved zkVM deserialization

let mut reader = STDINReader::new();
let witness = W::read_bytes(&mut reader);

// wrap "env::read_slice" from "risc0_zkvm" into a custom reader
struct STDINReader {
    buffer: Vec<u8>,
}
impl STDINReader {
    fn new() -> Self {
        STDINReader {
            buffer: Vec::new(),
        }
    }
}
impl SerialReader for STDINReader {
    fn read_slice(&mut self, buffer: &mut [u8]) {
        env::read_slice(buffer);
    }
    fn read(&mut self, size: usize) -> &[u8] {
        if self.buffer.len() < size {
            self.buffer.resize(size, 0);
        }
        env::read_slice(&mut self.buffer[..size]);
        &self.buffer[..size]
    }
}

ZK Witness Generation

1. ZkBinaryTrieStore tracks all operations performed on the trie
2. Generates minimal BinaryTrieWitness containing only touched nodes

Dependencies

• hex: For hexadecimal encoding/decoding on included types
• rayon: For parallel processing
• sha2: For SHA-256 hashing
• tiny-keccak: For Keccak hashing