Greetings all,
This report describes my work in November.
Stuff that happened in November. This has been an extremely successful month for Monero Research Lab, although it has seemed rather quiet. Sarang completed a Python implementation of the RTRS sublinear ring signature scheme brought to us late last year. I completed some graph theoretic code for finding optimal matchings in bipartite graphs. And several MRL contributors attended the second Monero Workshop jointly funded by MyMonero and Tari.
The vast majority of my time this month was spent on the graph matching paper and code (see below).
- Meeting dates: We had four meetings this month, 2018-11-05, 2018-11-12, 2018-11-19, and 2018-11-26. Logs will appear on my github shortly.
- Continued work on the following:
- Monero Konferenco organization and planning.
- Monero bipartite graph matching analysis paper.
- Ring sig replacement, accumulator research (reading).
- Cross-chain swaps and lightning-for-Monero papers.
- Completed work on the following:
- Bipartite graph matching code can be found here.
- Unit tests for Sarang's Python implementation of Ruffing, Thyagarajan, Ronge, and Schröder's (RTRS) sublinear ring signature.
- Reviewed Python code for Sarang's RTRS scheme in python
Details
Monero Konferenco organization and planning (ctd...): We have decided against using Kastelo to create badges for the first conference. We feel that Kastelo's resources right now are better directed elsewhere. In a cost/benefit sense, freaky Konferenco badges will not benefit the community or the project in the same way that proceeding with their current projects could. We have drafted invitation emails, we are constructing invitation lists, we are making lists of organizations to approach as sponsors, and we are constructing a timeline for disbursement of funds. Stay tuned, probably dropping some info on Monday, 3 December 2018.
Matching in bipartite graphs: This took up the bulk of my time this month. Financial privacy is an arms race, and Monero Research Lab contributors like to try to stay ahead of known problems. In this vein, Sarang and I are formalizing an obfuscation game related to Monero and investigating how varying threat models influence that game. This work is a generalization of traceability threats related to chain reactions, intersection attacks, Monerolink-style guess newest heuristics, and general properties related to small-anonymity-set obfuscation approaches.
You can see some code written for this project here that finds an optimally weighted maximal matching between a set of keys and a set of ring signatures. In short, we are formalizing how bad all the known problems with ring signatures really are. We hope our work will lay the groundwork for informing the Monero community on best practices like churn. But also, we wish to honestly illustrate to Monero users exactly where Monero transactions sit on the spectrum of anonymity. This work is extremely important to Monero in the same vein as our MRL-0001 bulletin on chain reactions. Results and recommendations moving forward will be forthcoming soon(tm).
Ring signature replacement: Our work on bipartite matching is leading us to toward looking for secure large-anonymity-set replacements for ring signatures that do not require a trusted setup and can be verified in reasonably short periods of time. Sarang and I have been presented with two sublinear ring signature schemes without trusted set-ups in papers with intersecting authors lists. You can find a dumb toy implementation of one of them in Python, written by Sarang and reviewed by myself here. As far as we are aware, this is the first sublinear ring signature scheme to see implementation... ever. Not merely produced by MRL, but ever. With appropriate batching, it appears that RTRS is equally as fast as our current scheme, so it appears there is no downside to switching to this sublinear scheme... but we aren't stopping here because at our current speeds ring sizes above 20 are inappropriately slow to mandate as a minimum ring size.
Cross-chain swaps and lightning-for-Monero: Pedro Moreno-Sanchez and donut laid the groundwork for dual output Monero transactions with trigger heights to enable refund transactions in Monero. Those two are working on a paper describing second layer solutions for Monero, and they began their work before I began my paper. So I have pivoted in the purpose of this document to not present the material freshly but instead to make some recommendations for the Monero core team based on the work by Pedro and donut. Consequently, this is temporarily beign put on the back burner until their papers have been published.
Thanks to everyone! I want to repeat my surf analogy from last time, but I don't like repeating myself.