ERC-8147: Locality-Preserving Layout for Binary Trie

Abstract

This ERC defines a storage layout convention for Solidity and other EVM languages that preserves data locality in binary trie. By deriving mapping slots as (hash(key) & ~0xFF) | base_slot, all mappings for the same key are co-located within a single 256-slot trie page. This reduces branch openings and witness sizes when accessing multiple values associated with the same key.

Motivation

The Binary Trie organizes contract storage into 256-slot pages sharing a common 31-byte stem. Slots 0–255 share one stem, slots 256–511 share another, and so on. Accessing multiple slots within the same stem requires only one branch opening, while accessing slots across different stems requires multiple branch openings.

Current Solidity mapping slot derivation uses:

slot = hash(key || base_slot)

This produces pseudorandom slot numbers, scattering logically related data across unrelated stems.

Consider a contract with multiple mappings keyed by address:

mapping(address => uint256) public balances;
mapping(address => uint256) public rewardDebt;
mapping(address => uint256) public lastClaimed;

function claim() external {
    uint256 balance = balances[msg.sender];
    uint256 debt = rewardDebt[msg.sender];
    uint256 last = lastClaimed[msg.sender];
    // ...
}

With standard Solidity layout:

Each slot falls in a different trie stem, requiring three branch openings for a single claim() call.

This ERC proposes an alternative derivation that co-locates all mappings for the same key:

All three slots share the same tree_index (slot // 256) and therefore the same stem, reducing three branch openings to one.

Specification

The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 and RFC 8174.

Slot Derivation Formula

For a mapping with base slot b and key k, the storage slot for mapping[k] SHALL be computed as:

slot(k, b) = (hash(k) & ~0xFF) | b

Where:

• hash(k) is the hash of the key
• & ~0xFF clears the least significant byte (bitwise AND with 0xFFFF...FF00)
• | b sets the least significant byte to the base slot (bitwise OR)

Constraints

1. The mapping base slot b MUST be less than 256
2. Contracts using this layout MUST NOT declare more than 256 top-level mappings
3. The key encoding MUST follow the language's standard ABI encoding rules

Interaction with Structs

For mappings to structs:

struct UserData {
    uint256 balance;     // offset 0
    uint256 debt;        // offset 1
    uint256 timestamp;   // offset 2
}
mapping(address => UserData) public users;  // base_slot b

The slot for users[k].field with field offset f SHALL be:

slot(k, b, f) = (hash(k) & ~0xFF) | (b + f)

This requires b + max_field_offset < 256.

NatSpec Annotation

Contracts using this layout SHOULD be annotated with:

/// @custom:storage-layout erc_8147
contract MyContract {
    // ...
}

Compilers and tooling MAY use this annotation to verify correct slot derivation.

Rationale

Why & ~0xFF?

The Binary Trie derives stems as tree_hash(address || tree_index // 256)[:31]. Dividing by 256 is equivalent to right-shifting by 8 bits, discarding the least significant byte.

By zeroing the least significant byte (& ~0xFF) and using it exclusively for the base slot, we ensure all mappings for the same key produce the same slot // 256 value and therefore share a stem.

Why Limit to 256 Mappings?

The least significant byte can hold values 0–255. Exceeding 256 top-level mappings would cause | b to overflow into higher bytes, breaking the locality guarantee.

In practice, contracts rarely exceed 20 top-level mappings, making this limit acceptable.

Backwards Compatibility

This ERC introduces a new storage layout that is incompatible with existing deployed contracts. Contracts compiled with this layout will have different storage slot assignments than contracts compiled with standard Solidity layout.

Migration considerations:

• Upgrading a proxy to an implementation using this layout will cause storage corruption
• This layout should only be used for new deployments or with explicit storage migration logic

Tooling considerations:

• Block explorers and verification tools must be updated to decode storage using this formula
• The NatSpec annotation enables tooling to detect which layout a contract uses

Reference Implementation

TBD

Security Considerations

Hash Collision Attacks

An attacker cannot force storage collisions without finding a hash collision on the first 31 bytes, which requires approximately 2^124 operations (birthday bound on 248 bits). This is computationally infeasible with any standard cryptographic hash function.

Copyright

Copyright and related rights waived via CC0.