Toleo: Scaling Freshness to Tera-scale Memory Using CXL and PIM

Secure processors like Intel SGX promise that memory can never be rolled back to a stale value by an attacker, but the Merkle tree they use to guarantee this adds so many extra memory accesses that it only protects a few megabytes — which is why Intel's scalable version quietly dropped the guarantee; this work from Michigan puts a small, tamper-proof smart-memory chip on the fast CXL interconnect to hold just the version numbers, so the chip itself becomes the root of trust and the tree disappears, and two compression tricks shrink the versions enough that one 168-gigabyte device can keep 28 terabytes of memory fresh for about 2 percent overhead.

The argument in one glance

Problem

Secure enclaves must block replay attacks, or integrity means nothing

A trusted execution environment like Intel SGX promises three things for data in memory: confidentiality (it is encrypted), integrity (tampering is caught by a checksum), and freshness (a read returns the most recent value). Freshness matters because without it an attacker with physical access can record an old encrypted value and its checksum and replay them later, rolling memory back in time — which passes the integrity check and can corrupt control flow or leak secrets. So a secure processor tags every cache block with an ever-increasing version number and checks it on every read.
What people did

Protect the version numbers with a Merkle tree

But the version numbers live in untrusted memory too, so they can be replayed as well. The standard fix is a Merkle tree: a tree of checksums whose leaves are the versions and whose root is kept inside the trusted CPU. To verify one read is fresh, the processor walks from the root down to the leaf, checking every node along the way. A small cache of tree nodes is meant to make this affordable.
Why it fell short

The tree does not scale past a few megabytes

The Merkle tree is the bottleneck. Every protected read triggers a walk that adds extra memory accesses — around 7 at a hundred megabytes, 13 at terabyte scale — and the node cache hit rate is only 60 to 70 percent even with a generous cache. So client SGX protects just a few megabytes of memory, and research pushed it only to tens of gigabytes. Intel gave up: its scalable SGX reaches large memory by abandoning freshness and integrity altogether. Nobody had all three guarantees at tera-scale for a reasonable cost.
This paper's idea

Let a tamper-proof memory chip be the root of trust

Toleo removes the tree by moving the versions into a small, trusted smart-memory device — logic fused to DRAM inside a package that self-destructs if probed — sitting on the fast CXL interconnect. Because that device is tamper-proof by construction, it simply is the root of trust for the versions it holds: no tree is needed to prove they are fresh. Data and checksums stay in cheap ordinary DRAM. Two compression ideas then shrink the versions so much that one 168-gigabyte device can keep an entire 28-terabyte memory pool fresh, shared across a whole rack, for about 2 percent overhead.

Why this problem is worth solving

The guarantee this paper scales is the least intuitive of the three that trusted hardware provides.

Memory freshness is the guarantee that when a program reads an address, it gets the value most recently written there — and not some older value an adversary has replayed. It is the third leg of trusted-hardware security, alongside confidentiality (encryption) and integrity (a checksum that catches tampering). Freshness is easy to overlook but essential, because an attacker with physical access to the memory bus can record a legitimate encrypted value together with its valid checksum and, later, feed that stale pair back to the processor. The encryption and the checksum both still verify — they were genuine, once — so without a freshness check the machine happily accepts a value from the past, which can corrupt a program’s control flow, break its memory safety, or leak its secrets. The standard way to provide freshness is to stamp each block of memory with a version number that only ever increases, so a replayed old value carries an old version and is caught.

The trick that makes Toleo work is a physical property of a certain kind of memory.

Smart memory, sometimes called processing-in-memory, is a package that fuses a layer of logic directly onto DRAM chips using advanced 3D or 2.5D stacking, connected by wires that run inside the sealed package. It is usually pursued for bandwidth — the logic sits right next to the data — but this paper wants a different property. Because the connections between the logic and the memory are buried inside the package, an adversary cannot probe or tamper with them without physically destroying the device. That makes the whole package a small island of trust in an otherwise untrusted machine: anything the logic layer computes or stores is safe from an attacker who controls the rest of the system and even has physical access to the memory bus. Toleo builds on exactly this, treating a small smart-memory device as a hardware root of trust rather than as a bandwidth booster.

What people did before, and where it broke

Client SGX with a Merkle tree. Protect the version numbers with a tree of checksums rooted inside the trusted CPU, walking it on every read. Where it broke. The walk adds up to 7 accesses at a hundred megabytes and 13 at terabyte scale, with a version-cache hit rate of only 60 to 70 percent, so it protects only a few megabytes of memory.
Smaller integrity trees (VAULT, MorphCtr). Compress the tree so it reaches more memory, up to tens of gigabytes. Where it broke. It is still fundamentally a tree, so the walk and its cache misses remain; the scalability wall just moves, it does not fall.
Scalable SGX with AES-XTS. Reach the full memory by dropping the nonce and the tree entirely. Where it broke. It abandons both freshness and integrity to get there — only a partial confidentiality remains — so replays and tampering go completely unprotected.
All-smart-memory designs (InvisiMem). Put all protected data on trusted smart memory, which removes the need for freshness checks entirely. Where it broke. Smart memory is expensive, so replacing an entire 28-terabyte pool with it is prohibitive, and these designs also carry heavy side-channel-hiding overhead, near 29 percent.
The gap. Every option gave up one of the three things that matter: the tree-based ones gave up scale, scalable SGX gave up freshness and integrity, and all-smart-memory gave up affordability. Nobody had a way to keep confidentiality, integrity, and freshness together across a tera-scale memory pool at a price a rack server could actually pay. That combination — all three guarantees, at scale, cheaply — is exactly the hole this work sets out to fill.

How Toleo works

Keeping tera-scale memory fresh with one small trusted chip

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

The idea

Let a device that is trustworthy by construction replace the structure built to earn trust. The Merkle tree exists for one reason: version numbers sit in untrusted memory, so something must vouch that a version read back is the real, current one and not a replay. An entire tree of checksums, walked on every access, is the machinery that does the vouching. Toleo notices that if the versions instead live inside a tamper-proof smart-memory package — one that physically cannot be probed or altered without destroying itself — then that package already provides the guarantee the tree was laboriously reconstructing, and the tree can simply be deleted. Recognizing that a piece of hardware you already have provides a property you were expensively rebuilding in software, and leaning on the hardware instead, is the same economy the SSD-deduplication work covered elsewhere on this site drives at, where a dedup layer stops maintaining a mapping table because the drive itself already keeps one.

Exploit the locality of what you must store to shrink it dramatically. Trusted smart memory is expensive, so the versions it holds have to be tiny. The insight is that versions are highly redundant: data-intensive workloads write to large structures uniformly, so within a page most cache blocks carry the same version or differ by a tiny stride, and many pages are read-only after they are built. Toleo represents a whole page of 64 versions, in the common case, as a single shared version plus a bit-vector marking which blocks are dirty — twelve bytes to protect four kilobytes, upgrading to richer formats only for the rare irregular page. Turning the structure and locality of the metadata you must keep into an aggressive compression that bounds its footprint is the same discipline the post-deduplication compression work covered elsewhere on this site relies on, exploiting the redundancy between neighboring items to store their bookkeeping in a fraction of the naive space.

Keep only the essential fraction in the scarce fast tier, and the rest in the cheap one. A version number is doing two jobs at once — it is a nonce that keeps the encryption strong, which demands a long, never-repeating value, and it is a freshness stamp, which only needs enough bits that a blind replay guess almost certainly fails. Toleo pries these apart, keeping just the short low-order “stealth” bits in the costly trusted memory and stashing the long upper bits in ordinary DRAM, so the expensive resource holds only what genuinely needs its protection. Reserving the scarce, expensive tier for a compact stand-in of what the computation truly requires while the bulk sits in a cheaper place is the same layering the out-of-core random-walk work covered elsewhere on this site depends on, holding only a succinct representation of the needed data in the fast, limited memory and leaving the rest further down the hierarchy.

Following the reasoning through Toleo

Catching a replay attack, the old way and the Toleo way

Following a single protected memory read shows where the Merkle tree's cost goes and how Toleo removes it.

Step 1 of 5

The CPU reads an address and must prove the value is fresh

A secure enclave loads a cache block from untrusted memory. Before using it, the processor must confirm the returned value is the most recent one written to that address, not an old encrypted value an attacker recorded and replayed — because the stale value would still pass the encryption and checksum tests.

A replay defeats integrity precisely because the replayed value and its checksum were once genuine.

Why it works

Making the memory chip itself the root of trust deletes the whole Merkle tree. Version numbers in ordinary memory can be replayed, which is why a tree of checksums rooted in the CPU had to vouch for them → but a tamper-proof smart-memory device guarantees the freshness of whatever it stores by construction → so the versions simply live there, and the tree walk that added up to thirteen accesses per read vanishes.
Storing only the versions, not the data, keeps the costly trusted memory tiny. Putting all protected data on smart memory, as prior designs did, is far too expensive at tera-scale → but versions are a small fraction of data, so only they need the trusted device while data stays in cheap DRAM → so one small 168-gigabyte chip suffices where all-smart-memory would need terabytes.
Splitting the version lets freshness ride on far fewer bits than encryption needs. A version doubles as an encryption nonce, which must be long and never repeat → but freshness only needs enough bits that a blind replay guess fails, so Toleo keeps just the low 27 bits in trusted memory and the rest in cheap DRAM → so the trusted storage roughly halves, since an adversary gets a one-in-134-million guess and a single shot before the kill-switch fires.
Compressing versions by page turns memory locality into a tiny footprint. Storing a full version per cache block is wasteful when neighbors share versions → but data-intensive workloads write pages uniformly, so most pages fold into one shared version plus a dirty bit-vector → so the metadata-to-data ratio drops to about one to 240, and 92 percent of pages need just twelve bytes to protect four kilobytes.
Caching the compact page versions in the TLB hides the remote device. A version store shared across a rack, sitting in a separate drawer, would seem to add crippling latency to every read → but the page-level format is small enough to ride along in the translation entry, hitting 98 percent of the time → so only rare misses reach the remote chip, and freshness adds only a couple of percent of overhead.

What it costs (trade-offs and scope)

It is a simulation study of assumed technology. Everything is modeled in a cycle-accurate simulator on a down-scaled node, and it leans on emerging or assumed pieces — CXL 2.0 encryption with a low-latency mode, and trusted smart memory with correct, side-channel-free logic — rather than a built system.
The 2 percent is freshness on top of an already-costly base. Confidentiality plus integrity alone averages 18 percent over no protection, dominated by fetching integrity checksums. Toleo’s freshness is the cheap increment, not the whole cost of a protected enclave.
It does not hide access patterns. Unlike the all-smart-memory baseline it is compared against, Toleo protects the values, not the addresses or timing, so an adversary watching the memory bus still learns what is accessed and when.
Latency-sensitive, poor-locality workloads still pay. The key-value stores redis and memcached, with random page access, hit the version cache only 67 to 85 percent of the time and see freshness add 72 to 112 percent of their read latency, even though their execution-time overhead stays modest.
The space win depends on version locality. It is excellent on the studied data-intensive workloads, where 92 percent of pages are the compact flat format, but an irregular writer like the FM-index kernel needs far more trusted memory — a third of its pages are uneven, costing 7.6 gigabytes per terabyte — so a bad-locality workload erodes the headline ratio, and Toleo assumes mixing good and bad workloads on one device.
Security rests on strong assumptions. The guarantee holds only if the package is truly tamper-proof, the trusted microarchitecture is correct and free of side-channels, the kill-switch reliably limits an adversary to one guess, and the probabilistic reset argument holds — reasonable but load-bearing premises.
It is a shared, single trust anchor for the rack. One remote device secures every node; the authors argue the bandwidth is fine, about 2 percent extra traffic, but it is a shared resource and a common root of trust for the whole rack.

The evaluation

Providing memory security guarantees at scale

Property	Client SGX (Merkle tree)	Scalable SGX
Guarantees provided
Memory protected
How versions are trusted		Not protected
Extra work per read
Performance overhead	Does not scale	Low, but insecure

Memory-protection approaches, with Toleo evaluated in cycle-accurate simulation across 12 privacy-sensitive genomics, graph, generative-AI, and database workloads on a 28-terabyte CXL rack. It compresses versions to a 1-to-240 metadata-to-data ratio, caches them at a 98 percent hit rate, and adds only 1 to 2 percent overhead for freshness on top of confidentiality and integrity — scaling the freshness guarantee about six orders of magnitude beyond a Merkle tree.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Toleo is an elegant re-architecting of a stubborn problem: instead of scaling the Merkle tree that guards version numbers, it makes a small, tamper-proof smart-memory device the root of trust so the tree disappears, then shrinks the versions with a stealth-bit split and page-level compression so one 168-gigabyte chip keeps 28 terabytes fresh at about 2 percent overhead. Read it with its boundaries. It is a simulation study built on emerging and assumed technology — CXL encryption, trusted smart memory — not a deployed system. Its 2 percent is only the freshness increment; the full confidentiality-plus-integrity base is around 18 percent. It deliberately does not hide access patterns, unlike the pricier baseline it beats. Its space efficiency leans on version locality, so irregular workloads cost much more trusted memory, and latency-sensitive random-access workloads do pay real freshness latency. And its security rests on the package being genuinely tamper-proof and the microarchitecture side-channel-free. The durable idea is the reframing: when a piece of hardware provides a guarantee by construction, you can throw away the elaborate structure built to prove it.

Background

Why we go to such lengths to distrust our own hardware

It is worth stepping back to see why confidential computing exists at all. The premise is unsettling: you want to run sensitive code and data — medical genomes, model weights, a rival company’s records pooled for joint analysis — on a machine you do not own and cannot physically trust, whether a cloud server administered by strangers or an edge device an adversary can pry open. Confidential computing answers by shrinking the circle of things you must trust down to a single hardware component, the secure processor, and treating literally everything else — the operating system, the memory bus, the other tenants, the person with a probe — as hostile. That is a demanding stance, and freshness is the subtle guarantee that makes it airtight, because an adversary who cannot read or forge your data can still try to rewind it, and a system that accepts stale values is quietly broken. The same refusal to trust the hardware blindly runs through the silent-data-corruption work covered elsewhere on this site, which assumes even a correctly manufactured chip can quietly compute the wrong answer and builds checking around it. The broader pattern is that as computation moves onto machines their owners cannot vouch for, security becomes a matter of assuming betrayal everywhere and engineering guarantees that survive it.

If you remember only three things

1. Trusted execution environments must guarantee freshness — a memory read returns the latest value, not an old one an attacker replays — by stamping each cache block with a version number, but the version numbers themselves sit in untrusted memory and are protected by a Merkle tree rooted in the CPU; walking that tree adds up to 13 memory accesses per read with a 60-to-70-percent cache hit rate, so it scales only to a few megabytes, which is why Intel's scalable SGX drops freshness and integrity entirely to reach large memory.
2. Toleo moves the version numbers into a small, tamper-proof smart-memory device on the CXL interconnect, so the device itself is the root of trust and the Merkle tree is eliminated, while data and checksums stay in cheap DRAM; two space optimizations make it affordable — keeping only the short low-order "stealth" bits of each version in the costly trusted memory (freshness needs fewer bits than an encryption nonce), and compressing a page's 64 versions into one shared version plus a dirty bit-vector when locality is high — plus caching the compact page versions in the TLB for a 98 percent hit rate.
3. In cycle-accurate simulation across genomics, graph, generative-AI, and database workloads, one 168-gigabyte Toleo device keeps a 28-terabyte CXL memory pool fresh — about six orders of magnitude beyond a Merkle tree — at a 1-to-240 version compression ratio and only 1 to 2 percent overhead on top of confidentiality and integrity; but it is a simulation of assumed technology, the 2 percent excludes the ~18 percent base cost, it does not hide access patterns, its space win depends on version locality (irregular writers cost far more), and latency-sensitive random-access workloads do pay real freshness latency.

Check yourself

Check your understanding

1. Why does the Merkle tree that guarantees memory freshness fail to scale?
2. What is Toleo's core idea for eliminating the Merkle tree?
3. How does Toleo make it affordable to protect 28 terabytes with a 168-gigabyte device?
4. Which statement best reflects the limits of Toleo's results?

Sources

The paper is “Toleo: Scaling Freshness to Tera-scale Memory using CXL and PIM” by Juechu Dong, Jonah Rosenblum, and Satish Narayanasamy, published at ASPLOS 2024, pages 313 to 328, DOI 10.1145/3622781.3674180. The authors are at the University of Michigan, Ann Arbor.

This explainer is written from the full 16-page text. Everything above comes from the paper’s own sections: the introduction and background on trusted-hardware guarantees (confidentiality, integrity, freshness), the version-number and Merkle-tree mechanism and its poor scaling (7 to 13 extra accesses per read, 60-to-70-percent cache hit rate, only a few megabytes protected), and the comparison of client SGX, scalable SGX, and all-smart-memory designs like InvisiMem; the CXL and smart-memory background, including CXL 2.0 Integrity and Data Encryption with its skid mode and the tamper-proof in-package connections of 3D and 2.5D smart memory; the Toleo design storing only versions in a small trusted smart-memory device that obviates the Merkle tree, its partial stealth versions splitting a 64-bit version into a 37-bit upper part in DRAM and a 27-bit stealth part in Toleo with random initialization and probabilistic reset to defeat address side-channels while keeping full versions unique, and the Trip tri-level page format (flat, uneven, full) that exploits version locality plus a TLB-based stealth version cache; and the evaluation in SniperSim with DRAMSim3 across 12 privacy-sensitive workloads reporting a 1-to-240 version compression ratio, a 98 percent version-cache hit rate, 1-to-2-percent freshness overhead on top of an 18-percent confidentiality-and-integrity base (versus 29 percent for InvisiMem), the per-format page breakdown (92 percent flat, 7.5 percent uneven, 0.32 percent full), a peak of 4.27 gigabytes of Toleo per protected terabyte, and the outlier latency costs on redis and memcached.