SLATE: A Key-Value Engine for Raw NOR Flash, With Proofs

If you've ever shipped firmware that writes to raw NOR flash, you know the question that keeps you up before a release: what does the device actually contain if power dies in the middle of a write? Most answers to that question are "should be fine" — a log-structured write path, a checksum, a prayer. I wanted an answer I could actually check, so I built SLATE.

SLATE is a no_std, no-alloc key-value storage engine for edge devices — bare-metal microcontrollers like the ESP32 up through small Linux boards — targeting the setting most storage engines aren't designed for: raw NOR flash with no filesystem underneath, no battery-backed cache, well under 100 KiB of RAM, and a power supply that can be interrupted mid page-program.

This post covers what it guarantees, how it's built, how to actually use it, and — just as importantly — what it doesn't solve yet.

The core idea

SLATE composes primitives that are individually well understood — log-structured storage, AEAD encryption, cuckoo hashing, Reed–Solomon parity — into a design where the guarantees are proven, with the proofs and conformance data checked in at docs/specification.md, not asserted in a comment.

Three properties hold simultaneously:

1. Prefix durability

After an arbitrary number of power failures at arbitrary instants, recovery returns exactly the state produced by some prefix of the acknowledged write sequence — every write acknowledged before the last crash is present, and nothing beyond it sneaks in.

This is verified across 20,000 power-loss trials with the cut point at a uniformly random byte offset. Zero violations.

The mechanism behind it is simple to state: a write is acknowledged when its commit marker is durable, not when the record lands. put() buffers into the currently open batch; nothing is acknowledged until commit() makes the marker durable. That ordering is what makes "recovered state is a prefix" true by construction rather than by convention, and the commit batch size (b_commit) is your dial between write throughput and durability latency.

2. Rollback resistance

If an adversary with physical access replaces the flash with an older authentic image, recovery detects it: accepting a stale epoch requires forging a MAC.

This protection is per-epoch — a rollback within the current epoch isn't distinguishable, bounded by a parameter theta — and SLATE says so rather than implying a stronger guarantee than it delivers. Verified across 5,000 splice attacks, all rejected.

3. Erasure tolerance

Segment parity is maximum-distance-separable (Reed-Solomon over GF(2^8)), so any n-k declared block erasures reconstruct exactly.

Verified exhaustively for RS(12,8): all 794 erasure patterns within the code's distance recover byte-exactly; all 792 beyond it are correctly refused. 1,586 patterns total, zero wrong bytes.

The closed forms

Beyond the three guarantees, a handful of closed forms make sizing a real deployment tractable instead of guesswork:

• Constant-time index lookup
• Recovery time linear in the post-checkpoint tail only, independent of total stored volume
• Steady-state write amplification of 1/(1-u) as a function of utilization u
• An optimal commit batch size B* = sqrt(2 * lambda * A / c), which landed within 5.35% of the measured optimum in the parameter sweep

Engineering details that matter day-to-day

• Heapless no_std core, under #![forbid(unsafe_code)], with zero dynamic allocation — every buffer is a fixed array or a caller-supplied slice.
• Async-native, blocking-projected. Every algorithm is written once as an async fn over an AsyncFlash trait; the blocking API is a one-line projection over it, so the two APIs can't drift out of sync with each other. It's zero-cost when the flash driver never actually suspends.
• Partial-key cuckoo index with a fixed arena and a small stash: exactly 2b+s = 16 slot probes per lookup, independent of load factor, at roughly 4.2 bytes of RAM per key.

Using it

Rust (std)

[dependencies]
slate-kv = "0.5"

use slate_kv::db::{Db, KeySource, Options, Profile};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Options::default() is a 4 MiB "Pi" profile volume with b_commit = 8.
    let opts = Options {
        profile: Profile::Pi,
        ..Options::default()
    };

    // The root key is 32 bytes — prefer KeySource::File or ::Env in
    // production so the key never lands in the binary.
    let mut db = Db::open(
        std::path::Path::new("./slate_db.bin"),
        KeySource::Bytes([0x42u8; 32]),
        opts,
    )?;

    db.put(b"sensor_1", b"23.5 C")?;
    db.commit()?; // acknowledged here — not before

    if let Some(val) = db.get(b"sensor_1")? {
        println!("sensor_1 = {}", String::from_utf8_lossy(&val));
    }

    // Rollback protection degrades honestly depending on hardware —
    // check what mode you're actually running in.
    println!("security mode: {:?}", db.security_mode());
    Ok(())
}

C / C++ via the stable FFI

make ffi-staticlib      # -> target/release/libslate_kv_ffi.a + include/slate.h
make ffi-native-libs    # prints the platform link flags you also need

#include "slate.h"

uint8_t key[32] = {0x42};
slate_options opts = {
    .capacity_bytes = 4u * 1024 * 1024,
    .max_keys       = 8192,
    .b_commit       = 8,
    .theta          = 0,   /* 0 = built-in default */
    .profile        = SLATE_PROFILE_PI,
};

struct slate_db *db = NULL;
slate_open("./slate_db.bin", key, &opts, &db);
slate_put(db, (const uint8_t *)"key1", 4, (const uint8_t *)"val1", 4);
slate_commit(db);

Check slate_abi_version() against SLATE_ABI_VERSION_MAJOR before relying on the ABI, and treat SLATE_ERR_TAMPERED / SLATE_ERR_ROLLBACK as distinct security failures — don't just retry them.

Go, via the C ABI

make bind-test    # builds the staticlib, runs the conformance suite

The Go binding is a thin cgo layer over the same C ABI, so it runs wherever Rust std runs — it isn't a microcontroller path.

Bare-metal ESP32

cd targets/esp32
cargo build --release --bin kv_demo \
  --no-default-features --features chip-esp32c3,counter-flash,metrics \
  --target riscv32imc-unknown-none-elf

counter-efuse selects the hardware monotonic counter for full rollback protection; counter-flash keeps the counter in a flash sector for best-effort protection instead. metrics wires up the write-amplification counters. CI runs a QEMU crash-injection suite and a Wokwi hardware scenario against this target on every push.

Repository layout

Crate	Contents
slate-kv-core	Heapless no_std engine: log, index, epochs, GC, recovery
slate-kv	std wrapper: Db, file-backed flash, POSIX durability
slate-kv-crypto	AEAD sealer and key derivation
slate-kv-erasure	Reed-Solomon over GF(2^8)
slate-kv-hal	Flash / counter traits and blocking-to-async adapters
slate-kv-ffi	Stable C ABI and generated slate.h
slate-kv-sim	Simulated flash, crash injection, study harnesses
slate-kv-cli	Command-line tool
targets/esp32	Bare-metal esp-hal firmware, QEMU and Wokwi harnesses
bind/go	Go / TinyGo binding over the C ABI

What's not solved yet

I'd rather put this up front than bury it — a guarantee is only worth something if you're honest about where it stops:

• Reclaimed space isn't reusable yet. The log head can't wrap into freed segments, so a long-running device eventually halts with most of its segments free. This is a format-level gap and the biggest remaining item of work.
• RAM is over budget on ESP32. The shipped configuration needs ~81 KiB resident (~86 KiB at mount peak) against a 64 KiB target, dominated by a checkpoint buffer holding the full serialized index. n_buckets = 1024 is the largest configuration that actually fits in 64 KiB.
• Mount replay doesn't yield. Recovery is still on the blocking flash trait, so replaying 8,192 records is one uninterruptible span of roughly 4.6 seconds.
• Sequential keys defeat the fingerprint. Keys like sensor_000123 drive the index collision rate to roughly 5.7x its theoretical bound; well-mixed keys stay under it.
• Rollback protection is only as strong as your counter. With a hardware monotonic counter, the guarantee is as stated. With a flash-backed counter, it's best-effort. With neither, it's absent — and the engine reports which mode it's actually in rather than implying the strongest one.

Try it, break it, tell me

SLATE is dual-licensed MIT/Apache-2.0. If you work with flash storage, crash consistency, or constrained devices, I'd like the pushback — particularly on the epoch-bounded rollback model and the ESP32 RAM budget, since those are the two places I'm least satisfied with the current state.

• Repo: https://github.com/ja7ad/slate
• Spec, with every proof and every conformance number behind it: https://github.com/ja7ad/slate/blob/main/docs/specification.md