--- id: TIP-1078 title: Lattice State Roots description: Replace Merkle Patricia Trie state roots with Lthash lattice state roots. authors: Alexey Shekhirin (@shekhirin), Sergei Shulepov (@pepyakin) status: Draft related: https://docs.rs/commonware-cryptography/latest/commonware_cryptography/lthash/index.html protocolVersion: TBD --- # TIP-1078: Lattice State Roots ## Abstract This TIP replaces Tempo's Merkle Patricia Trie state root with a flat Lthash lattice state root at T-TBD. The block header `state_root` commits to the post-execution account and storage set by adding one lattice element for each live account and one lattice element for each nonzero storage slot. The lattice hash is the BLAKE3-based `lthash16` construction (2048-byte accumulator, 32-byte BLAKE3 checksum). Lattice elements use hashed account and storage keys: `keccak256(address)` and `keccak256(slot)`. Plain addresses and slots are not part of the consensus element encoding. ## Motivation The MPT state root is expensive to update because small state changes can require trie walking, node hashing, and intermediate node persistence across account and storage tries. Tempo's execution path needs predictable state-root cost at high throughput, and a flat homomorphic accumulator lets nodes update the state commitment by subtracting old elements and adding new elements for the accounts and slots that changed. Lthash is additive, commutative, and incrementally updatable. Those properties let the state root be computed from a set of state elements without depending on trie shape, insertion order, or storage iteration order, while still giving every validator a deterministic consensus root for the same post-state. A plain-key lattice, using unhashed addresses and storage slots directly, is an attractive alternative for a node that stores plain state. It avoids the state-key hashing step, keeps unhashed state directly useful for tooling and debugging, and can be faster on workloads where key hashing is material. However, that design reverts the main Storage V2 optimization that lets Reth avoid storing full plain state. Existing Storage V2 databases cannot enumerate plain addresses and slots from hashed state or trie nodes, so a plain-key lattice would make migration a resync-from-snapshot problem again, or require a new plain-key side index. ## Assumptions - T-TBD activation is configured consistently across all validators. A node with a different T-TBD activation time will compute different header roots and will not stay in consensus. - Nodes can complete a pre-T-TBD shadow build of the lattice accumulator before T-TBD activates. A node that reaches T-TBD without a lattice accumulator for the T-TBD parent is not ready to validate or produce T-TBD blocks in real time. - The implementation pins a reviewed Lthash implementation and treats the 2048-byte accumulator state as derived local state. Consensus depends on the checksum root, not on trusting persisted accumulator bytes. - The lattice set contains at most one account element per live hashed address and at most one storage element per `(hashed_address, hashed_slot)`. Implementations must update by replacing elements, not by accumulating duplicate copies of the same final state element. - The lattice root is not an MPT root. Existing MPT proof semantics do not prove inclusion against a T-TBD+ header `state_root` unless a later TIP defines a compatible proof system. ## Threat Model - Block producers may propose headers with incorrect lattice roots. Validators recompute the lattice root from the executed post-state and reject headers whose `state_root` does not match. - Node databases may have missing, stale, or corrupt persisted lattice accumulator state. Persisted accumulators are treated as caches: nodes must validate their shape before use and rebuild or resume the shadow build from canonical hashed state when needed. - RPC clients, bridges, indexers, and wallets may assume `state_root` is an MPT root. T-TBD changes that interface expectation; consumers must not use Ethereum MPT proof verification against T-TBD+ Tempo headers. - The Lthash primitive is trusted for collision resistance at the chosen security level. Cryptanalytic breaks or implementation bugs in Lthash are in scope for security review but out of scope for runtime mitigation beyond pinning and conformance tests. --- # Specification ## Activation Before T-TBD, `Header.state_root` MUST retain its existing MPT meaning and all pre-T-TBD blocks MUST replay with pre-T-TBD state-root rules. Starting with the first T-TBD block, `Header.state_root` MUST be the lattice root of the block's post-execution state. The parent of the first T-TBD block may still have an MPT `state_root`; that parent root is not reinterpreted. Instead, the node uses the prebuilt lattice accumulator for the canonical T-TBD parent, executes the first T-TBD block, applies the block's state changes to that seed, and compares the resulting lattice root to the T-TBD block header. T-TBD activation MUST NOT require a full current-state scan in the first T-TBD block's validation or production path. Nodes that have not completed the shadow accumulator for the T-TBD parent MUST stop before importing or producing the first T-TBD block until the accumulator is available. If T-TBD is active at genesis, the genesis header `state_root` MUST be the lattice root of the genesis allocation and no MPT genesis root is used for that chain. ## Lattice State Root The lattice state root is the 32-byte checksum of an Lthash accumulator over the canonical post-state element set: ```text acc = Σ expand(element) over every element in the post-state set state_root = checksum(acc) ``` where `expand`, lane-wise accumulation, and `checksum` are defined in [Lthash Construction](#lthash-construction). Each element is the exact byte string defined below. Elements are not RLP, ABI, or SSZ encoded, and no field is length-prefixed. Each element is expanded independently; elements are never concatenated before hashing. The full Lthash accumulator state is 2048 bytes. Nodes SHOULD persist this full accumulator after canonicalizing each T-TBD+ block so the next block can update it incrementally. Persisted accumulator bytes are derived state and MUST NOT override consensus validation: if the persisted accumulator is missing, invalid, or known not to correspond to the selected parent state, the node MUST rebuild it from canonical hashed state before extending that parent. Element order MUST NOT affect the root. Implementations may visit accounts and storage slots in any deterministic or nondeterministic order as long as each final-state element is added exactly once. The lattice root of an empty element set is the checksum of the identity accumulator (Test Vector 1). It can occur only for a chain whose post-state contains no live accounts. ## Lthash Construction The lattice hash is the `lthash16` construction from "Securing Update Propagation with Homomorphic Hashing" instantiated over BLAKE3. This is the parameterization implemented by the `commonware-cryptography` `lthash` module. - **State.** The accumulator is 2048 bytes, interpreted as 1024 unsigned 16-bit lanes in little-endian byte order. The identity accumulator is all zeros. - **Element expansion.** `expand(e) = BLAKE3-XOF(e, 2048)`: the element byte string is hashed with BLAKE3 in extendable-output mode and the first 2048 output bytes are the element's lattice point. - **Addition and subtraction.** `add` and `subtract` combine a lattice point into the accumulator lane-wise with wrapping (mod 2^16) addition or subtraction. - **Checksum.** `checksum(acc) = BLAKE3-256(acc)`: the 32-byte BLAKE3 hash of the accumulator with lanes serialized little-endian. Because lattice points are also produced and serialized little-endian, this is the BLAKE3 hash of the raw 2048 accumulator bytes. Two consequences implementations may rely on: - An accumulator containing exactly one element equals that element's XOF output. - Lane-wise addition of two accumulators equals the accumulator of the union of their element sets, so a full-state build may be partitioned across workers and merged at the end. ## Account Elements For each live account in canonical post-state, add one account element: ```text 0x00 || hashed_address || nonce || balance || code_hash ``` where: - `0x00` is the account domain byte. - `hashed_address` is `keccak256(plain_address)`, encoded as 32 bytes. - `nonce` is the account nonce encoded as 8-byte big-endian unsigned integer. - `balance` is the account balance encoded as 32-byte big-endian unsigned integer. - `code_hash` is the account bytecode hash, or `KECCAK_EMPTY` for an account with no code. An account element is always 105 bytes. Account liveness follows the existing EVM state rules. Creating an account adds its account element keyed by the hashed address, changing nonce, balance, or code hash replaces its account element, and deleting an account removes its account element. ## Storage Elements For each nonzero storage slot in canonical post-state, add one storage element: ```text 0x01 || hashed_address || hashed_slot || value ``` where: - `0x01` is the storage domain byte. - `hashed_address` is `keccak256(plain_address)`, encoded as 32 bytes. - `hashed_slot` is `keccak256(plain_slot)`, encoded as 32 bytes. - `value` is the storage value encoded as 32-byte big-endian unsigned integer. A storage element is always 97 bytes. Zero-valued storage slots MUST be absent from the lattice set. Setting a slot from zero to nonzero adds its storage element, changing a nonzero slot replaces its storage element, and setting a nonzero slot to zero removes its storage element. Account deletion or selfdestruct removes all nonzero storage elements for that account before any post-deletion storage effects required by the active EVM rules are applied. ## Migration T-TBD does not perform a contract-visible state migration. Account balances, nonces, code hashes, storage slots, receipts, logs, and transaction execution semantics are unchanged at the activation boundary. Only the header state commitment changes. For an existing pre-T-TBD chain, nodes MUST shadow-build the lattice accumulator before T-TBD activates. The shadow accumulator is derived local state while MPT remains the consensus state-root mechanism. The shadow-build process is: 1. Choose a canonical pre-T-TBD base state early enough that the full scan can complete before activation. 2. Read every live account from canonical hashed account state at that base state and add its account element using the account encoding above. 3. Read every nonzero storage slot from canonical hashed storage state at that base state and add its storage element using the storage encoding above. 4. Persist the resulting 2048-byte accumulator and the block hash/number of the base state it represents. 5. Apply every canonical state transition after the base state to the shadow accumulator, subtracting old elements and adding new elements for changed accounts and storage slots, until the accumulator represents the canonical head. 6. Continue updating the shadow accumulator for each imported pre-T-TBD block so that, at the T-TBD parent, the accumulator is already available as the T-TBD seed. Pre-T7 headers are not changed and do not commit to the shadow accumulator. A shadow accumulator mismatch before T7 is an implementation readiness failure, not a pre-T7 consensus failure. The node MUST repair it by replaying missed state transitions or rebuilding from canonical hashed state before it validates or produces T7 blocks. At the first T7 block, the prepared T7 parent accumulator becomes the consensus seed. The node executes the first T7 block, updates the seed with that block's account and storage changes, and requires the resulting checksum to equal the block header `state_root`. At the first T-TBD block, the prepared T-TBD parent accumulator becomes the consensus seed. The node executes the first T-TBD block, updates the seed with that block's account and storage changes, and requires the resulting checksum to equal the block header `state_root`. The network SHOULD schedule T-TBD only after operators have enough lead time to complete the shadow build and observe the accumulator staying current through normal block import. A validator that is not T-TBD-ready at activation may continue catching up locally, but MUST NOT vote for, produce, or mark valid a T-TBD block until it has the correct parent accumulator. Historical pre-T-TBD MPT trie data may be retained for archive/debug purposes, but it is no longer the consensus state-root path for T-TBD+ blocks. For post-T-TBD restart, checkpoint sync, or snap sync, a node MUST not trust an unverified downloaded accumulator as a consensus input. It MUST either rebuild the accumulator from canonical hashed state for the checkpoint/tip being extended, or obtain it through a checkpoint mechanism whose trust assumptions are explicitly outside this TIP. If a reorg or unwind leaves the persisted accumulator out of sync with canonical hashed state, the node MUST rebuild the accumulator before importing the next T-TBD+ child. ## Validation and Block Production Validators MUST recompute the T-TBD+ lattice root from block execution output and reject the block if the computed root differs from the header `state_root`. Block producers MUST place the post-execution lattice root in the header. They MAY compute it by streaming per-transaction state changes into a background lattice accumulator, by applying the final bundle state to a parent accumulator, or by rebuilding from post-state. These paths are equivalent only if they produce the same element set and root. Implementations MUST be able to rebuild the lattice accumulator from canonical hashed state. Rebuild is the reference recovery path for persisted accumulator corruption and missed incremental updates, but it is not expected to run in the first T7 block's real-time validation path. # Benchmark Results Indicative figures from single-threaded microbenchmarks of the pinned Lthash implementation on commodity server hardware. They justify the design; they are not normative. - Adding or subtracting one element costs on the order of a microsecond, dominated by the fixed cost of the BLAKE3 XOF expansion. Element size is immaterial at 97–105 bytes, and subtraction costs the same as addition. - A full update cycle — subtract the old element, add the new one — is about two microseconds with prehashed keys, slightly more when the key still needs hashing. - Per-block fixed costs are negligible: computing the 32-byte checksum and persisting the 2048-byte accumulator are single-digit microseconds each, paid once per block. - A large block changing tens of thousands of accounts and roughly a hundred thousand storage slots needs on the order of a quarter second of lattice work on one core with prehashed keys. Key hashing is already paid today for hashed-state writes, so that is the marginal cost. Because the accumulator is additive, the work shards across cores and merges with a single lane-wise addition, bringing it to tens of milliseconds on typical validator hardware. - Lattice cost is flat: it depends only on the number of changed elements, not on total state size, trie depth, or access pattern. This is the property the MPT path cannot offer, where update cost varies with trie shape and intermediate node churn.