On the Anonymity Guarantees of Anonymous Proof-of-Stake Protocols

Markulf Kohlweiss, Varun Madathil, Kartik Nayak, Alessandra Scafuro

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

In proof-of-stake (PoS) blockchains, stakeholders that extend the chain are selected according to the amount of stake they own. In S&P 2019 the "Ouroboros Crypsinous" system of Kerber et al. (and concurrently Ganesh et al. in EUROCRYPT 2019) presented a mechanism that hides the identity of the stakeholder when adding blocks, hence preserving anonymity of stakeholders both during payment and mining in the Ouroboros blockchain. They focus on anonymizing the messages of the blockchain protocol, but suggest that potential identity leaks from the network-layer can be removed as well by employing anonymous broadcast channels.In this work we show that this intuition is flawed. Even ideal anonymous broadcast channels do not suffice to protect the identity of the stakeholder who proposes a block.We make the following contributions. First, we show a formal network-attack against Ouroboros Crypsinous, where the adversary can leverage network delays to distinguish who is the stakeholder that added a block on the blockchain. Second, we abstract the above attack and show that whenever the adversary has control over the network delay – within the synchrony bound – loss of anonymity is inherent for any protocol that provides liveness guarantees. We do so, by first proving that it is impossible to devise a (deterministic) state-machine replication protocol that achieves basic liveness guarantees and better than (1−2f) anonymity at the same time (where f is the fraction of corrupted parties). We then connect this result to the PoS setting by presenting the tagging and reverse tagging attack that allows an adversary, across several executions of the PoS protocol, to learn the stake of a target node, by simply delaying messages for the target. We demonstrate that our assumption on the delaying power of the adversary is realistic by describing how our attack could be mounted over the Zcash blockchain network (even when Tor is used). We conclude by suggesting approaches that can mitigate such attacks.
Original languageEnglish
Title of host publication2021 IEEE Symposium on Security and Privacy (SP)
Subtitle of host publicationSP 2021
Number of pages16
ISBN (Electronic)978-1-7281-8934-5
ISBN (Print)978-1-7281-8935-2
Publication statusPublished - 26 Aug 2021
Event42nd IEEE Symposium on Security and Privacy - Online, San Francisco, United States
Duration: 24 May 202127 May 2021

Publication series

NameIEEE Symposium on Security and Privacy
ISSN (Print)1081-6011
ISSN (Electronic)2375-1207


Symposium42nd IEEE Symposium on Security and Privacy
Abbreviated titleSP 2021
Country/TerritoryUnited States
CitySan Francisco
Internet address

Keywords / Materials (for Non-textual outputs)

  • cryptographic protocols / network attacks
  • anonymity
  • UC security
  • anonymous broadcast
  • privacy-preserving proof-of-stake


Dive into the research topics of 'On the Anonymity Guarantees of Anonymous Proof-of-Stake Protocols'. Together they form a unique fingerprint.

Cite this