Anonymous Messaging - January 2017

Public Audience
Purpose: To highlight project progress. Information is generally at a higher level which is accessible to the interested public. All information contained in the report (regions 1-3) is a Government Deliverable/CDRL.

PI(s): Pramod Vishwananth

Researchers: Giulia Fanti, Jiaqi Mu, and Ashok Vardhan Makkuva

HARD PROBLEM(S) ADDRESSED
This refers to Hard Problems, released November 2012.

Hard problem: Scalability and Composability

Anonymity is a basic right and a core aspect of Internet. Recently, there has been tremendous interest in anonymity and privacy in social networks, motivated by the natural desire to share one's opinions without the fear of judgment or personal reprisal (by parents, authorities, and the public). We propose to study the fundamental questions associated with building such a semi-distributed, anonymous messaging platform, which aims to keep anonymous the identity of the source who initially posted a message as well as the identity of the relays who approved and propagated the message.

PUBLICATIONS
Papers published in this quarter as a result of this research. Include title, author(s), venue published/presented, and a short description or abstract. Identify which hard problem(s) the publication addressed. Papers that have not yet been published should be reported in region 2 below.

[1] G. Fanti, S. Venkatakrishnan and P. Viswanath, "Dandelion: Redesigning BitCoin Networking for Anonymity", submitted to ACM Sigmetrics, 2017.

Abstract: Bitcoin and other cryptocurrencies have surged in popularity over the last decade. Although Bitcoin does not claim to provide anonymity for its users, it enjoys a public perception of being a `privacy-preserving' financial system. In reality, cryptocurrencies publish users' entire transaction histories in plaintext, albeit under a pseudonym; this is required for transaction validation. Therefore, if a user's pseudonym can be linked to their human identity, the privacy fallout can be significant. Recently, researchers have demonstrated deanonymization attacks that exploit weaknesses in the Bitcoin network's peer-to-peer (P2P) networking protocols. In particular, the P2P network currently forwards content in astructured way that allows observers to deanonymize users. In this work, we redesign the P2P network from first principles with the goal of providing strong, provable anonymity guarantees. We propose a simple networking policy called Dandelion, which achieves nearly-optimal anonymity guarantees at minimal cost to the network's utility. We also provide a practical implementation of Dandelion for deployment.

[2] G. Fanti and P. Viswanath, "Anonymity Properties of the Bitcoin P2P Network", submitted to ACM Sigmetrics, 2017.

Abstract: In the last decade, Bitcoin has evolved from a research project to a cryptocurrency with a multi-billion dollar market cap. Although Bitcoin does not explicitly provide anonymity guarantees to its users, it is publicly perceived as a privacy-preserving alternative to mainstream financial systems. However, recent attacks on Bitcoin's peer-to-peer (P2P) network demonstrated that its low-level networking protocols may enable user deanonymization---i.e., the linkage of a user's true identity with her pseudonym in the Bitcoin network. Deanonymization is problematic because it may allow an attacker to learn a user's entire transaction history. In this paper, we model the Bitcoin networking stack and analyze its anonymity properties. We theoretically prove that Bitcoin's original networking protocols offer poor anonymity properties on networks with a regular-tree topology; moreover, we show that the Bitcoin community's solution to this vulnerability (implemented in 2015) has equally poor anonymity properties. We also show empirically that the same networking protocols perform poorly on the true Bitcoin P2P network, which is not a regular tree.

ACCOMPLISHMENT HIGHLIGHTS

• Fundamental limits to spreading and hiding of in the BitCoin P2P networking stack.
• In this quarter our study of anonymity of the BitCoin networking stack has progressed smoothly, with significant research progress.