Sarang: funding for April/May 2018
It's your pal Dr. Sarang Noether, back again to request funding for continued research for the Monero Research Lab (MRL). I've been working full-time for MRL since last autumn and am excited to continue doing so if funding is available.
I am requesting continued funding for the upcoming months of April and May. A typical funding request would be for a full calendar quarter; however, I will be teaching a cryptology course in June as part of our education outreach efforts. Since I would be paid a small stipend for teaching it, I am not requesting funding for that month. Details on the requested amount are below.
Monero relies on good research to stay on the cutting edge of technology that benefits our users. In the past quarter, I've spearheaded and worked on several large projects, some of which I'll describe here.
The most visible of these projects has been Bulletproofs, the replacement to our existing range proof scheme used to protect confidential transactions. Using some recent excellent work led by Benedikt Bunz, I worked up prototype code that was later ported by the talented moneromooo for inclusion in our codebase. I am leading the fundraising process and management of the audit of our implementations, which is ongoing with several outstanding groups that include the lead Bulletproofs author. I also worked with another of the authors to test and implement further optimizations to the algorithms. The result is an unbelievable decrease in transaction size and verification time. This project has been months in the making, but is important work that has outstanding benefits. We're making sure that it's done correctly. And since Bulletproofs are also a more general technique that can be applied to arithmetic circuits, we are interested in possible future applications to Monero that extend beyond range proofs.
Many interesting papers have come out over the last few months with varying applications to cryptographic assets. If you wish to get a sense of the scale of research that happens, check out the cryptology eprint archive; it's a constant stream of new work, some of which I'll outline here.
I and my lab partner suraeNoether have maintained an interest in block graph structures because of their applications to transaction scaling; see papers on SPECTRE and PHANTOM. These protocols have their benefits and drawbacks, but graph analysis complexity and certain edge cases make them not ready for primetime quite yet. At the Stanford BPASE18 blockchain conference for which the community generously funded my attendance, there was discussion about ideas for a hybrid consensus mechanism combining the two techniques. We'll see where that goes!
There's much talk about zero-knowledge proof systems and their application to private currencies. For example, the Zcash project uses a technique called zk-SNARKs to offer (optional) fully anonymous transactions. As we've seen with the history and analysis of our ring signature scheme and key-reuse forks, the size and structure of anonymity sets matters, and I would like to see Monero move to a much larger anonymity set. Unfortunately, existing efficient zero-knowledge systems (like in Zcash) often require a trusted setup, which is an automatic no-go for us. Papers came out discussing trustless zk-SNARKs and zk-STARKs; these schemes unfortunately lack the level of scaling and efficiency required for our applications. Bulletproofs offer zero-knowledge possibilities that remain a more practical avenue of research. All of this work speaks to the rate at which new research continues in this area.
Other assorted interesting papers crossed my path. Matt Green and a student looked into a scheme for efficiently describing ring members to be used in ring signatures. Another paper proposed a new RingCT scheme that turned out to require a trusted setup (authors seem to hide these things). And the list continues!
Educational and charitable outreach have lingered in my mind since beginning work with MRL. There are many excellent researchers in this field, but a depressing lack of education into cryptocurrencies and applied cryptography relating to distributed ledgers at the high-school and undergraduate level. If we want to see cryptographic assets continue to grow and thrive to future generations, we need to get talented students interested and working with the mathematics, computer science, and technology specific to these kinds of projects. To that end, we have several initiatives in the pipeline.
The biggest of these initiatives is the brainchild of suraeNoether that I'm assisting with, a new registered nonprofit called Multidisciplinary Academic Grants in Cryptocurrencies (MAGIC) that will offer scholarships and research funding for students interested in this field. Working within the nonprofit legal infrastructure will help MAGIC to better integrate with institutions and organizations around the world to reach students. In a related effort, I will be teaching a course this summer through the Duke University Talent Identification Program on cryptography that will place a large focus on modern techniques and applications to cryptocurrencies. Working through this Duke program allows us to pilot and test the idea of more targeted courses in the future and reach identified gifted and talented high-school students to get them interested in STEM careers in applied cryptography. While I'm not allowed to record lectures (since the students are minors), all other course materials that I develop will be made publicly and freely available.
Relating to outreach are conferences and speaking engagements that have arisen. The community funded travel for me and suraeNoether to attend the BPASE18 conference at Stanford (mentioned earlier). This was a fantastic opportunity to meet with some of the finest researchers in applied cryptography and learn a great deal about new technology in development. Having a presence at conferences is important to maintain good relationships with leaders in academia, industry, and other related cryptographic projects. I was also asked to speak at the upcoming Discover Blockchains event in Portland to discuss privacy technologies in various cryptocurrency projects. The conference is intended for an introductory non-technical audience. There is a lot of really terrible information that gets presented to newcomers (from media and elsewhere), so having researchers available to provide correct information helps our project and encourages folks to get involved. My travel and lodging at this one-day conference are funded by the organizers.
These are just the start of many opportunities for outreach that we're excited for! Such efforts will both work to improve Monero's public image, as well as empower future generations; a rising tide of new talent lifts all boats, including ours.
Other smaller projects have received attention this quarter. In one example of note, with the lovely and talented moneromooo, I've been working on a few optimizations to some of the algorithms used in certain scalar-curve operations throughout the codebase. We used these optimizations in our Bulletproofs implementation, and are looking into ways they can be applied elsewhere, both in current code and future work like sublinear ring signature schemes.
My associate suraeNoether has continued his excellent work on multisignature scheme analysis, discussing it with several other researchers and taking in account new work in this area. We want to be sure that security definitions for multisignature schemes are well understood, and the ongoing paper works to tackle this. I've been offering what assistance I can with review of his work.
For the next two months, the audit of our Bulletproofs implementation will continue, and I will be managing the effort and offering assistance to the reviewers about our work. The result will be final reports from the reviewers that will be released publicly; any relevant changes to code will be made based on the audit results. Until then, expect not to hear much about the process while the auditors do their thing.
I will continue work on algorithm optimizations that can provide faster transaction operations for our users. We've implemented two useful algorithms for multiexponentation, and I want to add a third into the mix that will require development and testing.
The new nonprofit MAGIC group is just getting started, and there's plenty of administrivia and planning to be done to raise funds, determine the structure of our grant and scholarship programs, and start providing assistance and guidance to students.
I'll continue curriculum development for the pilot summer course in applied cryptography, finalizing the course materials and getting ready to teach for the three-week program. All course materials will be released freely for anyone to use!
New research and literature will cross my path, and a big part of my job here is to stay on top of it and determine what shows promise for the Monero codebase. Much of it doesn't see the light of day, but some research (like Bulletproofs) ends up being a big deal. It's the nature of research and development.
In line with my previous requests, I will be asking for the XMR equivalent of $9,000 USD per month. This is in line with market rates for a Ph.D. scientist and mathematician (accounting for the tax implications of working outside a traditional employer), and represents my assessment of fair compensation. Once discussion about this request has concluded and the request moves to Funding Required, I will use an exchange rate average to determine the XMR amount. I think this is the most fair and transparent way to set the desired funding level due to price volatility.
Edit: The amount has been set to 67 XMR now that the request has been moved to Funding Required.
I welcome and value community input regarding my funding requests and research reports. I work for the Monero community and want to ensure that my efforts reflect both the state of the art in applied cryptography and the desires of the community as to the direction that new development should take. I'm available as u/SarangNoether on r/Monero and as sarang on #monero-research-lab (and other related IRC channels) to chat publicly about research.
Thanks as always to everyone who supports my work and that of MRL, either financially or in spirit. Monero is an extremely unique project that only continues to exist and thrive because of the hard work of its community, and I'm thrilled to be able to help in this way. Onwards!
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!
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.
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.
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.
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.
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.