Hierarchical Differential State Storage & Regeneration

[nazarhussain]

Motivation

• Excessive Storage: Ethereum consensus clients typically do not need every historical state snapshot stored indefinitely. However, certain use cases (e.g., serving older blocks, running debugging/troubleshooting tools, or providing chain data to external consumers) require the ability to reconstruct historical states.
• Inefficient Full Backups: Storing the entire state at each finalized slot is prohibitively large and grows linearly with chain history, making “archive nodes” extremely heavy.
• On-Demand Historical Queries: An optimal design should allow reconstructing older states or blocks on demand but with minimal overhead in both storage and processing.

A hierarchical differential approach—where we store full snapshots only at certain intervals and keep diffs at more frequent intervals—can drastically reduce storage requirements while still enabling historical reconstruction.

Proposed Solution 

This solution introduces a multi-layered approach to storing and retrieving historical data in Lodestar. By combining large snapshot intervals at the lowest layer with a series of more frequent differential layers above them, clients can reassemble states on-demand without storing every historical snapshot. This balance of full backups and incremental diffs helps keep storage requirements in check while enabling relatively quick recovery of past states or blocks.

Following are the key factors to remember in this solution.

1. Snapshot Layer

   • At the lowest (least frequent) layer, store a full snapshot of the beacon state (and optionally relevant block data) at some large interval—e.g., every 512 epochs.
   • This acts as an anchor or base from which we can re-generate states around it.

2. Differential Layers

   • Add multiple higher-frequency layers that store incremental diffs between certain checkpoints or epochs.
   • Each diff is smaller than a full snapshot and can be applied to a lower layer’s state to regenerate an intermediate state.

3. Shortest Path Reconstruction

   • Given a target slot N, the system locates the “nearest” stored diff or snapshot by scanning from the top layer down.
   • For example, if N has a directly stored diff in the highest-frequency layer, the system applies that diff to the next-lower layer’s state, and so on, until eventually reaching a snapshot.
   • After reassembling the state that corresponds to a known epoch near N, the final few blocks are replayed to get the exact state at slot N.

4. Block Archiving & Retrieval

   • The same layering logic can be applied to block bodies. You can store:
     • Full block data at certain intervals,
     • Partial or summarized block diffs in between,
     • Or a combination, depending on your indexing needs.
   • This ensures that reconstructing older blocks does not require fully storing every block from genesis onwards.

Example Layer Configuration

• Snapshot every 512 epochs (lowest layer).
• High-level diffs every 128 epochs.
• Mid-level diffs every 32 epochs.
• Fine-grained diffs every 8 epochs.

Thus, the path from slot 700  to the nearest snapshot might look like (696 <- 672 <- 512). Once we have state at 696 we can then replay the block for slot 700 to get that state.

Following configuration is just for example, in actual implementation we can choose different values based on observation in the real nodes.

Mathematical Estimation of Layer Frequencies

We can use the cost equation (as shown in the references) to balance:

• Storage (size of snapshots + diffs)
• Backup time (how long it takes to produce each snapshot/diff)
• Restore time (how long it takes to reconstruct states for queries)
• Replay overhead (the extra blocks to replay once we have an approximate state)

By adjusting:

• F (frequency of snapshots),
• D_i (frequency of each differential layer),
• n (number of differential layers),

We can find a compromise between minimal storage and fast restoration time.

We can capture the whole process into a single value Cost to compare across different input values. Following equation can be used to calculate the Cost involved.

$$ \begin{align*} Cost &= \frac{w_{s}* Storage + w_{b} \times Backup Time + w_{r} \times Restore Time}{(n \times T_{diff} + T_{full}) \times G_{max}} + (G_{min} \times T_{replay}) \\ TotalStorage &= F \times S_{full} + \sum\limits_{i=1}^{n}D_{i}\times S_{diff}\\ BackupTime &= F \times T_{full} + \sum\limits_{i=1}^{n}D_{i} \times T_{diff}\\ RestoreTime &= F \times R_{full} + \sum\limits_{i=1}^{n}D_{i} \times R_{diff}\\ \\ \text{Where as}\\ \\ F &= \text{Frequency of full backup}\\ D &= \text{Frequency of differential backup}\\ S_{full} &= \text{Size of full backup}\\ S_{diff} &= \text{Size of differential backup}\\ T_{full} &= \text{Time to take full backup}\\ T_{diff} &= \text{Time to take differential backup}\\ T_{replay} &= \text{Time to replay a block}\\ R_{full} &= \text{Time to restore full backup}\\ R_{diff} &= \text{Tiem to restore differential backup}\\ G_{max} &= \text{Max gap between backups (usually the snapshot gap)}\\ G_{min} &= \text{Minimum gap between backups (usually the top layer gap)}\\ w_{s} &= \text{Weight for total storage}\\ w_{b}&= \text{Weight for total backup time}\\ w_{r} &= \text{Weight for total restore time}\\ n &= \text{Number of differential layers}\\ \end{align*} $$

Conclusion

This hierarchical diff-based storage strategy ensures that Lodestar can handle on-demand regeneration of historical data without ballooning disk usage. It strikes a balance between:

• Storing too many snapshots (leading to wasted space),
• Storing too few (causing large replay overheads).

By defining a set of layer frequencies (e.g., [8, 32, 128, 512] by default) and systematically storing diffs at each layer, Lodestar can:

• Quickly restore older states for debugging or external requests,
• Avoid incurring huge storage penalties,
• Maintain flexibility for future evolution in backup frequencies or diff formats.

Once in place, operators can run nodes with partial historical data yet still reconstruct needed states on demand—enabling more lightweight operation than a traditional “archive” node and improving the overall user experience of Lodestar.

[matthewkeil]

Looks great!!! I do have some questions surrounding the Cost calculations though. Would love to see this system of equations solved or at least understand how you solved it to arrive at a frequency of 4 between layers.

In addition to the analytical solution I think we should also do some empirical differential testing to understand this from a practical perspective. Like there may be some unforeseen system-level implications to the reconstruction that are not captured by the equation.

[ensi321]

@nazarhussain In your slot 700 example, why isn't slot 640 in layer 1 used in the reconstruction? Isn't it be 512->640->672->696?

Also to clarify, the diffs we are storing in each differential layer is the diff between slot i, and the closest slot to i in the layer one level below right? So in your example, the object layer 3 stores at 696 is the diff between state 696 and state 672 in layer 2. The object layer 2 stores at 672 is the diff between state 672 and state 640 in layer 1. Is this correct?

I also want to know if this hdiff proposal will store unfinalized states as well? My impression is that unfinalized state enquiry are served by state cache. Only finalized states are stores in hdiff storage

And how does #7005 play a role here if at all?

[nazarhussain]

Both the slots 640 and 672 on Layer 2 had binary diff on top of slot 512 on the snapshot layer. So to get the shortest possible path from slot 700 we skipped the slot 640. When reconstructing any state we should only pick maximum one diff from each layer.

HDiff is not (in foreseen future) is supposed to used for unfinalized states. Once we implement with the finalized state logic, will observe it's complication and behavior on real network and then can think of moving this approach to the unfinalized states.

Don't consider #7005 for now, it was 2nd iteration of full feature :), but now decided to move with the smaller PRs. So you can check following #7665 #7664 #7663