---
# System prepended metadata

title: Notes from Designing Partial BeaconState (with Multiproof)
tags: [zkvm]

---

# Notes from Designing Partial BeaconState (with Multiproof)

Date: 2025-05-09
By: Jun Song

---

Few weeks ago, O wrote a well-organized note about the [**Partial State**](https://hackmd.io/anrKevTkRla7nFvqWlLXew), and I've been investigating how we can design the partial state upon existing code. Any feedback is welcome.

# Background

## Merkle Multiproof

![image](https://hackmd.io/_uploads/HywXOVsgex.png)

For illustration, let's assume there are only 8 fields in the `BeaconState`. I intentionally omitted most of the fields and left only a few. (FYI: from Electra, there are a total of **37** fields.) The complex fields like `validators`, `fork` will have their subtree, but for simplicity, I just labeld them as "Root". **Generalized index** is denoted as a blue number that indicates the index of the node in the tree.

Inclusion proof for a single field(or leaf) is quite simple, as you only need to provide:

- State root
- Value of the leaf
- A merkle path to calculate the state root

The **merkle path** is an essence of the proof by reducing the computation to `O(log n)`. 

![image](https://hackmd.io/_uploads/BJT7_Vjxeg.png)

For example, if you want to prove for `slot` (Red-colored node), you need to pass a proof to a verifier like the above diagram. Blue-colored nodes are the merkle path, and they should be sorted by the generalized index in descending order.


Then, what if you want to prove for multiple leaves? Here, **Multiproof** comes into play. Multiproof provides plenty of data for the verifier to verify by computing the state root only once. 

![image](https://hackmd.io/_uploads/H1ZVOVille.png)


Let's take an example: you want to prove for `slot` and `slashings` (again, red-colored node). Instead of passing two independent single proofs, what you have to do is just to construct a multiproof that contains the list of node **with its generalized index**. Unlike the single proof, the generalized indices are mandatory, otherwise the verifier cannot compute the state root.

Every state transition function needs access to or mutation of multiple fields, and this multiproof will significantly reduce the total computation for verification.

## About existing libraries

As O [mentioned](https://hackmd.io/anrKevTkRla7nFvqWlLXew#Existing-libraries), [`ethereum_ssz`](https://github.com/sigp/ethereum_ssz) (which we are currently using) doesn't support the proof generation and verification. So what O did was to convert our `BeaconState` into an [`ssz_rs`](https://github.com/ralexstokes/ssz-rs)-compatiable version. ([Link](https://github.com/ReamLabs/consenzero/blob/866edfcdebef1206880a260dc07c39fc34158689/host/src/main.rs#L21-L32) to the code) Since migrating to a different SSZ library requires further discussion (and also `ssz_rs` is not for production), I wrote some lines of code (but unoptimized) to show how the beacon state can be handled in the context of zkVM. Next sections are mostly dedicated to explaining the design and concept.

---

# Example first.

> You can see the full code at [`consensp1us`](https://github.com/ReamLabs/consensp1us/tree/multiproof) (branch: `multiproof`).

> See [Design & Concept](https://hackmd.io/CC-x4AkxSeulDrfaVE2X6A?stext=8192%3A18%3A1%3A1746776169%3AdWHZZV&both=) if you want to skip the example.

```python
def process_slashings_reset(state: BeaconState) -> None:
    next_epoch = Epoch(get_current_epoch(state) + 1)
    # Reset slashings
    state.slashings[next_epoch % EPOCHS_PER_SLASHINGS_VECTOR] = Gwei(0)
```


I chose a very minimal STF for this example: `process_slashings_reset`. As the spec code indicates, it needs to 1) access `slot` and 2) mutate `slashings` field.

## Host-side

> [`script/src/bin/main.rs`](https://github.com/ReamLabs/consensp1us/blob/multiproof/script/src/bin/main.rs)

The host program is responsible for generating a multiproof to the guest program.

```rust
let mut pre_state: BeaconState = ... // Somehow gets the beacon state.
let root = pre_state.tree_hash_root(); // Calculate the root (will be generated to construct a multiproof).

// Constructs a tree.
let all_leaves = pre_state.merkle_leaves();
let tree = ream_merkle::merkle_tree(&all_leaves, BEACON_STATE_MERKLE_DEPTH).
            .expect("Failed to create merkle tree");

// We only need two fields: ``slot`` and ``slashings``. 
let target_indices = vec![BEACON_STATE_SLOT_INDEX, BEACON_STATE_SLASHINGS_INDEX];
let multiproof =
    ream_merkle::multiproof::Multiproof::generate::<BEACON_STATE_MERKLE_DEPTH>(
        &tree,
        &target_indices,
    )
    .expect("Failed to generate multiproof");

// Construct a builder with ``root``, the values of leaves, and the ``multiproof``.
let builder = PartialBeaconStateBuilder::from_root(root)
    .with_multiproof(multiproof)
    .with_slot(pre_state.slot)
    .with_slashings(&pre_state.slashings);

// Setup the prover client.
let client = ProverClient::from_env();

// Setup the inputs.
let mut stdin = SP1Stdin::new();

// Pass a builder object, so the guest can 
// 1) verify the multiproof and then
// 2) construct a "partial" beacon state with only ``slot`` and ``slashings``.
stdin.write(&builder);

// Execute.
let (output, report) = client.execute(SLASHINGS_RESET_ELF, &stdin).run().unwrap();

// Decode the output
let result: PartialBeaconState = bincode::deserialize(output.as_slice()).unwrap();

// Track "dirty" fields in the program, and only mutate the dirty fields of ``pre_state``.
for &mutated in result.dirty.iter() {
    match mutated {
        SLASHINGS_GENERALIZED_INDEX => {
            pre_state.slashings = result.slashings().unwrap().clone();
        }
        _ => {
            panic!("Unexpected mutated index: {}", mutated);
        }
    }
}

assert_eq!(expected_post.tree_hash_root(), pre_state.tree_hash_root());
```

## Guest-side

> [`program/slashings_reset/src/main.rs`](https://github.com/ReamLabs/consensp1us/blob/multiproof/program/slashings_reset/src/main.rs)

```rust
pub fn main() {
    // Read a builder.
    let builder: PartialBeaconStateBuilder = sp1_zkvm::io::read();

    // ``build()`` will 
    // 1) verify the multiproof
    // 2) verify for each fields
    // 3) build a partial beacon state.
    let mut partial_beacon_state = builder
        .build()
        .expect("Failed to build partial beacon state");

    // Do state transition.
    partial_beacon_state
        .process_slashings_reset()
        .expect("Failed to process slashings reset");
    
    // Commit the result.
    sp1_zkvm::io::commit(&partial_beacon_state);
}

```

## Result

```plaintext
2025-05-09T07:34:14.310213Z  INFO Executing with replay test...
2025-05-09T07:34:14.378363Z  WARN SP1_PROVER environment variable not set, defaulting to 'cpu'    
2025-05-09T07:34:14.844255Z  INFO vk verification: true
2025-05-09T07:34:16.696295Z  INFO execute: clk = 0 pc = 0x2054e8    
2025-05-09T07:34:16.696348Z  INFO execute: ┌╴main
2025-05-09T07:34:16.696359Z  INFO execute: │ ┌╴read-builder
stderr: WARNING: Using insecure random number generator.
2025-05-09T07:34:16.699973Z  INFO execute: │ └╴311,461 cycles
2025-05-09T07:34:16.699983Z  INFO execute: │ ┌╴build-partial-beacon-state
2025-05-09T07:34:16.808629Z  INFO execute: clk = 10000000 pc = 0x216250    
2025-05-09T07:34:16.920810Z  INFO execute: clk = 20000000 pc = 0x21612c    
2025-05-09T07:34:16.942291Z  INFO execute: │ └╴21,589,986 cycles
2025-05-09T07:34:16.942309Z  INFO execute: │ ┌╴process-slashings-reset
2025-05-09T07:34:16.942329Z  INFO execute: │ └╴1,043 cycles
2025-05-09T07:34:16.942336Z  INFO execute: │ ┌╴commit
2025-05-09T07:34:17.004544Z  INFO execute: │ └╴5,666,211 cycles
2025-05-09T07:34:17.004568Z  INFO execute: └╴27,570,631 cycles
2025-05-09T07:34:17.004979Z  INFO execute: close time.busy=311ms time.idle=1.75µs
2025-05-09T07:34:17.004988Z  INFO Program executed successfully.
2025-05-09T07:34:17.048389Z  INFO ----- Cycle Tracker -----
2025-05-09T07:34:17.048401Z  INFO Number of cycles: 27575689
2025-05-09T07:34:17.048403Z  INFO Number of syscall count: 8228
2025-05-09T07:34:17.048404Z  INFO process-slashings-reset: 1043
2025-05-09T07:34:17.048405Z  INFO read-builder: 311461
2025-05-09T07:34:17.048406Z  INFO commit: 5666211
2025-05-09T07:34:17.048407Z  INFO build-partial-beacon-state: 21589986
2025-05-09T07:34:17.048408Z  INFO ----- Cycle Tracker End -----
```

- Interestingly, `build-partial-beacon-state` consumes quite a lot cycles (~ 21M), as it needs to calculate the merkle root with provided multiproof.
    - The past dev note([Link](https://hackmd.io/@reamlabs/By9EzgXi1l)) provides actual numbers for reading the entire beacon state (~ 28M).
- Committing phase doesn't consume lots of cycles, as it only passes the "partial" beacon state.


### Update at 2025.05.19.

```plaintext
2025-05-19T12:33:53.645218Z  INFO Executing with replay test...
2025-05-19T12:33:53.708885Z  WARN SP1_PROVER environment variable not set, defaulting to 'cpu'    
2025-05-19T12:33:54.191675Z  INFO vk verification: true
2025-05-19T12:33:56.110820Z  INFO execute: clk = 0 pc = 0x2054e8    
2025-05-19T12:33:56.110864Z  INFO execute: ┌╴main
2025-05-19T12:33:56.110873Z  INFO execute: │ ┌╴read-builder
stderr: WARNING: Using insecure random number generator.
2025-05-19T12:33:56.114359Z  INFO execute: │ └╴311,461 cycles
2025-05-19T12:33:56.114369Z  INFO execute: │ ┌╴build-partial-beacon-state
2025-05-19T12:33:56.197700Z  INFO execute: │ └╴6,491,781 cycles
2025-05-19T12:33:56.197724Z  INFO execute: │ ┌╴process-slashings-reset
2025-05-19T12:33:56.197744Z  INFO execute: │ └╴1,043 cycles
2025-05-19T12:33:56.197751Z  INFO execute: │ ┌╴commit
2025-05-19T12:33:56.221089Z  INFO execute: │ └╴1,906,083 cycles
2025-05-19T12:33:56.221107Z  INFO execute: └╴8,712,298 cycles
2025-05-19T12:33:56.221488Z  INFO execute: close time.busy=112ms time.idle=1.67µs
2025-05-19T12:33:56.221496Z  INFO Program executed successfully.
2025-05-19T12:33:56.268002Z  INFO ----- Cycle Tracker -----
2025-05-19T12:33:56.268016Z  INFO Number of cycles: 8713684
2025-05-19T12:33:56.268017Z  INFO Number of syscall count: 18502
2025-05-19T12:33:56.268019Z  INFO process-slashings-reset: 1043
2025-05-19T12:33:56.268020Z  INFO read-builder: 311461
2025-05-19T12:33:56.268021Z  INFO commit: 1906083
2025-05-19T12:33:56.268022Z  INFO build-partial-beacon-state: 6491781
2025-05-19T12:33:56.268023Z  INFO ----- Cycle Tracker End -----
```

Using [`sha2` precompile](https://docs.succinct.xyz/docs/sp1/optimizing-programs/precompiles) from SP1 significantly reduces the cycle count.


---

# Design & Concept

> Full diff: https://github.com/syjn99/ream/pull/1

## `PartialBeaconState`

```rust
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct PartialBeaconState {
    // BeaconState fields
    pub slot: Option<u64>,
    pub slashings: Option<FixedVector<u64, U8192>>,
    // and other fields...

    // dirty fields with generalized indices
    pub dirty: Vec<u64>,
}
```

- This will **only** contain necessary fields for the corresponding state transition function, while other fields are just `None`.
    - It's a similar concept for the [`Partial<T>` utility type](https://www.typescriptlang.org/docs/handbook/utility-types.html#partialtype) in TypeScript, but I couldn't find the corresponding feature in Rust.
- Also, `dirty` will contain the **generalized indices** for **mutated** fields.


## `View`s

```rust
pub trait CoreView {
    fn slot(&self) -> anyhow::Result<u64>;
}

pub trait SlashingsView: CoreView {
    fn slashings(&self) -> anyhow::Result<&FixedVector<u64, U8192>>;
    fn slashings_mut(&mut self) -> anyhow::Result<&mut FixedVector<u64, U8192>>;
}
```

- `View`s will provide a functionality to access to or mutate of the field. (Getter/Setter) Using trait can be helpful, as we can combine multiple views into one view (e.g. `SlashingsResetView`).
- The original `BeaconState` can also implement this.
- IMO Writing the rest of other `View`s can be simpler with Rust macros.
- FYI) Sigp has their own crate called [`superstruct`](https://crates.io/crates/superstruct/0.9.0) for providing getter and setter for each field.


## State transition

```rust
impl PartialBeaconState {
    pub fn get_current_epoch(&self) -> anyhow::Result<u64> {
        let slot = self.slot.ok_or(anyhow::anyhow!("Slot is not set"))?;
        Ok(compute_epoch_at_slot(slot))
    }

    pub fn process_slashings_reset(&mut self) -> anyhow::Result<()> {
        let next_epoch = self.get_current_epoch()? + 1;

        // Reset slashings
        let slashings = self.slashings_mut()?;
        slashings[(next_epoch % EPOCHS_PER_SLASHINGS_VECTOR) as usize] = 0;

        // Mark dirty
        self.dirty.push(BEACON_STATE_SLASHINGS_GENERALIZED_INDEX);

        Ok(())
    }
}
```

- State transition will look like the original one, except for marking the dirty field.


## State Builder

```rust
#[derive(Debug, Clone, Serialize, Deserialize, Default)]
pub struct PartialBeaconStateBuilder {
    // For verification
    pub root: B256,
    pub multiproof: Multiproof,

    // For construct ``PartialBeaconState``
    pub slot: Option<u64>,
    pub slashings: Option<FixedVector<u64, U8192>>,
}
```

- This struct is for a builder pattern. `build()` will eventually return the `PartialBeaconState` after all validations are passed.

---

# Further things to do/discuss

## About serialzation (and SSZ encoding)

- Can we integrate other serialization methodology like [`rkyv`](https://rkyv.org/) for serialization? (As it is much more optimized on zkVM context...)
- Or do we have to pass a sequence of SSZ bytes, and decode into the actual state?

## `List` type of SSZ

- Fields like `validators`, `balances`, and `inactivity_scores` are the [List](https://github.com/ethereum/consensus-specs/blob/dev/ssz/simple-serialize.md#composite-types) with the limit of $2^{40}$. In the guest context, we need to calculate its "root", but is it feasible?
- At first, I thought that we need a way to access to a "single" validator, but I found there are several STFs that requires to access the "entire" validator set (e.g. `process_rewards_and_penalties`). Do we have to provide the functionality for generating proof of a subset of validators?

