--- id: TIP-1082 title: Provable Contract Trie description: A second, sparse Merkle Patricia Trie state root that commits only to a hardfork-governed whitelist of accounts, preserving Merkle proofs for Zone-facing state after the global MPT is replaced by a lattice state root. authors: Arsenii Kulikov (@klkvr), Roman Krasiuk (@rkrasiuk) status: Draft related: TIP-1078 (Lattice State Roots) protocolVersion: TBD --- # TIP-1082: Provable Contract Trie ## Abstract This TIP adds a second state commitment to the block header, `proof_root`, computed as a standard Ethereum-style Merkle Patricia Trie over a small, protocol-selected subset of L1 state. It is a companion to TIP-1078, which makes `state_root = LtHash(full L1 state)` the canonical execution commitment and removes the global MPT. This TIP assumes TIP-1078 is already active at its activation hardfork. `state_root` keeps execution commitment fast and incremental; `proof_root` preserves Merkle proofs, but only for accounts on a hardcoded, hardfork-governed whitelist. At the activation hardfork, a bounded set of existing protocol-owned contracts is migrated into the trie, building their sparse storage tries from canonical pre-activation state via a background build completed before the fork. Accounts added at later hardforks are usually new and empty and need no build; an account with pre-existing state MAY still be added by rebuilding its storage trie in the background ahead of the fork and inserting it at the transition. ## Motivation TIP-1078 replaces the global MPT with an additive lattice hash. LtHash gives a full-state commitment that updates per write without sorting or recomputing a global tree, which is the property we need at target throughput. What it does not give us is Merkle proofs: there is no efficient way to prove that a specific account or storage slot has a specific value against an LtHash commitment. We still need proofs for one concrete use case: mirroring a bounded set of L1 state into Zones. A Zone (or a bridge) must be able to verify "this key has this value on L1" against a commitment in the L1 header. Today that is served by the global MPT — exactly the structure TIP-1078 removes for performance reasons. The observation that makes this tractable is that the state Zones need is small, protocol-owned, and known ahead of time: precompile state such as `AccountKeychain` and TIP-403 policy state, plus Zone inbox/outbox and bridge precompile state introduced later. The vast majority of L1 state — TIP-20 balances, DEX order books, general contract storage — never needs to be proven and should not pay for trie maintenance. We therefore maintain a normal MPT, but only over a whitelist. The trie is sparse, cheap to maintain, and structurally identical to the one we compute today — it is the current state-root calculation filtered down to the whitelisted accounts. This TIP assumes TIP-1078 is already active. At the activation hardfork we perform a **migration**: a bounded set of existing, protocol-owned contracts is read from canonical pre-activation state and built into the sparse trie, so their current state is provable from the first post-activation block. Each member's account object and full storage trie are built in the background ahead of the activation fork — the per-contract storage seek discussed during design — and committed at the transition block. This is acceptable only because the migration set is small and bounded. Accounts added to the whitelist at later hardforks are typically new contracts or precompiles introduced at that same fork, so they are empty at insertion and require no background build: adding them is a single-step hardfork change. The protocol does not, however, rule out adding an account with pre-existing state at a later fork; doing so simply requires rebuilding that account's storage trie in the background ahead of the fork (as at the initial migration) and inserting it at the transition. To make facts about already-existing state provable without importing it, the protocol MAY instead introduce a new empty mirror/inbox/outbox precompile at a hardfork and write the facts into it from activation onward — the same pattern it would use to expose bridging facts without paying to represent all of TIP-20 storage. This is a prerequisite-dependent change: it assumes TIP-1078 is active at the activation hardfork. It is specified independently of TIP-1078 and adds a new commitment rather than modifying `state_root`. ## Assumptions - **TIP-1078 is active at the activation hardfork.** `state_root` is the LtHash of full L1 state and the global MPT is no longer maintained. If this TIP activated without TIP-1078 active, both a global MPT and the sparse MPT would be maintained, defeating the performance goal. - **Migration is deterministic and bounded.** Every node builds the migration trie from identical canonical pre-activation state. If two nodes derive different migrated tries, they compute different `proof_root` values at activation and fork. If a migration-set member's storage is too large, migration build time and ongoing maintenance become unacceptable. - **Every later addition is bounded and agreed.** A later addition is either empty at the block that adds it (a new contract/precompile, requiring no build) or an account whose pre-existing storage was rebuilt in the background before the fork and is of bounded size. A node that derived different state for an added account than its peers would diverge; implementations MUST agree byte-for-byte on any imported state. - **`proof_root` is non-executing.** It never affects state transition or `state_root`. An implementation that let `proof_root` influence execution would diverge from spec and from other nodes. - **Whitelist members are bounded, protocol-owned contracts.** A mirror/precompile that records facts without cleanup (the analogue of the AccountKeychain growth concern, TIP-1073) can grow unbounded, defeating the requirement that provable accounts stay small. - **Header encoding uses the trailing fork-activated optional pattern** established by TIP-1031, so pre-activation header hashes are preserved. ## Threat Model - **Block producers** may propose headers with incorrect `proof_root`. Validators recompute the `proof_root` from the executed post-state and reject headers whose `proof_root` does not match. - **Node operators at the activation fork** must complete the migration build before the activation timestamp. A node that has not built the migration trie, or builds it from non-canonical state, cannot produce or validate the first post-activation `proof_root` and falls out of sync — the same failure mode as not being ready with the TIP-1078 commitment at its fork. This divergence risk is confined to migration builds; empty additions require no build. - **Users writing to provable precompile storage** can encode chosen data into a whitelisted precompile's user-writable state — for example, arbitrary bytes packed into TIP-403 policy state — to make that data provable against `proof_root`. This abuse is in scope and accepted: demand is expected to be low, consequences are bounded, and it does not reintroduce a global trie. - **Storage-explosion DoS** against a whitelisted account (adversarial or accidental growth) is in scope; mitigated by restricting the whitelist to bounded protocol-owned contracts. - **Proof consumers (Zones, bridges, external verifiers)** are untrusted and verify standard MPT proofs against `proof_root`; soundness rests only on the header commitment. - Out of scope: proving arbitrary or non-whitelisted L1 state (TIP-20 balances, general contract storage); generic L1 light clients. --- # Specification This section assumes TIP-1078 is active. `proof_root` is defined and maintained independently of `state_root`. ## Header field When activated, a new field `proof_root` is appended to `TempoHeader`, following the trailing fork-activated field pattern of TIP-1031. It is encoded as `Option`: - For pre-activation headers the field is `None` and MUST be omitted entirely from the RLP stream, preserving existing block hashes. - From the activation block onward the field MUST be `Some` and set to the root of the Provable Contract Trie defined below. ```rust // Appended after any prior trailing fork-activated fields (e.g. TIP-1031 `Context`). // `None` pre-activation; `Some(root)` from the activation block onward. pub proof_root: Option, ``` `proof_root` is consensus-critical: because it is in the header, it is transitively committed to by any notarization or finalization certificate over the block digest. ## The Provable Contract Trie `proof_root` commits to a standard Ethereum-style secure Merkle Patricia Trie, identical in format and semantics to the pre-TIP-1078 global state trie, restricted so that only accounts in the active whitelist `PROVABLE_ACCOUNTS` are inserted. - The account trie is keyed by `keccak256(address)`; each leaf is the RLP-encoded account object `RLP([nonce, balance, storageRoot, codeHash])`. - Each provable account's `storageRoot` is the root of its storage trie, keyed by `keccak256(slot)`, with leaves `RLP(value)`, exactly as today. - Accounts not in `PROVABLE_ACCOUNTS` are absent. The trie contains no placeholder leaves for them. - If `PROVABLE_ACCOUNTS` is empty, `proof_root` is the canonical empty-trie root `keccak256(RLP(""))`. The keyspace is intentionally identical to the legacy EVM state layout rather than a custom namespace, so proof verification on the consumer side is indistinguishable from verifying a standard Ethereum account/storage proof. ## Whitelist `PROVABLE_ACCOUNTS` is a hardcoded set of account addresses and a hardfork parameter. It is not user-settable; an account becomes provable only through a network upgrade. - Membership is keyed by **address**. The full account object (nonce, balance, codeHash, storageRoot) is included so standard account proofs work unchanged. - The **initial set, activated at the activation hardfork**, consists of existing protocol-owned contracts with non-empty state — initially the `AccountKeychain` precompile and the TIP-403 policy precompile. These members are populated by the migration below. Additional precompiles MAY be added to the initial set before the fork is finalized. - **An account added after activation is usually empty at the block that adds it** — in practice a new contract or precompile introduced at that same hardfork — and is inserted as its empty account object. An account with pre-existing state MAY also be added; in that case its storage trie MUST be rebuilt in the background ahead of the fork and committed at the activating block, exactly as at the initial migration. Implementations MUST agree byte-for-byte on any imported state. - Members SHOULD be bounded, protocol-owned precompiles. User contracts MUST NOT be members. Address-keying is chosen for simplicity. Its consequence — that a future code change at a whitelisted address keeps that address provable — is acceptable because every member is a protocol-owned precompile. If finer control is later required, membership MAY be tightened to `(address, codeHash)`. ## Migration At the activation hardfork, `proof_root` is introduced and the initial `PROVABLE_ACCOUNTS` set is migrated into the trie. The same procedure applies to any later addition of an account with pre-existing state. **Snapshot point.** The migration is computed over canonical L1 state as of the activation parent block (the last pre-activation block's post-execution state). For each member, nodes build its account object and full storage trie from that state. **Node readiness.** This change is gated behind its activation hardfork and assumes TIP-1078 is already active. Node operators MUST upgrade before the activation timestamp; un-upgraded nodes will fall out of sync at activation. Ahead of the activation block, every node MUST build the Provable Contract Trie over the migration set from its canonical state as of the activation parent block, and MUST have the resulting trie persisted and ready before it produces or validates the first block at or after the activation timestamp. A node that has not completed the migration build by the activation block cannot produce or validate that block's `proof_root` and will fall out of sync, identically to the full-state commitment TIP-1078 requires at its fork. **Determinism.** All nodes MUST derive byte-identical migrated tries. The migration MUST reproduce exact account/storage semantics from canonical state, including absent vs. zeroed storage slots, account incarnation/recreate history, and `nonce`/`balance`/`codeHash`. A member whose storage is too large to build within the readiness window MUST NOT be included in the migration set. **Resulting root.** The `proof_root` of the activation block equals the migrated trie (as of the activation parent state) updated by that block's writes to migration-set members. From activation onward the trie is maintained incrementally per [Block production](#block-production-and-the-state-root-task). ## Block production and the state-root task From activation, proposers maintain `proof_root` as a filtered side-output of the existing state-commitment task: 1. Execution writes full L1 state as normal. Every account/storage write feeds the LtHash task that produces `state_root` (TIP-1078). 2. After execution, the same writes are filtered to those touching members of the active `PROVABLE_ACCOUNTS`. 3. Filtered writes — and only those — update the sparse MPT. Untouched provable state carries forward unchanged. 4. The proposer MUST set `header.proof_root` to the resulting root. Maintaining the trie is therefore the current state-root computation restricted to the whitelist. Accounts outside the whitelist never enter the trie regardless of how heavily they are written. ## Block verification 1. For pre-activation blocks, `proof_root` MUST be `None`. 2. From activation, `proof_root` MUST be `Some` and MUST equal the root recomputed by the verifier over the active whitelist after applying the block's writes (the activation block is verified against the migrated trie per [Migration](#migration)). 3. Verification otherwise proceeds as-is. A mismatch is a hard validity failure; the block MUST be rejected. ## Adding a provable account after activation Adding an account to `PROVABLE_ACCOUNTS` at a hardfork after the initial activation is gated behind that fork. Let `A` be the activating block. - **Empty account (common case).** If the account is empty at `A` — in practice a new contract/precompile created at the fork that activates at `A` — it is inserted into the trie as its empty account object. Because there is no pre-existing storage, there is nothing to import or backfill, no snapshot, and no readiness window beyond the ordinary fork upgrade. From `A` onward, writes to the account update the sparse MPT and proofs against it are valid immediately. - **Pre-existing-state account.** If the account has pre-existing storage at `A`, its account object and full storage trie MUST be rebuilt in the background from canonical pre-`A` state and committed at `A`, following [Migration](#migration). The same determinism and readiness requirements apply. - Adding an account MUST NOT alter any `proof_root` for a block before `A`; historical roots are fixed by the whitelist active at the time. To make facts about already-existing state provable without importing it, the protocol MAY instead introduce a new empty mirror/inbox/outbox precompile at a hardfork and write the relevant facts into it from activation onward. ## Proofs A consumer (a Zone, a bridge, an external verifier) proves an L1 fact by: 1. Obtaining the block header and its `proof_root`. 2. Verifying a standard MPT inclusion or absence proof for `(address, slot)` against `proof_root`. Absence proofs are first-class. The protocol MUST define exact, distinguishable semantics for: - **not whitelisted** — the address is not in `PROVABLE_ACCOUNTS`; nothing can be proven about it. - **whitelisted but empty** — the account is in the whitelist but has no state. - **storage key absent** — the slot was never written. - **storage key set to zero** — the slot was explicitly zeroed. These four cases MUST NOT be conflated, because bridge-style state machines rely on "this key is unset" being provable and unambiguous. ## Edge cases 1. **Migration determinism**: every node MUST derive identical migrated tries from canonical activation-parent state, including absent vs. zeroed slots, incarnation/recreate, and account fields. Divergence forks the node at activation. 2. **Migration bound**: an oversized migration-set member MUST be excluded; oversized members make the migration build miss the readiness window. 3. **Later-addition state agreement**: at any post-activation addition `A`, nodes MUST confirm an empty addition has zero storage, and MUST agree byte-for-byte on the imported storage of a pre-existing-state addition; a node that derives different state diverges. 4. **Reorgs**: trie state MUST roll back correctly across ordinary reorgs, including a reorg spanning the activation boundary (the migrated members revert to absent before activation) or a post-activation addition block. 5. **Redeploy / destruct**: because membership is address-keyed, the behavior when a whitelisted address self-destructs or is redeployed MUST be explicit. Members are protocol-owned precompiles, so this is constrained. 6. **Storage explosion**: a whitelisted account whose storage grows unexpectedly makes maintenance expensive; keep whitelist members bounded. A migrated precompile that keeps growing without cleanup is the live concern (cf. TIP-1073 for keychain cleanup). 7. **Partial inclusion**: proving only some storage keys of an otherwise-normal contract is not supported. Prefer mirror precompiles that write exactly the facts to be proven. 8. **Proof serving / retention**: nodes serving historical proofs MUST retain trie data for the requested range, or the header root exists but proofs are unavailable. 9. **Whitelist versioning**: proof consumers MUST know which whitelist applies to a given block, or they may verify against the wrong logical keyspace. --- # Tooling - **Header**: `proof_root` is exposed in block/header responses. SDKs and header types add the trailing optional field; encoders/decoders MUST follow the omit-when-`None` rule so pre-activation header hashes are unchanged. - **Migration command**: operators need a command to build and persist the Provable Contract Trie over the migration set from canonical activation-parent state, report progress, and emit the resulting root for cross-checking against the expected activation root before the fork (the proof-trie analogue of the TIP-1078 commitment build). - **Proof RPC**: an `eth_getProof`-style endpoint MUST verify against `proof_root` and succeed only for whitelisted accounts. Responses MUST surface the four-way absence distinction (not whitelisted / whitelisted but empty / storage key absent / storage key set to zero). The endpoint MUST indicate, or let the caller determine, the whitelist version applicable to the queried block. - **Zone / bridge verifiers**: proof-verification libraries MUST reference `proof_root`, not `state_root` (which is now an LtHash and not Merkle-provable), and MUST be whitelist-version aware. - **Test fixtures**: header fixtures with `proof_root: Some(..)` and `proof_root: None`; a migration fixture asserting a golden `proof_root` built from a canonical pre-activation state snapshot; a post-activation fixture adding a new empty account at `A` and asserting the root immediately before and after `A`. - **Recovery/debug**: a way to inspect and recompute the sparse trie for a given block and whitelist version to diagnose a `proof_root` mismatch. # Observability These are node-level metrics and alerts (not on-chain events); each MUST be emitted with the listed fields. - `proof_trie_migration_progress` (member address, slots imported, complete bool, ready-before-activation bool) — answers: will this node finish the migration build before the activation timestamp? - `proof_root_activation_agreement` (activation block, local root, expected/peer root, match bool) — answers: did all nodes derive the same migrated `proof_root` at activation? A mismatch MUST alert as a fork or a non-canonical migration build. - `proof_root_update_duration` (block number, slots touched, duration) — answers: is sparse-trie maintenance negligible relative to execution under target TPS? - `provable_account_trie_size` (address, slot count) — answers: is any whitelisted account growing unexpectedly large? If a deployment determines existing block/state telemetry already covers a given signal, it MAY map these onto existing metrics rather than adding new ones. # Invariants 1. **Independence**: `proof_root` is computed independently of `state_root`; `state_root` remains `LtHash(full state)` and `proof_root` never affects execution. 2. **Sparsity**: only members of the active `PROVABLE_ACCOUNTS` appear in the trie; no write to a non-whitelisted account can change `proof_root`. 3. **Bounded migration**: non-empty accounts enter the trie only via a background migration build — at the activation hardfork for the initial set, and again for any later addition of a pre-existing-state account; an empty addition imports nothing. 4. **Migration determinism**: at the activation block, every upgraded node derives the same migrated `proof_root` from identical canonical activation-parent state. 5. **Historical immutability**: for any block `N`, `proof_root` at `N` is fixed by the whitelist active at `N`; later whitelist changes MUST NOT alter it. 6. **Encoding backward compatibility**: `proof_root` is a trailing fork-activated field; for pre-activation headers it MUST be omitted from RLP so their hashes are unchanged. 7. **Commitment**: `proof_root` is transitively committed to by any certificate over the block digest. 8. **Proof soundness**: a valid inclusion/absence proof against `header.proof_root` reflects the exact L1 state of the whitelisted account at that block. **Critical cases the test suite MUST cover:** - RLP round-trip for `TempoHeader` with `proof_root: Some(..)` and `proof_root: None`, and that a pre-activation header's hash is unchanged after the upgrade. - Migration: two nodes independently building the migration set from the same canonical activation-parent snapshot derive identical tries (including absent/zeroed slots and recreate history) and agree on the activation `proof_root`; an oversized member is excluded. - `proof_root` equals the empty-trie root when the whitelist is empty. - A write to a non-whitelisted account does not change `proof_root`; a write to a whitelisted account does. - Inclusion and all four absence cases produce verifiable, distinguishable proofs against `proof_root`. - Post-activation addition of a new empty account at `A`: `proof_root` before `A` excludes it and is unchanged from the prior whitelist; after `A` it includes the empty account object, derived without any state import; nodes agree on both roots. - Post-activation addition of an account with pre-existing state at `A`: nodes independently rebuild its storage trie from canonical pre-`A` state, derive identical tries, and agree on the `proof_root` immediately before and after `A`. - A reorg spanning activation reverts migrated members to absent before activation; a reorg spanning a post-activation addition reverts the added account to absent before `A`. - Historical `proof_root` values are unchanged after a later whitelist addition.