Sarang: research funding for 2020 Q2
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 January, February, and March to see what I've been up to recently.
This funding request covers the period from April through June 2020. There's plenty to do.
- CLSAG testing and deployment. The CLSAG signature construction has undergone major work on its security model, development, and testing to make it faster and safer. It's expected to undergo final external review and deployment.
- Triptych research and testing. The Triptych proving system has been revised and released as a preprint. Research continues on a more efficient version that looks promising.
- Protocol updates. Research is ongoing to determine safe and efficient ways to improve transaction privacy, fungibility, and functionality through things like improved multisignature support and cross-chain interactions.
And of course, there is always research and development that arises as we go. 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. The request total is 845 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.
Edit: added March report and updated request total
Merge request reports
Activity
mentioned in commit 6d26873a
mentioned in merge request !110 (merged)
It's time for my monthly research report for April. As always, my thanks to the community for ongoing support of research in applied cryptography.
The CLSAG ring signature construction has several updates. The preprint, after undergoing a significant overhaul to its security model and proofs, has been posted as a revision to the IACR archive. The C++ implementation has received plenty of attention: plumbing to support hardware devices, better handling of ephemeral signing data, and improved tests and timing data.
I wrote a C++ implementation of the Triptych proving system as a proof-of-concept to show integration with the Monero codebase transaction handling code. This includes optimizations for multiscalar multiplication evaluation, common input key batching, commitment offsets, and point caching. Unit and performance tests are also completed, and show impressive verification performance. A version of the preprint has been revised and submitted for the PoPETs conference proceedings.
The preprint for the Arcturus proving system, which extends Triptych to support balance assertion and signing for multiple inputs within the same proof, was also updated to fix some notation problems. A version of the preprint has been revised and submitted for the PoPETs conference proceedings.
Due to renewed interest in the idea of protocol-enforced hidden timelocks, I revisited the requirements on signature and proof constructions to enable this. I rewrote code for 3-CLSAG, an extension of CLSAG that supports hidden timelocks, and wrote a timing test for this. Similarly, I wrote code for 3-Triptych, an extension of Triptych that supports hidden timelocks, and produced timing test data. Both show significant verification performance hits, as expected. This code and data can be used for future work and decisions relating to the topic of timelocks.
There were many other smaller tasks and projects. I wrote a simple change to the Bulletproofs code that speeds up verification significantly in batch operations. Code for more robust handling of in-memory key encryption is in progress and nearly completed. I assisted with informal review of a preprint on hierarchical Groth-type proofs. I made minor updates to code that centralizes the handling of hash domain separators to avoid collision. I contributed material to the recent update to the Zero to Monero technical guide. And I rewrote some existing signature tests for more consistent comparative performance data across different constructions.
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.
- An Empirical Analysis of Privacy in the Lightning Network
- Privacy Aspects and Subliminal Channels in Zcash
- Pointproofs: Aggregating Proofs for Multiple Vector Commitments
- Hierarchical One-out-of-Many Proofs With Applications to Blockchain Privacy and Ring Signatures
- The Multi-Base Discrete Logarithm Problem: Concrete Security Improvements for Schnorr Identification, Signatures and Multi-Signatures
- Multiparty Generation of an RSA Modulus
- Topological Properties of Multi-Party Blockchain Transactions
- Diogenes: Lightweight Scalable RSA Modulus Generation with a Dishonest Majority
- Efficient 4-way Vectorizations of the Montgomery Ladder
- Improving Speed and Security in Updatable Encryption Schemes
- Compressed Σ-Protocol Theory and Practical Application to Plug & Play Secure Algorithmics
Edited by Sarang NoetherIt's time for my monthly research report for May. As always, my thanks to the community for ongoing support of research in applied cryptography.
Work this month focused primarily on standardizing the code and test frameworks for different signature and proof constructions used in transaction protocols, as well as new and updated code to improve handling of key and proof data.
The Triptych proving system received several updates. Its preprint was revised and submitted to the upcoming Privacy Enhancing Technologies Symposium proceedings. The test implementation code received fixes and an overhaul to its performance tests to better represent the effects of balance verification.
The Arcturus proving system received major updates. Its preprint was also revised and submitted to the upcoming Privacy Enhancing Technologies Symposium proceedings. The security model is being updated to apply definitions inspired by Omniring to better formalize balance and non-slanderability. Most notably, I produced test implementation code integrated with the Monero codebase, along with a test framework and analysis of how proof/signature size and verification scale compared to other constructions.
I updated the way that key encryption is handled in memory and wallet files, along with some associated migration logic and tests. This results in more robust handling of keys during wallet use.
Code for message signing received an overhaul. This functionality is useful for cases when a user wishes to demonstrate control of one or more keys associated to a particular address. The new code binds signatures to complete addresses and key roles, as well as adding hash function domain separation to avoid misuse.
View tags were proposed last month as a way to to speed up scanning by replacing certain elliptic curve operations with simpler hash logic. I produced timing code to analyze the potential savings, as well as data to determine how tag sizes and scan times interact. While not enforceable by consensus, view tags show promise.
Finally, assorted projects related to MLSAG and CLSAG signatures continued. Performance tests for both signature methods were rewritten to account for balance verification, which enables more accurate comparison to other signature and proof constructions. Coordination with OSTIF and Teserakt to audit CLSAG for deployment in an upcoming network upgrade is in the final stages of planning.
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.
- Multi-Party Threshold Private Set Intersection with Sublinear Communication
- Alt-Coin Traceability
- Proof-Carrying Data from Accumulation Schemes
- BlockSim: An Extensible Simulation Tool for Blockchain Systems
- Using z14 Fused-Multiply-Add Instructions to Accelerate Elliptic Curve Cryptography
- Linear Generalized ElGamal Encryption Scheme
- ZeroJoin: Combining ZeroCoin and CoinJoin
- A Retrospective Analysis of User Exposure to (Illicit) Cryptocurrency Mining on the Web
- UC Non-Interactive, Proactive, Threshold ECDSA
- Blockchain Stealth Address Schemes
- Fast Threshold ECDSA with Honest Majority
- Threshold ECDSA for Decentralized Asset Custody
- One Round Threshold ECDSA with Identifiable Abort
- Atacking Zcash Protocol For Fun And Profit
mentioned in merge request !148 (merged)
It's time for my monthly research report for June. As always, my thanks to the community for ongoing support of research in applied cryptography.
Research this month focused primarily on major updates to the CLSAG security model, proofs, and preprint in response to initial results from the ongoing review; as well as work on an analysis toolkit for obtaining useful data from the blockchain.
The CLSAG linkable ring signature construction is currently undergoing formal review by JP Aumasson and Antony Vennard. The review is being conducted in two stages: the first to assert the correctness and applicability of the underlying mathematics and security model presented in the preprint, and the second to examine the implementation code for correctness and robustness. The reviewers found no major issues with the preprint, finding that the mathematics are correct and the security model reasonable. However, they made many suggestions for minor corrections and changes, as well as requested that some of the proofs be expanded for clarity. In particular, the proof that non-slanderability and unforgeability are equivalent has been entirely rewritten. Further, one of the cryptographic hardness assumptions has been reverted to another from an earlier draft with minor modifications. Finally, I completely overhauled and rewrote the proof of linkable anonymity security. Once the reviewers complete the second stage of the review process, they will release a final report that will be posted publicly. In the meantime, the reviewers and I have been discussing some of the specifics of their initial draft report. The revised preprint will be posted to the IACR archive after additional review.
After reading a preprint that looked at deducible transactions and related statistics from the Monero blockchain, I decided to independently verify the results. This grew into a Python toolkit that can be used to extract block, transaction, input, and output data from local block explorers for analysis. The results have been useful; in particular, the analysis showed that while a nonzero number of recent transactions are deducible (that is, they are susceptible to so-called chain reaction analysis), all such transactions spend old funds generated prior to the confidential transaction protocol upgrade. Indeed, precisely zero confidential transactions are deducible. This analysis led to ongoing discussion with the preprint authors, who confirmed the results and are making further updates to their work; several of their conclusions are rendered incorrect by this transaction classification.
The analysis toolkit was also used to analyze spend age patterns. Early work by Andrew Miller and collaborators examined these patterns in deducible Monero transactions and on the Bitcoin blockchain; their work led to the implementation of updated output selection algorithms. My updated analysis further examined whether coinbase outputs follow the same distribution, and how the distribution changed over time among deducible transactions. Results indicate that while there is variation over time, the spend age distribution reasonably matches the output selection distribution used by default, and that coinbase outputs follow the same distribution very closely. Ongoing work is in progress to conduct additional analysis using the toolkit.
On an unrelated note, I delivered a presentation to a cryptography study group held by MakerDAO at the group's invitation. This was a great opportunity to give an overview of how cryptographic constructions and building blocks are used to produce privacy-focused transaction protocols.
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.
- Counting Down Thunder: Timing Attacks on Privacy in Payment Channel Networks
- Everything is a Race and Nakamoto Always Wins
- Blockchain is Watching You: Profiling and Deanonymizing Ethereum Users
- Lelantus (revised)
- Bulletproofs+: Shorter Proofs for Privacy-Enhanced Distributed Ledger
- On the Confidentiality of Amounts in Grin
