Thank you guys so much for supporting me and MRL!

Supported, much love for your work.

please sticky this on reddit, it hurts to see 140k people not knowing they have to fund the person responsible for so much work and research done on Monero.

its been stuck at 12-20 XMR for 3 weeks now..

+15 XMR on behalf of XMR.TO

Donation coming your way

Super happy to donate to this, you and Sarang are really pushing the envelope in Monero!

:)

Sorry, I somehow missed both researchers funding requests. XMR on the way to you both! And, please know your work is greatly appreciated!

on its way

+1 XMR on behalf of Monerujo

Donated.

Donated; thank you for your work.

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).

1. 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.
2. 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.
3. 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.

Greetings all,

I am joining my September and October progress reports for convenience. First, broad strokes. Second, details.

September

1. Meeting dates: We had three meetings this month, 2018-09-10, 2018-09-17, and 2018-09-24. Logs will appear here shortly.
2. Continued work on the following:
   • Monero Konferenco organization and planning.
   • Cursory review of M/N general multisig by naughtyfox.
   • Monero traceability/churn
   • Outgoing view key functionality
   • Sublinear ring signature schemes/choices for ringCT2
3. Completed work on the following:
   • Assisted review of Sarang's DLSAG paper (see here).
4. Began work on the following:
   • Cross-chain swaps and lightning-for-Monero papers
   • Discussions on kovri boostrap/reseed
   • Fact finding re: university and FFS grants
   • Review of research paper by external contributors with Sarang

October

1. Meeting dates: We had five meetings this month, 2018-10-01, 2018-10-08, 2018-10-15, 2018-10-22, and 2018-10-29. Logs will appear here shortly.
2. *Continued work on the following:
   • Monero Konferenco organization and planning.
   • Monero traceability/churn
   • Sublinear ring signature schemes/choices for ringCT2
3. Completed work on the following:
   • Fact finding re: university and FFS grants
   • Research Lab roadmap split into multiple research-lab issues
4. Began work on the following:
   • Modification to wallet distribution, coinbase density, coinbase segregation
   • Studying quisquis and non-monotonic key image sets

Here are some progress notes on specific tasks.

1. Monero Konferenco organization and planning (ctd...): Right now we are chatting with Kastelo about badges for the conference, scoping out venues, and waiting for the FFS Funding Request to move to Funding Required.
2. General M/N multisig (ctd...): I need to continue the review I began in September. Currently the math appears fine, we merely must connect the dots with the code.
3. Monero traceability/churn (ctd...): This took up the vast majority of my time in October. I am working on a paper to publish on applications in graph theory and how they relate to traceability in Monero. The goal is to formalize some security games related to traceability, analyze the complexity of the problem from a powerful adversary's point of view, and to determine some quantitative recommendations for the community on moving forward. The first few sections of this document are done, and I will be sharing a draft with the community soon.
4. Outgoing view key functionality (ctd...): We are still interested in outgoing view key functionality. However, custodial KYC/AML exchanges can already perform the auditing tasks required by regulators (for example, file suspicious activity reports) with no modification to Monero as it stands. Consequently, we are de-prioritizing this area of inquiry for now.
5. Sublinear ring signature schemes (ctd...): Sarang and I have now been presented with two sublinear ring signature schemes without trusted set-ups in papers with intersecting authors lists. These are currently under investigation as possible upgrade options for RingCT2. We have been looking into prototyping, benchmarking, and streamlining both of these schemes, one of which has made it into dumb code that should never be directly put into production (see here or here). We are looking at our options very carefully.
6. Sarang's DLSAG paper can be seen here. These will enable refund transactions in Monero, but will require a change to transaction validation.
7. Fact finding and university grants: Short answer is that we can't do them, yet, except with university programs that are already actively accepting crowdfunded crypto research grants. This is essentially a no-go for the Monero FFS... for US-based universities... for now.
8. Research roadmap maintenance: Self explanatory, I split up our road map into a sequence of issues. Initially, the research roadmap was sort of a way for the community to track my research progress, but at this point this is a living MRL to-do list.
9. New work:
   • Cross-chain swaps and lightning-for-Monero papers. We can use Sarang/Pedro/donut's DLSAG scheme for refund outputs and implement cross-chain atomic swaps. I put a lot of work into this paper in September, and it is actually in pretty good shape even though it's under "new work." I'll be sharing this with the community soon; churn/traceability took me away from this project these past few weeks.
   • Discussions on kovri boostrap/reseed began. As far as I understand it, kovri nodes gain a view of the network by bootstrapping from the view of nodes they connect to. How to do this in a secure, trustless environment is a fun question.
   • Review of research paper by external contributors: Sarang and I were sent a preprint from some researchers based in Australia. Some of their work re-invented some wheels, and we were able to provide some feedback to them on their work.
   • Modification to wallet distribution, coinbase density, coinbase segregation: Our recent mix-in selection algorithm was switched up. Due to our selection method and due to the fact that around 20% of Monero blocks are empty (except for a coinbase transaction), it ends up that around 20% of ring members are coinbase transactions. This allows a heuristic to disregard coinbase transactions as plausible ring members. However (i) the majority of ring signatures will still have a larger effective ring size than before our hard fork to ring size 11, and (ii) we are currently discussing an additional modification to our output selection algorithm to reduce the efficacy of such heuristics.
   • Studying quisquis and non-monotonic key image sets. This is brand new work. I'm very interested in this paper.

Thanks to everyone! I cannot describe my joy at working with the Monero community. I hope that my work so far at MRL has been a helpful contribution to Monero. Earlier this week, I was reminded how Monero Research Lab is a self-assembling entity. No one can claim to run the thing, just like a surfer can't claim to run a wave, the best we can do is hang on for dear life. I want to thank you all for not shaking me off yet, because it's a wild ride.

Down to donate!