Funding for Sarang at MRL for Q1 2018
WHO Me again, Sarang Noether. I've been working for Monero Research Lab during the present quarter, researching new developments in cryptocurrency technology and applying them to Monero where appropriate. I have a history with the project and have thoroughly enjoyed my work keeping Monero on the cutting edge.
WHAT I am requesting a continuation of funding for the upcoming four month period. This is a slight change that aligns my request with the usual fiscal quarter system. Details follow.
WHY During the current quarter of Forum Funding System support, I've contributed to several important areas of Monero academic research:
- RuffCT / StringCT / RTRS: We're apparently all terrible at consistent naming, but this is the proposal that was put forward in a paper to shorten Monero ring signatures while securely incorporating confidential transaction amounts in a stronger way than the current setup. Turning our linear (in ring size) signatures into logarithmic signatures while throwing in private amounts was an impressive feat by the authors, and I (with my Lab partner, Surae Noether) vetted the mathematics. Along with associate Knaccc, we produced working Java code for the scheme and analyzed its efficiency. While the results weren't as spectacular as our wildest dreams had hoped, the production of sublinear ring signatures was an important step in understanding the nature of Monero's signature scheme as well. It can be proven (unfortunately) that any sublinear scheme must have at least linear verification time. This implies that in terms of computation, the existing scheme is close to optimal (but we pay for it in signature size).
- Subaddresses: A proposal in the works for a while suggested adding subaddresses to the project (thanks to Kenshi84 and several others). This would allow a recipient to use a secret master wallet address to generate an arbitrary number of unlinkable subaddresses. This has the advantage of allowing the recipient to scan incoming transactions only once to identify those destined for any controlled subaddress. There are subtleties in the integration of subaddresses with the existing transaction protocol and in the ways that outputs fit in, but this represents an overall large step for Monero. I authored a whitepaper documenting this scheme and analyzing its security and efficiency. Subaddresses have since been added to the codebase.
- Multisignatures: It's desirable to secure outgoing funds by allowing a sender to demand that several devices or parties produce a single aggregated signature on a transaction, akin to multifactor authentication. However, the goal in our case is to mathematically force the use of multiple parties, rather than have the multisignature be a part of policy alone. An earlier multisignature scheme had errors in its proofs, so I have been working with Surae Noether to produce new and improved security definitions and proofs for a modified scheme. A whitepaper is being finalized for the scheme, and it is being thoroughly checked against the existing codebase to ensure proper implementation.
- Ongoing research topics: A big part of having the Monero Research Lab is ongoing research into the state of the art, whether or not there is an immediate application to the project. After all, if we knew what we needed to research completely in advance, it'd hardly be true research! I and my Lab partner have been actively digging into sidechain technologies (to determine the proper integration into Monero), aggregate signatures (which would allow for compression of multiple signatures), proxy ring signatures, hash function aggregators (and specifically some promising new compact forms), problems with pseudorandom number generators (and how to standardize them in secure ways), consensus algorithms (specifically theoretical and simulation-based work on SPECTRE), and proofs of stake/work/proof-of-work/erasure.
The next quarter (technically, trimester, or whatever) holds a great deal of promise. Specifically, the topics in the previous section are large and ongoing projects. As always, our work product is varied and includes: Whitepapers: These are usually reserved for more "important" changes to the protocol or mathematics that are either novel to Monero or differ substantially from earlier use.
- Summaries: These are usually included in monthly reports and other communications, where the subject is less monumental than those in whitepapers.
- Community interaction: I'm active with other Lab members on our dedicated IRC channels, where the community is welcome to jump in with questions. We also hold regular research meetings (where updates are provided in a structured way) and office hours (where discussion is less formal). I also chime in to r/monero to answer research questions, but most productive discussion happens in real time on IRC.
- Code: Most of my work focuses on math and the cryptography, but we sometimes produce code with other collaborators in the Lab and development group. Code is made publicly available and is used for testing and analysis.
HOW MUCH My request is for 380 XMR for continued full-time research over the four-month period beginning at the start of December 2017 and concluding at the end of March 2018. This represents my interpretation of a fair salary for a qualified independent research mathematician and physicist, where the amount is reasonably averaged using several weeks of XMR market data.
Prices are always in flux with a dynamic project like Monero, so I do my best to keep things fair while accounting for volatility. Should there be large market changes before this proposal is open to funding, we can discuss updating the amount before funding begins.
LET'S DISCUSS I strongly value community input into the funding process, and welcome discussions regarding this proposal.
This request is being made well in advance of the end of the current funding period. This is to provide ample time for transparent inquiry by the community into the research goals, as well as general conversation. One of the things I respect most about the Monero community is its open approach to development, and I want to continue making such openness a cornerstone of the Research Lab.
This timeline provides ample time for questions, comments, complaints, suggestions, and generally vigorous debate. Once there is general consensus, the proposal will be open to community funding.
LAST WORD To close out this proposal, I want to offer my sincere thanks to the community for its overwhelming support for me and the Monero Research Lab in general. I'm passionate about Monero and the beautiful advances in cryptocurrency technology that it represents, and it's been my honor to dedicate my time and efforts to the project. The Lab couldn't function without the community, so I want to thank everyone who has contributed in funding, discussion, moral support, and general well-wishes. I'd thank each funder personally if I could, but that would defeat the point of a kickass private currency, wouldn't it? ;)
EDIT: I've also been putting substantial work into bulletproofs, a proposal for range proofs that has the possibility to reduce transaction sizes. Work into this area of research will continue into this funding period as needed.
Once again, I am blown away by the support and generosity of the Monero community. To everyone who contributed in Monero or in spirit, please accept my sincerest thanks and appreciation. You are the reason Monero continues to succeed!
Hello, friends! Sarang here with my monthly report for February. Once again, my sincere thanks go out to the entire Monero community for your support, both financially and in spirit.
The long and winding road to Bulletproofs continues. Having been in long discussion with several professional groups and interested volunteers, I have received statements of work from all interested auditors, and am compiling them for review. Expect to see a funding request once we have decided on the final selection. I am pleased to report that we have secured the interest of Benedikt Buenz, the lead author on the Bulletproofs paper, to review our Java prototype code. This is an important step in the audit process, since Benedikt is the ideal candidate to examine our implementation of the underlying mathematics. A second auditor (whom we will determine after our final review of the received statements of work) will examine the C++ port and audit for implementation. All in all, the review process is proceeding slowly but surely. We've heard rumblings of other projects interested in our implementation of Bulletproofs, and I've seen indications that some may nab our finished code and receive the advantage of our careful work and audits. This is an unfortunate but necessary consequence of our open development process, but it also speaks to the leadership role Monero is taking in this deployment. Imitation is the sincerest form of flattery, perhaps.
From the land of the literature, I've examined the usual selection of papers. Surae brought to my attention some interest work on succinct representations of partially-ordered sets, which caught our interest because of the data structures required for the SPECTRE block graph protocol. A new paper was released on PHANTOM, a cousin to SPECTRE written by the same authors and discussed at the recent Stanford conference. It has the downside of potentially slow confirmation times and a requirement for a good understanding of network parameters. The authors suggest a possible blend of both SPECTRE and PHANTOM, but details have yet to be worked out. Interesting work, to be sure. Other new work of interest is a paper on Schnorr multisignatures, a paper relating to memory-hard functions, and others. Cryptographic research is alive and well as always.
One literature item of note is an update to the Bulletproofs paper that was released recently. I have been working with one of the authors to discuss and learn about optimizations to the algorithms that have been under development since the release of the original paper. The updated paper includes these optimizations and others, and details the batch verification scheme that is now part of our code. It is certainly worth reading to anyone who has interest in exactly how Bulletproofs work. The paper contains a few small errors in algorithm listings that I found and reported while reviewing it against our code, which the authors will update in a future revision. Work to speed up verification times in Bulletproofs and elsewhere in the codebase (without sacrificing too much clarity, to permit good review) continues with tests of optimizations to common curve operations.
I have been asked to speak about privacy in the cryptocurrency space at an upcoming one-day conference in Portland next month, Discovering Blockchains. It is a non-technical conference intended to provide information to newcomers interested in projects like Monero. I've prepared a talk that offers a basic introduction to the different types of privacy technologies used in cryptocurrencies, discusses the tradeoffs that different projects make, and highlights how to spot things to watch out for. I will be sure to post links to the talk after it's delivered. This is part of my goal to increase general outreach and appreciation for Monero and the importance of privacy technologies. There's no shortage of incorrect information out there, but we can help to ensure that the right information is at the forefront, especially for people just starting to get involved with cryptocurrencies. My attendance at the talk is funded by the organizers and requires no community funding.
Discussions have been ongoing regarding the upcoming change to our proof-of-work algorithm, intended to reduce the mining power possible by ASICs and working to make Monero mining as egalitarian as possible. By instituting regular changes and variants to our proof-of-work method, we can reduce the incentive for new ASIC development. Other operational changes under consideration are an increase in minimum ring size and a protocol requirement to fix ring sizes for all transactions. Allowing variable ring sizes can lead to outlier transactions "standing out" due to unusual ring sizes, and the recent announcement of another project forking the Monero blockchain and offering their own asset to users for spending outputs on their chain has led to suggestions that a small increase in ring size is one step to protect users against worst-case scenarios. It goes without saying that users should not spend Monero outputs on forked chains to avoid deanonymization.
The upcoming month will see more progress in the Bulletproofs review process, additional curriculum development for this summer's outreach cryptography course (discussed in last month's report), and research into new technology that comes our way. Keeping the blockchain small, transaction verification fast, and anonymity high are at the core of what we do. My thanks to the Monero community for generous support of my work. Onward!
Yo there; Sarang Noether here with my monthly report for March. This report is a bit shorter than some previous months, but certainly not for a lack of progress. As always, my thanks go out to you fine folks in Moneroland for your continued support of my work and Monero research in general.
The audit process for Bulletproofs is underway, thanks to generous funding support from the community. Due to recent price fluctuation, expect a second round of funding to cover the needed amount, which is set in U.S. dollars.
I presented at the Discover Blockchains event in Portland about the importance of privacy in cryptographic assets. The audience was primarily non-technical, so as the only active researcher on the speaking roster, I was glad to provide good information that the audience likely did not already know. There were some dubious claims made in a few other talks that it was nice to address.
Related to this, msvb-lab and I submitted a proposal to present at the upcoming DEF CON China event in Beijing. The presentation would cover the basic mathematics and cryptography behind Monero, an overview of known weaknesses and our approach to mitigation, as well as hands-on experience with hardware. We are waiting to hear if the talk is accepted. Expenses are covered by the organizers, so we would not expect a need for community support to attend.
I further assisted Surae Noether with the last steps of his excellent multisignature paper. Expect to see it on an internet near you in the near future once the last bits of narrative and proofreading polish are complete.
There has been an increased amount of outreach and analysis this month in response to some high-profile media attention surrounding both an unaffiliated key-reuse fork (not our scheduled network upgrade, mind you, which is different) and the release of an updated paper on tracing. The tracing paper doesn't really address anything we didn't already know about, despite some of the poor journalism regarding it in the media. Much of the material from the paper was addressed last year with a larger standard ring size and the widespread use of RingCT-only transactions taking advantage of the ring benefits. Further, we are in the process of once again updating the way we select fake outputs in ring signatures to better match known spend patterns; this change does not require consensus and is independent of any network upgrades. As to the key-reuse fork, our fine developers have mitigations ready for both Monero and alternate projects to use, but the safest course of action for all users is not to claim funds on unaffiliated forks. We will continue to educate the public on best practices for safe use. It was put very elegantly by sgp that "Monero is a tool that can provide significant privacy under a variety of use-cases."
It was recently announced that Surae Noether and I will serve on the board of MAGIC: Multidisciplinary Academic Grants in Cryptocurrencies, a new U.S. nonprofit organization dedicated to supporting education and outreach for cryptocurrency research and public knowledge. Funding permitting, in its first year of operation, the group expects to offer several grants to graduate and undergraduate students; it will also plan and operate a free cryptocurrency development and research conference next year focusing on privacy. The organization is not directly affiliated with either the Monero Project or Monero Research Lab (for legal reasons), but operates independently and with community support. We strongly believe that encouraging and supporting education will empower new generations of researchers and developers and benefit projects like Monero far into the future. The organization's board will meet next month for planning and nonprofit legal paperwork.
Now on to Sarang's Reading Corner. A lot of interesting papers come to my attention, both old and new, and there have been requests that I share some of them. Here are a few of the interesting ones:
zkLedger: Privacy-Preserving Auditing for Distributed Ledgers, an audit-friendly distributed ledger that would not scale outside of a semi-centralized system
Stake-Bleeding Attacks on Proof-of-Stake Blockchains, a great analysis of certain proof-of-stake attacks that continue to convince me why PoS is not a good idea
A neat paper describing efficient Pippenger multiexponentiation
An Empiric Analysis of Traceability in the Monero Blockchain, an update to a paper describing known methods of analysis of certain transactions
zkSNARKs in a Nutshell, a nice overview
Thanks again to the community for ongoing support of the Monero Research Lab. Onward!
Hello there! Sarang Noether here with my monthly report for December. I'm pleased to report good progress on several important projects, and want to start by thanking the Monero community for your support.
The primary task this month has been a continuation of Bulletproofs. As you've probably read elsewhere (like this blog post), range proofs are an important component of Monero's confidential transactions that allow us to keep amounts secret. Bulletproofs are a replacement for our existing range proofs that used Borromean ring signatures and took up a substantial amount of space on the blockchain. I used the recent Bulletproof white paper to work up Java code, perform testing on correctness and efficiency, and work with moneromooo to get the test code ported for eventual inclusion into the Monero codebase. Single-output Bulletproofs are currently undergoing testing on testnet and will be included in a future release when ready. Multi-output Bulletproofs, which offer even more space savings that scale to larger transactions, are being tested separately since they necessitate a change to the way we handle fee scaling in order to avoid denial-of-service attacks from transaction packing. Releasing Bulletproofs in stages will provide an immediate reduction in transaction size and continue to offer further benefits once the rollout is complete.
I've been working with Surae Noether on finalizing the multisig project. Surae has put a lot of excellent work into updates, documentation, and analysis of our multisig mathematics in a forthcoming whitepaper, and I have been assisting with the analysis and review. The multisig code is set for release already, and the corresponding paper will be released after final review.
A project that was started earlier is a study of SPECTRE, a proposal to replace a blockchain structure with a more generalized graph structure. I began investigating this during my previous funding period, but it was placed on the back burner when Bulletproofs took center stage. Now that we have Bulletproofs staged for future release, my interest in SPECTRE has been renewed. Because it uses a more complex consensus algorithm than the Nakamoto longest-chain consensus method, there is a lot of testing and analysis that needs to be done. The benefits, however, are intriguing: an implementation could increase the block rate substantially without compromising the security of the network. Surae wrote up a test implementation in Python that he and I are playing with. The implementation makes the voting protocol much faster than listed in the original whitepaper. We're testing edge cases by hand and in code, and generally working toward a more complete understanding of the benefits and drawbacks of SPECTRE for Monero. There are no defined plans to switch our chain structure, but I maintain an interest in determining the feasibility of SPECTRE for the future.
An ongoing topic of conversation within the research group has been a desire to develop educational outreach opportunities in applications of cryptography to distributed ledgers like Monero. I will be sharing the good news about modern cryptography with gifted students this summer through a Duke University program in the United States. I've taught courses to less advanced students that touched on modern topics, but this course would permit more time to discuss modern techniques and constructions to students with more mathematical experience. It would of course include projects in cryptocurrencies like Monero! Development of the curriculum is ongoing.
Finally, a new paper was released on efficient zk-SNARKs without trusted setup. Earlier work on zk-SNARKs required trusted parties, and some coins already use this. Monero's philosophy of privacy means that a trusted setup is an automatic no-no, which makes the new paper so interesting since it assumes no trusted parties. I have been working through the whitepaper and plan to write up a simulation if it continues to show promise. A comprehensive analysis of the potential space and computation costs is also in order, and this will continue into next month. Again, there are no immediate plans to switch to a zk-SNARK setup in Monero, but the technology is interesting and merits ongoing investigation.
Once again, it's been my pleasure to continue working for the Monero Research Lab. As always, there has been a flurry of activity in the cryptographic community, and the Lab prides itself on keeping up with new developments to determine their applicability to the Monero project. Many investigations do not see the light of day, but others (like Bulletproofs) do; this is the blessing and curse of the research community! Expect to see a continuation of my current projects into next month, as well as whatever new work is thrown my way.
Onward and upward!
This is absolutely excellent to hear, Sarang. Your work and that of the rest of the MRL are in large part what make Monero such an outstanding cryptocurrency; keep it up!
Thank you for all that you do for the community! You and moneromoo are two of the many reasons I really believe that Monero is leaps ahead of the others in regards to research and testing. I'll continue to donate as long as you want to work on the project!
Good day to you! This is Sarang with my monthly report for January. As always, my sincere thanks go out to the entire Monero community for your support, both financially and in spirit.
Much of my time this month was devoted to finalizing our implementation of bulletproofs. You might recall that we began investigating bulletproofs, which are a replacement for the range proof component of our confidential transactions, after they were introduced in a paper late last year spearheaded by Stanford's applied cryptography group. After verification of the underlying mathematics, I worked up some Java prototype code using our test libraries, both for the single-output and aggregated multi-output cases. The code for both proof styles has now been ported by moneromooo and tests correctly. Due to the key role that range proofs play in our transactions and the lack of peer review for the paper since the technique is new, there was general consensus that our code should receive the benefit of independent third-party review. This is due to the sensitivity of Monero's functionality to the correctness of range proofs, and because of the important role that external review plays in the broader research community. I've been working this month with several professional security groups to arrange statements of work; expect an FFS request once this "audit of the auditors" is complete. While the study and integration of bulletproofs has been a long process, the end result is smaller and speedier transactions. The review timeline means that bulletproofs will not make it into the March hard fork, but we consider this a necessary tradeoff for our belt-and-suspenders approach to such an important change.
Thanks to generous FFS support, my Lab brother Surae Noether and I attended the Blockchain Protocol Analysis and Security Engineering 2018 conference at Stanford. The conference featured a packed schedule of presentations on new theory and techniques for cryptocurrencies and distributed ledger technologies, and it was a great honor to represent the Monero research team. One notably interesting and unexpected technical result from the conference was Andrew Poelstra's discovery (made during a break between talks!) of a simple but useful batch verification that can be applied to bulletproofs, offering yet another optimization for proof verification. I'm adding the functionality to our prototype code before inclusion in the ported code that will go into the formal review process. Additionally, I met several people working with cryptocurrency funds and was pleasantly surprised to learn of the support Monero has within such companies despite initial perceptions of regulatory challenges. This was a reminder to me of Monero's growing role and position in the cryptocurrency space, and also of the need for the community to be conscious of the importance of outreach and education about our technology and its benefits. Face-to-face conferences remain an essential part of quality academic research, and this event was no exception.
To advance educational outreach in a meaningful and broader way, and to build relationships between the Monero community and educational institutions, my lab bro Surae Noether and I have been actively engaged on initial planning for a new project. We don't want to release details just yet until a few more things have been worked out, but we are pretty excited. We hope to share details soon about ways to reach out to students for structured research and learning opportunities.
Related to educational outreach, I am continuing work on curriculum development for a three-week intensive summer course on cryptology and cryptocurrency development written for audiences of gifted high-school students. An opportunity to pilot such a course this summer in the United States has been confirmed. The course is a perfect avenue to begin our outreach efforts under the organizational structure of a host university, since bootstrapping a broader academic program is challenging when done outside of more traditional academic settings. The course would not require any community funding; by way of full disclosure, I would be compensated for teaching it, and so would not seek regular FFS funding for my research time during the course. While the host university's policies would not allow me to record or distribute lectures (for student privacy), all other course materials would be made publicly and freely available for use and modification by anyone. Comments and suggestions regarding the course structure and curriculum are welcome!
Finally, several small projects rounded out the month's research activities. For example, I and the lovely and talented moneromooo proposed changes to the way we handle certain large exponentiation operations. These offer speedups in the bulletproof code and elsewhere, making our code a little snappier and our users a little happier. The optimizations are also being integrated into the sublinear ring signature prototype code that was written late last year; you might recall that the project stalled due to slow verification times, but it is being revisited thanks to the speed and space savings offered by bulletproofs (and a C implementation is forthcoming). Ongoing work into block graph structures continues, and I expect continued interest in techniques like SPECTRE will help fuel work to make DAGs more efficient for use in distributed ledgers. New developments in zk-SNARKs and zk-STARKs were reviewed and found to be interesting, but will not be pursued for Monero at the present time due to concerns over space and memory requirements.
The Lab exists and operates thanks to the support of Monero's fine community, and I remain always grateful for the opportunity. As always, I and others in the Lab welcome questions, comments, and suggestions regarding our work. Like with all research, most developments in this space do not see direct application, but we distill as much good work as possible into the codebase. Monero remains a shining example of how open and dedicated collaboration can produce outstanding results, and this will continue to next month's research and beyond.
One topic of research interest not mentioned in the proposal is that of range proofs. I've been looking into bulletproofs to assess their usefulness as a replacement for our current range proofs. Code is underway!