Join GitHub today
GitHub is home to over 28 million developers working together to host and review code, manage projects, and build software together.Sign up
An alternative approach to analyzing anonymity in cryptocurrencies #36
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 . 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 .
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.
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)
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.
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
We would spend the requested budget towards graduate students stipends, equipment expenditures and research visits among the research team members.
** Schedule **
Email address(es) for direct contact
Foteini at gmu dot edu
@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.
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.
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@example.com 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.
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.
Grant Review Committee comments: