Heyo, Dr. Sarang Noether here with my May monthly report, the last one for the current funding period. As always, my thanks to the community for funding my research and the Monero Research Lab in general. I'll be teaching a cryptography course during June (during which time I won't be receiving any FFS funding), so expect my next funding request when that is finished. This month has been a flurry of interesting work surrounding research into exciting developments for Monero.
Much research this month has gone into new developments in refund transactions, which were briefly introduced in my last report. I'm working with other researchers on interesting and novel non-interactive approaches to refunds that were originally suggested at a workshop in London. This work led to the construction of a modified type of transaction output and ring signature that has been examined for security and efficiency; details are in a Lab technical note I've written that will be broadly released after the usual internal review. Refund transactions are important for the construction of payment channels, and this work provides one option for enabling them. Research in this area is ongoing.
Work on our Bulletproofs implementation continues toward the next network upgrade, when we intend to release them. Prior to this, auditors will complete their reviews and provide feedback. Because of the efficiencies that Bulletproofs provide, we need to adjust our fee formula to avoid denial-of-service attacks by correctly taking into account the space and time savings. Basically, if the fee formula were unchanged, an attacker could pack a transaction with meaningless outputs very cheaply in a way that would force other nodes to waste a lot of processing time. We've acquired additional test data and will be making proposals for consideration. On a related note, I've completed prototyping of some additional low-level algorithms (Bos-Coster, Straus, and Pippenger multiexponentation) for even faster range proof verification than we saw in our early tests, and they are being implemented and benchmarked. The Lab is confident that this long effort will result in much faster and cheaper transaction processing. Hooray!
As mentioned above, I'm teaching a three-week cryptography course for a Duke University program during June. The program brings challenging university-level courses to gifted high-school students who are extremely motivated and interested in the subject material. This is a great opportunity for outreach to inspire the next generation of mathematicians and cryptographers. Monero and other projects need good talent! I'm not allowed to record course lectures due to Duke policy, but all my notes and other materials will be posted to GitHub for anyone to use, enjoy, or modify.
The research roadmap for the Lab is updated, and I recommend you check it out and comment with any questions or suggestions on GitHub.
Many papers crossed my desk, so here's the next installment of Sarang's Reading Corner.
MuSig: This paper on key aggregation in a Schnorr-type multisignature scheme was revised after a flaw was identified in one of its security proofs. No exploit is known, but the scheme was modified to provide correct and more robust proofs. An update to our multisignature scheme was considering using a similar approach, so this update is being taken under consideration.
On the Provable Security of Multi-Signatures: This paper introduces the MuSig flaw and a flaw in another signature scheme. As you can tell, multisignature schemes are a hot topic of research these days.
Practical Constant-Size Ring Signature: We'd all love smaller ring signatures, right? They're more complicated than you might think, especially given the unique requirements we have for linkability and integration with our transaction model. This paper offers a suggestion involving accumulators, but an efficient realization isn't there.
Zero to Monero: Our researcher friend Koe has released an update to a document he based on earlier work by Kurt Alonso that explains Monero's transaction model in detail. The new update includes some great information on our multisignature scheme. This is a must-read if you want a better understanding of how your favorite cryptocurrency works.
Dandelion: This paper introduces a new networking model for Bitcoin to help users stay anonymous. It splits transaction propagation into two stages in a clever way. There are some tricky subtleties involving efficiency and security.
Homomorphic Secret Sharing: This is a neat idea on how to split a secret among multiple parties such that each of them can perform part of a computation on the data. There are interesting potential applications to such a scheme.
An Empirical Analysis of Anonymity in Zcash: This paper is a deep dive into several techniques for reducing the practical anonymity of Zcash. One lesson to be learned is that user behaviors associated to optional privacy can cause problems. If you use Zcash, keep your transactions shielded.
Post-Quantum One-Time Linkable Ring Signature: This paper introduces a lattice-based one-time linkable signature and proposes applications to confidential transactions.
My next funding request will appear in advance of the completion of my cryptography course, after which I'll dive right back into research. Ongoing projects for the next funding period include the finalization of the Bulletproofs implementation for the next network upgrade, further algorithm optimizations for speedier transaction processing, more work on refund transactions, new investigations into atomic swaps, work on transaction behavior and heuristics, and plenty more!
My thanks to everyone who offered support, both financially and in spirit. Monero continues to succeed because of quality research and an outstanding community. Onwards!