A Midsummer Night's Tree: Efficient and High Performance Secure SCM

Samuel Thomas, Kidus Workneh, Jac McCarty, Joseph Izraelevitz, Tamara Lehman and R. Iris Bahar

Non-volatile main memory keeps data through a power cut, which is great for storage but dangerous for security — the integrity tree that detects tampering is cached on-chip and lost on a crash, so its metadata must be persisted too, and doing that safely is either brutally slow or leaves a huge recovery; this work from Brown, Colorado, and Bryn Mawr builds A Midsummer Night's Tree, a tree-within-a-tree that persists only the small hot region lazily and the rest strictly, cutting runtime overhead up to 41 percent below the state of the art while using a tiny 96 bytes of on-chip space instead of tens of kilobytes.

The argument in one glance

Problem

Non-volatile main memory keeps its data through a crash — including corruption

Storage-class memory is main memory built from non-volatile technology, so it keeps its contents through a power failure — near-DRAM speed with the persistence of storage, ideal for large in-memory data. Secure memory protects that memory from physical tampering by an attacker with hardware access, using encryption for confidentiality and an integrity tree of hashes whose root, kept on-chip, can detect any corruption of off-chip data. But the tree's metadata is cached in volatile on-chip caches, which vanish on a crash. On volatile DRAM you would just reboot from a safe state; on non-volatile memory the data, and any tampering, survive the reboot, and the lost metadata means you can no longer tell corruption from crash inconsistency.
What people did

Persist the metadata either strictly or lazily

To keep the integrity metadata usable after a crash, there are two extremes. Strict persistence writes every metadata update straight through to memory, so the tree is always consistent and recovery is trivial — nothing to rebuild. Leaf persistence is lazy: it persists only the leaves (the encryption counters) and the root directly, letting the inner tree nodes stay in the volatile cache and be written back only on eviction, which is fast at runtime.
Why it fell short

Strict is far too slow, lazy recovers far too slowly, and fixes cost chip area

Strict persistence is crash-safe but brutally slow — up to 25 times the runtime overhead, because every data write must push its whole path up the tree to memory. Leaf persistence is fast but, on a crash, must assume every inner node is stale and recompute the entire tree from its leaves, taking billions of cycles and scaling with memory into the terabytes. Dynamic schemes navigate this by tracking hot regions in hardware, but that tracking is complex and hungry for on-chip area — one uses tens of kilobytes — stealing space from the last-level cache and binding performance right back to the slow memory.
This paper's idea

Put a fast subtree for the hot region inside one strict tree

A Midsummer Night's Tree observes that only a small, contiguous region of memory is usually hot. So within a single integrity tree it makes just the subtree covering that hot region lazy (leaf persistence, fast writes) while the rest of the tree is strict (fast recovery). A crash can leave only the small subtree stale, so recovery is bounded and set by how high the subtree root sits — an administrator can dial it in. A tiny history buffer tracks which region is hottest and moves the subtree there, and it all fits in 96 bytes of on-chip space.

Why this problem is worth solving

The heart of the difficulty is that non-volatility, the whole point of storage-class memory, is exactly what makes its security metadata a liability.

Secure memory assumes the chip is trusted and everything off-chip — the memory, the buses — is not, exposed to an attacker who can snoop, splice in stale data, or replay old values. Confidentiality comes from encrypting each block; integrity comes from a Bonsai Merkle Tree, a tree of keyed hashes built over the encryption counters. Each leaf hashes a counter, siblings are hashed into their parent, and so on up to a single root that is kept on-chip and therefore trusted. To verify a block, the hardware fetches its path up the tree and recomputes the hashes; if they match the trusted root, the data is authentic, and a mismatch means tampering. On ordinary volatile memory this is enough, because a detected attack just triggers a reboot to a clean state. Storage-class memory breaks that escape hatch. Its contents — and any corruption an attacker planted — survive the reboot, so you cannot simply restart. Worse, the tree’s metadata (counters, hashes, inner nodes) lives in volatile on-chip caches for speed, and a crash wipes it. When the machine comes back, the persisted data reflects the latest writes but the persisted metadata is stale, and the hardware cannot distinguish a legitimate hash mismatch caused by that staleness from a real attack. Keeping the security metadata crash-consistent with the data it protects is therefore not optional — it is what makes secure non-volatile memory possible at all, and getting it fast is the whole game.

The reason the two obvious solutions both fail is that they sit at opposite ends of a tradeoff, and the fixes in between quietly spend a third scarce resource.

Persisting the metadata safely forces a choice. Strict persistence writes every metadata update through to memory immediately, so nothing is ever stale and recovery is instant — but every single data write now drags its entire ancestral path up the tree out to slow memory, inflating runtime by as much as twenty-five times. Leaf persistence flips this: it persists only the leaf counters eagerly and leaves the inner tree nodes lazily in cache, so writes are fast, but a crash leaves every inner node potentially stale, and recovery must recompute the whole tree from the leaves. Because a parent hash depends on its children, this recomputation is largely serialized level by level and bounded by memory bandwidth, running into billions of cycles and scaling with the memory’s size — which for storage-class memory can be terabytes. So there is a spectrum from fast-runtime-slow-recovery to slow-runtime-fast-recovery, and the state of the art tries to land in the middle by dynamically tracking which regions are hot and treating them specially. But that tracking introduces a third cost the field has underweighted: on-chip area. Hot-region tracking hardware, shadow tables, extra caches — these consume trusted on-chip space, and every kilobyte they take is a kilobyte the last-level cache does not have, which pushes more accesses out to the slow secure memory and binds performance right back to it. A good solution must be fast at runtime, bounded at recovery, and frugal with area all at once, which is what makes the design genuinely hard.

What people did before, and where it broke

Strict persistence — write all metadata through to memory. Keep the tree always consistent so recovery is instant. Where it broke. Every data write must push its whole path up the tree to memory, inflating runtime by up to twenty-five times — far too slow to be practical.
Leaf persistence — persist only the leaves, lazily update the rest. Persist the counters eagerly and let inner nodes be written back on eviction for fast writes. Where it broke. A crash leaves every inner node stale, so recovery must recompute the whole tree from its leaves, taking billions of cycles and growing with memory into terabyte-scale recovery times.
Track the cached metadata addresses to recover only them (Anubis). Shadow the addresses currently in the metadata cache so recovery corrects just those. Where it broke. It hits a slow path on every metadata cache miss, so its performance is tied to cache locality, and its shadow structures need tens of kilobytes of on-chip and in-memory space, growing with memory size.
Cache frequently-accessed subtree roots for full coverage (Bonsai Merkle Forest). Keep a non-volatile on-chip cache of hot subtree roots, pruning and merging by access frequency. Where it broke. It requires every leaf to be covered by a persistent root, which makes a true hybrid persistence strategy impossible, so it inherits the limits of whichever single policy it runs, and needs kilobytes of non-volatile on-chip cache.
The gap. Every approach either sat at a slow extreme, recovered pessimistically over the whole tree, or bought a middle ground with on-chip hardware that steals space from the cache and scales with memory. What was missing was a scheme that is near-leaf-fast at runtime, bounded and tunable at recovery, and nearly free in area — which is what practical secure storage-class memory needs.

How A Midsummer Night’s Tree works

A lazy subtree for the hot region inside a strict tree

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Spend the expensive strict persistence everywhere except the small region that dominates the writes. The waste in strict persistence is that it treats every write as if it happened in the hottest, most latency-critical spot, pushing the whole tree path to memory each time; leaf persistence avoids that but pays it all back at recovery. AMNT’s move is to notice that writes concentrate in a small contiguous region, make only that region lazy so the common writes are cheap, and keep the rare cold writes strict so recovery stays trivial for the bulk of the tree. Persisting non-volatile-memory metadata cheaply by exploiting that only a small, localized region is hot, rather than treating all of memory uniformly, is exactly the strategy the GPU persistency-model work covered elsewhere on this site follows, keeping the common local updates in fast on-chip state and paying the full persistence cost only where the ordering truly reaches across the machine.

Find the hot region with a cheap runtime tracker, and move to it. The hard part of any hot-region scheme is knowing which region is hot without expensive hardware, and AMNT answers with a tiny history buffer that counts recent writes per region and keeps the busiest at its head, moving the fast subtree there only occasionally and off the critical path. It adapts to where the program is actually working rather than guessing statically. Using a lightweight, always-updating tracker of what is genuinely hot to steer where the system spends its effort is the same discipline the adaptive-SLAM-runtime work covered elsewhere on this site applies, reading a cheap live signal of the workload’s real behavior instead of a costly or static proxy.

Treat on-chip area as a first-class budget, offloading complexity to software. Prior dynamic schemes bought their speed with tens of kilobytes of trusted on-chip structures, forgetting that every such kilobyte shrinks the last-level cache and pushes accesses back to the slow memory. AMNT deliberately keeps its hardware to 96 bytes, and when the single-hot-region assumption fails under multiprogramming, it fixes that not with more silicon but by biasing the operating system’s page allocator to consolidate hot pages. Right-sizing the hardware to a tight area budget rather than reaching for the largest structure, and shifting the remaining complexity into software, is the same instinct behind the in-storage accelerator work covered elsewhere on this site, which chooses a modest design that fits the real constraints instead of the biggest one that would blow them.

Following a write and a crash through AMNT

Writing to the hot region, then recovering from a crash

Tracing a hot write and a recovery shows both halves of the design.

Step 1 of 5

A program writes repeatedly to a small, contiguous region

A write-intensive workload keeps updating a small set of addresses. Each write must be encrypted and have its integrity metadata updated, and under strict persistence that would mean pushing the whole tree path out to slow non-volatile memory on every write.

Write-intensive workloads suffer most from strict persistence, since writes sit on the critical path.

Why it works

Making only the hot region lazy keeps the common writes cheap. Strict persistence pushes every write’s whole tree path to slow memory → but confining leaf persistence to the small hot subtree lets the writes that dominate execution stay in the cache → so runtime approaches the fast leaf baseline while the rare cold writes stay strict.
Only the subtree can be stale, so recovery is bounded and tunable. Leaf persistence must recompute the whole terabyte-scale tree because any inner node could be stale → but everything outside the subtree is written through, so only the subtree’s nodes can be stale → so recovery is bounded by the subtree size, set by the administrator’s chosen level, independent of memory size.
A tiny history buffer finds the hot region without costly hardware. Tracking hotness in hardware normally demands large structures that steal cache space → but a 768-bit buffer counting recent writes per region, kept sorted only at its head, is enough to pick the hottest → so AMNT tracks hot data in 96 bytes where prior dynamic schemes use tens of kilobytes.
Write-through everywhere else makes subtree moves cheap and safe. Shifting the fast region could require persisting a lot of newly-cold metadata → but since only subtree nodes are ever dirty, a scan of the dirty bits finds exactly what to persist, plus the path to the root → so moving the subtree preserves consistency with minimal extra writes.
Biasing the OS allocator restores locality that multiprogramming destroys. Several programs at once scatter their hot data across regions, breaking the single-hot-region assumption → but nudging the page allocator to place pages within the busiest subtree region funnels their accesses together → so the subtree hit rate climbs without any per-core tracking hardware.

What it costs (trade-offs and scope)

The single-hot-region assumption breaks under multiprogramming. AMNT’s speed depends on a small contiguous region being hot, which holds for one program but not when several run at once and scatter their working sets — recovered only by the optional OS-allocator co-design, which is an extra deployment dependency.
The recovery-runtime knob is manual. An administrator must choose the subtree level in the BIOS, trading faster recovery (a lower, larger subtree) against lower runtime overhead (a higher, smaller subtree); there is no automatic tuning.
Recovery is bounded but not instant. Unlike strict persistence, which recovers immediately, AMNT still recomputes its subtree — milliseconds to seconds depending on the level and memory size — so the fast-recovery configurations give back some runtime benefit.
Cold-region and region-thrashing writes see no benefit. Writes outside the hot region still pay full strict-persistence cost, and a workload with no stable hot region gains little — though the evaluation found the subtree moves only about 0.3 percent of accesses, so thrashing was rare in practice.
It is simulated on a specific configuration. Results come from a cycle-accurate simulator with phase-change-memory parameters, a fixed tree arity, and the general Bonsai-tree format; an SGX-style tree needs small modifications, and side-channel attacks are explicitly out of scope.
The area win is against particular prior schemes and is orthogonal to other optimizations. AMNT’s 96 bytes beats the shadow caches of prior dynamic schemes, but other integrity-tree area optimizations exist and would need to be combined separately, not evaluated together here.

The evaluation

Four ways to persist secure-memory metadata on non-volatile memory

Property	Strict persistence	Leaf persistence	Anubis (shadow table)
Runtime overhead
Recovery time			Fast, fixed
On-chip area	Small	Small
Adapts to hot data	No	No	Tracks cached addresses
Area scales with memory	No	No

Four ways to keep secure-memory integrity metadata crash-consistent on non-volatile memory, evaluated in a cycle-accurate simulator on PARSEC and SPEC CPU 2017 with phase-change-memory parameters. AMNT cuts runtime overhead up to 41 percent (13 percent on average) below the state-of-the-art Anubis, stays within 2 percent of leaf persistence, and offers recovery bounded by the administrator-chosen subtree level — all in 96 bytes of on-chip space versus tens of kilobytes — because it confines lazy persistence to a tracked hot subtree inside an otherwise strict tree.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

A Midsummer Night’s Tree is an elegant, economical answer to a three-way squeeze. Secure non-volatile memory must keep its integrity-tree metadata crash-consistent, and the two clean options are opposite disasters — strict persistence is up to twenty-five times slower, leaf persistence recovers over the whole terabyte-scale tree — while the dynamic middle grounds buy speed with tens of kilobytes of on-chip hardware. AMNT’s tree-within-a-tree makes only the small hot region lazy and the rest strict, tracks the hot region with a 96-byte history buffer, and lets an administrator bound recovery by choosing how high the subtree root sits. It cuts runtime overhead up to 41 percent below the state of the art, stays within 2 percent of leaf persistence, and uses a fraction of the area. Read it with its scope. Its speed rests on a small contiguous hot region existing, which multiprogramming breaks and only the optional OS-allocator co-design restores; the recovery-runtime tradeoff is a manual BIOS knob; recovery is bounded but not instant; cold writes see no benefit; and the results are simulated on a specific memory model with a general tree format, side channels excluded. The durable lesson is that navigating a hardware tradeoff well often means counting the resource everyone else ignored — here, on-chip area — and refusing to buy runtime or recovery with silicon you cannot spare.

Background

Why trusted memory keeps paying a tax to prove itself honest

It helps to see AMNT within the long project of protecting memory an attacker can physically reach. The premise of secure memory is stark: trust the chip, trust nothing outside it, and assume an adversary can snoop the buses, splice in old data, or replay stale values. That premise forces a heavy, continuous tax — every block leaving the chip must be encrypted, and every block returning must be re-verified against a tree of hashes, so the machine is forever proving to itself that its own memory has not lied. This is the same adversarial world the memory-disambiguation side-channel work covered elsewhere on this site inhabits, where an attacker with access to the shared hardware bends a microarchitectural mechanism into leaking secrets — a reminder that the boundary between trusted and untrusted hardware is exactly where security is won or lost. Non-volatility raises the stakes, because now the untrusted memory remembers across a reboot, so the integrity machinery must remember too, crash-consistently, without letting that requirement crush performance. The broad lesson is that as memory becomes both persistent and adversarial, the cost of trust is not a one-time check but a standing obligation, and the engineering that matters is making that obligation cheap enough — in time, in recovery, and in the scarce trusted area on the chip — that the protection is actually worth deploying.

If you remember only three things

1. Storage-class (non-volatile) main memory keeps its contents through a crash, which is its value but also a security problem: secure memory detects physical tampering with an integrity tree (a Bonsai Merkle Tree of hashes rooted on-chip), but the tree's metadata is cached in volatile on-chip caches that vanish on power loss. If that metadata is not persisted crash-consistently with the data, a reboot cannot tell real corruption from stale metadata. Strict persistence (write all metadata through) is crash-safe but up to 25 times slower; leaf persistence (persist only leaves, lazily update inner nodes) is fast but must recompute the whole tree at recovery, taking billions of cycles that scale with terabyte-scale memory; and dynamic hot-region schemes navigate this only by spending tens of kilobytes of scarce on-chip area.
2. A Midsummer Night's Tree is a tree-within-a-tree: within one integrity tree, it applies lazy leaf persistence to the subtree covering a small contiguous hot region (fast writes) and strict persistence everywhere else (instant recovery). The subtree root sits at an administrator-chosen level in a non-volatile on-chip register, so only the small subtree can be stale after a crash and recovery is bounded by the subtree size, independent of memory size. A 768-bit (96-byte) history buffer counts recent writes per region off the critical path and moves the subtree to the hottest region, persisting only its dirty nodes (found via dirty bits) on a move. An optional co-design (AMNT++) biases the OS page allocator to funnel multiprogram hot pages into one subtree region, restoring locality without per-core hardware.
3. In a cycle-accurate simulator on PARSEC and SPEC CPU 2017 with phase-change-memory parameters, AMNT reduces runtime overhead by up to 41 percent (13 percent on average) versus the state-of-the-art Anubis, stays within 2 percent of leaf persistence and up to 8 times better than strict, and uses only 96 bytes of on-chip space versus Anubis's tens of kilobytes, with recovery configurable from milliseconds to seconds via the subtree level. Its limits: the hot-region assumption needs the OS co-design under multiprogramming, the recovery-runtime tradeoff is a manual BIOS knob, recovery is bounded but not instant, cold-region writes see no benefit, and results are simulated on one memory model with the general tree format, side channels excluded.

Check yourself

Check your understanding

1. Why does non-volatile main memory create a new problem for secure-memory integrity trees that volatile memory did not have?
2. What is the core idea of A Midsummer Night's Tree?
3. How does AMNT keep its hardware cost so low, and why does that matter?
4. Which statement best reflects the scope and limits of AMNT?

Sources

The paper is “A Midsummer Night’s Tree: Efficient and High Performance Secure SCM” by Samuel Thomas, Kidus Workneh, Jac McCarty, Joseph Izraelevitz, Tamara Lehman, and R. Iris Bahar, published at ASPLOS 2024, DOI 10.1145/3620666.3651354. The authors are at Brown University, the University of Colorado Boulder, Bryn Mawr College, and the Colorado School of Mines, and the artifact is available open-source.

This explainer is written from the full 16-page text. Everything above comes from the paper’s own sections: the introduction and background on traditional secure memory (counter-mode encryption and Bonsai Merkle Trees with keyed hashes, the on-chip trusted root) and the new crash-consistency challenge of storage-class memory, where volatile metadata caches are lost on a crash; the strict-versus-leaf persistence tradeoff (strict up to 25 times slower, leaf recomputing the whole tree over billions of cycles at recovery) and the underweighted third dimension of on-chip area; the survey of dynamic prior work (Anubis’s shadow table and its cache-miss slow path, Bonsai Merkle Forest’s persistent root set requiring full leaf coverage, ProMT, Bo-Tree, ASSURE, Osiris, Triad-NVM); the AMNT design of a hybrid tree-within-a-tree with a strict main tree and a leaf-persistent subtree whose root sits at a BIOS-configurable level in a non-volatile register; the hot-region tracking via a 768-bit (96-byte) history buffer promoting a new subtree root after 64 writes and persisting only dirty subtree nodes on a move; the AMNT++ hardware-software co-design biasing the Linux buddy allocator during page reclamation; and the evaluation in gem5 on PARSEC (single 16 percent and AMNT++ 10 percent overhead, canneal under 0.1 percent) and SPEC CPU 2017 (up to 41 percent and 13 percent average reduction versus Anubis, within 2 percent of leaf, up to 8 times better than strict, xz at 32 percent versus Anubis 41 percent and BMF 7 times), the hardware overhead table (AMNT 96 bytes volatile and 64 bytes non-volatile versus Anubis’s 37 kilobytes), and the recovery-time table scaling with subtree level rather than memory size.