Paper 2021/409

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

Markulf Kohlweiss, University of Edinburgh
Varun Madathil, North Carolina State University
Kartik Nayak, Duke University
Alessandra Scafuro, North Carolina State University

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-2\f)$ 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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. 42nd IEEE Symposium on Security and Privacy
network attacks anonymity UC security anonymous broadcast privacy-preserving proof-of-stake
Contact author(s)
markulf kohlweiss @ ed ac uk
vrmadath @ ncsu edu
kartik @ cs duke edu
ascafur @ ncsu edu
2022-06-24: last of 4 revisions
2021-03-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Markulf Kohlweiss and Varun Madathil and Kartik Nayak and Alessandra Scafuro},
      title = {On the Anonymity Guarantees of Anonymous Proof-of-Stake Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2021/409},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.