An adversarially robust data-market for spatial, crowd-sourced data

Aida Manzano Kharman, Christian Jursitzky, Quan Zhou, Pietro Ferraro, Jakub Marecek, Pierre Pinson, Robert Shorten

TL;DR

This paper introduces a hybrid data-market architecture designed specifically for crowd-sourced spatial data, such as vehicle sensor networks in smart cities. By combining centralized identity verification with decentralized consensus and an adaptive, "useful" proof-of-work mechanism based on game theory, the system ensures fair participant compensation while remaining highly resilient against Sybil, wormhole, and data poisoning attacks.

What Problem Does This Paper Address?

As industries shift toward data-driven business models, traditional centralized platforms (like Google Maps) often harvest user data without direct, fair compensation or robust privacy guarantees. Conversely, fully decentralized alternatives like traditional blockchains introduce their own flaws: massive energy waste from Proof-of-Work (PoW), transaction fees that favor wealthier users, and a tendency to centralize over time.

Furthermore, crowd-sourced spatial data is uniquely vulnerable to malicious manipulation. Attackers can spoof multiple identities (Sybil attacks), fake their geographic locations (wormhole attacks), or collude to upload fraudulent measurements (data poisoning). The authors address the challenge of building a data marketplace that is decentralized in its core operations, guarantees fair rewards based on data utility, and can withstand adversarial environments.

Methods

The authors propose a hybrid architecture that splits tasks between centralized and decentralized infrastructures:

Figure 1. Data Market Architecture. Credit for the images is given in 3
  • Verification (Centralized): A trusted authority uses a Proof-of-Position (PoP) mechanism and identity checks (like vehicle license plates) to issue validity tokens. This stops Sybil and wormhole attacks at the gate.
  • Voting Scheme (Decentralized): To select a committee to aggregate data, the paper introduces Combination-MEV (C-MEV), a novel, iterative variant of Maximum Entropy Voting. C-MEV drastically reduces the factorial computational complexity of standard MEV by selecting groups of preferred candidates sequentially rather than evaluating every possible permutation.
Figure 2. Example of an election performed with C-MEV with parameters J = 3, K = 3.
  • Data Consensus (Decentralized): The elected committee uses a privacy-preserving mean-median algorithm to filter out faulty sensors and malicious outliers without exposing individual raw data points to competitors.
  • Useful, Adaptive Proof-of-Work: Instead of burning energy on useless cryptographic puzzles, participants must perform "useful" work: computing the Shapley value (a game-theoretic measure of marginal contribution) for the next batch of incoming data. Crucially, the amount of work required is inversely proportional to the quality of the data the user contributes—high-value data requires minimal PoW, while spam data becomes prohibitively time-consuming to list.

Datasets

To demonstrate the architecture, the authors utilize a real-world air quality dataset from India, originally provided by the Central Pollution Control Board (accessed via Kaggle).

The dataset includes measurements of various pollutants (PM2.5, PM10, NO2, CO, etc.) across multiple cities. The authors use this data to train a linear regression model that predicts the Air Quality Index (AQI). This model serves as the market's "objective function" to calculate the Shapley values of individual data contributions. Synthetic data is also generated to run Monte Carlo simulations for evaluating the system's breakdown points under data poisoning attacks.

Key Insights and Ideas

  • PoW Doesn't Have to Be Wasteful: By turning the security mechanism into the actual computational workload required to maintain the market (calculating data utility for others), the system eliminates the environmental downside of traditional blockchains.
  • Economics as a Defense: Tying PoW difficulty to data value creates a natural economic barrier against spam. If an attacker attempts a data poisoning attack with low-utility fake data, they are penalized with an immense computational burden.
  • The Pragmatic Hybrid Approach: Purely decentralized systems struggle with identity verification. By using a centralized verifier solely for initial identity/location checks while keeping data aggregation, consensus, and transactions decentralized, the architecture achieves both security and trustlessness where it matters most.

Key Results

  • High Breakdown Point: Monte Carlo simulations demonstrate that combining the reputation-based C-MEV voting scheme with the mean-median consensus algorithm significantly boosts robustness against data poisoning.
  • Collusion Resistance: In a network with a functional reputation system, a malicious coalition must control between 40% and 60% of the entire network to successfully alter the agreed-upon dataset.
  • Computational Efficiency: The iterative C-MEV algorithm successfully scales candidate selection, making reputation-based voting computationally feasible for large crowd-sourcing networks.

Limitations and Future Work

  • Centralized Identity Trust: The initial verification phase still relies on a centralized authority to validate real-world identities (e.g., license plates). The authors note that exploring fully decentralized proofs of identity is a key direction for future work.
  • Reputation System Dependency: The market's high resilience to data poisoning assumes the existence of a functional, rational reputation system. If the underlying reputation metrics are successfully gamed, the practical breakdown point of the consensus mechanism degrades.

Summary updated

Abstract

We describe an architecture for a decentralised data market for applications in which agents are incentivised to collaborate to crowd-source their data. The architecture is designed to reward data that furthers the market's collective goal, and distributes reward fairly to all those that contribute with their data. We show that the architecture is resilient to Sybil, wormhole, and data poisoning attacks. In order to evaluate the resilience of the architecture, we characterise its breakdown points for various adversarial threat models in an automotive use case.
BibTeX
@article{kharman2022adversarially,
  author = {Aida Manzano Kharman and Christian Jursitzky and Quan Zhou and Pietro Ferraro and Jakub Marecek and Pierre Pinson and Robert Shorten},
  title = {{An adversarially robust data-market for spatial, crowd-sourced data}},
  journal = {Distributed Ledger Technol. Res. Pract.},
  year = {2022},
}
Figure