Conservative Updates Pay Twice Inside an Enclave

A frequency sketch is a small table of counters that estimates how often each item appears in a huge stream. Each item is hashed to one counter per row, and its estimate is the smallest of those counters. Conservative update (CU) is a simple trick that makes these sketches far more accurate for the same memory. On each arrival it increments only the counters that currently hold the item's minimum, so counters already inflated by collisions stop growing. A formal analysis shows CU reaches the same heavy-hitter precision with roughly 7x less memory than standard sizing rules require.

CU is also the kind of code a security reviewer distrusts. Which counters get written depends on the hidden contents of the table. When sketches run inside trusted hardware enclaves on untrusted clouds, the host can watch which memory addresses are touched even though the data itself is encrypted. For that reason the existing oblivious sketch design uses plain, unconditional updates. This note argues the opposite trade. In an oblivious implementation, every update costs time in proportion to the size of the table, so CU's memory savings become throughput savings. The price of hiding CU's conditional write turns out to be a constant factor of about two, while the table shrinks by a factor of about seven.

Core Claim

Our claim is that a CU sketch can be made fully oblivious, meaning its sequence of memory addresses, instruction path and timing depend only on the stream length. We would do this with two linear passes of constant-time conditional moves over each row, and no oblivious RAM (ORAM, a scheme that hides which memory block is accessed by reshuffling blocks along a tree path on every access).

At equal accuracy, this design should beat an ORAM-wrapped standard Count-Min sketch in throughput on realistic traces, and it should stay inside the enclave's protected memory at stream sizes where the baseline starts paging. The cost comparison is simple. Let $d$ be the number of rows, $w$ the row width in counters, and $B$ the ORAM bucket cost per tree level. The two per-update costs are then roughly:

$$ T_{\text{scan-CU}} \approx 2\,d\,w_{\text{CU}}, \qquad T_{\text{ORAM-CMS}} \approx d\,B\,\log_2(d\,w_{\text{CMS}}). $$

The factor 2 comes from one pass to read the minimum and one pass to write. The logarithm comes from the height of the ORAM tree.

The formal CU analysis says that $w_{\text{CU}}$ can be several times smaller than $w_{\text{CMS}}$ at the same precision. If that holds, the scan wins over a range of widths that plaintext reasoning would never predict. The first thing to establish is where that range ends on real data.

A second, sharper question decides whether the idea is worth pursuing at all. CU's advantage is concentrated on the most popular items. Oblivious deployments already pull the heaviest flows out into exact counters. Does CU still help on the residual tail that remains in the sketch? We treat this as a potential falsifier, not an assumption.

Relation to Prior Work

The method draws on two lines of work that have never met.

The first line supplies the accuracy argument. CU was introduced for flash hot-data identification in Efficient on-line identification of hot data for flash-memory management. Goyal et al. brought it to natural language processing in Sketching Techniques for Large Scale NLP, and reported at least a 1.5x drop in average relative error in Sketch Algorithms for Estimating Point Queries in NLP. A Formal Analysis of the Count-Min Sketch with Conservative Updates proves a "popularity privilege": high-frequency items are shielded from collision error. It also derives sizing formulas giving 6.63x less memory on synthetic Zipfian traffic and 7.12x on Wikipedia logs at 97.5% precision. That analysis assumes memory accesses are private and streams are independent draws. We reuse its sizing rules, and we test whether its gains survive once heavy items are removed from the stream.

The second line supplies the threat model and the incumbent design. OblivSketch: Oblivious Network Measurement as a Cloud Service runs a Count-Min sketch inside Path ORAM within an Intel SGX enclave. Heavy flows go to linearly scanned exact buckets. The system fits in about 6 MB and pays a 2–8x "obliviousness tax" relative to non-secure code. OblivSketch never uses CU. Our proposal differs in two ways: it adds CU, and it replaces ORAM on the sketch with a scan that CU's smaller table makes affordable.

Connecting the Dots: Privacy Leakage via Write-Access Patterns to the Main Memory motivates why the write pattern matters even to an attacker who sees only writes. It recovers a 512-bit key from the supposedly balanced Montgomery ladder via DMA snapshots in 3 minutes 34 seconds, because the destination of each write depended on the secret. CU's choice of which rows to write has exactly that shape.

Two works constrain the design space without supplying the method. Streaming Algorithms with Few State Changes shows that the number of writes can be made sublinear. However, CU always writes at least once per arrival, and hiding which cells are written is a different goal from writing rarely. Differentially Oblivious Database Joins relaxes full obliviousness to bounded, differentially private leakage in order to escape worst-case cost. We keep full obliviousness here. If the scan design is fast enough, that relaxation is unnecessary for sketches of this size.

Research Program

We would build three implementations of CU inside SGX, each run with secret keyed hashes.

The first is the naive, branching CU. It exists to measure what leaks. With hashes hidden, the leakage that remains is the number of rows written per update and which rows those are. We would estimate the mutual information between this signal and the item's frequency rank. We would also train a simple classifier that predicts from the trace alone whether an arriving item is a heavy hitter.

The second is ORAM-wrapped CU. It needs one ORAM access per row to read and one per row to write back, so roughly double OblivSketch's per-update cost.

The third, the proposal, is scan-CU. Pass one computes the minimum over the $d$ target counters using constant-time selects over every cell of each row. Pass two applies a masked increment to every cell, where the mask is "this cell is the item's target and holds the minimum." The pass structure is identical for every input. We would vectorize both passes, and apply the same scan to queries.

Around these we reproduce OblivSketch's split between exact heavy buckets and a sketch for light flows. We then vary the bucket threshold, so we can see how CU's gain depends on how much of the heavy tail has already been removed.

Analytically, we would extend the popularity-privilege error bounds to a stream with its top-$k$ items deleted. This yields a predicted width ratio $w_{\text{CMS}}/w_{\text{CU}}$ as a function of $k$ and the Zipf exponent, which we then check empirically.

Baselines

The strongest existing method is OblivSketch's ORAM-wrapped Count-Min sketch with oblivious heavy buckets, per OblivSketch. Its reported figures are a 2–8x throughput tax over non-secure baselines, a footprint of about 6 MB, query latency under 15 ms on a 5-second, 70k-flow CAIDA trace, and up to 15x speedup over baselines that exceed enclave memory and page. We would reimplement it on the same machine, trace and bucket threshold, and size its sketch with standard rules for the same target error as ours. Scan-CU beats it if it delivers higher update throughput at equal or lower error and equal leakage, meaning a trace fixed by stream length.

The second baseline is an oblivious CountSketch with noise-floor thresholding, following Improved Frequency Estimation Algorithms with and without Predictions. That paper proves CountSketch is better suited than Count-Min to Zipfian data and reports up to a 17x weighted-error reduction over prior learned sketches on CAIDA at small memory. CountSketch updates are unconditional and the sketch is linear, so obliviousness costs one pass instead of two, and the sketches can be merged. We would run it with the same scan implementation and the same memory grid. Its thresholding would be tuned on a held-out trace prefix with the same budget we use for choosing CU's width.

The naive reference point is a non-oblivious plain CU and plain Count-Min sketch in the same enclave. This fixes the ceiling on throughput and the leakage we are removing.

One ablation isolates CU: scan-CMS, which is identical code minus the minimum pass and the mask. It separates the gain due to CU's smaller table from the gain due to dropping ORAM. A second ablation, ORAM-CU, separates the same two effects from the other direction.

Why not just…?

Why not just keep OblivSketch's ORAM Count-Min and skip CU? This works, and it is the incumbent. But its cost grows with the logarithm of the table, it carries ORAM's constant factors, and it needs a table several times larger for the same precision per the formal CU analysis. The larger table matters most at scale, where OblivSketch itself shows paging costs up to 15x. The comparison against scan-CMS and ORAM-CU shows directly whether that size gap translates into throughput.

Why not just add dummy writes to every row? That is essentially what we do. The masked pass writes every cell, so dummy writes are the mechanism rather than an alternative. The substantive questions are whether the dummies can be made indistinguishable at cache-line granularity and in snapshots, and what they cost. Connecting the Dots shows that balanced dummy operations failed when the destination of the write still depended on the secret. That is why we write every cell of the row, not just the $d$ target cells, and why we test the output with a snapshot-diff check.

Why not just use oblivious thresholded CountSketch? This is the real threat. It is cheaper per memory cell and can be merged across enclaves, which CU cannot. If at matched memory it equals CU's error on the residual tail, the case for CU collapses. In that event the contribution reduces to showing that scans beat ORAM for small sketches, applied to CountSketch. The error-versus-memory curves on CAIDA and Wikipedia will settle this, and we will report the result either way.

Why not just rely on write-back caches to hide writes? Cache eviction under large working sets still pushes dirty lines to memory, as the snapshot attack exploited. Enclave threat models also grant the host visibility of page-level and cache-line accesses. We treat cache behavior as out of scope and require traces to be independent of the data.

Proposed Experiments

The datasets are the CAIDA Equinix traces, the September 2007 Wikipedia page-access log (over 10M requests, 1.7M pages), synthetic Zipfian streams with exponent 0.8 and 1.0 (1M items), and AOL queries. The metrics are average relative error, heavy-hitter precision at the 97.5% target used by Ben Mazziane et al., and the weighted error used by Aamand et al., together with update throughput, query latency, footprint and enclave paging events.

The first decisive check is the residual-tail test. We would sweep the heavy-bucket threshold and measure $w_{\text{CMS}}/w_{\text{CU}}$ at fixed error. If the ratio falls below roughly 2 once OblivSketch-scale buckets absorb the heavy flows, the two-pass scan cannot beat one-pass alternatives, and the idea fails.

The second is the crossover plot. We would plot throughput against target error for scan-CU, scan-CMS, ORAM-CMS, ORAM-CU and oblivious CountSketch, and locate the widths where scans stop winning. We would also locate the stream sizes where each design leaves enclave memory.

The third is a leakage audit, reported with both a positive and a negative control. On the positive side, the classifier and mutual-information estimate should show that naive CU leaks heavy-hitter status. On the negative side, recorded address traces and DMA-style snapshot diffs for scan-CU should be identical across pairs of streams of equal length with different contents.