SIMD-0215

TL;DR

This proposal adds a new hash, **Accounts Lattice Hash**, that uses homomorphic hashing to maintain a hash of the total account state. The **Accounts Lattice Hash** is both fast to update, and secure, enabling (1) every block to contain the hash of all accounts, instead of only the accounts changed in that block, and (2) removing the **Epoch Accounts Hash**.

Summary

This proposal adds a new hash, **Accounts Lattice Hash**, that uses homomorphic hashing to maintain a hash of the total account state. The **Accounts Lattice Hash** is both fast to update, and secure, enabling (1) every block to contain the hash of all accounts, instead of only the accounts changed in that block, and (2) removing the **Epoch Accounts Hash**.

Motivation

The main goal is to scale Solana to billions accounts, and compute a "hash of all accounts" in practical time and space. Currently there are two main kinds of accounts hashes used in Solana: 1. The **Epoch Accounts Hash**, which is a merkle-based hash of the total account state. 2. The **Accounts Delta Hash**, which is also a merkle-based hash of accounts written in a single block. Both of these hashes have limitations. They calculate the root of a Merkle tree of accounts, sorted by public key, which makes scaling challenging due to the amount of data required. This is also why there are two distinct hashes: the **Epoch Accounts Hash** hashes the every account, but is infrequent; and the **Accounts Delta Hash** is every block, but only contains the subset of accounts written in that block. Ideally every block would contain a hash of the total account state. Homomorphic hashing functions enable computing the hash of the total account state by *incrementally* accumulating the hash of each account. This removes the need to sort and maintain large intermediate state. Said another way, the total account state hash for block `B` can now be computed from block `B - 1`'s total account state hash plus *only* the accounts that changed in block `B`.

Key Changes

• The order in which account lthashes are add/sub is irrelevant.
• If an account is modified by multiple transaction, it is possible to either compute its lthashes before/after each individual transaction or the entire block. The final result is the same.
• Every account modified in a block must be reflected in that block's Accounts Lattice Hash. This applies to both on-chain and off-chain modifications.

Impact

Only validators will be impacted.

Backwards Compatibility

*(Optional)* Incompatible. This changes the bank hash, thus changing consensus.

Security Considerations

LtHash instantiated with BLAKE3 and a 2048-byte output provides the desired 128-bit security [1, Appendix A].