Differential Privacy-Based Online Allocations towards Integrating Blockchain and Edge Computing

Jianxiong Guo, Weili WuarXiv 2021 · DOI · arXiv · OpenReview

TL;DR

This paper tackles the challenge of allocating limited edge computing resources to blockchain-enabled IoT devices. They propose a novel online auction mechanism that ensures truthful bidding, fair allocation, and crucially, protects user privacy using differential privacy. This work is significant for building more secure and efficient decentralized IoT ecosystems.

What Problem Does This Paper Address?

The Internet of Things (IoT) is rapidly expanding, with devices increasingly leveraging blockchain for decentralized operation. However, many IoT devices are "lightweight" and lack the computational power for blockchain consensus or other demanding tasks. Edge computing offers a solution by providing nearby servers to handle these computations. The core problem this paper addresses is how to fairly and securely allocate these limited edge computing resources to IoT devices in a highly untrustworthy environment. Existing solutions often struggle to balance the need for truthful participation, efficient resource allocation, and, critically, the privacy of users' bidding information, which can be exploited through inference attacks.

Methods

The authors introduce a Multi-Item Double Auction (MIDA) mechanism. In this model, IoT devices seeking computing power act as buyers, and edge servers offering this power act as sellers. The auction is designed to be:

  • Online: Allocations are made in real-time, round-by-round, reflecting the dynamic nature of the system.
  • Truthful: Participants are incentivized to bid their true valuations (buyers) or ask their true costs (sellers).
  • Privacy-Safe: This is a key innovation. They integrate differential privacy into the auction process. This involves adding carefully calibrated noise to sensitive information (like median ask prices) to prevent adversaries from inferring individual participants' private bids or asks, even if they observe auction outcomes over multiple rounds.

They also propose two variants:

  • MIDA-G: A more general version that allows edge servers to serve multiple devices (many-to-one mapping), making it more realistic than the initial one-to-one mapping.
  • MIDA-DP (and MIDA-G-DP): These are the differentially private versions of MIDA and MIDA-G, respectively, incorporating the Laplace mechanism for noise injection.

Datasets

Not discussed in the paper. The authors use simulated scenarios for evaluation.

Key Insights and Ideas

  • The Auction as a Solution: Framing resource allocation as a double auction elegantly captures the competitive dynamics between IoT devices and edge servers.
  • Truthfulness is Key for Fairness: Without truthful bidding, the system can be manipulated, leading to unfair outcomes and potentially undermining the blockchain's integrity.
  • Inference Attacks are a Real Threat: Observing auction results over time can reveal private bidding strategies, allowing adversaries to gain an unfair advantage.
  • Differential Privacy as a Shield: Applying differential privacy, specifically through the Laplace mechanism, effectively masks individual bids/asks without completely destroying the auction's integrity or significantly impacting social welfare.
  • Trade-off Between Privacy and Welfare: The degree of privacy protection (controlled by the privacy budget, ε) directly influences the social welfare achieved. A stronger privacy guarantee leads to a slight reduction in overall efficiency.
  • MIDA-G for Realism: The generalization to a many-to-one mapping (MIDA-G) is crucial for accurately modeling real-world scenarios where edge servers can handle multiple requests.

Key Results

  • Theoretical Guarantees: The proposed MIDA and MIDA-G mechanisms are proven to be individually rational, budget-balanced, computationally efficient, and truthful.
  • Privacy Protection: The MIDA-DP and MIDA-G-DP mechanisms are shown to provide ε-differential privacy for sellers' asks, and by extension, protect buyers' privacy.
  • Simulation Performance:
    • Figures 2-3 demonstrate the truthfulness and individual rationality of the MIDA mechanism in a simplified scenario.
  • Figure 4 shows that MIDA-DP achieves social welfare close to MIDA, with the gap narrowing as the privacy budget (ε) increases.
  • Figure 5 illustrates the online performance, showing that social welfare decreases over time due to resource constraints, with smaller privacy budgets leading to larger welfare fluctuations.
  • Figure 6 indicates that MIDA-G significantly improves social welfare compared to MIDA due to its more flexible assignment.
  • Figure 7 shows that MIDA-G also converges faster in online scenarios.

Limitations and Future Work

  • Privacy-Welfare Trade-off: The paper acknowledges the inherent trade-off between the strength of privacy protection and the achieved social welfare. Future work could explore more sophisticated privacy mechanisms that minimize this trade-off.
  • Dynamic Environments: While the mechanisms are online, the simulations primarily focus on static scenarios within each time slot. Further investigation into highly dynamic environments with frequent changes in device availability or server capacity could be beneficial.
  • Adversary Sophistication: The paper focuses on inference attacks based on auction outcomes. Exploring defenses against more complex adversarial models might be necessary.
  • Scalability: While computationally efficient, the scalability of the proposed mechanisms with a massive number of IoT devices and edge servers could be a subject for future research.

Summary updated

Abstract

In recent years, the blockchain-based Internet of Things (IoT) has been researched and applied widely, where each IoT device can act as a node in the blockchain. However, these lightweight nodes usually do not have enough computing power to complete the consensus or other computing-required tasks. Edge computing network gives a platform to provide computing power to IoT devices. A fundamental problem is how to allocate limited edge servers to IoT devices in a highly untrustworthy environment. In a fair competition environment, the allocation mechanism should be online, truthful, and privacy safe. To address these three challenges, we propose an online multi-item double auction (MIDA) mechanism, where IoT devices are buyers and edge servers are sellers. In order to achieve the truthfulness, the participants' private information is at risk of being exposed by inference attack, which may lead to malicious manipulation of the market by adversaries. Then, we improve our MIDA mechanism based on differential privacy to protect sensitive information from being leaked. It interferes with the auction results slightly but guarantees privacy protection with high confidence. Besides, we upgrade our privacy-preserving MIDA mechanism such that adapting to more complex and realistic scenarios. In the end, the effectiveness and correctness of algorithms are evaluated and verified by theoretical analysis and numerical simulations.
BibTeX
@misc{guo2021differential,
  author = {Jianxiong Guo and Weili Wu},
  title = {{Differential Privacy-Based Online Allocations towards Integrating Blockchain and Edge Computing}},
  year = {2021},
  eprint = {2101.02834},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.02834},
}
Figure