# Exploring Partial State Updates

Date: 2025-04-18
By: Unnawut

## TLDR

-

## Details

It started with this suggestion by Justin after our primitive zkSTF benchmarks showed that committing to the beacon state requires 200M cycles.

> Loading the full state is suboptimal. State reads and write are better to be done statelessly.
>
> First load the state root. Then:
>
> * for reads: load the Merkle path from the leaf being read and authenticate the Merkle path to the state root
> * for writes: first read, then update the value, then remerkleise the Merkle path to get a new state root
>
> Some SSZ libraries should have all this implemented.

To expand on above, while it may seem straightforward that we can just pick an SSZ library and a Merkleization library that supports partial reads and updates, in fact, we need to keep in mind that there we are dealing with 2 environments:

1. **The host environment** - This is the runtime that manages the zkVM and the data that goes in and out of it. It is not part of the zkVM, and thus is an untrusted environment. The host is able to pass in any arbitrary data into the guest environment.
2. **The guest environment** - Basically the zkVM runtime. Whatever gets run here is part of the snarkification.

Because the input data provided by the host is untrusted, the guest must have a way to authenticate such data. For instance, the guest must have pre-determined a trusted root and requires the host to provide an inclusion proof along with the host's input. The guest can then use the provided inclusion proof to authenticate input against its trusted state root.

We also need to be aware that there are 3 phases involved with state merkleization:

1. Data structure
2. SSZ serialization
3. Merkleization

Data structure -> SSZ-serialized data -> Merkle leaves & root

E.g. for a simple STF like `process_block_header()`, the responsibilites are:

1. **Host environment**
- Maintains the full and persistent consensus state across slots and epochs
- Initializes the guest with a trusted state root
- Passes the required partial-state to the guest along with the inclusion proof
- Receives from the guest the updated partial-state and the guest's re-computed merkle root
- Applies the partial-state back to its persistent state, re-computes the merkle root and checks that the root matches the guest's returned root
2. **Guest environment**
- Initializes with a trusted state root (provided by the host)
- Receives from the host the partial-state, its inclusion proof and the inputs to be processed
- Authenticates that the partial-state is part of the state root
- Processes the transition function
- Recomputes the state root with the updated partial-state
- Returns to the host the updated partial-state and the new state root

This means that we need different SSZ & Merkleization functionalities for the host and guest:

1. **Host environment**
- The host must be able to provide a partial state and its inclusion proof
- Recompute the state root based on the updated partial-state (Good to have. The host could recompute from the entire state albeit less efficiently)
2. **Guest environment**
- The guest must be able to authenticate the partial-state against the state root
- The guest must be able to update the partial-state and re-compute the state root (without having the full state in view)

## Illustration


## Existing libraries

Operation | [ethereum_ssz](https://crates.io/crates/ethereum_ssz) | [grandine's ssz](https://github.com/grandinetech/grandine/tree/develop/ssz) | [ssz_rs](https://crates.io/crates/ssz_rs) | [tree_hash](https://crates.io/crates/tree_hash) | [merkle_light](https://crates.io/crates/merkle_light) | [milhouse](https://crates.io/crates/milhouse) |
----------|--------------|----------------|-------|-|-|-
Read partial data | ✅ | ✅ | ❌ | Not Applicable | Not Applicable
Write partial data | ❌ | ✅ | ❌ | Not Applicable | Not Applicable
Provide inclusion proof | Not Applicable | ✅ | ✅ | ❌ | ✅
Authenticate a leaf | Not Applicable | ✅ | ✅ | ❌ | ✅
Re-compute root on a leaf mutation | Not Applicable | ✅ | Not Applicable | ❌ | ❌
*Remarks* | | Internal crate | | | |

## Understanding SSZ in general

- https://ethereum.github.io/consensus-specs/ssz/simple-serialize/
- https://www.ssz.dev/altwalk
- https://eth2book.info/capella/part2/building_blocks/ssz/
- https://www.ssz.dev/

## What is SSZ partial?

Protolambda's answer to [What is an SSZ partial? on StackExchange](https://ethereum.stackexchange.com/questions/74026/what-is-an-ssz-partial):

> The idea of a SSZ partial is that any SSZ type (see SSZ spec what SSZ is) is just used to provide a typed "view": you have type information for everything that could be there, but you may only need partial access to the actual value.
>
> For small pieces of data it is more common to just represent it as the abstracted data-type in whatever programming language you are using to interact with the value. And then it only gets converted to a binary tree last-minute during merkleization of the value.
>
> For large pieces of data, like the BeaconState type, Eth2 beacon clients started caching parts of this tree, or fully represent it as tree. The intention here is to use a persistent-tree (the functional programming concept) to share subtrees that do not change between different states.
>
> When you only need a small subset of a large piece of data, you can leave out the parts of the tree you do not need, while still being able to use it the same otherwise, this is why it is called a "partial".
>
> Additionally, with your partial data you can keep the root node of irrelevant subtrees you prune away (called "helper" or "sibling" node). Then you are left with the part of the tree you do want to read, and the helper nodes that allow you to construct a merkle proof for the data you are interested in.

## A working library in Rust

https://github.com/grandinetech/grandine/tree/develop/ssz

## Lighthouse's tree-states ELI5 & Milhouse

[ghiliweld](https://x.com/ghiliweld) also mentioned https://lighthouse-blog.sigmaprime.io/tree-states-part1.html

## Notable work

- https://github.com/ethereum/consensus-specs/pull/1184
- https://github.com/ethereum/consensus-specs/pull/1261
- https://github.com/ethereum/consensus-specs/issues/1303
- https://github.com/protolambda/eth-merkle-trees/blob/master/typing_partials.md
- https://github.com/protolambda/remerkleable
- https://github.com/protolambda/ztyp
- https://github.com/prysmaticlabs/hashtree

## Next