CoinMagic: A Differential Privacy Framework for Ring Signature Schemes

Wangze Ni, Han Wu, Peng Cheng, Lei Chen 0002, Xuemin Lin, Lei Chen 0048, Xin Lai, Xiao ZhangarXiv 2020 · arXiv

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.

The structure of a ring signature linking historical transaction outputs to a new transaction input.

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:

  1. $\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$.
  2. 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.
  3. 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.
Permutation trees representing possible spent coin scenarios under different constraints, used to calculate indistinguishability.

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

Abstract

By allowing users to obscure their transactions via including "mixins" (chaff coins), ring signature schemes have been widely used to protect a sender's identity of a transaction in privacy-preserving blockchain systems, like Monero and Bytecoin. However, recent works point out that the existing ring signature scheme is vulnerable to the "chain-reaction" analysis (i.e., the spent coin in a given ring signature can be deduced through elimination). Especially, when the diversity of mixins is low, the spent coin will have a high risk to be detected. To overcome the weakness, the ring signature should be consisted of a set of mixins with high diversity and produce observations having "similar" distributions for any two coins. In this paper, we propose a notion, namely $\epsilon$-coin-indistinguishability ($\epsilon$-CI), to formally define the "similar" distribution guaranteed through a differential privacy scheme. Then, we formally define the CI-aware mixins selection problem with disjoint-superset constraint (CIA-MS-DS), which aims to find a mixin set that has maximal diversity and satisfies the constraints of $\epsilon$-CI and the budget. In CIA-MS-DS, each ring signature is either disjoint with or the superset of its preceding ring signatures. We prove that CIA-MS-DS is NP-hard and thus intractable. To solve the CIA-MS-DS problem, we propose two approximation algorithms, namely the Progressive Algorithm and the Game Theoretic Algorithm, with theoretic guarantees. Through extensive experiments on both real data sets and synthetic data sets, we demonstrate the efficiency and the effectiveness of our approaches.
BibTeX
@misc{ni2020coinmagic,
  author = {Wangze Ni and Han Wu and Peng Cheng and Lei Chen and Xuemin Lin and Lei Chen and Xin Lai and Xiao Zhang},
  title = {{CoinMagic: A Differential Privacy Framework for Ring Signature Schemes}},
  year = {2020},
  eprint = {2003.06826},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2003.06826},
}
Figure