.png)
Let's talk about defragmentation. Not the kind you do to a hard drive, but defragmenting a merkle log to make an in-memory index dramatically smaller.
In TVC Verifiable State, persistent storage for apps running on Turnkey Verifiable Cloud (TVC), an 8 TB volume could require more than 100 GB of memory just to index its data and proofs. By exploiting the relationship between page numbers and their locations in the merkle log, we found a way to compress that index and keep shrinking it as the system runs.
This article covers that index, and how we got it small enough to keep in memory while still being able to spin one node off another nearly instantly.
The challenge: Keeping verifiable storage fast
TVC Verifiable State runs a virtual userspace block device on top of a custom, highly optimized, interactive merkle proving protocol built on a fork of Commonware's excellent QMDB library.
TVC Verifiable State verifies every single read and write inside of the Trusted Execution Environment (TEE) before the kernel sees it. For an 8 TB volume, upstream QMDB's in-memory index alone would take roughly 60 GB.
QMDB merkle log with an external index
QMDB is a merkle log. Fundamentally it's a log of operations, where each operation is a location in the merkle log. The operation log is committed to by the upper layers of the merkle tree, and with each operation it stores the key it's talking about.
There is an external index in QMDB that maps each key to the location in the operation log that currently holds it. That index is not committed to by the merkle tree.
In the ordered variant, which is the only variant that can be used correctly and soundly inside of TEEs and zero-knowledge (ZK) systems, we also store the next key in the operation log. So that's basically a mapping, committed to in the operation log, from each key to the current next key in the database.
What that allows you to do is use the external index to get the location in the merkle log where a key is currently stored, and get the location of its next key from that. The next-key lookup is necessary for doing things like exclusion proofs, and also for doing a stateless verify of a state transition from one merkle root to another merkle root, which is why you need it in ZK and in TEEs.
In the current variant of QMDB there's also a bitmap that tracks, for each location in the operation log, whether it's still active. Those bitmaps are grafted into another layer of the merkle tree.
Why QMDB's index sits on the hot path of every read
The really unfortunate thing about this is that QMDB's external index is always on your hot path. If it's stored on disk, your merkle tree is going to be insanely slow.
So the solution upstream is to store the index in memory, which for the ordered variant is a normal Rust std BTreeMap. Upstream also keeps the activity bitmap and the top of the grafted tree in memory, and the merkle nodes that a proof needs are just arithmetic on the location, so it reads them all at once.
That means QMDB doesn't actually do dependent reads. A get is a lookup in memory and then one read of the log.
Keeping the index in memory is great, but it has a problem, which is O(n) load times in your live keys. When a node starts up it has to rebuild the index and the bitmap by replaying the log.
We needed to make nodes rapidly spawnable, so that was not an option. I want to be able to spin one node off another nearly instantly, not wait for it to replay a log.
We tried lazy loading the index instead, from a checkpoint. But lazy loading is not enough. Every time the part of the index you need isn't in memory, you're hitting storage on the hot path again.
Realistically you want this index to always be in memory, which means it has to be small.
How large QMDB's index gets for an 8 TB volume
So let's discuss the size of this index. The size is determined by the number of live keys in your database at any time. That's fine, but that can grow.
So let's say that you are writing a verifiable block device with 4 KB pages. An 8 TB volume is about 2 billion pages, and once it fills up every page is a live key. A BTreeMap of just key to location for that would already be roughly 60 GB.
Needless to say it's really big, which is not ideal for rapid startup time of nodes, and is just a very large memory requirement for running QMDB.
And that's not even all of the storage you need in RAM to have a really fast instance of QMDB. You also need to know where to get the contents of each block and where to get the associated proof records, so you can rapidly make the merkle proofs. Put that in the same BTreeMap and you're past 100 GB.
Exploiting our key space to compress the index
In TVC Verifiable State we fortunately have a constrained key space. Our key space consists entirely of mappings from page number to 4 KB blocks. It's effectively u64 to u64, page number to operation number.
To solve this problem I exploited the key space.
We take advantage of the natural alignment between three numbers.
Our W objects, the write-ahead log objects that actually contain the data, have monotonically increasing numbers. The operation log is again a monotonically increasing u64. And page numbers are not monotonically increasing in the operation log.
So we look at that and we say, well, several of these things grow together. One of them doesn't. But in an ideal scenario it does, because when you're doing sequential writes the operation number and the page number actually do grow monotonically together.
So this leaves you with a pretty exploitable property, which is that you can have a smaller index in memory if you encode this relationship, and try to enhance this relationship in your key space.
In other words, the less fragmented your block device is relative to your merkle operation log, the less information you need to store the location of every key and value in the operation log and in your storage engine. We call this the compressed index.
How bucket encoding stores 128 pages in as little as one byte
For each page we pack its operation, its W object and its slot in that W object together, in buckets of 128 keys. That's parameterized and can be changed.
The reading is contextual. When you start reading a bucket you start at a location in the operation stream, and at a location in the stream of W objects. Then we only have to insert an integer into the stream when things move out of sync with each other in an unexpected way.
In the normal case, when you have sequential stuff, you don't need to insert anything, so you don't have to store redundant information. And when a value can be expressed using a smaller integer, we express it using a smaller integer.
So a bucket of 128 sequential pages is a single byte. If one page in the middle gets rewritten, the bucket is 13 bytes: a couple for the run before it, a few for the page that moved, a few more to get back in line, and one for the rest.
So immediately we began exploiting that property, and relatively easily we got about an 8x smaller index with an encoding based around deltas. The delta encoding effectively gives us a mapping that is much, much cheaper to maintain than individual mappings of each of these things to each of the other things.
Why dependent reads hurt on high-latency storage
All of this is in the name of not adding dependent reads. A dependent read is a read that must wait for another read before it can be dispatched. So in other words, I have to go to the disk, get some information, and then go back to the disk for some more information.
Avoiding dependent reads matters a lot for us because we write to S3, and we can also operate fully on S3 buckets. An S3 read normally takes tens of milliseconds, which is a lot slower than reading a local disk, so a dependent read on S3 really hurts.
Normally we run with an NVMe cache in front of the reads, which makes dependent reads less important, but avoiding them is still necessary to get really good performance. And the NVMe cache in our architecture can be thrown out at any point, so we can't count on it being there.
In our storage engine, we've minimized dependent reads so that in the normal case there are two independent reads, one for the W object and one for the P object, where we store the proof data.
All other reads in the normal case hit memory on the proof path. That's when you're generating a merkle proof of a particular page and providing the data for it, the page itself.
How merkle log defragmentation keeps the index shrinking
While this relationship is somewhat natural, in that a lot of software does do sequential writes, we can actually enhance it more. Since QMDB is a log, you have a floor. The floor is the point below which you do not keep log records.
The floor keeps the log relatively compact, and normally you move the records from the floor to the tip of the log periodically. QMDB supports parameterized policies for this.
What we do instead is exploit the buckets to discover when we should move things from near the floor to the tip, to maximize the sequential runs in our write-ahead log, our operation log and our key space. We're already reading those buckets for normal reads, so finding what to move doesn't cost any extra reads.
We move a page that's out of line together with its neighbors, so they land at the tip as one sequential run again. Moving pages together maximizes the one-to-one relationship, enhancing the natural property of it to compress our index even further and accelerate reads even more.
We also back off when we're under load. When we're behind on latency we do less defragmentation, and when we're keeping up we do more.
The operation log and the W objects never get to a perfect one-to-one with the page numbers, but they keep getting closer, and the index keeps getting smaller.
Join TVC Verifiable State as a development partner
TVC Verifiable State lets web2 databases, agent sandboxes and other file-based software run inside AWS Nitro Enclaves, fully cryptographically attested, with persistent state. Alpha opens to development partners on November 13, 2026. If you want to run your own database or agent sandbox with verifiable persistent state, contact the Turnkey team.
Further reading on TVC Verifiable State and QMDB
.png)
