Sarang: research funding for 2019 Q3
Hello to you. This is Dr. Sarang Noether, requesting ongoing research funding for the next quarter. My current funding period is complete at the end of June, and I'm ready to go for another three months of research and development for the Monero Research Lab.
My monthly reports for the current funding period are available, and I encourage you to read them:
The last few months have seen plenty of work on formalization and testing of new signature schemes, output selection, sublinear transaction protocols, Bulletproofs, input merging, and more.
As always, the list of research topics of interest is constantly evolving! Some items of interest:
- CLSAG review and deployment: Both the mathematics and implementation of the CLSAG signature scheme should be reviewed prior to deployment.
- Analysis of sublinear transaction protocols: This includes Lelantus, RingCT3.0, and Omniring. Each presents different tradeoffs in efficiency, privacy, and usability.
- Ristretto: The use of an abstraction layer may provide a useful way to take advantage of some of the efficiency and security benefits of this curve representation.
- Output selection: There are aspects to this (like fixed output sets) that are of interest, especially as we look toward transaction protocols with larger practical anonymity sets.
- Dynamic block size improvements: This is a holdover from my last request that there was not time to investigate properly.
- Efficient circuit code: Several different scaling solutions to zero-knowledge circuit evaluation, from Bulletproofs to Spartan, are of interest.
- Literature review: This is, as always, ongoing.
- Outreach and education: These typically include episodes of Breaking Monero, Coffee Chats, and other avenues.
- The unexpected: Research rarely goes precisely the way we expect, so it is important to stay on top of whatever new proposals or issues arise unexpectedly.
As always, I work hard to provide value to the community and project for the value you provide here. For the funding period beginning July 2019 and continuing through September 2019, my request continues to be 10415 USD per month, my assessment of market compensation for an independent Ph.D. researcher in the United States with a record of quality work. Therefore, the request total is 355 XMR, based on a 14-day exponential moving average of 88 USD/XMR taken from Kraken.
Please read this paragraph carefully. As was done for my previous request, this request will be paid out in full immediately when it is funded. This greatly reduces the volatility that otherwise arises from being paid out over time for ongoing work, and ensures that the value of donations is the value that reaches me. I hope that my record of work for the project speaks for itself, and that I continue to earn your trust to continue that work.
Comments, questions, and discussion about this proposal are welcome. This community continues to stand out as unique for its ongoing support of research and development, and I want to thank everyone who supports the project in whatever way they choose. Let's continue to build and improve Monero. Onwards!
Merge request reports
Activity
MRL is continually working on the fundamentals of Monero and that work cannot be overstated.
Sarang is also active in many community related activities such as the coffee chats and the breaking bad video series. Sarang seems to contribute wherever he sees a need above and beyond the "on topic" list of work he has provided above.
mentioned in commit 88129428
It's time for the first monthly research report for my current funding period. My thanks as always to the entire community for ongoing support of research and development for the Monero ecosystem.
Verification time improvements to MLSAG signatures, as well as updates for more robust security, are now available as a pull request. Similar updates have been made for the CLSAG signature scheme as well.
The CLSAG paper has been updated to reflect comments, corrections, and suggestions we received. Versions are available on IACR and the internal archive.
The author of the Lelantus transaction protocol developed a method for layering proofs in order to significantly decrease prover complexity at the cost of added space and verifier complexity. Code examining this updated proving scheme is available.
I have completed a space and verification complexity analysis of the RingCT 3.0 (RCT3) transaction protocol. This protocol uses a Bulletproofs-type proving system to show the validity of spends, and supports batch verification. The analysis shows the effects of this batching on typical transactions.
In conjunction with this analysis, I have prototype code for RCT3 in progress. It demonstrates correctness, shows sample transaction flows, and examines how to apply some efficiency improvements to the verification described in the original paper. This proof-of-concept implementation is ongoing, as is research into ways to maintain key image compatibility.
Finally, there were many small updates to other libraries that I've written, from basic curve operations to Bulletproofs.
Shortly, I will be presenting a talk and workshop at DEF CON in Las Vegas at the Monero village, in addition to participating in a panel discussion in the blockchain village. In the talk, I will discuss recent proposals for the Monero transaction protocol: CLSAG, DLSAG, Lelantus, Omniring, and RCT3. The workshop will be a hands-on opportunity for participants to build simple cryptographic constructions similar to those used in Monero; handouts and sample code are available.
On a more whimsical note, I delivered a fun lecture on the Enigma cipher machine to a cryptography course taught by a friend. It had nothing to do with Monero whatsoever, but Enigma is a fascinating story with some really clever mathematics behind its analysis, and it's always great to get students excited about applied cryptography!
And now on to Sarang's Reading Corner, a short listing of some interesting papers that I have come across this month. The appearance of a paper in this list does not mean that I necessarily agree with its contents or correctness, or that I endorse it. Papers are in no particular order.
- The privacy of the TLS 1.3 protocol
- Temporary Censorship Attacks in the Presence of Rational Miners
- Efficient Perfectly Sound One-message Zero-Knowledge Proofs via Oracle-aided Simulation
- Security Audit of Particl Bulletproof and MLSAG
- Cryptocurrency Egalitarianism: A Quantitative Approach
- Sucker punch makes you richer: Rethinking Proof-of-Work security model
- A Survey on Zero Knowledge Range Proofs and Applications
- Map-Z: Exposing the Zcash Network in Times of Transition
It's time for the secondly monthly research report for my current funding period. Thanks as always to the community for its support for research.
Transaction protocol analysis continues. While the current RingCT 3.0 protocol contains an exploitable flaw, a fix is forthcoming. Its proof-of-concept code has already been updated to include a more efficient verifier and support for fees, and the code will be further updated once the fix is released. Proof-of-concept code for Lelantus has also been updated for robustness. I continue to research the applicability of new proving systems that have been released as preprints.
At this year's DEF CON event in Las Vegas, I had several roles. Besides answering many research questions, I presented a talk on transaction protocol efficiency, led a workshop on coding basic cryptographic constructions, created a cryptographic challenge puzzle, and participated in a panel.
A couple of pull requests deserve mention. One of them, PR 5807, fixes an issue where basic Schnorr signatures used a biased nonce value. Note that these signatures are not used for on-chain transaction signing. Another, PR 5707, speeds up MLSAG ring signatures by removing redundant point operations. This has been updated to simplify available hash-to-point operations. Code for CLSAG has been updated to reflect these underlying changes.
New material has been written for the somewhat outdated Zero to Monero document. I have updates covering Bulletproofs and commitment data available.
Both the CLSAG and threshold ring signature preprints are being revised in preparation for their submission for peer review. Several possible conference and journal destinations have been identified, but the review process is often quite lengthy.
Thanks to recent work by Surae Noether, code used for analyzing bipartite graph matchings is being updated and analyzed to run simulations. The results will be used to better understand the relationship between transaction operations and tracing heuristics.
And now on to Sarang's Reading Corner, a short listing of some interesting papers that I have come across this month. The appearance of a paper in this list does not mean that I necessarily agree with its contents or correctness, or that I endorse it. Papers are in no particular order.
- Bitcoin Security under Temporary Dishonest Majority
- New Efficient, Constant-Time Implementations of Falcon
- Analysis of Nakamoto Consensus
- Does "www." Mean Better Transport Layer Security?
- Traceable and linkable ring signatures, traceable range proofs and applications on regulatable privacy-preserving blockchains
- Linear Approximations of Random Functions and Permutations
- A Stealthier Partitioning Attack against Bitcoin Peer-to-Peer Network
- Security analysis of two lightweight certificateless signature schemes
- Homomorphic Encryption Standard
- Ouroboros Clepsydra: Ouroboros Praos in the Universally Composable Relative Time Model
- Efficient zero-knowledge arguments in the discrete log setting, revisited
- Security of Hedged Fiat-Shamir Signatures under Fault Attacks
- Succinct Arguments for Bilinear Group Arithmetic: Practical Structure-Preserving Cryptography
mentioned in merge request !96 (merged)
This is the last monthly report for the current funding period, covering the month of September. My thanks to the community for support of cryptographic research!
The preprint for the CLSAG signature construction, which contains rigorous security definitions and proofs as well as applications, has been extensively revised and submitted to Financial Cryptography and Data Security 2020. The version on the IACR preprint archive has been updated to reflect a number of updates and changes. The preprint for the DLSAG signature construction has also been revised and submitted to the same conference by collaborators.
I have been working with the author of the Lelantus transaction protocol on new constructions to solve its tracing issue, both with and without the use of non-interactive one-time addresses. A short technical note describing one approach to this is forthcoming, but a full solution is still not known at this point. Research is ongoing.
A new sublinear transaction construction was proposed that uses a modification to a proof also used in Lelantus, but in a different way. This construction, tentatively called Triptych, does not scale optimally, but is a very interesting application of this particular type of proof. After several revisions to the proving system, I've written up an efficiency analysis and proof-of-concept code for Triptych, but its security has not been formally analyzed.
Based on work in a recent preprint, I produced some initial code for a modified inner-product argument similar to that used in Bulletproofs, but with a more efficient single-round verifier. While in theory very slightly more efficient than Bulletproofs, the practical effects on verification are negligible, and I suspect the efficiency numbers in the preprint are not correct when considering such a verifier. However, the proving systems introduced in the preprint are very interesting and deserve additional consideration.
The preprint for the RingCT 3.0 transaction protocol has been extensively updated by its authors to reflect both a fix for an exploitable flaw and much better proof size scaling. I am in the process of reviewing these changes and updating proof-of-concept code and space/time analysis numbers.
Finally, I'm preparing a presentation for the World Crypto Conference developer stage, along with Diego Salazar and Dr. Daniel Kim. The talk is an overview of different historical and present cryptographic approaches toward transaction privacy and fungibility, as well as a comparison of the tradeoffs involved in different design choices. I'll post the presentation slides publicly when finalized.
And now on to Sarang's Reading Corner, a short listing of some interesting papers that I have come across this month. The appearance of a paper in this list does not mean that I necessarily agree with its contents or correctness, or that I endorse it. Papers are in no particular order.
- Halo: Recursive Proof Composition without a Trusted Setup
- A New Method for Geometric Interpretation of Elliptic Curve Discrete Logarithm Problem
- A New Public Key Cryptosystem Based on Edwards Curves
- Analysis of Solitaire
- Breaking the Bluetooth Pairing - The Fixed Coordinate Invalid Curve Attack
- RingCT 3.0 for Blockchain Confidential Transaction: Shorter Size and Stronger Security (updated)
- What's in a Downgrade? A Taxonomy of Downgrade Attacks in the TLS Protocol and Application Protocols Using TLS
- The SPHINCS+ Signature Framework