reth_trie_common/
ordered_root.rs

1//! Incremental ordered trie root computation for append-only streams.
2//!
3//! Ethereum block transaction and receipt roots are ordered trie roots keyed by the RLP encoding of
4//! each item index.
5//! [`OrderedTrieRootEncodedBuilder`](crate::ordered_root::OrderedTrieRootEncodedBuilder) accepts
6//! items in their final contiguous order, without requiring the final item count until the stream
7//! ends.
8//!
9//! # Why this works
10//!
11//! RLP-encoded integer keys sort differently around small indices:
12//!
13//! - indices `1..=127` encode as single bytes `0x01..=0x7f`;
14//! - index `0` encodes as `0x80`, so it sorts after `1..=127`;
15//! - indices `>= 128` encode as longer byte strings and sort after `0`.
16//!
17//! This means the final insertion order for a dense list is:
18//!
19//! ```text
20//! len = 0:      []
21//! len = 1:      [0]
22//! 2..=128:     [1, 2, ..., len - 1, 0]
23//! >=129:       [1, 2, ..., 127, 0, 128, 129, ...]
24//! ```
25//!
26//! While the stream is open, the only ambiguous leaf is index `0`: for short lists it is inserted
27//! when the stream ends, and for lists with at least 129 items it can be inserted as soon as index
28//! `128` arrives. All other leaves can be added as they arrive in append-only order.
29//!
30//! # Example
31//!
32//! ```
33//! use reth_trie_common::ordered_root::OrderedTrieRootEncodedBuilder;
34//!
35//! let mut builder = OrderedTrieRootEncodedBuilder::new();
36//! builder.push_next(b"encoded_item_0");
37//! builder.push_next(b"encoded_item_1");
38//!
39//! let root = builder.finalize();
40//! ```
41
42use crate::{HashBuilder, Nibbles, EMPTY_ROOT_HASH};
43use alloc::vec::Vec;
44use alloy_primitives::B256;
45
46/// First index whose RLP-encoded key sorts after index 0.
47///
48/// Indices `1..=0x7f` encode as their own single byte, so they sort before the RLP encoding of
49/// index 0 (`0x80`). Index `0x80` and larger use long-form RLP integer encoding and sort after
50/// index 0, so index 0 must be flushed before inserting this index.
51const ZERO_KEY_FLUSH_INDEX: usize = 0x80;
52
53/// A builder for computing ordered trie roots from an append-only stream of pre-encoded items.
54///
55/// This type does not require the total item count up front. It relies on a strict input contract
56/// instead: every pushed item must be the next contiguous item in the final list.
57///
58/// This builder is intended for transaction and receipt root computation while a block is still
59/// being built. It buffers only index `0`, then streams all other leaves directly into the
60/// [`HashBuilder`] in the same order as `alloy_trie::root::ordered_trie_root_encoded`.
61#[derive(Debug, Default)]
62pub struct OrderedTrieRootEncodedBuilder {
63    /// Number of items pushed so far. This is also the next append-only index.
64    len: usize,
65    /// Index 0 is the only item whose final insertion position depends on whether more items
66    /// arrive.
67    zero: Option<Vec<u8>>,
68    /// The underlying hash builder.
69    hb: HashBuilder,
70}
71
72impl OrderedTrieRootEncodedBuilder {
73    /// Creates an empty builder.
74    pub fn new() -> Self {
75        Self::default()
76    }
77
78    /// Pushes the next pre-encoded item.
79    ///
80    /// Items must be pushed in their final contiguous order.
81    #[inline]
82    pub fn push_next(&mut self, bytes: &[u8]) {
83        let index = self.len;
84        self.len += 1;
85
86        match index {
87            0 => {
88                self.zero = Some(bytes.to_vec());
89            }
90            1..=0x7f => {
91                self.add_leaf(index, bytes);
92            }
93            ZERO_KEY_FLUSH_INDEX => {
94                self.flush_zero();
95                self.add_leaf(index, bytes);
96            }
97            _ => {
98                debug_assert!(self.zero.is_none(), "index 0 must be flushed before indices > 128");
99                self.add_leaf(index, bytes);
100            }
101        }
102    }
103
104    /// Returns the number of items pushed so far.
105    #[inline]
106    pub const fn pushed_count(&self) -> usize {
107        self.len
108    }
109
110    /// Returns `true` if no items have been pushed.
111    #[inline]
112    pub const fn is_empty(&self) -> bool {
113        self.len == 0
114    }
115
116    /// Finalizes the builder and returns the trie root.
117    ///
118    /// This method is the end-of-stream signal. If fewer than 129 items were pushed, index `0` is
119    /// inserted here because it is the final leaf in RLP key order for that short list.
120    pub fn finalize(mut self) -> B256 {
121        if self.len == 0 {
122            return EMPTY_ROOT_HASH;
123        }
124
125        self.flush_zero();
126        self.hb.root()
127    }
128
129    fn flush_zero(&mut self) {
130        if self.zero.is_none() {
131            return;
132        }
133
134        let zero = self.zero.take().expect("index 0 must be buffered before it is flushed");
135        self.add_leaf(0, &zero);
136    }
137
138    fn add_leaf(&mut self, index: usize, bytes: &[u8]) {
139        let index_buffer = alloy_rlp::encode_fixed_size(&index);
140        self.hb.add_leaf(Nibbles::unpack(&index_buffer), bytes);
141    }
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147    use alloy_trie::root::ordered_trie_root_encoded;
148    use proptest::prelude::*;
149
150    fn item(index: usize) -> Vec<u8> {
151        format!("encoded_item_{index}").into_bytes()
152    }
153
154    fn items(len: usize) -> Vec<Vec<u8>> {
155        (0..len).map(item).collect()
156    }
157
158    fn root_with_push_next(items: &[Vec<u8>]) -> B256 {
159        let mut builder = OrderedTrieRootEncodedBuilder::new();
160        for item in items {
161            builder.push_next(item);
162        }
163        builder.finalize()
164    }
165
166    #[test]
167    fn test_ordered_encoded_builder_equivalence() {
168        for len in [0, 1, 2, 3, 10, 127, 128, 129, 130, 200] {
169            let items: Vec<Vec<u8>> =
170                (0..len).map(|i| format!("item_{i}_data").into_bytes()).collect();
171
172            let expected = ordered_trie_root_encoded(&items);
173
174            let mut builder = OrderedTrieRootEncodedBuilder::new();
175
176            for item in &items {
177                builder.push_next(item);
178            }
179
180            let actual = builder.finalize();
181            assert_eq!(
182                expected, actual,
183                "mismatch for len={len}: expected {expected:?}, got {actual:?}"
184            );
185        }
186    }
187
188    #[test]
189    fn empty_builder_returns_empty_root() {
190        let builder = OrderedTrieRootEncodedBuilder::new();
191        assert!(builder.is_empty());
192        assert_eq!(builder.pushed_count(), 0);
193        assert_eq!(builder.finalize(), EMPTY_ROOT_HASH);
194    }
195
196    #[test]
197    fn test_ordered_builder_count_tracks_pushed_items() {
198        let mut builder = OrderedTrieRootEncodedBuilder::new();
199        assert!(builder.is_empty());
200
201        builder.push_next(b"item_0");
202        assert!(!builder.is_empty());
203        assert_eq!(builder.pushed_count(), 1);
204
205        builder.push_next(b"item_1");
206        assert_eq!(builder.pushed_count(), 2);
207    }
208
209    #[test]
210    fn matches_ordered_root_for_boundary_lengths() {
211        for len in [0, 1, 2, 3, 4, 126, 127, 128, 129, 130, 200, 255, 256, 512] {
212            let items = items(len);
213            let expected = ordered_trie_root_encoded(&items);
214
215            assert_eq!(root_with_push_next(&items), expected, "push_next mismatch for len={len}");
216        }
217    }
218
219    #[test]
220    fn short_lists_flush_zero_on_finalize() {
221        for len in 1..=128 {
222            let items = items(len);
223            let expected = ordered_trie_root_encoded(&items);
224
225            let mut builder = OrderedTrieRootEncodedBuilder::new();
226            for item in &items {
227                builder.push_next(item);
228            }
229
230            assert_eq!(builder.pushed_count(), len);
231            assert_eq!(builder.finalize(), expected, "mismatch for short len={len}");
232        }
233    }
234
235    #[test]
236    fn long_lists_flush_zero_when_index_128_arrives() {
237        let items = items(129);
238        let expected = ordered_trie_root_encoded(&items);
239
240        let mut builder = OrderedTrieRootEncodedBuilder::new();
241        for item in &items {
242            builder.push_next(item);
243        }
244
245        assert_eq!(builder.pushed_count(), 129);
246        assert_eq!(builder.finalize(), expected);
247    }
248
249    proptest! {
250        #[test]
251        fn arbitrary_encoded_items_match_ordered_root(items in proptest::collection::vec(
252            proptest::collection::vec(any::<u8>(), 0..128),
253            0..1024,
254        )) {
255            let expected = ordered_trie_root_encoded(&items);
256
257            prop_assert_eq!(root_with_push_next(&items), expected);
258        }
259    }
260
261    #[cfg(feature = "arbitrary")]
262    mod arbitrary_consensus_roots {
263        use super::*;
264        use alloy_consensus::{
265            proofs::{calculate_receipt_root, calculate_transaction_root},
266            EthereumReceipt, ReceiptWithBloom, Signed, TxLegacy,
267        };
268        use alloy_eips::eip2718::Encodable2718;
269        use alloy_primitives::Signature;
270        use proptest::test_runner::Config;
271        use proptest_arbitrary_interop::arb;
272
273        fn open_ended_2718_root<T: Encodable2718>(items: &[T]) -> B256 {
274            let mut builder = OrderedTrieRootEncodedBuilder::new();
275            let mut buf = Vec::new();
276
277            for item in items {
278                buf.clear();
279                item.encode_2718(&mut buf);
280                builder.push_next(&buf);
281            }
282
283            builder.finalize()
284        }
285
286        proptest! {
287            #![proptest_config(Config::with_cases(32))]
288
289            #[test]
290            fn arbitrary_transactions_match_alloy_consensus_root(
291                transactions in proptest::collection::vec(
292                    (arb::<TxLegacy>(), arb::<Signature>())
293                        .prop_map(|(tx, signature)| Signed::new_unhashed(tx, signature)),
294                    0..1024,
295                ),
296            ) {
297                let expected = calculate_transaction_root(&transactions);
298                let actual = open_ended_2718_root(&transactions);
299
300                prop_assert_eq!(actual, expected);
301            }
302
303            #[test]
304            fn arbitrary_receipts_match_alloy_consensus_root(
305                receipts in proptest::collection::vec(
306                    arb::<ReceiptWithBloom<EthereumReceipt>>(),
307                    0..1024,
308                ),
309            ) {
310                let expected = calculate_receipt_root(&receipts);
311                let actual = open_ended_2718_root(&receipts);
312
313                prop_assert_eq!(actual, expected);
314            }
315        }
316    }
317}
reth_trie_common/ordered_root.rs

reth_trie_common/
ordered_root.rs
