Surae's End of February Report!
Howdy everyone! Another month gone. More results. Some news. This report was late because I had to speak to some lawyer types about our surprise announcement...
Multisig RingCT: In the past month, the multisig paper has undergone a drastic revision read here, main.tex for clarity purposes. As of last Monday's research meeting, I thought the final big changes would take about a day, but they took about a week and a half. The result is above: a more compact paper with a moderately more compact presentation. Some details in some proofs still need to be fleshed out, references and citations need to be verified, the appendix describing the C++ code needs to be modified heavily, and a few more decisions need to be made before submission. Excluding the appendix describing the C++ code, I am hoping that some community members start reading through the current proofs looking for gaps, incomplete parts, logical problems, etc. The primary body of the thing is down to around 14 pages or so. In total, this was around 75% of my month.
Bulletproof Audits: We have made available here the statements of work from the various audit groups we've been discussing at research meetings, bulletproof meetings, and developer meetings, and we have started our discussion on BP audits on the FFS here. Please drop by and give us your thoughts. In particular, there have been rumblings that perhaps we could pay for an independent formal audit for the multisig code to go with my review. I support this, FWIW.
Where my sublinear ring sigs at? I am writing up a brief research note with Sarang. The idea is this: (i) small anonymity sets are worse than large anonymity sets, (ii) authentication still requires touching all keys in the anonymity set at least once, leading to linear verification times, and (iii) improving the space-efficiency of a blockchain therefore interacts with this linear verification time in a way that produces a space-time trade-off, leading to (iv) a trade-off between traceability and the space-time efficiency of the blockchain, (v) several ways that several different currencies have handled this trade-off, and (vi) implications from cost of running an untraceable cryptocurrency network at scale on this time-space trade-off. Our interests are now turning toward bulletproofs: in implementing bulletproofs, we learned many optimizations for elliptic curve arithmetic that will make our current ring signature schemes faster, but also since SHA-256 is bulletproof-compatible, we are idly toying with the idea of bulletproofing the SHA-256 versions of, say, LSAG or MLSAG signatures.
Sublinear TLDR: Monero is using ring signatures that are practically optimal in the sense that every other scheme we've looked at has either been too big or too slow. So we are trying to make elliptic curve arithmetic faster and trying the black magic of bulletproofs.
Monero Standards: I have an ASCII adaptation and compression of the multisig paper for ready for the Standards. We are starting to compile everything together for a deep theoretical documentation of Monero. That brings me to....
Mostly Complete Description of RingCT: A Monero contributor Kurt Alonso at Universitat Autonoma de Barcelona has written a rather comprehensive report on the crypto underlying Monero. His report can be found here. I am trying to decide if I want to switch all my notation for the multisig paper around to be consistent with the notation in this paper. Kurt's contribution is a valuable resource to the Monero community, and we thank him! I'll be spending a day or two looking through this.
Blockchain compression: Matthew Green of John Hopkins contacted me about a paper he and his student Alishah Chator are writing here. They describe a recoverable sampling scheme, RSS, which can efficiently describe how to retrieve outputs for use in verifying a signature. These RSS approaches scale with the number of outputs, and the result is extreme reduction in the space complexity required to describe a subset of a ledger for a given transaction. Currently, this does not provide us much gain, but as Monero scales upward, techniques such as this will become really easy wins. So we put this in the category of "futurizing Monero," or rather: we shall describe methods such as these in Monero Standards, each of which will have sections describing long-term improvements to our protocol.
Bulletproofs in general: Sarang recently made available a brief technical note on the Monero-specific implementation of BP range proofs... and then within about a day of being completed, Blockstream came out with an amended version of the BP paper that included all of our implementation variations, making this publication somewhat redundant. Check out where a brief technical note goes to die. This is how research goes, unfortunately: about six months before my MS thesis was completed, for example, another grad student elsewhere did exactly the same thesis and I had to start over from scratch.
Plans: Before the end of the month, the next MRL roadmap, which are sub-quarterly apparently, will be announced. At this point, we have enough options on the table to start laying out a vision of what future versions of Monero will probably look like (primarily, we have a few options on the table for better anonymity, and we need to start discussing the practicality of implementing these various options).
Announcement? A portion of my month was spent speaking with lawyers about incorporating an educational non-profit. How would you feel about funding a few elementary school teacher salaries in South Africa or Chile for a year or two? What about providing a handful of one-year no-strings free-ride scholarships to some qualified undergraduates at a university? How would you feel about providing a research grant to someone who figures out an environmentally-friendly version of proof-of-work? These things are all similar in three ways: each are in pursuit of improved educational and research-based outreach, all of these are purely philanthropic, and none of these are reasonable to fund with the FFS on a per-project basis.
This morning, I finished filing articles of incorporation for an educational non-profit Multidisciplinary Academic Grants in Cryptocurrencies (MAGIC) with the Secretary of State of Colorado. We would like Monero to be an active player in improving the educational environment across the world. We want the Monero community to help build a pipeline between education and workers capable of contributing to cryptocurrencies and related industries, providing scholarships to students in the US, providing research grants to principal investigators looking into research areas adjacent to cryptocurrencies, and providing infrastructure grants to disadvantaged schools across the world. An additional convenient component of registering as a non-profit is this: now we have a legal vehicle through which we can fund Monero conferences.
How will it be funded? To start, I am going to match up to 5% of donations, up to 50 XMR, in a soon-to-be posted FFS. Any funding we get above will go directly to the non-profit. Hopefully we get enough money to do a lot of cool stuff the first year plus have XMR carry over to the following year. We will also be soliciting funds from donors in more traditional ways in future years.
Who will run it? Sarang and I will be running MAGIC. We have a partner at Clemson University and a partner in South Africa. My wife, who was also in higher education for nearly a decade, will be helping me run it as a board member. None of the board members will be paid for their work as board members.
Why not call it Monero Academic Grants in Cryptocurrency? For Monero to be in the title, The Monero Project has a requirement that the organization must be a work-group at The Monero Project, which is an open-source software project. Open-source software projects cannot be granted non-profit status in the US. So we cannot be an official work group at The Monero Project without losing tax exemption status, and we cannot use the Monero name without being a work group at the Monero Project.
Why should we fund this? Well, if the feel-good warm-fuzzy feeling of helping folks go to university to study cryptocurrency, or building libraries for disadvantaged third graders in ZA, isn't enough for you, then you may be a bit of a nihilist. But even nihilists care about their bottom line, and I hope that everyone can see what sort of good this can do for Monero's image. Not to mention, programs like this help bring a new generation of students into cryptocurrencies in general and Monero in particular!
Thanks everyone! I want to, once again, thank the Monero community. I have been granted (heh) the most amazing opportunity to work on this project, and I am incredibly thankful. I hope that all of you appreciate the work that Sarang and I have put into Monero, and I hope that you guys think your funds are being well-spent.