Module ordered_root 

Incremental ordered trie root computation. Incremental ordered trie root computation for append-only streams.

Ethereum block transaction and receipt roots are ordered trie roots keyed by the RLP encoding of each item index. OrderedTrieRootEncodedBuilder accepts items in their final contiguous order, without requiring the final item count until the stream ends.

Why this works

RLP-encoded integer keys sort differently around small indices:

• indices 1..=127 encode as single bytes 0x01..=0x7f;
• index 0 encodes as 0x80, so it sorts after 1..=127;
• indices >= 128 encode as longer byte strings and sort after 0.

This means the final insertion order for a dense list is:

len = 0:      []
len = 1:      [0]
2..=128:     [1, 2, ..., len - 1, 0]
>=129:       [1, 2, ..., 127, 0, 128, 129, ...]

While the stream is open, the only ambiguous leaf is index 0: for short lists it is inserted when the stream ends, and for lists with at least 129 items it can be inserted as soon as index 128 arrives. All other leaves can be added as they arrive in append-only order.

Example

use reth_trie_common::ordered_root::OrderedTrieRootEncodedBuilder;

let mut builder = OrderedTrieRootEncodedBuilder::new();
builder.push_next(b"encoded_item_0");
builder.push_next(b"encoded_item_1");

let root = builder.finalize();

Structs

OrderedTrieRootEncodedBuilder

A builder for computing ordered trie roots from an append-only stream of pre-encoded items.