GrantProposals-2018Q2
GrantProposals-2018Q2 copied to clipboard
ZcashFoundation
An alternative approach to analyzing anonymity in cryptocurrencies
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
@bfoteini thanks for the really interesting submission! I think even formal definitions for anonymity in Monero-like coins is an interesting topic, and developing a better (Monero-like) protocol is also very promising goal. From the plan recommended, I see no "Schedule" part in the proposal. Do you have any milestones and dates in mind?
Thanks! It's a bit hard to make a concrete schedule when trying to tackle a research problem but I did update the proposal with a tentative one.
@bfoteini Is the idea to use differential privacy to develop a better method for sampling decoy/mixin transactions or did you have something else in mind?
Right, we want to explore whether this can give us a better (i.e. DP anonymous) Monero-style protocol.
I have several concerns about this approach in terms of what meaningful privacy can be achieved with mixing/decoy based systems even with tools taken from the differential privacy literature. At best, I think you'd get a negative result.
The analysis of these mixing/decoy systems typically ignores both the existence of repeated payments, change addresses, and active attacks. Compared to that, the issue of what distribution decoy payments are selected from is a minor problem. Differential privacy doesn't seem to resolve these issues: the achilles heals of differential privacy are correlated events and the exhaustion of privacy budgets by repeated usage and these are precisely where problems crop up already.
Consider a simple scenario: you buy coffee every day in the morning on the way to work. Can the coffee shop link any of your transactions together? From that can they collude with other merchants to build up a profile of you? The answer is seemingly yes: every time you make a payment, you get back a change transaction. The odds that the change ends up in the decoy set of a subsequent payment to the coffee shop are tiny if that payment is made by someone else. But if you made the payment, the odds are very high. Even if you launder the change, it will still leave a trace. Not just can the coffee shop mount this type of analysis, but so can the coffee shop’s exchange/bank.
Consider also active attacks: suppose a dissident solicits donations online pseudonymously. Ideally, we should prevent a hostile regime from identifying the dissident even if they control the dissident's bank/exchange. But in existing mixing/decoy systems, merely paying the dissident a few times likely identifies them: the regime can look at each account at the exchange and find the one with all of the marked payments in its upstream decoy set. That account is almost certainly the dissident.
Even if one adopts a definition of privacy that precludes both repeated payments and active attacks, it is not clear how to achieve any privacy over a long time horizon. How do we deal with privacy budget exhaustion? Vuvuzela and Stadium used a differentially private approach for anonymous messaging and did not provide a good answer. The issue seems worse here, since payments are more correlated than anonymous messages, the data is completely public, and there is even less of a clear way to “reset.”
Do you see any way to address these issues?
Thanks for the comment! These are indeed the kind of questions that we want to explore as part of the project.
Our hope is to be able to provide a protocol with better anonymity guarantees when compared to a Cryptonote style protocol and explore what are the efficiency <-> privacy tradeoffs. By having a user run our protocol over multiple rounds in sequence a user can rope in a much larger number of mix-ins. We plan to provide bounds on the numbers of rounds and mixins users need to involve for certain anonymity thresholds.
The Zcash Foundation Grant Review committee has reviewed your pre-proposal, including the above discussion, to evaluate its potential and competitiveness relative to other proposals. Every pre-proposal was evaluated by at least 3 (and typically more than 4) committee members .
The committee's opinion is that your pre-proposal is a promising candidate funding in this round, and the committee therefore invites you to submit a full proposal. Please submit a full proposal by June 15th, following the detailed structure described in the Call for Proposals. We encourage you to submit a draft as early as possible, to allow for community feedback.
Monero's newly-published a protocol spec may be useful for this work: https://eprint.iacr.org/2018/535.pdf
I'm thrilled to inform you that the Grant Review Committee and the Zcash Foundation Board of Directors have approved your proposal, pending a final compliance review. Congratulations, and thank you for the excellent submission!
Next steps: Please email [email protected] from an email address that will be a suitable point of contact going forward. We plan to proceed with disbursements following a final confirmation that your grant is within the strictures of our 501(c)(3) status, and that our payment to you will comply with the relevant United States regulations.
We also wish to remind you of the requirement for monthly progress updates to the Foundation’s general mailing list, as noted in the call for proposals.
Before the end of this week, the Zcash Foundation plans to publish a blog post announcing grant winners to the public at large, including a lightly edited version of the Grant Review Committee’s comments on your project. The verbatim original text of the comments can be found below.
Congratulations again!
Grant Review Committee comments:
The proposal is made by a team of researchers from George Mason University and Boston University. They are offering to analyze small-anonymity-set approaches and develop formal definitions for them by using differential privacy techniques; with the formal definitions formulated they will propose a new provably secure construction for an anonymous cryptocurrency.
The Zcash Foundation would like to support development in small-set privacy techniques as they are popular amongst users, and protecting user privacy is the top mission of the Foundation. Formal definitions and formally secure protocols, unlike ad-hoc approaches used in the industry right now, can get solid privacy guarantees against any adversarial strategy (if assumptions made about adversarial capabilities and environment are reasonable and practically achievable). With that in mind, and also considering clearly written proposal text with well-defined milestones and deliverables. We thus recommend funding this proposal.
I share @imichaelmiers' skepticism, and I'd like to say that the grant awardees should not feel pressured to publish a full protocol construction if the conclusions they come to about the security of this approach are negative. Negative results are useful.
