Funding allows Matchstick to quickly assess, fund and grow solutions that can improve people’s lives. Financial and technological support is available for companies that are using technology in innovative ways to improve the world.
The goal of our proposed project is to research how techniques inspired from the area of differential privacy (DP) can be used in order to construct anonymous cryptocurrencies without the need to rely on a trusted setup process.
Our motivation rises from the fact that Monero, one of the most popular private cryptocurrencies that does not require a trusted setup, has been recently empirically analyzed to find that approximately 80% of the transactions provide no or very limited privacy [1]. Monero utilizes ring signatures in order to conceal the source of a transaction. In a nutshell, when a user spends a coin, she first finds other unspent transactions with the same denomination, and uses the public keys corresponding to those transactions to create her ring. The user’s identity will be hidden within the set of PKs that are part of the ring. However, the number of Monero mixins is usually rather small and sampled in a way that can be distinguished from the real transaction [1].
Our plan is to investigate whether we can build a protocol for mixing transactions in the spirit of Monero, while formally proving that we preserve differential privacy for the users. Specifically, we would like to claim that two neighboring transaction graphs are nearly equally likely to give rise to the same chain. We view a transaction graph as a set of transactions between n users and n recipients, and define a neighboring graph as any that results from swapping the recipients for two senders. In order to keep the size of each individual ring signature small while providing a large number of potential options for the real transaction, our plan is to have users submit several ring signatures in sequence that rope in an ever-increasing number of possible mix-ins.
Technical approach
We will work towards building a protocol that will (a) provide the right graph structure to be analyzed for differential privacy and (b) will be efficient enough for practical implementation. We expect that a rather challenging step in our approach will be the the security analysis of the protocol, as it involves studying the differential privacy of graphs in a new setting, where each individual contribution influences multiple nodes and edges. We finally plan on providing a proof of concept implementation of the proposed protocol and detailed comparisons with other private cryptocurrencies.
Team background and qualifications
Our team consists of a group of cryptographers with expertise in differential privacy, MPC and building anonymity solutions for cryptocurrencies.
Foteini Baldimtsi (George Mason University)
Ethan Gertler (George Mason University)
Dov Gordon (George Mason University)
Mayank Varia (Boston University)
Evaluation plan
Our proposed approach will be evaluated in the form of providing formal cryptographic definitions and proofs to showcase the exact level of security and privacy that we achieve. On the practical side, we will provide a proof of concept implementation to showcase the level of efficiency that we achieve.
Security considerations
This project will advance knowledge on the flavors of anonymity that a private cryptocurrency can achieve and will explore the efficiency - privacy trade-offs.
Budget and justification
$25K
We would spend the requested budget towards graduate students stipends, equipment expenditures and research visits among the research team members.
Schedule
(2 months) Work on new DP based definitions for privacy in cryptocurrencies
(3 months) Construction and proofs
(1 month) Discuss trade-offs and comparisons with existing solutions and if time permits provide a proof of concept implementation.
Email address(es) for direct contact
Foteini at gmu dot edu
References
[1] Malte Möser, Kyle Soska, Ethan Heilman, Kevin Lee, Henry Heffan, Shashvat Srivastava, Kyle Hogan, Jason Hennessey, Andrew Miller, Arvind Narayanan, and Nicolas Christin, “An Empirical Analysis of Traceability in the Monero Blockchain”, to appear in PETS 2018
Motivation and Overview
The goal of our proposed project is to research how techniques inspired from the area of differential privacy (DP) can be used in order to construct anonymous cryptocurrencies without the need to rely on a trusted setup process.
Our motivation rises from the fact that Monero, one of the most popular private cryptocurrencies that does not require a trusted setup, has been recently empirically analyzed to find that approximately 80% of the transactions provide no or very limited privacy [1]. Monero utilizes ring signatures in order to conceal the source of a transaction. In a nutshell, when a user spends a coin, she first finds other unspent transactions with the same denomination, and uses the public keys corresponding to those transactions to create her ring. The user’s identity will be hidden within the set of PKs that are part of the ring. However, the number of Monero mixins is usually rather small and sampled in a way that can be distinguished from the real transaction [1].
Our plan is to investigate whether we can build a protocol for mixing transactions in the spirit of Monero, while formally proving that we preserve differential privacy for the users. Specifically, we would like to claim that two neighboring transaction graphs are nearly equally likely to give rise to the same chain. We view a transaction graph as a set of transactions between n users and n recipients, and define a neighboring graph as any that results from swapping the recipients for two senders. In order to keep the size of each individual ring signature small while providing a large number of potential options for the real transaction, our plan is to have users submit several ring signatures in sequence that rope in an ever-increasing number of possible mix-ins.
Technical approach
We will work towards building a protocol that will (a) provide the right graph structure to be analyzed for differential privacy and (b) will be efficient enough for practical implementation. We expect that a rather challenging step in our approach will be the the security analysis of the protocol, as it involves studying the differential privacy of graphs in a new setting, where each individual contribution influences multiple nodes and edges. We finally plan on providing a proof of concept implementation of the proposed protocol and detailed comparisons with other private cryptocurrencies.
Team background and qualifications
Our team consists of a group of cryptographers with expertise in differential privacy, MPC and building anonymity solutions for cryptocurrencies.
Foteini Baldimtsi (George Mason University) Ethan Gertler (George Mason University) Dov Gordon (George Mason University) Mayank Varia (Boston University)
Evaluation plan
Our proposed approach will be evaluated in the form of providing formal cryptographic definitions and proofs to showcase the exact level of security and privacy that we achieve. On the practical side, we will provide a proof of concept implementation to showcase the level of efficiency that we achieve.
Security considerations
This project will advance knowledge on the flavors of anonymity that a private cryptocurrency can achieve and will explore the efficiency - privacy trade-offs.
Budget and justification
$25K
We would spend the requested budget towards graduate students stipends, equipment expenditures and research visits among the research team members.
Schedule
(2 months) Work on new DP based definitions for privacy in cryptocurrencies (3 months) Construction and proofs (1 month) Discuss trade-offs and comparisons with existing solutions and if time permits provide a proof of concept implementation. Email address(es) for direct contact
Foteini at gmu dot edu
References [1] Malte Möser, Kyle Soska, Ethan Heilman, Kevin Lee, Henry Heffan, Shashvat Srivastava, Kyle Hogan, Jason Hennessey, Andrew Miller, Arvind Narayanan, and Nicolas Christin, “An Empirical Analysis of Traceability in the Monero Blockchain”, to appear in PETS 2018