Crate ubt 

Unified Binary Tree (UBT)

Implementation of EIP-7864: Ethereum state using a unified binary tree.

This crate provides a binary tree structure intended to replace the hexary patricia trees used in Ethereum. Key features:

• Single tree: Account and storage tries are merged into a single tree with 32-byte keys
• Code chunking: Contract bytecode is chunked and stored in the tree
• Data co-location: Related data (nonce, balance, first storage slots, first code chunks) are grouped together in 256-value subtrees to reduce branch openings
• ZK-friendly: Designed for efficient proving in ZK circuits
• Parallel hashing: Uses rayon for concurrent stem hash computation (default feature)
• Incremental updates: O(D*C) root updates instead of O(S log S) rebuilds

Tree Structure

The tree uses 32-byte keys where:

• First 31 bytes: stem (defines the subtree)
• Last byte: subindex (position within the 256-value subtree)

Node types:

• InternalNode: Has left_hash and right_hash
• StemNode: Has stem (31 bytes), left_hash and right_hash for its 256-value subtree
• LeafNode: Contains a 32-byte value or empty
• EmptyNode: Represents an empty node/subtree (hash = 0)

Quick Start

use ubt::{UnifiedBinaryTree, TreeKey, Blake3Hasher, B256};

let mut tree: UnifiedBinaryTree<Blake3Hasher> = UnifiedBinaryTree::new();
let key = TreeKey::from_bytes(B256::repeat_byte(0x01));
tree.insert(key, B256::repeat_byte(0x42));
let root = tree.root_hash();

Features

• parallel (default): Enables parallel stem hashing via rayon. Provides significant speedup for trees with many dirty stems per rebuild cycle.
• serde: Enables serialization support for tree types.

Performance Modes

Parallel Hashing (default)

When the parallel feature is enabled (default), stem hashes are computed concurrently using rayon’s parallel iterators. This is beneficial when many stems are modified between root_hash() calls.

Incremental Updates

For block-by-block state updates where only a small subset of stems change, enable incremental mode to cache intermediate node hashes:

use ubt::{UnifiedBinaryTree, Blake3Hasher};

let mut tree: UnifiedBinaryTree<Blake3Hasher> = UnifiedBinaryTree::new();
// ... initial inserts ...
tree.root_hash(); // Initial full build

// Enable incremental mode for subsequent updates
tree.enable_incremental_mode();

// Future updates only recompute affected paths: O(D*C) vs O(S log S)
// where D=248 (tree depth) and C=changed stems per block

Hash Function

Note: The hash function is not final per EIP-7864. This implementation uses BLAKE3 as a reference. Candidates include Keccak and Poseidon2.

The Hasher trait is Send + Sync to support parallel hashing contexts.

Structs

AccountStem

Helper struct for computing account keys.

Address

Re-export alloy primitives for convenience An Ethereum address, 20 bytes in length.

BasicDataLeaf

Basic account data packed into a single 32-byte leaf.

Blake3Hasher

BLAKE3-based hasher (reference implementation).

CodeChunk

A code chunk with leading PUSHDATA count.

InternalNode

Internal branching node.

LeafNode

Leaf node containing a 32-byte value.

MultiProof

A multi-proof for multiple keys.

Proof

A Merkle proof for a value in the UBT.

Sha256Hasher

SHA256-based hasher (go-ethereum compatible).

Stem

A 31-byte stem that identifies a subtree of 256 values.

StemNode

Stem node that roots a 256-value subtree.

StreamingTreeBuilder

A streaming tree builder that computes root hash with minimal memory.

TreeKey

A complete 32-byte tree key (stem + subindex).

UnifiedBinaryTree

The Unified Binary Tree.

Witness

Witness data for stateless execution.

Enums

Direction

Direction in the tree (for proof paths)

Node

A node in the UBT.

ProofNode

A node in a Merkle proof path.

UbtError

Errors that can occur during UBT operations.

Constants

BASIC_DATA_BALANCE_OFFSET

Offset in basic data leaf for balance (bytes 16-31)

BASIC_DATA_CODE_SIZE_OFFSET

Offset in basic data leaf for code size (bytes 5-7)

BASIC_DATA_LEAF_KEY

Subindex for basic account data (nonce, balance, code size)

BASIC_DATA_NONCE_OFFSET

Offset in basic data leaf for nonce (bytes 8-15)

CODE_HASH_LEAF_KEY

Subindex for code hash

CODE_OFFSET

Offset for first 128 code chunks within account stem (subindexes 128-255)

HEADER_STORAGE_OFFSET

Offset for first 64 storage slots within account stem (subindexes 64-127)

STEM_LEN

Length of a stem in bytes (31 bytes = 248 bits)

STEM_SUBTREE_WIDTH

Width of a stem subtree (256 values)

SUBINDEX_BITS

Number of bits in the subindex (8 bits = 256 possible values)

Traits

Hasher

Trait for hash functions used in the UBT.

Functions

chunkify_code

Chunkify bytecode into 31-byte chunks with PUSHDATA tracking.

dechunkify_code

Reconstruct bytecode from chunks.

generate_stem_proof

Generate a proof for a key in a stem node.

get_basic_data_key

Get the tree key for basic account data (nonce, balance, code size).

get_binary_tree_key

Derive a tree key using the go-ethereum algorithm.

get_code_chunk_key

Get the tree key for a code chunk.

get_code_hash_key

Get the tree key for code hash.

get_storage_slot_key

Get the tree key for a storage slot.

get_storage_slot_key_u256

Get the tree key for a storage slot from U256.

Type Aliases

B256

Re-export alloy primitives for convenience 32-byte fixed byte-array type.

SubIndex

Subindex within a stem’s subtree (0-255).

U256

Re-export alloy primitives for convenience 256-bit unsigned integer type, consisting of 4, 64-bit limbs.