Modern key-value databases store data in log-structured merge trees (LSM trees). These are stores that never overwrite data in place. They append new versions and later merge files in the background, a step called compaction. Compaction rewrites the same logical data many times, which is the main source of write amplification, the ratio of bytes physically written to bytes the application asked to write. Cryptographic integrity checking ties authentication to where data sits, usually through a Merkle hash tree over block addresses. Combine the two and every compaction pass re-authenticates data the user never touched. When the store is outsourced, a second problem appears: the untrusted server is the one doing the compacting, so the client has no cheap way to know that compaction preserved its data.
The proposal is to authenticate what the logical contents are rather than where they live. Each entry carries a client-made tag over its key, version and value, and the tag contains no file or offset. The client keeps one small digest of the live data set: a signed sum of keyed hashes of entries. When compaction moves an entry, its tag moves with it and its removal and re-insertion cancel exactly in the digest. Only superseded or deleted versions change the digest, and those changes are checked by random spot-check audits of the kind used in provable data possession. If this works, integrity metadata traffic grows with the user's logical writes instead of with compaction write amplification, and compaction becomes something the client can audit without downloading the data.
Core Claim
Our claim is that integrity cost in outsourced LSM stores can be made independent of compaction write amplification. Integrity metadata writes, meaning bytes of tags, tree nodes and digests written per logical byte, should stay flat as the LSM size ratio and compaction aggressiveness grow. Every address-bound scheme in the file instead scales roughly linearly with physical rewrites.
The mechanism is a digest
$$D = \sum_{e \in W} F_K(e) \;-\; \sum_{e \in X} F_K(e) \pmod{q},$$
where $e=(k,\text{ver},v)$ is an entry, $W$ is the multiset of all entries the client ever wrote, $X$ is the multiset the server claims to have dropped as superseded or deleted, $F_K$ is a keyed pseudorandom function whose key only the client holds, and $q$ is a large prime. A legitimate compaction leaves $W$ unchanged and adds to $X$ only entries for which a newer version of the same key exists. A compaction that silently drops live data, resurrects stale versions, or alters values produces an $X$ whose superseding evidence fails under audit.
Summing modulo a prime, rather than XOR-ing, makes the digest track multiplicities. The keyed function makes forging a cancelling set as hard as breaking the function.
Relation to Prior Work
The closest work is the pairwise line connecting write amplification and integrity. It motivates the gap and supplies pieces of the method.
Three systems all assume a flat block device whose addresses are rewritten in place:
- Cloud Storage Integrity at Scale: A Case for Dynamic Hash Trees reshapes Merkle trees by splaying hot blocks toward the root.
- Efficient Storage Integrity in Adversarial Settings (PAC) defers tree updates to a secure queue and lets repeated writes to one block override each other.
- Enabling Efficient Verification of Dynamic Data Possession and Batch Updating in Cloud Storage (RB-MAT) relaxes AVL balance and batches updates through locked parent nodes.
An LSM store breaks that assumption. Compaction writes merged data to fresh files, so PAC's overriding never fires and every rewritten block is a new tree update. We keep PAC's idea of deferring authentication to an epoch boundary tied to fsync, which also prevents rollback. We drop address binding entirely.
Iris reduces parity write amplification with sparse erasure codes and absorbs tree updates at a trusted portal. We borrow the idea of a small trusted party absorbing churn, but our trusted state is a constant-size digest rather than a cache of tree nodes.
The homomorphic authenticator line supplies the auditing primitive: tags that aggregate linearly under random challenge weights so a verifier can check a combination without seeing blocks. This line is Homomorphic Authenticators for Blockless Data Verification and Towards Efficient Provable Data Possession. Those schemes authenticate static, position-indexed blocks. We apply the same aggregation to position-free entries and to the drop set $X$, which is what makes compaction auditable.
On the storage side, two systems define the regime and the cost we target. TRIAD reduces LSM write amplification by up to 4x through deferred compaction and log indexing. AegonKV offloads garbage collection to a SmartSSD. Neither carries any integrity mechanism. The AegonKV setting, where an untrusted device does the compacting, is exactly where verifiable compaction matters.
Resonance-continuum interference contributes a measurement lesson, not a mechanism. In particle physics, a resonance and its background add as amplitudes, so the observed rate contains a cross term that can be positive or negative:
- Study of the ρ'(1600) Mass Region Using γp collisions shows the cross term produces enhancement on one side of a peak and suppression on the other.
- Measurement of the total hadronic cross section in e+e− annihilation below 10.56 GeV observes the destructive dips this produces.
- Dielectron Widths of the Υ(1S, 2S, 3S) Resonances shows that subtracting background as if it were additive biases extracted quantities by as much as the total experimental error.
Systems papers report integrity overhead by subtracting an unprotected run from a protected run, which is the "additive background" assumption. In an LSM store, integrity work and compaction work interact: epoch seals can coincide with or straddle compactions, and tag traffic competes for the same flush bandwidth. Whether that interaction term is large is an empirical question. We test it by scanning a control parameter, borrowing the physicists' energy-scan design. We do not claim any deeper physical analogy.
Research Program
Write and compaction path. We will build the scheme into RocksDB through the TRIAD codebase (epfl-labos/TRIAD). The client computes $F_K(e)$ and a per-entry message authentication code (a keyed tag proving the entry came from the client) at write time. It stores both alongside the value and adds $F_K(e)$ to $D$.
The server compacts freely. For each compaction it appends to a log the identifiers of dropped entries, paired with the identifier of the superseding entry or tombstone. It also sends the client the aggregate of the dropped entries' tags. The client subtracts that aggregate from $D$ at the next epoch seal.
Auditing. An audit challenges a random sample of live keys and a random sample of logged drops. For a live key, the server returns the entry with its tag, and the client checks the tag. For a drop, the server must produce both the dropped and the superseding entry, which must have the same key and a higher version. A full-state audit checks that the server-claimed live set, aggregated with random weights, matches $D$. The standard spot-check argument applies: if a fraction $f$ of drops is illegitimate, $s$ samples miss all of them with probability $(1-f)^s$.
Read freshness. Per-read freshness, meaning proof that a returned version is the newest, is harder and we treat it as a separate component. Each immutable SSTable (a sorted file produced by a flush or compaction) gets a sorted Merkle tree, built once when the file is written and never updated. Proving that a key is absent from a level is then a pair of adjacent-key proofs. The only mutable authenticated object is the manifest of live files, which is small and changes once per compaction.
The open question is who builds those per-file trees when the server compacts. The design choice we will evaluate is that the server builds them and audits sample them against client tags. That makes freshness probabilistic rather than per-read, and we will report that weakening honestly.
Hardware offload. As a stretch goal we will port the compaction-side bookkeeping to the SmartSSD path used by AegonKV. The device is untrusted, so this is the natural setting for verifiable compaction.
Baselines
Unprotected stores. RocksDB with no integrity checking is the naive reference point. It gives the floor for throughput and physical write amplification. RocksDB with authenticated encryption at the block layer, and no tree, is the next reference. It matches PAC's own "AEAD baseline", against which Efficient Storage Integrity in Adversarial Settings reports reaching over 85% of throughput.
PAC under RocksDB. This is the strongest existing method. PAC sits as the block device beneath an unmodified LSM store, with its 0.1% hash cache and fsync-tied sealing. That paper also reports up to 5.5x throughput over Dynamic Merkle Trees on fio Zipfian workloads. DMT under RocksDB is a second competitor. Cloud Storage Integrity at Scale reports up to 2.2x throughput over static balanced trees on 4 TB volumes. All of these numbers are for flat block workloads. We found no reported result on Lacuna for any integrity scheme running under an LSM store, so the comparison itself is new measurement.
Trusted rebuild. This is the simple alternative: per-SSTable Merkle trees rebuilt by a trusted party at every compaction, plus an authenticated manifest. It isolates whether position-free tags matter beyond simply exploiting file immutability.
Ablation. The key ablation keeps our full system but binds each tag to its file and offset. Every compaction must then re-tag moved entries. This isolates position independence as the active ingredient.
Fairness. All systems run on the same hardware, dataset sizes and RocksDB configuration. Each gets the same budget for tuning its main knob: PAC's cache and queue size, DMT's splay rate, and our epoch length.
What counts as beating PAC. We count it as beating PAC if both of the following hold on write-heavy workloads:
- integrity metadata write amplification at least 3x lower; and
- equal or better throughput.
Integrity overhead must also stay flat while the LSM size ratio varies from 4 to 16. Under PAC we expect it to grow with physical write amplification.
Why not just…?
Why not just run PAC underneath RocksDB? PAC's savings come from repeated writes to the same block address overriding each other in its queue. Compaction writes to newly allocated files, so those overrides rarely occur. This is a prediction, not a finding in the file, and the PAC baseline tests it directly. If PAC's queue absorbs most compaction churn anyway, the core claim fails and we will say so. One way that could happen is if file systems recycle freed blocks quickly enough that new files reuse hot addresses. We will log the override hit rate to explain the result either way.
Why not just build a Merkle tree per immutable SSTable and authenticate the manifest? This is the real threat. When the client or a trusted proxy performs compaction, it may well be enough. Its cost is one hashing pass per physically written byte, so integrity overhead tracks write amplification but adds no tree-update churn. Our advantage exists only when the untrusted side compacts. In that case the trusted side either re-reads every compacted byte or trusts the server's new trees. The trusted-rebuild baseline measures the re-read cost, and our attack experiments show what is lost by trusting server-built trees without tags. If the client-compaction setting turns out to be the practical one, the contribution shrinks to auditable outsourced compaction, and the proposal should be framed that way.
Why not just use homomorphic authenticators over blocks, as in standard provable data possession? Block-indexed tags are bound to a position. Every compaction that moves a block would require the client to regenerate its tag. Towards Efficient Provable Data Possession shows tag generation is already the client-side bottleneck. These tags also cannot say which version of a key is current. The position-bound ablation is exactly this design applied to an LSM store.
Why not just use a wider, static balanced Merkle tree with more threads? Cloud Storage Integrity at Scale reports a 75% throughput collapse for balanced trees scaling from 16 MB to 4 TB. It also shows that wider nodes increase sibling hashing per update. Under an LSM store the number of updates is further multiplied by write amplification, so this baseline should be dominated. We include it only through the DMT comparison.
Proposed Experiments
Workloads. We use YCSB workloads A, B and F with Zipfian and Latest request distributions, following Benchmarking cloud serving systems with YCSB. For production replays we use the first 500 million operations of Twitter cache clusters 39, 19 and 51 (write-heavy, mixed and read-heavy), as in AegonKV. We also run TRIAD's db_bench.
Metrics. We measure:
- integrity metadata write amplification;
- total physical write amplification;
- throughput and 99th-percentile latency;
- client CPU per logical write;
- audit bandwidth;
- attack detection probability.
First decisive check. We sweep the LSM size ratio and the level-0 compaction trigger. The core claim predicts that our integrity write amplification stays roughly flat while PAC's and the position-bound ablation's rise in step with physical write amplification.
Second decisive check: attacks. We inject a misbehaving server that does one of three things: drops a fraction of cold live entries during compaction, resurrects superseded versions, or rolls back the manifest. We measure detection probability as a function of audit sample size against the $(1-f)^s$ prediction.
Third decisive check: interference scan. We vary epoch length against the compaction period and fit throughput with and without an interaction term between integrity work and compaction work. We then compare the overhead estimate from the joint fit with the naive "protected minus unprotected" subtraction. A large gap means existing overhead reports for integrity under LSM stores are biased, in the same way background subtraction biased the Υ dielectron widths. A negligible gap retires the lens, and we will report it as such.
References
- Cloud Storage Integrity at Scale: A Case for Dynamic Hash Trees
- Efficient Storage Integrity in Adversarial Settings
- Enabling Efficient Verification of Dynamic Data Possession and Batch Updating in Cloud Storage
- Iris: a scalable cloud file system with efficient integrity checks
- Privacy-Preserving Public Auditing for Secure Cloud Storage
- Towards Efficient Provable Data Possession
- TRIAD: Creating Synergies Between Memory, Disk and Log in Log Structured Key-Value Stores
- AegonKV: A High Bandwidth, Low Tail Latency, and Low Storage Cost KV-Separated LSM Store with SmartSSD-based GC Offloading
- Study of the<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mrow><mml:msup><mml:mrow><mml:mi>ρ</mml:mi></mml:mrow><mml:mrow><mml:mo>′</mml:mo></mml:mrow></mml:msup></mml:mrow><mml:mn/><mml:mo>(</mml:mo><mml:mn>1600</mml:mn><mml:mo>)</mml:mo><mml:mn/></mml:math>Mass Region Using<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi>γ</mml:mi><mml:mi>p</mml:mi><mml:mo>→</mml:mo><mml:mrow><mml:msup><mml:mrow><mml:mi>π</mml:mi></mml:mrow><mml:mrow><mml:mo>+</mml:mo></mml:mrow></mml:msup></mml:mrow><mml:mrow><mml:msup><mml:mrow><mml:mi>π</mml:mi></mml:mrow><mml:mrow><mml:mo>−</mml:mo></mml:mrow></mml:msup></mml:mrow><mml:mi>p</mml:mi></mml:math>at 20 GeV
- Measurement of the total hadronic cross section in<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:msup><mml:mi>e</mml:mi><mml:mo>+</mml:mo></mml:msup><mml:msup><mml:mi>e</mml:mi><mml:mo>−</mml:mo></mml:msup></mml:math>annihilation below 10.56 GeV
- Dielectron Widths of the<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mi>Υ</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mn>1</mml:mn><mml:mi>S</mml:mi><mml:mo>,</mml:mo><mml:mn>2</mml:mn><mml:mi>S</mml:mi><mml:mo>,</mml:mo><mml:mn>3</mml:mn><mml:mi>S</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math>Resonances
- Benchmarking cloud serving systems with YCSB