Sarang: research funding for 2020 Q1
Hello! Dr. Sarang Noether here, ready to continue full-time research, development, and analysis in privacy-focused cryptography and applications. You can read my previous monthly reports for October and November to see what I've been up to recently.
This funding request covers the period from January through March 2020. There's plenty to do.
- Protocol research. Most work will likely focus on continuing updates to security models, proofs, and preprints for CLSAG, DLSAG, and Triptych. Additionally, I am working to add multisignature support for Triptych and RingCT 3.0 to extend functionality.
- Graph-theoretic analysis. This research is ongoing with colleague Surae Noether, with a lot of new code and math to review relating to blockchain analysis.
There is always plenty to do that arises unexpectedly. Expect code review, the usual updates and changes, outreach, literature review, proof-of-concept code and testing, documentation, and more.
I work hard to provide value in my research for the value provided here. As before, this request is for the equivalent of 10415 USD monthly, my assessment of fair market compensation for an independent Ph.D. researcher in the United States. Therefore, using a 14-day EMA of 49.46 USD/XMR from Kraken with a 10% buffer to account for recent volatility, the request total is 695 XMR. Further, note that this request will be paid in full as soon as it is funded, in order to reduce the effects of price fluctuations and ensure that contributed value is the value that reaches me.
Questions, comments, and feedback about this request are welcome.
Merge request reports
Activity
mentioned in commit 3ccfecc6
It's time for my monthly research report for January. As always, my thanks to the community for ongoing support of research in applied cryptography.
At long last, the preprint for the Triptych proving system is available on the IACR preprint archive, and has been updated and generalized to a more comprehensive multi-dimensional linkable ring signature construction. Accompanying proof-of-concept is also available, as well as an analysis. You can also read the announcement post on r/Monero or an article on Cointelegraph. An improved version of Triptych is still in the works, with accompanying changes to the proving system and security model.
A multisignature protocol for the aggregated Triptych proving system is now available, along with the earlier version I wrote for the non-aggregated version.
The DLSAG preprint was accepted to the Financial Cryptography and Data Security 2020 conference, and has undergone revision in preparation for its appearance in the conference proceedings. We plan to revisit and extend its security model for a future submission.
I made major updates to the elliptic curve libraries that I use for many research projects, as well as the test suite. The changes have been ported to a number of other projects in the repository. Code for other projects like Lelantus has also been updated with fixes and improvements. Minor code changes to CLSAG are also complete.
The DLSAG preprint contains a method for supporting hidden timelocks, originally intended to act as a switch between possible recipients of a transaction and enable non-interactive refunds. The idea can be slightly modified to support arbitrary timelocks, where a sender asserts that a hidden amount of time has passed to allow signing for a transaction input. I worked up a brief example that shows how to use modified CLSAG signatures and Bulletproofs to enable this functionality with minimal impact on transaction size and verification complexity. Additionally, I produced a modified version of Triptych that supports this functionality as well. C++ code examining the effects on CLSAG verification complexity is also available.
I wrote up a short and informal blog post on supply auditability in response to comments and questions that often arise on the topic. The post tries to clarify and enumerate some of the tradeoffs that projects and protocols make relating to privacy, fungibility, security, and supply soundness.
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.
- Too Much Crypto
- Double point compression for elliptic curves of j-invariant 0
- New Constructions of Traceable Range Proofs: Towards Multiple Regulation and Joint Regulation
- Characterizing Orphan Transactions in the Bitcoin Network
- Efficient Fully Secure Leakage-Deterring Encryption
- Triptych: logarithmic-sized linkable ring signatures with applications
- SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust
- BLAKE3 cryptographic hash function
- Simulated Blockchains for Machine Learning Traceability and Transaction Values in the Monero Network
- Correlations of Multi-input Monero Transactions
- Threshold Multi-Signature with an Offline Recovery Party
- A Graduate Course in Applied Cryptography
- Stake Shift in Major Cryptocurrencies: An Empirical Study
- Efficient Elliptic Curve Operations On Microcontrollers With Finite Field Extensions
- Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof
- A Performant, Misuse-Resistant API for Primality Testing
- BabySNARK
It's time for my monthly research report for February. As always, my thanks to the community for ongoing support of research in applied cryptography.
It is possible to store data in different proving systems. I've written code to do so for Bulletproofs, single-input Triptych, multi-input Triptych, single-input RCT3, and multi-input RCT3. This has applications for storing private data intended for signers and provers to later reconstruct.
For CLSAG, a related technique can be used to extend view-only wallet functionality to identify outgoing transactions in an opt-in manner. This could be useful for future wallet development without a consensus change or added transaction bloat. The C++ code has been updated to include hash function domain separation and general cleanup. Another CLSAG branch has some speedups that I applied by combining auxiliary commitments directly in signature verification. (A similar MLSAG branch does not see the same efficiency benefits, unfortunately.)
Much research work has focused on transaction proofs, for use in opt-in assertions of information about transaction data. I began a technical write-up of existing incoming and outgoing proving methods. Related to this, I rewrote the Schnorr proofs for these to include hash function domain separation and proper challenge construction; this has been included in a pull request with tests and wallet integration. Separately, I've written a test implementation for a method of proving the spend status of an output more safely than existing methods.
A few promising future transaction protocols would require a change to the format of key images, which poses a challenge for multisignature construction. To help this, I overhauled an initial idea for a key image construction multiparty computation protocol to be conjectured secure against malicious players. There's now a set of write-ups and a much better example implementation of this protocol.
Related to transaction protocols, I used chain data provided by Noncesense Research Lab collaborators to produce more direct chain growth and verification time estimates for different protocol proposals. Analysis code for this is available.
There are many smaller items of interest. One possible Janus attack mitigation has been mapped out. I've done preparation of a talk for possible presentation at the upcoming Monero Konferenco, review of upcoming material for the next revision of Zero to Monero, and review of a Dandelion++ pull request. The Stanford Blockchain Conference was this month, and had some very interesting talks that are available on video. And I wrote up a quick pull request for better hash function domain separation across the codebase.
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.
- Authenticated Data Structures for Privacy-Preserving Monero Light Clients
- Double-Base Chains for Scalar Multiplications on Elliptic Curves
- Recursive Proof Composition without a Trusted Setup
- Efficient polynomial commitment schemes for multiple points and polynomials
- Bandwidth-efficient threshold EC-DSA
- On the Profitability of Selfish Mining Against Multiple Difficulty Adjustment Algorithms
- A Refined Analysis of Zcash Anonymity
- Triptych: Comparing Anonymous Transaction Protocols from Linkable Ring Signatures (video talk)
- Zendoo: a zk-SNARK Verifiable Cross-Chain Transfer Protocol Enabling Decoupled and Decentralized Sidechains
- Threshold Ring Signatures: New Definitions and Post-Quantum Security
- Trustless Groups of Unknown Order with Hyperelliptic Curves
mentioned in merge request !131 (merged)
It's time for my monthly research report for March. As always, my thanks to the community for ongoing support of research in applied cryptography.
This month took a strange turn with the rapid emergence of the global pandemic, but research was ongoing in protocol development, testing, and coding.
The original Triptych preprint was updated with minor fixes and changes. Further, the extended Triptych-2 preprint is now completed and posted! It has also been added to the Monero Research Lab page. As always, keep in mind that preprints do not undergo peer review prior to posting.
I've completed additional review of a pending update to the CLSAG preprint with a much more robust security model, and will post the update after final proofreading. I rewrote the higher-level prover and verifier routines for improved performance, to decrease overall verification time for signatures. Performance testing was similarly updated.
A preprint describing a general approach to linkable ring signatures was posted to the IACR archive by another team of researchers. The authors apply two different ring signature constructions, and compare the results to CLSAG and other existing constructions. I've been in contact with the authors to fix some issues with this preprint; in particular, the original version was not safe for deployment due to a key image flaw, and the general technique does not apply to Monero for this reason. However, one modified version appears to be applicable, pending changes to the security proofs; I worked up some prototyping code to better understand how it might compare to CLSAG. My conclusion is that verification time is very comparable to CLSAG.
There was, as always, miscellaneous work as well. Performance testing for the current MLSAG signatures was updated for improved comparison with CLSAG signatures. I contributed to a pending update for the Zero to Monero technical document. My latest funding proposal was opened and completed. And I completed formal peer review for preprints submitted to the IEEE S&B conference as a member of the program committee.
Stay safe and well, everyone.
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.
- Deterministic-Prover Zero-Knowledge Proofs
- Generic-Group Delay Functions Require Hidden-Order Groups
- Compact NIZKs from Standard Assumptions on Bilinear Maps
- Separate Your Domains: NIST PQC KEMs, Oracle Cloning and Read-Only Indifferentiability
- A Note on the Ending Elliptic Curve in SIDH
- An Axiomatic Approach to Block Rewards
- Privacy-friendly Monero transaction signing on a hardware wallet, extended version
- "Many-out-of-Many" Proofs with Applications to Anonymous Zether
- The security of Groups of Unknown Order based on Jacobians of Hyperelliptic Curves
- This PIN Can Be Easily Guessed
- Triptych-2: efficient proofs for confidential transactions
- A Simpler and Modular Construction of Linkable Ring Signature
- Secure Multiparty Computation (MPC)
- A Quantitative Analysis of Security, Anonymity and Scalability for the Lightning Network
- A Blockchain Traceable Scheme with Oversight Function
- plookup: A simplified polynomial protocol for lookup tables
- Balancing confidentiality and auditability in a distributed ledger environment
