0xMiden / 0xMiden/node

Disk-backed Mmr

Abierto
#2,470 2 comentarios 0 reacciones 1 asignado Reclamado por @sergerad Ver en GitHub
Lenguaje dominante
Rust
Estrellas
104
Forks
138
Merge medio
1 d 13 h
PR fusionados (30 d)
56

Descripción

# Support a partially on-disk `Mmr`

## Motivation

`Mmr` currently holds its entire postorder node buffer in memory. Growth is ~64 bytes per leaf (`2n − popcount(n)` nodes × 32-byte `Word`). For the block-hash MMR at a 3s block time:

| Horizon | Size |
|---|---|
| 6 months | ~335 MB |
| 1 year | ~670 MB |
| 10 years | ~6.7 GB |

Not urgent for RAM at one leaf per block, but worth designing the seam early. Full-buffer scans (serialization, startup deserialization, `PartialEq`) go linear in the multi-GB range first; per-transaction/per-note MMRs would make the disk tier a hard requirement (~670 GB/year at 1k leaves/block).

## Key properties

Based on the chunked storage refactor from: https://github.com/0xMiden/miden-vm/pull/3562:

- The node buffer is strictly append-only: every full 32 KiB `NodeStore` chunk is immutable forever — no cache invalidation, lock-free reads of frozen chunks, chunk index is a natural storage key.
- `add` only reads the current peaks (≤64 words), so with peaks cached in memory, appends require zero historical reads.
- Required resident set: `forest` (one `usize`), peaks (≤2 KiB), partial tail chunk (≤32 KiB), plus a cache of full chunks for `open()`/`peaks_at`/`get_delta`.

## Options

### A. Make `Mmr` generic over a chunk-granular storage trait

Existing `NodeStore` becomes the default in-memory impl (no downstream breakage, keeps miden-crypto no_std); a RocksDB backend lives in the node crate, e.g. key = chunk index, value = 32 KiB chunk, full chunks + `forest` committed in the same `WriteBatch` as the block.

```rust
pub trait ChunkStore {
type Error;
fn num_chunks(&self) -> usize;
fn get_chunk(&self, idx: usize) -> Result>, Self::Error>;
fn append_chunk(&mut self, idx: usize, chunk: &[Word]) -> Result<(), Self::Error>;
}
```

Cost is the API ripple in miden-crypto: `Index` → fallible `get_node`, a storage error variant on `open`/`peaks_at`/`get_delta`, and `MmrNodeIter` streaming owned `Arc` chunks instead of borrowed slices.

### B. `PartialMmr` + external archive

Leave `Mmr` untouched. The node keeps a `PartialMmr` (peaks + tracked paths) in memory and streams the full buffer to its own storage via the existing `nodes_from(start)` sync API, serving historical `open()` from that storage. Least invasive to miden-crypto, but duplicates `collect_merkle_path_and_value`'s postorder walk downstream (or requires extracting it over an abstract reader).

### C. mmap'd flat append-only file

Fixed 32-byte records at `index * 32`; the OS page cache provides partial residency for free. Operationally the simplest, but can't live in a no_std crate, involves unsafe mmap handling, and loses atomic batching of MMR state with the rest of the node's RocksDB state.

## Open questions

- Which operations must be served from the cold tier (historical `open()`? `get_delta`?), since that determines how much of the read path needs to be storage-aware.
- Tail-chunk durability: write-through per block vs. rebuilding the last ≤1023 nodes from the leaf source on restart.

Guía de contribución

Abrir la guía de contribución

Evaluación

Este issue todavía no se ha evaluado.

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.