Rejection as an Oracle: Backdoor Evasion of Byzantine Filters in Decentralized Learning

When a system checks submitted work and answers yes or no, each answer carries information about the checker's internal state. Cryptographers have learned this the hard way: in verifiable outsourced computation, an untrusted worker who submits perturbed proofs and watches the verifier accept or reject can reconstruct the verifier's secret key and then forge proofs freely (Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers); in server-aided cryptography, observing success versus abort events prunes an adversary's key search space from $\mathcal{P}$ to $2\sqrt{\mathcal{P}}$ (Kim et al.). Machine learning is now rebuilding the same trap. In decentralized federated learning — training without a central server, coordinated by gossip between peers and smart contracts on a blockchain — defenses against poisoned updates work by checking each submitted update and rejecting the suspicious ones. Those verdicts are recorded on a public ledger, permanently, for everyone to read.

This proposal argues that this rejection stream is a query oracle for backdoor attackers, and that the oracle has a second, quieter port: the physical and timing side channels of the verification computation itself. A backdoored model — one that behaves normally on clean inputs but misbehaves when a secret trigger appears — is exactly the kind of attack these filters exist to stop, so the attacker has a strong incentive to probe them. We propose to formalize the oracle, measure how much it accelerates backdoor evasion in a realistic decentralized testbed, and design defenses that leak less without collapsing availability.

Core Claim

Consider the standard decentralized defense pattern exemplified by PPBFL, where edge nodes run a multi-party computation (MPC) — a protocol in which several parties jointly compute an answer without any one seeing the inputs — to compute the cosine similarity between each client update $\Delta_i$ and the aggregate $\bar{g}$, rejecting updates below a threshold $\tau$ on-chain (Privacy-Preserving Poisoning-Resistant Blockchain-Based Federated Learning). The same pattern appears in reputation ledgers that publish contribution scores (Transparent Contribution Evaluation for Secure Federated Learning on Blockchain) and in server-side representation filters like SABRE-FL (SABRE-FL). All of these publish, per round and per update, a bit or score computed against a secret reference (the hidden aggregate direction, or a hidden detector boundary).

Our claim is that this feedback is structurally identical to the pruning oracle of Kim et al.. Each probe update $\Delta$ submitted by the attacker yields the observation

$$f(\Delta) = \mathbb{1}\!\left[\cos(\Delta, \bar{g}) \ge \tau\right],$$

which is a membership query on a halfspace whose normal vector is the secret aggregate $\bar{g}$. After $q$ queries the attacker holds a feasible cone $C_q$ of aggregate hypotheses consistent with all observations, and can optimize a backdoor objective (à la constrain-and-scale, How To Backdoor Federated Learning) inside $C_q$ — sending poisoned updates that the filter provably cannot distinguish from honest ones, because the attacker knows exactly where the boundary lies. The halfspace structure means the feasible cone contracts geometrically in $q$, so we expect evasion in tens of queries, not thousands of rounds of blind trial and error.

Two things make this worse in decentralized settings specifically. First, verdicts are immutable and public on the ledger, so probing costs nothing but transaction fees and leaves a permanent training set for the attacker. Second, the verdict arrives twice: once logically on-chain, and once physically. The MPC verification runs on real hardware, and just as the re-encryption check in post-quantum key encapsulation leaks a plaintext-checking oracle through power and electromagnetic emissions even when the software comparison is constant-time (Curse of Re-encryption, Multiple-Valued Plaintext-Checking Side-Channel Attacks, Ueno et al.), the share-comparison step of the verification MPC leaks before the ledger publishes anything — an unlogged, unrate-limited query port. SNPeek showed that a hostile hypervisor can already read federated workloads inside "confidential" virtual machines at 497 kbit/s (SNPeek), and CSI Neural Network showed that power analysis alone recovers neural network weights and activations on edge hardware (CSI Neural Network), so the physics is not exotic.

Research Program

The work has three parts. First, the oracle model: we formalize the Byzantine filter as a membership-query oracle over a secret halfspace (cosine or norm filters) or a secret detector surface (representation filters), and derive query-complexity bounds for recovering the reference direction to within an angular error $\varepsilon$ sufficient for guaranteed evasion. This imports the pruning-oracle analysis of Kim et al. and the malicious-security analysis of leaking integrity checks in secret-shared shuffles (Secret-Shared Shuffle with Malicious Security), both of which proved that a binary validation signal collapses security, into the federated aggregation setting neither covers.

Second, the side-channel port: we instrument a PPBFL-style verification MPC and measure what leaks from its execution. The cheapest channel is timing — on-chain verification latency varies with how many shares fail the check, and every peer can observe block inclusion times without any hardware access. The richer channel is the power/EM signature of the share-comparison arithmetic, which we first emulate with a standard Hamming-distance power model (the model validated by CSI Neural Network) and then verify on a small FPGA target of the SAKURA-X class used by MaskedNet (MaskedNet). Following the multi-valued classifier methodology that cut required traces for key recovery by up to 87% in post-quantum KEM attacks (Multiple-Valued Plaintext-Checking Side-Channel Attacks, Tanaka et al.), we train a classifier to distinguish which client's share failed the check — information that tells the attacker which of its neighbors is near the boundary and where to probe next.

Third, the defenses. The obvious fix — never publish per-update verdicts — is insufficient because the attacker still sees the post-aggregation model, and because timing leaks predate publication. We design and evaluate three countermeasures: randomized delayed disclosure (verdicts for a random subset, published $d$ rounds late, so queries stop being attributable); constant-time MPC verification that removes the timing dependence; and query budgeting via stake, so probing has a price. We deliberately evaluate availability too, because the known alternative — abort and re-key on every failed verification (Non-Interactive Verifiable Computing) — is a denial-of-service invitation in asynchronous peer-to-peer networks, and the principled fix from verifiable computing (Delegation of Computation without Rejection Problem) needs non-standard assumptions and multi-level FHE, which is far too heavy for edge nodes.

Proposed Experiments

We build a decentralized testbed with DSGD and Swift gossip over ring and grid topologies, following DBA-DFL's setup, since that work established that backdoor propagation in serverless learning is exquisitely sensitive to the graph (DBA-DFL). Datasets: CIFAR-10, MNIST, and PathMNIST/OCTMNIST from MedMNIST v2 (MedMNIST v2), matching the evaluation suites of DBA-DFL, STRIP, and PPBFL respectively. The attacker injects backdoors via model replacement with constrain-and-scale (How To Backdoor Federated Learning), augmented by oracle-guided probe scheduling. Metrics: attack success rate (backdoor accuracy) at fixed clean accuracy, rounds-to-first-accepted-poisoned-update, query budget consumed, and — for the side channel — classifier accuracy on share-failure identification and traces required.

Experiment 1 (logical oracle) varies the feedback available to an otherwise identical attacker: full on-chain verdicts, aggregate-model-only feedback, and no feedback. The headline number is the ratio of queries-to-evasion between the full-verdict and no-verdict conditions; we predict an order-of-magnitude gap. Experiment 2 (timing channel) measures whether verification-latency leakage lets the attacker infer per-share verdicts before publication, defeating randomized disclosure. Experiment 3 (defense) measures the cost of each countermeasure in convergence rounds, final accuracy, and residual evasion rate, with MaskedNet's reported overheads (first-order DPA resistance up to 100,000 traces at a 2.8x latency and 2.3x area cost, MaskedNet) as the reference point for what hardware-level protection typically costs.

Baselines

The naive reference point is doing nothing: no Byzantine filter, attacker runs plain model replacement. How To Backdoor Federated Learning reports that 8 compromised clients out of 80,000 achieved 50% backdoor accuracy on the Reddit word-prediction task, persisting over 20 rounds after the attacker left — we will reproduce this regime on our datasets and topologies so the filter's added value and the oracle's subtraction from it are both measured against a known quantity.

The strongest existing defense competitor is the PPBFL-style on-chain cosine filter with MPC-protected updates (PPBFL), which reports maintaining classification accuracy over 50 iterations on PathMNIST and OCTMNIST under label-flipping poisoning while baselines like Krum were matched or beaten (no reported numerical accuracy value found on Lacuna for that setting, so we will re-run it ourselves). We implement it faithfully — same topology, datasets, rounds, and compute — and attack it two ways: with a static constrain-and-scale adversary that never reads feedback, and with our oracle-guided adversary under the same tuning budget and the same number of communication rounds. Beating the baseline means the oracle-guided attacker achieves higher backdoor accuracy at matched clean accuracy, or the same backdoor accuracy in far fewer rounds, than the static adversary against the same filter. If the static adversary already defeats the filter, the leakage story is moot for that filter class and we say so.

The strongest attack competitor is DBA-DFL's topology-aware clustered attack (DBA-DFL), the best documented backdoor attack in serverless learning; the file reports it consistently outperforms naive and centralized backdoor attacks on CIFAR-10 and MNIST but contains no numerical attack success rate, so again we re-run it. Crucially, DBA-DFL assumes cleartext communication and ignores verification entirely; running it against the cosine filter, with and without our oracle, isolates exactly what verification feedback adds on top of topology awareness.

Two ablations isolate the proposal's ingredients. First, the same oracle-guided attacker with verdicts hidden (aggregate-model feedback only) measures how much of the advantage comes from the explicit rejection bits rather than from ordinary model observation. Second, the same attacker with timing signals removed but verdicts published measures how much the pre-publication side channel adds over the ledger alone.

Why not just…?

Why not just use constrain-and-scale without any oracle? This is the most serious alternative, and we test it head-on rather than argue around it: the static-adversary baseline above is this attack. The case for expecting it to fall short is that constrain-and-scale needs to know what the anomaly detector penalizes; against a cosine filter whose reference direction is a secret, continuously re-estimated aggregate, the attacker is optimizing against a moving, unseen target, whereas the oracle converts that target into a learnable halfspace. But if the static adversary matches oracle-guided evasion on our testbed, that result stands and reframes the contribution toward the defense side — the timing channel and randomized-disclosure design would then carry the paper.

Why not just hide the rejection decisions? Simply not publishing verdicts is necessary but we expect it to be insufficient, for two reasons grounded in the file. The verdict is observable before publication through the verification computation's own leakage — the same lesson as the constant-time-comparison defeat in post-quantum KEMs, where uniform software responses did not stop the re-encryption power channel (Curse of Re-encryption) — and microarchitectural leakage persists even inside confidential VMs running federated workloads (SNPeek). And the published aggregate model is itself a feedback signal every round. Experiment 2 is designed precisely to quantify the residual channel under hidden verdicts; if it measures near zero, hiding decisions is the answer and we will report that.

Why not just study this on a centralized server (an adaptive attack on SABRE-FL)? It would be simpler, and SABRE-FL does leave exactly this adaptive-attacker gap open — but the centralized version omits everything that makes the problem distinctive: verdicts there are private server state with natural rate limits, not immutable public ledger entries; there is no MPC verification step with a timing channel; and there is a trusted operator who can re-key, audit, or throttle, whereas decentralized re-keying on failure is a denial-of-service vector (Non-Interactive Verifiable Computing). We will still run SABRE-FL's rejection mechanism as a filter variant, using its published numbers (backdoor accuracy 41.7% reduced to 1.1% on Flowers-102 and 93.9% to 7.6% on FGVC Aircraft) as a sanity anchor for our reimplementation, so the centralized question gets answered as a by-product rather than avoided.

Decisive Checks

Three outcomes would decide the proposal. If oracle-guided evasion needs no fewer queries than blind evasion across filters and topologies, the leakage claim is refuted. If hiding verdicts plus constant-time verification drives evasion back to blind levels at under, say, the 2.8x latency cost that hardware masking cost MaskedNet, then a practical defense exists and the contribution is the defense, not the attack. And if the timing channel on a real permissioned testnet leaks per-share verdicts with high classifier accuracy, then the field's current on-chain Byzantine filters are queryable oracles in the exact sense the verifiable-computation literature already understood — a connection nobody has yet made for decentralized machine learning.