TL;DR
This paper introduces MODiCuM, a decentralized market for outsourcing computation to idle devices. It tackles the challenge of ensuring fair play in a trustless environment by using smart contracts, partially trusted mediators, and a system of rewards and fines, all while minimizing computational overhead. This approach aims to unlock the vast potential of edge computing resources for more competitive and efficient computation.
What Problem Does This Paper Address?
The proliferation of personal and IoT devices has led to an explosion of available, yet often idle, computational power at the edge. While volunteer computing projects like BOINC harness some of this power, they are typically centralized, limiting participation and pricing control. The authors envision a decentralized, open market where resource owners and users can trade computational services directly. However, creating such a market faces a significant hurdle: preventing malicious actors from misbehaving (e.g., providing incorrect results, not completing jobs) in a trustless, decentralized setting. Existing decentralized solutions often incur substantial computational overhead for verification. This paper aims to bridge this gap by proposing a system that incentivizes honest behavior and efficiently resolves disputes without requiring global consensus on every computation.
Methods
MODiCuM is built upon a decentralized architecture involving several key components:
- Smart Contract: The backbone of the system, enforcing protocol rules, managing deposits, and facilitating payments.
- Job Creators (JC): Users who need computation performed and post job offers.
- Resource Providers (RP): Owners of idle computational resources who offer their services.
- Mediators: Partially trusted third parties responsible for resolving disputes when JCs and RPs disagree on job results.
- Solvers: Services that find compatible matches between JC and RP offers.
- Directories: Network storage services for job and result transfer.
The core innovation lies in MODiCuM's approach to dispute resolution and misbehavior deterrence:
- Partially Trusted Mediators: Instead of relying on global consensus for every verification, MODiCuM uses mediators to settle disputes. This significantly reduces computational overhead.
- Verification of Random Subsets: To keep verification costs low, the system verifies random subsets of results, making it efficient for a wide range of jobs.
- Incentive Mechanism (Rewards and Fines): Participants are required to provide security deposits. Misbehavior is deterred through enforceable fines, while honest behavior is rewarded.
- Game-Theoretic Analysis: The authors model the interactions between JCs and RPs as a game to analyze participant behavior and derive optimal strategies, ensuring that rational agents are incentivized to act honestly.
Datasets
Not discussed in the paper. The evaluation uses a simulated environment and experimental setup with a custom benchmark.
Key Insights and Ideas
- Decentralized Markets Can Be Efficient: The paper demonstrates that a decentralized market for computation can be designed to be computationally efficient by moving away from global consensus for every verification.
- Mediators as a Scalable Solution: Using partially trusted mediators for dispute resolution is a key insight that allows for scalability, avoiding the bottlenecks of fully decentralized verification.
- Deterrence Over Detection: The focus is on deterring misbehavior through economic incentives (fines and rewards) rather than solely on detecting every instance of cheating.
- The Importance of Job Design: The authors highlight that for this system to work, jobs must be deterministic and isolated. They also discuss how non-deterministic jobs can be handled by recording their specific outputs.
- Rational Agents and Nash Equilibrium: The game-theoretic analysis reveals that with carefully chosen parameters, a Nash equilibrium can be achieved where rational participants are incentivized to act honestly.
Key Results
- Analytical Proofs: The paper provides analytical results proving that MODiCuM can effectively deter misbehavior by rational agents.
- Experimental Evaluation: An implementation of MODiCuM was built and tested.
- Cost Comparison: For the JC, the average gas cost of a nominal execution is 592,000 gas, translating to approximately $0.168 per job on Ethereum. This is competitive with AWS Lambda for jobs lasting around 6 hours, especially considering the significantly lower electrical costs for edge devices.
- Platform Overhead: MODiCuM introduces a RAM overhead of about 20-25MB per agent type and a CPU overhead on the Mediator (80%), Job Creator (30%), and negligible on the Resource Provider.
- Runtime: Running jobs via MODiCuM increased runtime by about 1 second (4%) and memory consumption by 0.1MB (3%) compared to native execution.
- Mediation Cost: A mediated execution incurs higher gas costs for the JC (991,000 gas) and the Mediator (187,000 gas) to post the mediation result.
- Minimum Verification Rate: The analysis suggests that with optimal parameter settings, the JC might only need to verify about 2% of results, and mediation would occur in about 0.02% of cases if the JC is cheating.
Limitations and Future Work
- Ethereum Transaction Costs: The current implementation's reliance on Ethereum makes it suitable primarily for very long-running jobs due to transaction costs. The authors note that improvements to Ethereum will benefit their platform.
- Job Type Restrictions: MODiCuM is designed for deterministic, batch jobs that are not time-critical and do not require external information.
- Collusion: While the paper analyzes two-party collusions, it acknowledges that more complex collusions are not explicitly addressed.
- Future Work: The authors suggest exploring other platforms that support smart contracts and leveraging ongoing improvements to Ethereum. They also plan to provide formal proofs for their conjectures regarding mediator and directory honesty.
Summary updated