Productive Hops: Hiding Who Contributed in Decentralized Learning by Aggregating Along Anonymous Walks

Decentralized learning replaces the central server in federated learning (training a shared model across devices that never upload raw data) with peer-to-peer exchange of model updates. It has two privacy leaks, and current work patches them separately. The first is a network leak: whoever watches traffic can trace an update back to the device that sent it. The second is a model leak: whoever holds an individual update can tell which device owns a given training record, because that device's local model fits the record best. Hiding the sender at the network layer is useless if the node that finally receives the update can still read the owner off the update itself. And the tools that hide the sender, such as random walks and "silent" relay hops, buy anonymity by adding latency that does no useful work.

We propose to make every relay hop do useful work. A message travels along a random walk, and each node it visits adds its own model update to a running sum before forwarding it. No curious node on the path, and no node at the end, ever sees a single device's update. Everything it sees is a sum over several contributors, and the walk's starting point is just one of those contributors. The hops that anonymity requires are also the aggregation that learning requires. The research question is how the trade-off between anonymity and round time changes when forwarding hops stop being pure overhead. We will measure that trade-off on non-IID learning tasks (tasks where each device's data follows a different distribution) against both network-layer and model-level attackers.

Core Claim

The closest prior work is Source Anonymity for Private Random Walk Decentralized Learning. It forwards each encrypted update along a random walk and chooses the walk's destination so that every node looks equally likely to be the source. Two things limit it. First, the destination decrypts one intact update, so a curious destination can run the source inference attack of Source Inference Attacks in Federated Learning directly on it. That paper shows the attack succeeds 55.2% of the time on CIFAR-10 and 75.1% on the Foursquare Location data under non-IID splits. Second, its anonymity comes from silent hops whose cost grows roughly linearly with the privacy level. It was also evaluated only through hitting-time entropy on synthetic regular graphs, with no training.

We claim that accumulating the updates along the walk removes both problems at once. Let a walk visit nodes $v_1, \dots, v_L$, and let the message after hop $j$ be

$$S_j = S_{j-1} + u_{v_j},$$

where $u_{v}$ is node $v$'s update, computed on the round's shared base model, and $S_0 = 0$. A curious node at hop $j$ sees only $S_{j-1}$, a sum over $j-1$ honest contributors. The attacker's natural question, "which device's model fits this record best?", then has a weaker answer: at most "someone among these $j-1$ devices."

One individual update can still leak. Two colluding nodes at hops $j$ and $j+2$ can subtract what they see and recover $u_{v_{j+1}}$ exactly. If a fraction $p$ of nodes collude and walks pick next hops roughly uniformly, a given honest contribution is sandwiched this way with probability on the order of $p^2$. This mirrors the $p^2$ precision floor that Dandelion: Redesigning the Bitcoin Network for Anonymity proves for its randomized "stem" forwarding phase.

A second variant closes this hole. Each node quantizes its update, splits it into $R$ additive shares modulo a large integer, and injects each share into a different walk. Any single share, and any partial sum missing at least one share of each contributor, is then uniformly random. The added cost is $R$ times the bandwidth. The proposal is therefore a two-knob mechanism, walk length $L$ and share count $R$, plus a measured frontier showing where each knob pays off.

This changes what is protected, not the known limits. On the Inherent Anonymity of Gossiping proves that any gossip protocol with $f$ curious nodes loses at least $\ln(f-1)$ in differential-privacy terms about who originated a message. We do not claim to beat that bound. Accumulating walks make "who originated this message" nearly irrelevant, because the originator is just the first of $L$ interchangeable contributors. The quantity we protect is who contributed a given record. The gossip bound does not directly apply to that quantity, and we will measure it empirically.

Research Program

The system runs in rounds. At the start of a round, a set of walks begins at uniformly random nodes, all using the current base model. Each visited node trains locally, adds its update to the walk's sum, and forwards the message to a neighbor chosen with the power-of-two-choices rule that Dandelion uses to keep stems line-like. After $L$ hops, the terminal node divides by the contributor count and broadcasts the averaged model to everyone.

Every hop performs the same work: receive, train, add, and forward a message of the same size. Hop timing therefore does not single out the starting node. This matters because the gossip bounds above break when the adversary observes a global clock.

In source-location-privacy terms, an eavesdropper who backtracks the traffic direction reaches the walk's start. That node is, as in phantom routing (A Survey on Intelligent Internet of Things: Applications, Security, Privacy, and Future Directions), a decoy relative to the data. Here, though, the decoy is a real contributor rather than wasted cover traffic. The cover-traffic approach in Improved Scheme for Data Aggregation of Distributed Oracle for Intelligent Internet of Things adds about 2 seconds per false request, which is the cost we are trying to avoid.

The analysis has three parts. First, we derive the sandwich-exposure probability as a function of $p$, $L$, and graph degree on regular and irregular graphs. Second, we adapt the source inference attack to partial sums. The attacker ranks candidate contributors by how much removing each one's shadow-estimated update changes the loss on the target record. We report attack success against the partial sum, against the final walk sum, and against sandwich-recovered updates. Third, we measure convergence. A walk sum averages over only $L$ clients per walk rather than all clients, so we expect the effect on non-IID convergence to depend on the number of walks per round. Decentralized Federated Learning: A Segmented Gossip Approach never tested non-IID data for gossip, so we measure this directly.

Baselines

The naive reference point is plain decentralized gossip that exchanges intact updates with neighbors. We implement it as Combo from Decentralized Federated Learning: A Segmented Gossip Approach, which reached about 82% final accuracy on CIFAR-10 and was 3.01 times faster than FedAvg to 80% accuracy with 40 workers over 10 Mbps links. It sets the speed ceiling and the privacy floor. We run it on the same graphs, data splits, and simulated bandwidth, with the same local-training budget per round.

The strongest existing route-anonymity method is the silent-hop random walk of Source Anonymity for Private Random Walk Decentralized Learning, using its optimized destination distribution and encryption to the destination. No reported accuracy or attack-success result was found on Lacuna for this method; it reports only source entropy and a near-linear latency-versus-anonymity relation. We therefore implement it ourselves and give it the same wall-clock budget per round. We beat it if, at matched round time, our attack success against a curious receiver is lower. Alternatively, at matched attack success, our round time should be lower.

The strongest existing model-level defense is the lossless bit-shuffling scheme of Protection against Source Inference Attacks in Federated Learning. It reduces source inference success from 50–80% to the 10% random-guess level for 10 clients, with zero accuracy loss and 1.04 to 1.8 times the communication. We run it with one designated node acting as a trusted, non-colluding shuffler. This gives it an advantage our setting does not grant, so we treat it as a privacy upper reference rather than a direct competitor. Our goal is to come within a few points of its attack success without the trusted party.

We also compare against local differential privacy, meaning noise each device adds to its update before sending. Source Inference Attacks in Federated Learning reports that it cut attack success on Location only from 75.1% to 55.1% while accuracy fell from 71.2% to 12.3%.

Two ablations isolate the key ingredient. The first keeps walk length, message size, and timing identical but makes the hops silent, forwarding the update without adding to it. The second toggles share splitting between $R=1$ and $R>1$ to measure what closing the sandwich hole costs and buys.

Why not just…?

Why not just add local differential privacy noise and send updates directly? The file's evidence here is direct. On Location, noise large enough to reduce attack success to 55.1% dropped accuracy to 12.3% (Source Inference Attacks in Federated Learning). Noise also leaves the traffic direction intact, so physical backtracking still works. We include this as a baseline to show the gap on our own splits.

Why not just send each update through Tor or a mixnet? Onion routing hides the sending address, but the receiver still gets one intact update, and the minimum-loss attack needs nothing else. Tor-style low-latency routing also remains open to timing correlation (Shirazi et al.). Our silent-hop ablation is effectively this design with idealized onion layers. If it matches our accumulating walks on attack success, our central claim is false.

Why not just use secure aggregation or the bit-shuffling defense? This is the real threat. When a trusted shuffler exists, Protection against Source Inference Attacks in Federated Learning is lossless and reaches random guessing. Our share-splitting variant is, in effect, additive secret sharing carried over walks. The case for our design rests on three things. It needs no trusted third party. It needs no all-pairs coordination among thousands of peers, and the file flags scaling beyond about 100 clients as unverified for the shuffling defense. It also hides network-layer origin, which cryptographic aggregation alone does not. Standard pairwise-masked secure aggregation over gossip has no reported result on Lacuna in this setting. We therefore implement a simple version and compare round time and robustness to dropouts at 300 nodes. If it wins on all three measures, the contribution reduces to the $R=1$ accumulation analysis, and we will say so.

Proposed Experiments

We use random regular graphs with 300 nodes and degree 4, matching the random-walk anonymity paper. We also use a Facebook social graph from the topologies used by Hiding the Rumor Source: Adaptive Diffusion for Anonymous Communication and X-Vine: Secure and Pseudonymous Routing in DHTs Using Social Networks, subsampled to the same size, to test irregular degrees. Links are simulated at 10 Mbps, as in Combo. Tasks are CIFAR-10 and Foursquare Location under Dirichlet non-IID splits, sweeping the concentration parameter downward, since source inference strengthens as data becomes more heterogeneous.

We report four quantities. The first is the success rate of source inference at curious nodes and receivers, compared against random guessing. The second is the precision of a network spy guessing the walk's originator. The third is test accuracy. The fourth is wall-clock time and bytes per round. We sweep walk length $L$, share count $R$, and colluding fraction $p$ from 0.01 to 0.2.

The decisive check is the comparison with the silent-hop ablation at identical traffic. If accumulation lowers source-inference success toward random guessing at $L$ around 8, while silent hops leave it near the unprotected 55.2% (CIFAR-10) and 75.1% (Location), the core claim holds. A second check fits the measured sandwich exposure against the predicted $p^2$ scaling; systematic deviation would show that graph structure matters more than the analysis assumes. A third check asks whether accuracy on the most skewed splits stays within one point of unprotected gossip. If it does not, the number of walks per round, not privacy, is the binding constraint.