Systems that write training updates to a tamper-proof public log are spreading. These are append-only ledgers, chained by cryptographic hashes, that let anyone check that nobody rewrote history. They are used to catch federated clients who poison the model or contribute nothing. Writing to such a log has a cost that is easy to miss. Every entry stays permanently readable by every future attacker, including attackers using inversion methods that do not exist yet. Most of these logged updates come from embedding layers, recommender item factors, or word embeddings, and those updates are sparse. Which rows are nonzero reveals what the client touched: the movies a user rated, or the words in a sentence. The values in those rows reveal the details, such as the ratings themselves.
We propose treating each logged client update as a key-value record. The key is which row was touched; the value is the update to that row. We then protect it with the correlated local perturbation methods built for key-value data collection, which randomize the key and the value together instead of adding independent noise to every coordinate. The claim to test is this: at matched privacy budget, a ledger of jointly perturbed key-value reports supports the audits these ledgers exist for (contribution scoring, poisoning detection, and owner verification) at least as well as independent-noise ledgers. It should also resist the two attacks that work against independent noise: reading the touched keys off the update's nonzero pattern, and denoising additive values with a learned generative model.
Core Claim
Three findings in the file motivate the reframing. Recovering Private Text in Federated Learning of Language Models (FILM) recovers a client's bag of words just by reading which word-embedding rows have nonzero gradients, then reorders the words with a language model. That attack works on the keys of the update and is unaffected by noise on the values. Gradient Diffusion: A Perturbation-Resilient Gradient Leakage Attack (Mjölnir) treats additive Gaussian or Laplace noise as the forward step of a diffusion process and learns to undo it, reaching 18.25 PSNR on CIFAR-100 at $\epsilon=1$, where plain inversion scores 0.112. Auditing Privacy Defenses in Federated Learning via Generative Gradient Leakage (GGL) shows that differential privacy noise, clipping, and even 90% sparsification leave enough signal for a GAN-guided search to recover recognizable images.
The closest system combining a ledger with leakage defense is Marking the Pace (LIBERATE). It hash-chains federated matrix-factorization updates and protects them with independent Laplace noise on ratings and factor gradients, which is exactly the perturbation class that FILM-style key reading and Mjölnir-style denoising exploit. Fine-Grained Traceability for Transparent ML Pipelines (FG-Trac) goes further. It commits per-sample influence trajectories, computed from loss-gradient inner products, to a Merkle-anchored log, and applies no perturbation at all.
Our proposal differs from both in what it changes. We alter the content of each log entry: a padded, sampled, jointly randomized key-value report replaces a dense noised vector or a raw signal. The hash chain stays as it is.
The method comes from PCKV. PCKV pads each user's item set to length $\ell$, samples one pair, and splits the privacy budget between key and value. It randomizes the value conditionally on what happened to the key, and proves this costs less privacy than perturbing the two independently (the "privacy discount"). Its estimates of key frequencies and value means are unbiased in a single round. It also reports 95% top-20 precision on MovieLens 20M with up to 250,000 keys, where older methods collapse. PrivKV supplies the earlier joint-perturbation design and its multi-round calibration.
Our contribution is to show that a federated update for sparse parameters is key-value data in PCKV's sense. Once it is reported this way, the ledger's audit queries become frequency and mean estimation problems over perturbed reports, and these have known error bounds. No paper in the file applies correlated key-value perturbation to gradients or to audit logs.
Research Program
The first component is an encoding. For a client in round $t$, the update to a sparse parameter block, such as item factors in matrix factorization or a word-embedding table, becomes a set of pairs $(k, v_k)$. Here $k$ is a row index and $v_k$ is that row's update, clipped to a norm bound and projected to a low-dimensional discretized value. A shared random projection per round turns the vector-valued rows into a few bounded scalars, which PCKV's value mechanism can handle. The client pads the set to $\ell$ pairs with dummy keys, samples one pair, or a fixed small number $m$, and applies PCKV's joint randomization. Dense, non-embedding parameters are handled by a separate, explicitly accounted mechanism, so the comparison isolates the sparse block. That block is where key leakage lives.
The second component is the server-side estimator and the audits it supports. The aggregator rebuilds an unbiased estimate of the summed update to each row from the perturbed reports, and the training step uses that estimate. The same reports, read from the ledger, answer three audit questions.
The first is per-client contribution: how much the client's reports move the estimated aggregate. The second is anomaly scoring for poisoning: whether a client's reported keys and values are statistically inconsistent with the population, tested using PCKV's known perturbation distribution. The third is owner verification: whether a data owner who knows their true items can confirm that their reports are consistent with honest participation.
Each audit has a computable false-alarm rate, because the randomization distribution is public. This is the property that makes perturbed logs auditable rather than merely noisy.
The third component is the ledger itself, built in the style of FG-Trac and LIBERATE. Reports are batched into a Merkle tree, a hash structure that lets anyone prove a single entry is included without revealing the others, and only the root is anchored on chain. Separately, each client commits to a hash of its raw update and its randomness seed. That commitment is opened only to a dispute-resolution auditor. Opening the seed publicly would reveal the noise and void the privacy guarantee.
This is a deliberately modest answer to the privacy-versus-verification tension that Towards Verifiable Federated Learning identifies in its survey. The public can verify integrity and the aggregate audits. Only a designated party can verify that perturbation was applied honestly. We do not claim zero-knowledge proofs of honest randomization.
The fourth component is privacy accounting for a permanent log. The adversary model is a "ledger adversary" who reads every round for a client and may later train new attacks. The ledger exposes all $T$ rounds of a client's reports. Under basic composition, the client's total local privacy loss is at most $T\epsilon_t$, where $\epsilon_t$ is the per-round budget. We report that cumulative figure, not the per-round one.
Sampling one of $\ell$ padded pairs per round matters here for a structural reason as well as for accounting. Under independent noise, each round re-exposes every touched row, so a ledger adversary can average a fixed row over $T$ rounds and shrink the noise roughly as $1/\sqrt{T}$, the usual rate for averaging independent errors. Under sampling, each row appears in only about $T/\ell$ rounds, and even then through a randomized key.
Baselines
The naive reference point is the unprotected ledger: raw sparse updates are hash-chained as FG-Trac does for its traced signals, with no perturbation. It fixes the ceiling on audit utility and on model quality, and the floor on privacy. We expect FILM-style key recovery to be near perfect here. Training uses the same model, data split, and number of rounds as every other arm.
The strongest existing competitor is LIBERATE: independent Laplace noise on ratings and factor gradients before a SHA-256 hash-chained log, evaluated on MovieLens 1M subsets. It is the only system in the file that combines an immutable training ledger with local perturbation against gradient inference, so it is the direct comparison. LIBERATE reports an NDCG of 0.865 with privacy enabled against 0.876 without, and 360 seconds of blockchain recording for 20 users and 90 items. For its resistance to inversion attacks, no reported result was found on Lacuna. We will measure that ourselves.
To keep the comparison fair, we re-implement LIBERATE's noise on the same matrix-factorization model and the same 10/40, 15/70, and 20/90 user/item subsets with its 80/20 split. Every arm is matched on cumulative privacy budget $T\epsilon_t$ and given the same hyperparameter search budget over learning rate, clipping bound, and budget split. Beating LIBERATE means matching its NDCG within its own 0.011 private-versus-non-private gap while cutting key-recovery F1 and denoised-value error substantially. Alternatively, it means achieving equal attack resistance at clearly higher NDCG.
A second strong competitor is clipped Gaussian noise on the full dense update, applied locally to every row whether touched or not. This hides the nonzero pattern by construction, which defeats FILM-style key reading. It pays for that by spreading noise over the whole table. It is run with the same accounting and tuning budget.
Three ablations isolate the key ingredient. In the first, keys and values are perturbed independently at the same total budget, which tests the privacy discount directly. In the second, padding is removed, which tests whether the length of the key set itself leaks. In the third, the full mechanism is kept but the ledger is replaced by ephemeral transmission, which measures how much the permanent multi-round view adds to the adversary's success.
Why not just…?
Why not just log hashes of updates and never their contents? This is the most serious alternative. If the only goal is tamper evidence, a ledger of commitments leaks nothing and costs less. Hash-only logging, however, cannot support third-party audits of contribution or poisoning: anyone running those audits has to see the raw updates and must be trusted with them. Our experiments compare a hash-only ledger plus a trusted auditor against our public perturbed ledger on the three audit tasks. If public audit accuracy turns out to be too low to be useful, the honest conclusion is that hash-only logging dominates. We would report that.
Why not just freeze the embeddings, as FILM itself suggests? FILM reports that freezing word embeddings keeps perplexity at 11.48 against 11.40 and cuts its recovery to zero. For language models this is a real threat to our proposal, so we include it as a baseline in the language extension and expect it may win there. In matrix-factorization recommenders, however, the item factors are the model, and freezing them removes the learning. The recommender setting is therefore where our claim stands or falls.
Why not just use secure aggregation or central differential privacy and log only the round aggregate? That hides individual updates, but it also destroys the per-client record that ledgers are deployed to provide, because free-riding and poisoning are per-client properties. We include a log of aggregates only as a reference arm. Our expectation is that per-client anomaly detection then falls to chance, and the experiment checks this.
Why not just add more independent noise? Mjölnir is built to remove additive noise of known form. More independent noise does nothing about the nonzero-row pattern FILM reads unless it is spread over the full table, which is the dense Gaussian baseline above. Whether joint randomization beats that baseline at matched utility is the central empirical question.
Proposed Experiments
The primary testbed is federated matrix factorization on MovieLens 1M. We use LIBERATE's subsets for a direct comparison, then scale to full MovieLens 1M and to MovieLens 20M, where PCKV's 250,000-key regime tests whether padding-and-sampling keeps utility at catalog scale. Utility is measured by NDCG and RMSE.
The attacks follow the leakage literature. Key recovery is FILM-style reading of nonzero rows, extended to pool every round of a client's ledger entries; we score it by precision and recall of the client's rated items. For value recovery, a Mjölnir-style diffusion denoiser is trained on clean surrogate updates from a disjoint user pool, and we score rating RMSE after denoising. A rating-attribute attack scores how well the recovered keys and values predict held-out sensitive user attributes.
Audit quality is measured by three things: correlation of estimated contribution with ground-truth contribution, AUROC for flagging injected poisoning and free-riding clients, and the false-alarm rate of owner verification. We also report ledger storage, hashing time against LIBERATE's 360 seconds, and the cost of each training round.
A secondary language extension runs GPT-2 on WikiText-103 and Enron using the Princeton-SysML/FILM code, with the embedding table as the key-value block. FILM reports ROUGE-L near 1.0 at batch size 1. We measure how far joint perturbation pushes this down at fixed perplexity cost, alongside the frozen-embedding baseline.
The decisive check is a curve of privacy against utility at matched cumulative budget, comparing joint and independent perturbation, both read through a ledger adversary. If joint perturbation does not dominate independent perturbation on both key-recovery F1 and denoised-value error at equal NDCG, the privacy discount does not carry over to gradients, and the core claim fails. If the gap between the ephemeral and ledger arms is large for independent noise and small for ours, that would confirm the specific reason permanence matters.
References
- Recovering Private Text in Federated Learning of Language Models
- Mjölnir: Breaking the Shield of Perturbation-Protected Gradients via Adaptive Diffusion
- Auditing Privacy Defenses in Federated Learning via Generative Gradient Leakage
- Marking the Pace: A Blockchain-Enhanced Privacy-Traceable Strategy for Federated Recommender Systems
- Fine-Grained Traceability for Transparent ML Pipelines
- PCKV: Locally Differentially Private Correlated Key-Value Data Collection with Optimized Utility
- PrivKV: Key-Value Data Collection with Local Differential Privacy
- Towards Verifiable Federated Learning