Donated.

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!

Commenting to help get this to funding! You do amazing work for this community!

Hello there! Sarang here with my April monthly report. This month has been a flurry of activity as usual, and here is a short summary of my work. Every month at the Lab is different and unique, but always interesting. As always, my thanks to the community for continuing to fund research that helps keep Monero safe, secure, and on the cutting edge.

IEEE Workshop

The community generously provided funding for me and labmate Surae Noether to attend the recent IEEE Security & Privacy on the Blockchain workshop in London. Prior to the event, we had a chance to meet up with two organizers of Monero meetups in London (and got some great Monero stickers). Always a pleasure to spend time with fellow Monero lovers!

The workshop featured quality talks on security in cryptographic assets, some of which had direct Monero applications. One talk by Kevin Lee discussed the implications of adversarial remote Monero nodes when generating transactions. In particular, it was suggested that an evil remote node could provide corrupted mixins to a light client and, when the client requests new mixins, use their intersection to identify a true spender. However, wallet software warns the user if an output is known to be corrupted, making this attack infeasible. The evil remote node could also selectively corrupt outputs in the hope that the client does not detect the behavior, but this is a far less effective method of gaining any information. A proposed mitigation is to use an authenticated data source to prevent remote nodes from corrupting outputs, but this could be costly for little practical benefit. Another mitigation is to have clients query multiple nodes and ensure their responses agree. It is worth noting that users should not be using remote nodes that they do not trust, and that the use of a local full node prevents any funny business. This research was responsibly disclosed to Monero developers in advance of its publication.

A second talk relating to Monero was given by Alishah Chator on a method of compressing the description of ring mixins for large ring sizes to save space. If Monero were to move to extremely large ring sizes, the identification of ring members may become unnecessarily large; note that this is separate from the ring signature itself. The Lab was provided a copy of this paper prior to the workshop and considered its implications. Unfortunately, it provides no benefits for the relatively small ring sizes used as current defaults. Any move to very large ring sizes would require a sublinear signature scheme; unfortunately, any ring signature scheme must have verification times that are linear in the ring size. This makes known approaches too slow for practical use with ring sizes for which this research applies. However, if a sublinear signature becomes practical in the future, this compression technique may prove useful.

As always, the Monero Research Lab appreciates the work done by independent researchers into the security, privacy, and efficiency of Monero. We encourage new research and investigation, and always ask that suspected vulnerabilities be responsibly disclosed to us prior to publication.

Audits

Two of the three Bulletproofs audits have begun, with Kudelski Security and QuarksLab starting their processes. I will continue to coordinate the effort and work with reviewers during this time. Expect results in the next month or so, depending on the reviewers' timelines. Results from the audits will be made publicly available. Separately from the audits, additional unit testing is underway for some optimizations made to our Bulletproofs implementation to ensure speedy performance.

Hair on Fire

We sometimes see scary-sounding reports come out about this technology or that, which require folks like me to devote unexpected time to analyzing their potential effects on Monero. Here are a couple from this month.

A preprint (not a peer-reviewed paper, mind you) was released that provided an overview of some historical and patched attack vectors on Monero anonymity. The paper also discussed a supposed new attack whereby the attacker reuses the same ring of her own controlled outputs to attempt to reduce other transactions' effective ring sizes. I reviewed the paper and consider this not to be anything of concern. It is already trivial to look at another transaction that includes an output you've already spent, as this is simply a consequence of the use of mixins in ring signatures. The only new addition here is that ring reuse makes this spend pattern public instead of secret. An attacker doing this is simply making it known that she is doing so (which is not necessarily a clever approach!); out of an abundance of caution, wallet software will have the option of blacklisting such rings. It's worth noting that the authors of this paper did not contact us in advance or otherwise provide responsible disclosure. Personally, I consider this a poorly-written paper that mostly describes old material and may be an attempt to gain publicity (but who can tell for sure). The Lab remains unconcerned, and disappointed that the authors did not use established channels to let us know.

It was recently discovered that certain implementations of the SecureRandom library in JavaScript, used by some applications for producing random data, are flawed and produce biased output with low entropy. Concern was raised that any use of SecureRandom to generate private keys for cryptographic assets could put those users at risk of having their keys recovered by an adversary. We analyzed the two popular JavaScript-based Monero key generators. Neither library uses SecureRandom, so no users of these tools are at risk of the listed problems. Additionally, we confirmed that these tools will only generate keys using high-quality random number generators found in modern browsers, and will fail to produce anything if they are not able to do so securely. However, this is a good opportunity to remind everyone that you should always run the most recent patches for your browser and computing environment to keep yourself safe.

Churn

A topic of interest this month has been that of churn, whereby you send funds to yourself one or more times to expand the size of the "ring tree" from your original receipt of the funds to the end of your churn cycle. A possible attack vector may involve an adversary making controlled spends to a vendor, who may churn before depositing funds in an exchange that knows his identity. If the adversary obtains the exchange's records, it can examine the ring tree and attempt to make conclusions about the presence or absence of the controlled spends. Of course, many other transactions likely include the controlled spends as ring mixins, so the vendor is still guaranteed the plausible deniability afforded by ring signatures. However, we want to better understand the role of churn in these heuristics. We're working on some statistical models and simulations to determine what, if any, is the optimal churn to give users better control of their privacy if they are concerned about such controlled spends, while saving time and money by not churning unnecessarily. It's worth noting that nothing about a controlled spend affects the mathematical security of ring signatures or funds, as it is only a heuristic.

Refund Transactions

Informal discussions with a Purdue researcher at the IEEE workshop yielded great new information about refund transactions under active research by one of his students. Refund transactions are a necessary component of certain payment channel applications. A scheme was proposed to us that involves modifying the structure of outputs and ring signatures to allow for a sender to include two outputs: one is valid prior to a specified block height, and the other is valid afterward. We are working with the researchers on the details and security of this scheme, which could have great applications to Monero transactions.

Sarang's Reading Corner

Continuing last month's new tradition, here is a (partial) list of papers that I've come across recently. Their inclusion here doesn't imply my endorsement or agreement with the conclusions.

• Zero to Monero: A great technical and mathematical overview of Monero's transaction model.

• How to Squeeze a Crowd: Relatively new research on how to efficiently describe members of large rings. This was provided to the Lab earlier and also presented at the IEEE conference.

• FruitChains: A Fair Blockchain: A clever method of performing "dual mining" of transactions and blocks to reduce incentives for pool mining.

• Backyard Cuckoo Hashing: An efficient dynamic dictionary, along with a good overview of related work in this area.

• Invisible Sanitizable Signatures: Results showing that delegated signatures, which allow for the offloading of certain modifications to the message, are equivalent to public-key schemes.

• Pseudorandom synethesizers, Functions, and Permutations: Doctoral dissertation with a fantastic review of pseudorandom functions and permutations, as well as constructions for generating randomness in parallel.

• Efficient Zero-Knowledge Arguments for Arithmetic Circuits: The zero-knowledge construction that was used (with modifications) as the basis for Bulletproofs.

• Updatable and Universal Common Reference Strings with Applications to zk-SNARKs: A new method for allowing users to update the common reference string for zk-SNARK operations on their own, offering new applications to the "trusted setup" of current efficient schemes.

• Constant-Size Traceable Ring Signatures Scheme: A ring signature scheme providing constant-size operation that unfortunately requires a trusted setup.

• In Search of CurveSwap: An overview of elliptic curve use in the wild.

• Rethinking Large-Scale Consensus: A formalization of permissionless consensus with interested bounding results and applications to Nakamoto consensus.

• Burning Zerocoins for Fun and Profit: A new attack on Zerocoin protocols that allows an attacker to burn the funds of other users.

6.7 xmr sent. Thanks for your amazing work.

donation on its way :) thanks a lot!