ubt 0.3.0

Unified Binary Tree implementation based on EIP-7864
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

//! # 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
//!
//! ```rust
//! 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().unwrap();
//! ```
//!
//! ## 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:
//!
//! ```rust
//! use ubt::{UnifiedBinaryTree, Blake3Hasher};
//!
//! let mut tree: UnifiedBinaryTree<Blake3Hasher> = UnifiedBinaryTree::new();
//! // ... initial inserts ...
//! tree.root_hash().unwrap(); // 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.

#![cfg_attr(not(test), warn(unused_crate_dependencies))]

// Optional deps used by the `simulate` binary. Rust checks unused deps per-crate,
// so we reference them here to avoid `unused_crate_dependencies` warnings when the
// feature is enabled.
#[cfg(feature = "simulate")]
use num_cpus as _;
#[cfg(feature = "simulate")]
use rand as _;

mod code;
mod compat_tests;
mod embedding;
mod error;
mod geth_compat;
mod hash;
mod key;
mod node;
mod proof;
mod streaming;
mod tree;

pub use error::UbtError;
pub use hash::{Blake3Hasher, Hasher, Sha256Hasher};
pub use key::{Stem, SubIndex, TreeKey, STEM_LEN, SUBINDEX_BITS};
pub use node::{InternalNode, LeafNode, Node, StemNode};

pub use code::{chunkify_code, dechunkify_code, CodeChunk};
pub use embedding::{
    get_basic_data_key, get_binary_tree_key, get_code_chunk_key, get_code_hash_key,
    get_storage_slot_key, get_storage_slot_key_u256, AccountStem, BasicDataLeaf,
    BASIC_DATA_BALANCE_OFFSET, BASIC_DATA_CODE_SIZE_OFFSET, BASIC_DATA_LEAF_KEY,
    BASIC_DATA_NONCE_OFFSET, CODE_HASH_LEAF_KEY, CODE_OFFSET, HEADER_STORAGE_OFFSET,
    STEM_SUBTREE_WIDTH,
};
pub use proof::{generate_stem_proof, Direction, MultiProof, Proof, ProofNode, Witness};
#[doc(hidden)]
pub use std::collections::HashMap;
pub use streaming::StreamingTreeBuilder;
pub use tree::UnifiedBinaryTree;

/// Re-export alloy primitives for convenience
pub use alloy_primitives::{Address, B256, U256};