Private Proof-of-Stake Blockchains using Differentially-private Stake Distortion

Chenghong Wang, David Pujol, Kartik Nayak, Ashwin Machanavajjhala

TL;DR

This paper introduces the first practical stake inference attack against randomized Proof-of-Stake (PoS) blockchains, demonstrating that existing privacy-preserving designs are still vulnerable. To counter this, they propose a novel "differentially-private stake distortion" mechanism that injects noise into stake values, effectively protecting against these attacks while preserving essential blockchain properties like safety and liveness.

What Problem Does This Paper Address?

Blockchains, particularly Proof-of-Stake (PoS) systems, face a critical challenge in balancing three core properties: safety (ensuring transactions are valid and agreed upon), liveness (guaranteeing transactions are eventually processed), and privacy (protecting sensitive information). While hiding transaction details is a start, a significant privacy concern in PoS blockchains is the leakage of a user's "stake" – the amount of cryptocurrency they hold, which directly influences their influence in the network. Prior research has shown that even with private transaction processing, a party's stake can be inferred through side-channel attacks, such as analyzing the frequency of block proposals. This paper tackles two key questions: 1) Are there practical stake inference attacks against real-world, randomized PoS protocols? and 2) Can PoS designs effectively prevent these attacks while maintaining other crucial properties?

Methods

The paper makes two main contributions:

  1. Stake Inference Attack (SIA) Paradigm: They propose a general framework for stake inference attacks that can be applied to randomized PoS protocols. This paradigm accounts for probabilistic liveness and uses robust inference strategies to handle unreliable feedback. They then present "RdBin," a concrete attack that combines random walk and binary search, achieving a significantly more efficient running time (sublinear complexity) compared to previous methods.
  2. Differentially-Private Stake Distortion: To address the identified privacy risks, they introduce a novel approach of "differentially-private stake distortion." This involves modifying the stake values used in the lottery for block proposal selection by adding carefully calibrated noise. They propose two specific distortion mechanisms:
  3. Timer Mechanism: Periodically distorts stakes with Laplace noise.
  4. Binary Mechanism: Uses a binary interval tree to provide a smoother, logarithmic privacy decay over time. These mechanisms are designed to be pluggable into existing PoS protocols, ensuring provable stake and transaction privacy while preserving safety and liveness.

Datasets

Not discussed in the paper. The evaluation uses simulated data based on Ethereum 2.0 statistics.

Key Insights and Ideas

  • Real-world PoS is vulnerable: The paper demonstrates that existing privacy-preserving PoS designs are susceptible to practical stake inference attacks, even with randomized protocols. This highlights a significant gap in current security models.
  • Stake distortion as a privacy solution: Injecting differentially private noise into stake values is a viable and effective method to mitigate stake inference attacks. This approach allows for a trade-off between privacy and safety, enabling customization.
  • Privacy decay is crucial: The paper emphasizes the importance of privacy decay, especially for dynamic systems like blockchains where stakes can change. The "Binary Mechanism" offers a smoother decay, which can be beneficial for long-term privacy.
  • Trade-off between safety and privacy: There's an inherent trade-off. Stronger privacy guarantees (lower epsilon, higher alpha) can sometimes lead to weaker safety guarantees (lower malicious tolerance). This allows practitioners to tune the system based on their specific needs.

Key Results

  • RdBin Attack: The proposed RdBin attack achieves sublinear complexity, significantly outperforming previous linear-time attacks.
  • Stake Distortion Effectiveness: The stake distortion mechanisms (Timer and Binary) were shown to provide reasonable stake privacy while retaining safety and liveness.
  • Privacy Levels: For Ethereum 2.0 parameters, privacy was ensured for over 99.95% of users, even with a 30% malicious tolerance.
  • SIA Mitigation: The stake distortion mechanisms reduced SIA inference errors by at least 2x and up to 7.8x compared to non-private protocols.
  • Performance Overhead: The implementation of stake distortion added a small overhead (less than 13% of Zcash's protocol) and amortized costs could be even lower due to periodic distortions.

Limitations and Future Work

  • Assumptions: The work assumes a globally synchronized clock for simplicity. Integrating with permissionless clock synchronization protocols is suggested as future work.
  • Privacy Decay: While the Binary Mechanism offers smoother decay, the Timer mechanism provides better short-term privacy. The choice depends on the specific requirements.
  • Gaussian Noise: The paper explores Gaussian noise as an alternative to Laplace noise for potentially smoother privacy decay, but further analysis is needed.
  • Optimization: The current implementation focuses on demonstrating the core concepts, and further optimizations for the underlying cryptographic primitives (like ln(x) circuits) could improve performance.

Summary updated

Abstract

Safety, liveness, and privacy are three critical properties for any private proof-of-stake (PoS) blockchain. However, prior work (SP'21) has shown that to obtain safety and liveness, a PoS blockchain must in theory forgo privacy. Specifically, to ensure safety and liveness, PoS blockchains elect parties based on stake proportion, potentially exposing a party's stake even with private transaction processing. In this work, we make two key contributions. First, we present the first stake inference attack applicable to both deterministic and randomized PoS with exponentially less running time in comparison with SOTA designs. Second, we use differentially private stake distortion to achieve privacy in PoS blockchains and design two stake distortion mechanisms that any PoS protocol can use. We further evaluate our proposed methods using Ethereum 2.0, a widely-recognized PoS blockchain in operation. Results demonstrate effective stake inference risk mitigation, reasonable privacy, and preservation of essential safety and liveness properties.
BibTeX
@article{wang2023private,
  author = {Chenghong Wang and David Pujol and Kartik Nayak and Ashwin Machanavajjhala},
  title = {{Private Proof-of-Stake Blockchains using Differentially-private Stake Distortion}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2023},
}
Figure