Sarang: research funding for 2020 Q3
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 April and May to see what I've been up to recently. A report for June is forthcoming at the end of the quarter.
This funding request covers the period from July through September 2020. There's plenty to do, with a few big-ticket items in particular:
- CLSAG audit. The CLSAG audit planning process (which has been quite the endeavor) is being finalized, and I will coordinate the technical efforts for this process.
- Arcturus applications. The Arcturus proving system leads naturally to an efficient transaction protocol. Math and implementation involving multisignatures, cooperative signing, and anonymity set selection are ongoing.
- Protocol improvements. As always, research and development are ongoing to determine safe and efficient ways to improve transaction privacy, fungibility, and functionality while mitigating different types of adversarial heuristics.
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. Therefore, using an SMA-20 of 66.37 USD/XMR from Kraken with a 10% volatility buffer, the request total is 518 XMR. To reduce the effects of price fluctuation, the XMR equivalent of the USD total for this request will be used to determine the amount for full payment when the request is filled. Any shortfall or excess at that time will be taken up by the general fund, as agreed to by the Monero core team.
Questions, comments, and feedback about this request are welcome.
Merge request reports
Activity
I will donate the moment this goes live, as you provide some of the most important updates and research going into Monero and the space at large.
Excited to see Arcturus progress (and hopefully be implemented!) over the next few months! You keep helping Monero iterate and improve, cementing it's place as a tool for both financial and digital freedom.
Keep up the great work!
-
To clarify the above:
My priority among what I've been following in your work would definitely be Arcturus (or an alternative), as continuing to drive forward ring-size while decreasing/maintaining size/verification time is key to staying ahead of the arms race. The stats around that look amazing so far, and I'm hopefully we can move to it sooner rather than later!
mentioned in commit 2cc53398
It's time for my monthly research report for July. As always, my thanks to the community for ongoing support of research in applied cryptography.
At long last, the external review of the CLSAG linkable ring signature construction is complete! This is set to be deployed at the upcoming network upgrade in October. The CLSAG construction is a drop-in replacement for the current MLSAG signature construction, but produces smaller signatures that are faster to verify. The Monero community commissioned a professional external audit of both the mathematics and implementation code; for details, you can read the blog post that describes the audit results and links to the report. As a result of the audit, the CLSAG preprint has been extensively updated to improve the security model, computational hardness assumptions, security proofs, and overall narrative. The implementation code required no security updates. Related to this, I have been working with the Ledger and Trezor hardware wallet teams to ensure that support for those devices is ready for the network upgrade. Provided you keep your Monero software (and device firmware, if applicable) up to date, you'll be ready to go! The implementation code has been rebased and prepared for merging.
A recent CCS proposal suggests the addition of Bulletproofs+ to the Monero protocol. Bulletproofs+ is a zero-knowledge proving system used for proving that Pedersen commitments are within a fixed range, and is an extension to the Bulletproofs proving system currently deployed as part of the Monero confidential transaction model. I initially examined Bulletproofs+ when its preprint was first released, and renewed interest as a result of the proposal brought it again to my attention. After useful discussion with the proposers, I identified some issues with the methodology they used to produce verification timing and overall size estimates. Deploying Bulletproofs+ as a replacement to Bulletproofs would save a few dozen bytes per transaction, and would be marginally (very marginally!) more efficient to verify. The proposers have expressed their willingness to audit an implementation instead of writing one; I'm in favor of this approach given their expertise with the construction, and am in the process of producing test code and an implementation.
Next-generation transaction protocol ideas received minor updates. The Arcturus construction was updated for more efficient data storage. The preprint was unfortunately rejected from the PoPETs conference since it was considered too specific in scope and iterative in design; such is life! Its security model is being hardened to more formally account for balance and slanderability properties, after which it will be submitted elsewhere. The related Triptych construction was also updated for more efficient data storage. Its preprint, which was also submitted to the same conference, was (you guessed it!) rejected for similar reasons of scope and design iteration. I happen to disagree with these conclusions, but have nonetheless resubmitted the preprint to the ESORICS CBT conference, which is more specific in scope and perhaps a better home for this work.
There were many assorted updates and tasks as well. I removed analytics code from the
monero-siterepository andccs-frontrepository to help set an example for applications of privacy to site visitors, and reviewed and updated pull requests and posts. Pull requests relating to in-memory and stored key encryption, transaction proofs, and wallet message signing were updated and improved. I assisted with ongoing research into atomic swaps conducted by other researchers, helping to include an interesting cross-group discrete logarithm equality proof that can be used to enable cross-chain functionality with assets like Bitcoin; this work still has open questions on privacy implications that I am looking into carefully. Finally, I'm conducting some analysis on the effects of output merging in transactions on heuristics and adversarial analysis, to complement earlier work on blockchain and transaction statistics.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.
- Demystifying the Role of zk-SNARKs in Zcash
- One-Time Verifiable Encrypted Signatures
- Post-Quantum Adaptor Signatures and Payment Channel Networks
- FROST: Flexible Round-Optimized Schnorr Threshold Signatures
- Decentralized Lightweight Detection of Eclipse Attacks on Bitcoin Clients
- The Provable Security of Ed25519: Theory and Practice
- Cross-Layer Deanonymization Methods in the Lightning Protocol
- Proofs of Useless Work -- Positive and Negative Results for Wasteless Mining Systems
- Fast, Small, and Area-Time Efficient Architectures for Key-Exchange on Curve25519
- A Generalization of Paillier's Public-Key System With Fast Decryption
- Crowd Verifiable Zero-Knowledge and End-to-end Verifiable Multiparty Computation
- Fast hash-based additive accumulators
- Logarithmic-Size (Linkable) Threshold Ring Signatures in the Plain Model
- Stronger Notions and a More Efficient Construction of Threshold Ring Signatures
- Calamari and Falafl: Logarithmic (Linkable) Ring Signatures from Isogenies and Lattices
- Alt-Coin Traceability (revised)
It's time for my monthly research report for August. As always, my thanks to the community for ongoing support of research in applied cryptography.
The Triptych zero-knowledge proving system was developed to power confidential transaction protocols, like that used in Monero. The preprint has been accepted for presentation and publication to the ESORICS workshop on Cryptocurrencies and Blockchain Technology! This is an exciting development that you can read more about in this blog post. Slides for the presentation are also available, and video of the presentation will be made available if possible after the workshop in September. Code for Triptych in Python and C++ has also been updated for more efficient proof storage.
Work on the Arcturus zero-knowledge proving system continues, albeit slowly. As discussed previously, the construction is more efficient than Triptych, but relies on a non-standard cryptographic hardness assumption. Research is ongoing into this assumption, as well the security model underlying the transaction model associated to the Arcturus proving system. Code for Arcturus in Python has also been updated for more efficient proof storage.
The CLSAG linkable ring signature construction will be activated at the next network upgrade! Following a successful audit of the code and underlying mathematics, code has been merged to support these signatures. I have also been working with hardware wallet developers on the Ledger and Trezor teams, who are working to ensure CLSAG support for these devices.
Following the earlier release of a preprint on an update to the Bulletproofs zero-knowledge range proving system called Bulletproofs+, I've been working on code to support this in the Monero protocol. There is now proof-of-concept code in Python demonstrating the weighted inner product argument that powers the proving system. Building on this, there is also code that performs range proving and verifying operations and supports proof aggregation, unrolled verifier recursion, efficient verification using Pippenger multiscalar multiplication, and batch verification of multiple proofs. Work is ongoing to port these algorithms to the Monero codebase, using the existing Bulletproofs implementation as a base.
There are other assorted topics, as usual. A pull request relating to improved wallet message signing has been merged. An older preprint on cross-curve discrete logarithm equality was revisited due to its application in recent work on atomic swaps. Finally, Justin Ehrenhofer and I interviewed Dave Jevans, the CEO of CipherTrace, about a recent press release. The video of the interview is available and worth a watch.
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.
- A Practical Public Key Encryption Scheme Based on Learning Parity With Noise
- Quantum Resistant Ledger
- Discouraging Pool Block Withholding Attacks in Bitcoins
- Performance Trade-offs in Design of MimbleWimble Proofs of Reserves
- Optimized Binary GCD for Modular Inversion
- SoK: Why Johnny Can't Fix PGP Standardization
- Security Analysis on Tangle-based Blockchain through Simulation
- Practical Dynamic Group Signature with Efficient Concurrent Joins and Batch Verifications
- Formalizing Nakamoto-Style Proof of Stake
- Multi-Currency Ledgers
- Does Fiat-Shamir Require a Cryptographic Hash Function?
- JugglingSwap: Scriptless Atomic Cross-Chain Swaps
It's time for my monthly research report for September. As always, my thanks to the community for ongoing support of research in applied cryptography.
Research contributor cargodog proposed a clever method for using Gray codes in Groth/Kohlweiss proofs, and suggested an adaptation for use in Triptych and Arcturus. I used this idea to produce working prototypes:
The efficiency tradeoffs for this method are subtle and interesting, and depend highly on the input anonymity size for the proofs, as well as how batching is constructed.
I made other updates to the code for Triptych and Arcturus as well. I updated the Triptych code in Python to support batch verification across proofs within the same transaction. The Arcturus Python code received updates for efficient verification and a better construction for aggregation coefficients.
The Arcturus preprint received attention as well. The correctness proof was expanded to more clearly show important derivations. The treatment of the linking tag as an injective one-way pseudorandom function was slightly modified for clarity. Discussion of the correspondence between witnesses for two relations was modified to better describe the connection to a particular cryptographic hardness assumption. And the precise proof statement for transaction applications was added in greater detail. Taken together, these updates make the preprint more clear and complete for readers.
I gave several talks this month. At the recent Magical Crypto Conference, I gave a talk on the collision between theory and practice in privacy techniques, and also participated in a panel on privacy. At the ESORICS CBT workshop, I gave a presentation on Triptych. Finally, I led a short discussion on Triptych for the Chicago BITDEVS group.
There were other assorted tasks and updates. I updated prototyping code for the Bulletproofs range proving system to extend its data embedding, adding additional data that can be secretly stored and recovered by the prover. Similarly, I updated the code for the Bulletproofs+ range proving system to add data embedding as well. I have been participating in ISO-affiliated workgroups to assist in developing standards like ISO/TR 23244, which helps to define aspects of distributed ledgers relating to personally-identifiable information and privacy techniques. Finally, I have been assisting research contributors studying the security implications of hypothetical quantum adversaries relating to the Monero protocol, providing data and reviewing results.
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--Monero Cross-chain Atomic Swap
- Anti-Money Laundering Regulation of Privacy-Enabling Cryptocurrencies
- MuSig-DN: Schnorr Multi-Signatures with Verifiably Deterministic Nonces
- SeF: A Secure Fountain Architecture for Slashing Storage Costs in Blockchains
- Lunar: a Toolbox for More Efficient Universal and Updatable zkSNARKs and Commit-and-Prove Extensions
- Hashing to elliptic curves
y^2 = x^3 + bprovided thatbis a quadratic residue - Attacking Threshold Wallets
- Mimblewimble Non-Interactive Transaction Scheme
Edited by Sarang Noether
