# A Walk Down seismic-trie

We currently maintain a fork [seismic-trie](https://github.com/SeismicSystems/seismic-trie) of alloy-trie. This document has goal to propose and evaluate getting rid of this fork.

Seismic privacy feature is powered by the `FlaggedStorage = (value, is_private): (U256, bool)` replacement for U256 for contract storage slots, where is_private slots are considered shielded and can't be read by `eth_getStorageAt` or `eth_getProof` rpcs, among other things.

The big question is how/where we should encode this `is_private` bool in the trie and database layout.

## TODO

Decisions we still need to:
1. settle on an rlp encoding implementation for FlaggedStorage
2. decide whether to put storage_root helpers in seismic-alloy or keep a minimal alloy-trie fork

## Current Fork Implementation

FlaggedStorage is serialized/encoded differently in the trie and database.

### Trie

Currently the value is tucked/hidden into the LeafNode's encodedPath (but see bug section below):
- Path header uses the (starting from the left) second bit of the first nibble for is_private: 0x0 for public, 0x4 for private


Thus instead of being part of the value, `is_private` is actually treated as trie leaf metadata!! And this is basically the only reason afaiu why we need this fork.

This might have been done originally by someone thinking that this trick was saving 1 byte of storage, but given that the LeafNode is actually not stored in the database, and is really only a temporary in-memory data structure used to compute/update the MPT root, this is actually not the case. This structure is really only created to be keccak256 hashed, and keccak256 ingests 136 bytes at a time, which is way larger than the largest possible LeafNode (header is few bytes, max nibbles path is 32 bytes, value is 32 bytes); so adding an extra is_private byte at the end would not affect MPT updating speed.

One nice feature of this encoding however is that public LeafNodes have the exact same memory layout as upstream ethereum LeafNodes (which simply don't use that 2nd bit). This means we can run the EELS tests without any modifications and get the same state roots. However.. this is currently not true because there's a bug in our code.

#### Inconsistent Encoding Bug

I just realized that we encode `is_private` differently in different codepaths. Our current state root thus doesn't match with that of ethereum [even when we only store public slots](https://github.com/SeismicSystems/seismic-reth/blob/seismic/crates/trie/db/src/state.rs#L315-L319) in certain tests!

Turns out we encode differently in 2 separate code paths:

| Code path | Encodes | Value bytes | Root |
| ------------------------------------------------------- | -------------------------- | ------------------------ | ------------------------------ |
| [seismic-trie::storage_root()](https://github.com/SeismicSystems/seismic-trie/blob/420123bdf0561894c7d8d202ae919283327234ed/src/root.rs#L101) (used in genesis, tests) | `&value.value` (bare U256) | No extra byte | Ethereum-compatible for public |
| [seismic-reth::trie.rs](https://github.com/SeismicSystems/seismic-reth/blob/757b2485300a82361e9adee0b5535dcf8d305677/crates/trie/trie/src/trie.rs#L678)thats (used in block processing) | `&value` (FlaggedStorage) | Always appends bool byte | Never Ethereum-compatible |

  ┌────────────────────────────────────────────┬────────────────────────────────────────┐
  │             Encodes bare U256              │         Encodes FlaggedStorage         │
  ├────────────────────────────────────────────┼────────────────────────────────────────┤
  │ seismic-trie::storage_root() (root.rs:101) │ StorageRoot::calculate() (trie.rs:669) │
  ├────────────────────────────────────────────┼────────────────────────────────────────┤
  │ sparse test (state.rs:1153)                │ sparse engine (sparse_trie.rs:194)     │
  ├────────────────────────────────────────────┼────────────────────────────────────────┤
  │                                            │ proof verify (proofs.rs:776)           │
  ├────────────────────────────────────────────┼────────────────────────────────────────┤
  │                                            │ test_utils (test_utils.rs:28,104,128)  │
  └────────────────────────────────────────────┴────────────────────────────────────────┘

### Database

The database encodes `is_private` completely differently and actually puts it in front of the U256 value.


We could and probably should change this encoding to also use the same encoding that I am proposing below. Probably makes sense to encode both the same actually.

## Proposal

Implementation:
- https://github.com/SeismicSystems/seismic-reth/pull/328
- https://github.com/SeismicSystems/seismic-alloy/pull/80
- https://github.com/SeismicSystems/seismic-alloy-core/pull/58

My main proposal is twofold:
1. Always encode is_private as part of the value. That way we don't need our seismic-trie fork and can just use stock alloy-trie
2. Proposing the below encoding which retains the benefits of having our public-only state roots match those of ethereum

Taking a step back for a second, there are 3 places where `is_private` could be encoded:
- key: this would allow storing both public/private values in the same trie at the same address
- CSTORE/CLOAD and SSTORE/SLOAD would work on completely separate address spaces, which would however be merkleized together as a single trie.
- I personally like this approach a lot because it makes the evm semantics cleaner imo, but its probably too late to make this big change
- leaf metadata: what we currently have
- value: by doing this we can use stock alloy-trie without forking it

### Custom RLP Encoding for FlaggedStorage

If we do this, we have leeway to "rlp" encode FlaggedStorage however we wish. In order to retain compatibility with ethereum's state root, I'm proposing adding a byte with value 1 iif the slot is private. When the slot is public, we only store the U256 encoded value. Note that we could change this to only add a byte for public slots instead if we expect there to be more private than public slots.

impl Encodable for FlaggedStorage {
    fn length(&self) -> usize {
        self.value.length() + if self.is_private { 1 } else { 0 }
    }

    fn encode(&self, out: &mut dyn BufMut) {
        self.value.encode(out);
        if self.is_private {
            true.encode(out);
        }
    }
}

This encoding deviates from the RLP schema, where FlaggedStorage would have to be encoded as a list [U256, bool]. The custom encoding that we have works because RLP encoding of FlaggedStorage is only ever done for MPT leaf nodes, so there is never anything encoded after FlaggedStorage (hence the is_private bool can't be confused with another following value).

If we were ever to use FlaggedStorage as part of a list that neds to be RLP encoded, then we'd probably want to just derive the Encodable macro. Only downside for this is that we lose ethereum state root compatibility...

Claude analysis:

FlaggedStorage is never RLP-encoded as part of a list. Every usage is as a standalone trie leaf value:

  1. seismic-trie storage_root() — encodes as leaf value passed to hb.add_leaf()
  2. seismic-alloy storage_root() — same, encode_fixed_size(&value) as leaf value
  3. seismic-foundry trie_storage() — same pattern
  4. Proof verification (proofs.rs:771) — encode_fixed_size(&FlaggedStorage::new(...)) compared against a leaf
  5. Proof decoding (proofs.rs:488) — FlaggedStorage::decode(&mut &leaf.value[..]) from a leaf

  No struct containing FlaggedStorage derives RlpEncodable. No Vec<FlaggedStorage> is ever RLP-encoded. No encode_list ever touches it.

### Pros/Cons

- pros:
- no fork, which means:
- less burden for developers
- less bug-prone. I noticed that we have revm [specific semantics](https://github.com/SeismicSystems/seismic-revm?tab=readme-ov-file#flagged-storage) for how cstore/cload/sstore/sload interact. This same semantics is not enforced by our trie fork afaiu however, so a bug could creap in and have a public value overwrite a private one... as one example. The current ongoing audits have also found some bugs so far.
- more extensible: if we ever decide to extend our schema and store more metadata per leaf (for eg owner address), the metadata fork approach would require a lot of changes to the trie, whereas storing in value would be a trivial small change of rlp encoding in reth
- exact same state root as ethereum when state trie only contains public values, so we can run EELS tests (however fork also has this benefit if we fix the bug)
- cons (aka pros of fork):
- possibly harder to debug, as for example our trie fork currently has specific errors when is_private value doesn't match expected. I feel like we can likely get the same benefits by having the errors caught when reth rlp encodes FlaggedStorage values and queries the API though. Might be a cleaner separation of concerns too.
- not a concern in either:
- actual number of bytes used. As explained above, the actual amount of bytes taken by the LeafNode is not a concern because it anyways gets padded to 136 bytes before getting keccak256 encoded.

## Benchmark

If my reasoning above is correct, then I wouldn't expect any difference in MPT update computation since keccak256 pads its input to 136 bytes anyways. For completeness ran a single sparse serial trie benchmarks, since that is the one used to update storage tries:
- HashBuilder (build tree from leaves from scratch)
- used for txs + receipts roots
- Sparse Parallel Trie (parallelizes across 16 top-level branches)
- used for account tries
- Sparse Serial Trie
- used for each accounts' storage trie
- (non-sparsse) Parallel Trie
- fallback in case sparse trie fails during validation (start back from scratch as fast as possible)

Ran this on my macbook pro m1 while listening to spotify, so take results with a grain of salt... but TLDR is there doesn't seem to be any performance difference, as expected.

### no fork result

samlaf ~/devel/seismic-workspace/seismic-reth/crates/trie/sparse [feat--no-trie-fork-wip] $ cargo bench -p reth-trie-sparse --bench root -- \
      "repeated/sparse trie/init size 10000 \| update size 1000 \| num updates 10" \
      --save-baseline no-fork --sample-size 100 --warm-up-time 5

Benchmarking calculate root from leaves repeated/sparse trie/init size 10000 | update size 1000 | num updates 10: Collecting 20 samples in estimated 5.2558
calculate root from leaves repeated/sparse trie/init size 10000 | update size 1000 | num updates 10
                        time:   [16.307 ms 16.569 ms 16.825 ms]

and a second benchmark with larger db size, and pinning alloy-trie to =0.9.1 (instead of 0.9.4 which it defaults to atm)

samlaf ~/devel/seismic-workspace/seismic-reth/crates/trie/sparse [feat--no-trie-fork] $ cargo bench -p reth-trie-sparse --bench root -- \           
      "repeated/sparse trie/init size 1000000 \| update size 10000 \| num updates 10" \
      --baseline no-fork --sample-size 100 --warm-up-time 5

Benchmarking calculate root from leaves repeated/sparse trie/init size 1000000 | update size 10000 | n
calculate root from leaves repeated/sparse trie/init size 1000000 | update size 10000 | num updates ... #4
                        time:   [555.96 ms 565.18 ms 577.79 ms]
Found 12 outliers among 100 measurements (12.00%)
  11 (11.00%) high mild
  1 (1.00%) high severe

### seismic branch (fork) result

samlaf ~/devel/seismic-workspace/seismic-reth/crates/trie/sparse [feat--no-trie-fork-wip] $ cargo bench -p reth-trie-sparse --bench root -- \
      "repeated/sparse trie/init size 10000 \| update size 1000 \| num updates 10" \
      --baseline no-fork --sample-size 100 --warm-up-time 5

Benchmarking calculate root from leaves repeated/sparse trie/init size 10000 | update size 1000 | num updates 10: Collecting 20 samples in estimated 5.0522
calculate root from leaves repeated/sparse trie/init size 10000 | update size 1000 | num updates 10
                        time:   [15.867 ms 15.968 ms 16.092 ms]
                        change: [-3.9681% -2.1122% +0.0297%] (p = 0.06 > 0.05)
                        No change in performance detected.
Found 2 outliers among 20 measurements (10.00%)
  2 (10.00%) high severe

samlaf ~/devel/seismic-workspace/seismic-reth/crates/trie/sparse [seismic] $ cargo bench -p reth-trie-sparse --bench root -- \
      "repeated/sparse trie/init size 1000000 \| update size 10000 \| num updates 10" \
      --baseline no-fork --sample-size 100 --warm-up-time 5

Benchmarking calculate root from leaves repeated/sparse trie/init size 1000000 | update size 10000 | num updates ... #4: Collecting 100 samples in estimate
calculate root from leaves repeated/sparse trie/init size 1000000 | update size 10000 | num updates ... #4
                        time:   [553.44 ms 559.25 ms 566.07 ms]
                        change: [-6.9701% -4.7358% -2.6339%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 10 outliers among 100 measurements (10.00%)
  4 (4.00%) high mild
  6 (6.00%) high severe

# Claude audit

For completeness, here's an "audit" done by Claude of my current proposal's implementation. It raised a few good issues, but all of them are solvable, and some probably apply to our current implementation anyways.

1. The FlaggedStorage::decode() buffer-emptiness heuristic is fragile

  fn decode(buf: &mut &[u8]) -> RlpResult<Self> {
      let value = U256::decode(buf)?;
      let is_private = !buf.is_empty();  // ← any trailing byte = private
      Ok(Self { value, is_private })
  }

This only works when the caller passes exactly the leaf value bytes with no trailing data. If FlaggedStorage::decode() is ever called on a buffer that
contains more data after the value (e.g., concatenated RLP items), it will falsely report is_private = true. Currently this is safe because:
- proofs.rs slices exactly: FlaggedStorage::decode(&mut &leaf.value[..])
- encode_fixed_size produces exact-length output

Risk: If anyone adds a new decode site that passes a larger buffer, it silently misreads privacy. There's no validation that the trailing byte is
actually 0x01.

2. No compile-time enforcement that FlaggedStorage encoding is used

The biggest risk: any code path that calls add_leaf(nibbles, encode_fixed_size(&value.value)) (encoding just the U256, not the FlaggedStorage) will
silently produce the wrong root. There's no type-level distinction between "already-encoded FlaggedStorage bytes" and "plain U256 bytes" — both are Vec<u8>.

In the old design, add_leaf took an explicit is_private: bool parameter, so forgetting it was a compile error. Now the privacy info must be baked into
the bytes before calling add_leaf, and the compiler can't check that.

Places to audit: Every call to add_leaf() / update_leaf() / storage_root() that touches storage values. Currently these are correct, but any future code
adding trie leaves must remember to encode FlaggedStorage, not bare U256.

3. Proof verification re-encodes from split fields

  // proofs.rs — StorageProof::verify()
  let expected = Some(encode_fixed_size(&FlaggedStorage::new(self.value, self.is_private)).to_vec());
  verify_proof(root, self.nibbles, expected, &self.proof)

The StorageProof struct carries value: U256 and is_private: bool as separate fields, then re-combines them for verification. If any code path constructs a StorageProof with the wrong is_private value, verification will fail with an opaque error. The old design had is_private extracted directly from the trie leaf node, so it was always consistent. Now the extraction happens in storage_proof() via FlaggedStorage::decode(), which should be correct — but there's a gap between extraction and verification where the fields could be modified independently.

Recommendations

1. Add a wrapper type like EncodedFlaggedStorage(Vec<u8>) for pre-encoded values to get compile-time enforcement that the right encoding was used before
passing to add_leaf()
2. Validate the trailing byte in FlaggedStorage::decode() — assert it's 0x01 if present, not just "non-empty"
3. Add integration tests that specifically verify: encode FlaggedStorage → insert into trie → compute root → generate proof → decode from proof → compare
privacy flag. This replaces the old seismic-trie property tests that explicitly tested privacy roundtrips