Abstract
Privacy-centric blockchains like Monero utilize ring signatures to obfuscate transaction origins. However, these systems are vulnerable to "chain-reaction" attacks that deanonymize users by identifying and eliminating known "chaff" coins. This paper introduces CoinMagic, a framework that applies differential privacy to the selection of transaction "mixins." By utilizing a new metric called $\epsilon$-coin-indistinguishability and maximizing mixin diversity within a fixed transaction fee budget, CoinMagic significantly enhances the resilience of privacy-preserving blockchains against deanonymization.
Introduction
Privacy-preserving blockchains such as Monero and Bytecoin rely on ring signatures to protect sender identity. In a typical transaction, a user's real coin is grouped with several "mixins" (fake or "chaff" coins), making it difficult for an observer to determine which coin is actually being spent.
Despite this mechanism, these systems are susceptible to "chain-reaction" analysis. If an adversary can prove that certain mixins in a ring were spent in other transactions, they can eliminate them from the set of possibilities. If all mixins are eliminated, the sender's identity is exposed. Current selection methods often fail to account for the "diversity" of these coins—the variety of historical transactions from which they originate—leaving users at risk.
The CoinMagic Framework
The authors propose a formal framework to address the CI-aware mixins selection with disjoint-superset constraint (CIA-MS-DS) problem. CoinMagic focuses on three core pillars:
- $\epsilon$-Coin-Indistinguishability ($\epsilon$-CI): Inspired by Differential Privacy, this metric ensures that the probability distribution of any coin in a ring being the "real" one is nearly identical, within a factor of $e^\epsilon$.
- Diversity Maximization: The framework prioritizes mixins from a wide array of historical transactions, making it significantly harder for an attacker to "clear" multiple mixins simultaneously.
- Disjoint-Superset Constraint: To manage the mathematical complexity of transaction histories, the authors require that each new ring signature is either entirely separate from or a complete superset of previous ones. This allows for the construction of tractable "spent coin permutation trees" to calculate spending probabilities.
Proposed Algorithms
Since the mixin selection problem is NP-hard, CoinMagic employs two approximation algorithms:
- Progressive Algorithm: This approach uses a modified 0-1 Knapsack method to identify a set that satisfies privacy constraints, then greedily adjusts the selection to fit the user's budget. It offers the highest diversity but is computationally intensive.
- Game Theoretic Algorithm: This model treats potential mixins as "players" in a strategic game. The system reaches a Nash Equilibrium where the collective choice maximizes diversity while adhering to privacy and budget rules. This method is optimized for speed, making it suitable for high-throughput blockchains.
Evaluation and Results
The researchers evaluated CoinMagic using both real-world Monero blockchain data (blocks 2028242 to 2028273) and synthetic datasets.
Key findings include:
- Superior Diversity: Both algorithms significantly outperformed standard "Random" and "Greedy" selection methods.
- Efficiency: The Game Theoretic Algorithm proved fast enough for real-time use in consortium blockchains while maintaining high privacy standards.
- Resilience: The framework successfully maintained the $\epsilon$-CI level as the blockchain grew, effectively neutralizing chain-reaction threats by ensuring no single coin appeared more likely to be the spent one than others.
Conclusion
CoinMagic shifts the paradigm of ring signature privacy from simple k-anonymity to a distribution-based indistinguishability model. While the current framework utilizes a "disjoint-superset" simplification, it provides a robust foundation for future work to address even more complex transaction patterns in decentralized ledgers.
Summary updated