Skip to content
Crypto.world

Research

Bernoulli CUSUM and Bayes-Optimal Detection Ceilings for Trust Fraud in Sparse Rating Networks

Trust systems on Bitcoin trading platforms rely on ratings to decide whether a trader is honest or fraudulent, and prior work has applied sequential change-point detectors (CUSUM) that assume ratings…

Bernoulli CUSUM and Bayes-Optimal Detection Ceilings for Trust Fraud in Sparse Rating Networks
arXiv
2606.05090
Published
2026-06-03
Authors
Talal Ashraf Butt

AI summary

Overview

Research area: Cryptography and Security — specifically trust and fraud detection in signed rating networks (Bitcoin-OTC, Bitcoin-Alpha), drawing on sequential change-point detection from statistical process control.

Technical level: Intermediate. The paper uses a small amount of statistical machinery (CUSUM recursions, KL divergence, Bayes-optimal classification) but presents each piece with enough plain-language framing that a reader comfortable with basic probability can follow the argument.

Scope: The paper diagnoses why continuous observation models fail on sparse, point-mass-heavy rating data, derives an information-theoretic ceiling on achievable F1 for per-node sequential detectors, and proposes a dual-regime Bernoulli CUSUM architecture that operates within that ceiling.

What This Paper Is About

Trust systems on Bitcoin trading platforms rely on ratings to decide whether a trader is honest or fraudulent, and prior work has applied sequential change-point detectors (CUSUM) that assume ratings arrive as smooth, continuous values. The author shows that this assumption is categorically false on real data: 56% of the 35,592 Bitcoin-OTC ratings equal +1, and the standard linear mapping to [0, 1] piles that mass into a single point at 0.55, breaking the parametric assumptions of every continuous detector tested. The goal is to explain why unsupervised trust detection has stagnated near F1 ≈ 0.4 for years, and to build a detector whose observation model actually matches the data.

Key Contributions

  1. A Bayes-optimal F1 detection ceiling. The paper derives an upper bound on the F1 score achievable by any per-node sequential detector operating on Bernoulli observations with known pre- and post-change parameters, and evaluates it using empirically measured — not attack-specified — observation parameters. At Bitcoin-OTC's median in-degree of 2, the ceiling falls to 0.451 for strategic attacks.

  2. A detector-model matching diagnosis. The paper documents for the first time that 56% of Bitcoin-OTC ratings collapse to a single mapped value under standard normalization, and shows that detection performance is governed by the match between the observation model and the detector's distributional assumptions rather than by raw mutual information content.

  3. A dual-regime Bernoulli CUSUM architecture. Bernoulli CUSUM monitors the binarized rating stream and, on alarm, switches an exponential moving average trust score into an asymmetric decay regime. The combined system reaches AUC 0.749 on Bitcoin-OTC and 0.796 on Bitcoin-Alpha.

  4. An ablation exposing a co-design constraint. Binarization and CUSUM-triggered modulation are not independently substitutable: the same modulation that adds +0.030 AUC on binary observations removes 0.094 AUC on continuous observations.

Main Findings

  • A single value dominates the benchmark. Of 35,592 Bitcoin-OTC ratings, 56% take the value +1, with a secondary concentration at −10. The standard mapping r ↦ (r + 10)/20 places the +1 spike at 0.55, so one value holds more than half the probability mass. The paper describes the Gaussian assumption continuous CUSUM requires as "categorically wrong" rather than approximately wrong on this data.

  • The F1 ceiling explains a decade of stagnation. At median in-degree 2, the Bayes-optimal ceiling is 0.451 for strategic attacks. Unsupervised methods on Bitcoin-OTC have clustered at F1 ≈ 0.3 to 0.4 for years, and the paper argues the constraint is informational, not algorithmic — no per-node detector can fix a per-node Bayesian error rate that dominates at n = 2.

  • Community amplification raises the ceiling. Empirical observation parameters diverge sharply from attack specifications because honest evaluators independently react to adversary behavior. For bad_mouth, the specified p₁ = 0.85 drops to an empirically received p₁ = 0.503, and honest p₀ falls from 0.900 to 0.731. This raises KL divergence from 0.003 nats to 0.111 nats — a 37-fold increase — and lifts the bad_mouth ceiling from 0.333 (specification-based) to 0.414 (empirical).

  • Binary models sacrifice little information but extract far more. For strategic attacks, the continuous model retains 0.038 bits of mutual information and the binary model 0.033 bits, a 14% sacrifice. The binary model therefore retains 86% of MI — and, critically, Bernoulli CUSUM's parametric assumptions are satisfied exactly, activating Moustakides' minimax optimality guarantee in full. Gaussian CUSUM's log-likelihood ratio cannot accumulate consistently against a point mass.

  • KL structure predicts per-attack performance. For always_lie (p₁ = 0.10), binary KL reaches 1.75 nats versus 0.18 nats continuous — nearly 10×. For colluding (p₁ = 0.60), the binary advantage narrows to 0.31 versus 0.18 nats. A crossover occurs at bad_mouth and on_off, where p₁ approaches p₀ and the continuous model retains more discriminability — exactly the attacks where BernoulliCUSUM's per-attack advantage shrinks.

  • Headline detection results. BernoulliCUSUM reaches mean AUC 0.749 on Bitcoin-OTC across 8 attacks and 10 seeds, versus GaaSTrust 0.704, BTGAggDA-Cal 0.562, SimpleMean 0.558, and REV2 0.554. It is highest on all 8 attacks after Holm–Bonferroni correction, seven at p < 0.0001 and strategic at p = 0.003, with Cliff's δ ≥ 0.620.

  • Per-attack margins. The widest margin is bad_mouth at +0.134 (0.683 vs 0.549), where the adversary's negative ratings toward honest nodes create a clear binary signature. The narrowest is strategic at +0.016 (0.685 vs 0.670), where 70% honest behavior makes the binary signal weakest. Always_lie shows +0.034 (0.949 vs 0.915, Cliff's δ = 1.000).

  • Generalization and organic labels. Bitcoin-Alpha yields AUC 0.796 versus GaaSTrust 0.748, with the same attack ordering (bad_mouth largest margin, always_lie smallest). On the organic founder-label evaluation without synthetic injection, BernoulliCUSUM reaches AUC 0.999, versus GaaSTrust 0.998 and REV2 0.633.

  • Efficiency degrades as nodes get well observed. BernoulliCUSUM achieves 95.1% of the Bayes-optimal ceiling at median in-degree 2 (achieved F1 0.545 against a bin ceiling of 0.573), but only 76.2% at median in-degree 19 (0.672 against 0.883), where the ceiling rises faster than detection improves.

  • Regime crossover. On Balanced, High-variance, and Uniform synthetic profiles, continuous CUSUM (BTGAggDA-Cal) dominates; on Bimodal 80/20, BernoulliCUSUM wins across all four attacks tested. On the intermediate Bimodal 70/30 profile, GaaSTrust is competitive with both. The paper's operational rule: if more than 50% of observations map to a single value, deploy Bernoulli CUSUM; otherwise continuous CUSUM.

  • The co-design constraint is non-decomposable. Binarization alone (binary EMA, no CUSUM) gives +0.015 AUC (0.719). Dual-regime modulation on binary data adds +0.030, for +0.045 combined. The raw CUSUM statistic as a stand-alone score reaches 0.720, comparable to binary EMA. Applying the same modulation to continuous observations drops AUC from 0.704 to 0.610, a −0.094 swing. The interaction swing (+0.124) exceeds either component's individual contribution.

  • AUC is preferred over F1 for a structural reason. SimpleMean posts F1 = 0.400 at the default threshold versus BernoulliCUSUM's 0.309, and GaaSTrust reaches 0.524 at its own optimal threshold versus BernoulliCUSUM's 0.496. Both comparisons mislead: SimpleMean's wider score spread buys threshold-dependent F1 despite AUC 0.558, roughly 0.2 below BernoulliCUSUM's 0.749. Deployment ranks nodes rather than making fixed-threshold accept/reject calls.

  • CUSUM adds a detection-delay guarantee, not just ranking. Among adversary nodes that accumulate enough observations to reach threshold, CUSUM flags them in a median of 3 observations (on_off) to 18 (bad_mouth). On_off triggers fastest because adversarial phases produce concentrated bursts of negative ratings. At Bitcoin-OTC's sparse in-degree, only 19–59% of adversary nodes receive enough ratings for CUSUM to fire, so the architecture splits the task: CUSUM handles well-observed nodes with formal optimality, EMA handles sparse nodes with best-effort ranking.

  • Rater-relative binarization fails. Of 4,814 unique raters, only 45.7% have three or more ratings. Rater means have a standard deviation of 2.140 on the raw [−10, +10] scale (0.117 mapped), indicating homogeneity. Per-rater baselines are unreliable at this sparsity, and the resulting detector reaches AUC 0.596. A separate per-evaluator monitoring stream improves bad_mouth marginally but reduces founder-label AUC from 0.999 to 0.971.

Methodology in Plain English

The author starts with the standard trust-detection benchmark, Bitcoin-OTC, and a specific question nobody had asked: what does the rating distribution actually look like after the usual normalization step? Plotting it reveals a dominant spike at +1 that lands at 0.55 under linear mapping, which immediately explains why detectors built for smooth bell-shaped data struggle.

From there, the argument is set-theoretic. If each node's label is fixed, ratings are independent coin flips with an honest positive rate p₀ and an adversary positive rate p₁, and the detector sees only that node's own ratings, then the best possible classifier is the one that ranks by posterior probability given the count of positive ratings. That gives a computable F1 ceiling for any number of observations n — which the author plots, marking Bitcoin-OTC's median in-degree of 2 with a vertical line.

A subtle but important move is measuring the observation parameters after injection rather than using the attack design values. Honest traders react to adversaries — downrating bad_mouth's mediocre output, for instance — so the positive rate an adversary actually receives differs from what it emits. Using these empirical parameters makes the ceiling reflect the real detection problem rather than the idealized one.

The proposed detector is then deliberately minimal. Every rating becomes a 1 if positive and 0 otherwise. A Bernoulli CUSUM runs per target node, accumulating a two-valued log-likelihood ratio and resetting to zero whenever it would go negative. When the statistic crosses a threshold of 3.0, the node is permanently flagged, and the exponential moving average that produces the final trust score switches from a symmetric decay of 0.10 into an asymmetric regime that weights negative evidence at 0.30 and positive recovery at 0.05, with flagged scores capped at 0.30. All parameters are fixed globally with no per-attack tuning.

Evaluation injects adversaries onto the real network topology, replacing 20% of nodes with agents following one of eight strategies, and runs 10 random seeds per configuration. Significance is assessed with bootstrap confidence intervals over 10,000 resamples and Holm–Bonferroni correction, with Cliff's δ reported as an effect size. An ablation then separates the contribution of binarization from the contribution of CUSUM-triggered modulation, and a synthetic regime-crossover study sweeps six distributional profiles to find where the method should and should not be used.

Why This Matters

Impact on research. The paper reframes a decade of mediocre unsupervised results on Bitcoin-OTC as an information-theoretic limit rather than a modeling failure, and supplies a ceiling that future methods can be measured against. It also introduces a cross-disciplinary transfer that had not been made: Bernoulli and categorical CUSUM are mature tools in statistical process control and public-health surveillance, but the paper states that no prior work has applied them to trust fraud detection. The co-design finding — that an adaptation mechanism can help on one observation model and harm on another — is a general caution for sequential monitoring system design.

Real-world applications:

  • Peer-to-peer trading and escrow platforms (Bitcoin-OTC, Bitcoin-Alpha style) that must rank counterparties by trustworthiness without labeled fraud data.
  • Marketplace and review-platform integrity teams deciding whether a seller or reviewer has shifted behavior, where rating distributions are similarly skewed toward a single modal value.
  • Reputation systems in decentralized or federated networks, where per-node evidence is sparse and supervised labels are unavailable.
  • Clinical and operational monitoring, where Bernoulli CUSUM already has an established track record (surgical outcome monitoring) and shares the structural features of sparse binary observations, a known in-control rate, and controlled false alarms.

Industry relevance. The method runs in a single temporal pass with O(|E|) time and O(|V|) memory, completing Bitcoin-OTC's 35,592 edges and 5,881 nodes in under a second on one CPU core with no per-attack retuning. The regime-selection rule (>50% single-value mass) is a cheap pre-deployment check that tells an engineering team which detector family to use before any tuning begins.

Future Directions

  • Closing the gap on well-observed nodes. Efficiency falls to 76.2% of the ceiling at median in-degree 19. The author proposes a Bayesian posterior update that weights all observations uniformly instead of exponentially discounting early evidence, which should approach the bound more tightly.
  • Designing for community amplification. Because honest evaluators' independent reactions raised empirical KL divergence up to 37× over specification parameters, the paper suggests rating-interface design that encourages strong negative opinions when warranted could widen the p₀–p₁ gap and directly lift the ceiling.
  • Adaptive adversaries. The evaluation uses static injection where each agent follows a fixed strategy start to finish. An adversary that monitors its own trust score and throttles behavior to stay below threshold is flagged as a harder, unaddressed problem.
  • An online regime classifier. Boundaries between the Bimodal 70/30 and 80/20 profiles are not crisp, and no single detector dominates in that zone. A real-time classifier that selects the observation model per stream has not been built.
  • Testing the co-design constraint elsewhere. Whether observation model and detection architecture are similarly entangled in other sequential monitoring domains remains open.

Target Audience

Researchers and practitioners in trust-and-reputation systems, fraud detection on signed networks, and sequential change-point analysis — particularly those who have worked with Bitcoin-OTC or Bitcoin-Alpha and wondered why unsupervised scores plateau. It is also useful for platform integrity engineers who need a deployment-ready, distribution-aware detector with a defensible false-alarm story, and for statisticians interested in a concrete case study of what happens when an SPC method is applied outside the distributional regime it was designed for. Readers seeking a graph-neural-network or supervised approach to trust prediction should note that this paper deliberately solves a different problem: detecting behavioral change in nodes, without labeled training data.

Authors’ abstract

Sequential trust detection in rating networks relies on continuous observation models that fail on real data. On Bitcoin-OTC, 56\% of ratings take a single value under standard mapping, breaking the distributional assumptions that parametric detectors require. This paper makes three contributions. It derives a Bayes-optimal F1 detection ceiling for per-node sequential detectors using empirically measured observation parameters. At Bitcoin-OTC's median in-degree of 2, this…

The full abstract on arXiv
Read the original paper