It's monthly report time. As always, my thanks to the Monero community for ongoing support of my research and the project ecosystem.
Along with general code library cleanup, a good deal of work was completed on signature schemes this month. The formal analysis of the DLSAG dual-address signature construction continues, with ongoing coauthor review and edits for conference submission and release of the preprint. Some questions remain about the consequences of a proposed modification to dual-address key images.
Another signature scheme was proposed by research contributor RandomRun that reduces the size of ring signatures substantially. The scheme, denoted CLSAG (compact LSAG), uses key aggregation to reduce the number of scalars required for a ring signature (at the cost of a single additional group element per signature). I produced example code in Python, as well as timing code in C++, to determine if the signature scheme could be made fast enough to be useful. After the addition of some modified cryptographic functions to increase efficiency, tests showed that CLSAG signatures are indeed faster to verify than our current MLSAG ring signatures! Note that both the example code and the timing code are for research only, and are not yet suitable for use in production without review.
For our present ring size of 11, a typical 2-input/2-output transaction uses 2.54 kB of space and takes (on my test machine) 13.0 ms to verify the MLSAG signature. Using CLSAG, the same transaction requires only 1.9 kB of space and takes 11.1 ms to verify the signature. This reduces the transaction size by 25% and the verification time by 15% too! A technical note describing the scheme with security proofs is still underway, since there are some design choices to make about hash coefficients that could give an additional 5% benefit in verification time. There is no formal plan to move to CLSAG signatures yet, but they are very promising.
My proposed modification to ring decoy selection has been updated to account for a moving window that is used to determine average output arrival times. This proposal has been merged in a pull request by moneromooo with accompanying tests. It helps to mitigate some weighting issues and analysis heuristics.
I have proposed to integrate the Dandelion++ (D++) transaction relay scheme into Monero. The D++ protocol helps to mitigate against certain types of network observation by building a random node graph that is used when initially broadcasting a new transaction, before the transaction is diffused to all nodes in the network. Variations on this are already being used in other projects like Zcoin and Grin, with a Bitcoin BIP also available. The use of D++ does not remove the need for other network-level approaches (like Tor or I2P) that are helpful to mitigate targeted node analysis, but it is a good complement that can be handled entirely at the relay level.
Work analyzing the Lelantus transaction construction is available. This proposal was released as a preprint by a Zcoin researcher and has undergone several recent revisions. It is a clever application of modified Bulletproofs, zero-commitment proofs, and double-blinded Pedersen commitments that extends some of the ideas originally introduced in Zerocoin. The protocol has some privacy limitations and questions of efficiency, but the underlying approach deserves careful review to determine if any part of it may be feasible for Monero in the future. I have example code that demonstrates simple transaction flows, have worked up a method for safely transitioning Monero outputs to the Lelantus format, and am in contact with the paper's author to discuss future work and offer suggestions for efficiency improvements. Depending on the precise use of common anonymity sets across groups of transactions, initial calculations suggest impressive batched verification times. This is research only, with no plans to move to such a protocol.
For the next month, I plan to continue analysis of transaction protocols like Lelantus, complete code and tests to efficiently generalize Bulletproofs for arbitrary input length, and tidy up some loose ends with the CLSAG signature scheme proofs.
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.
- ZETH: On Integrating Zerocash on Ethereum
- Cryptanalysis of Curl-P and Other Attacks on the IOTA Cryptocurrency
- SoK: Off The Chain Transactions
- On polynomial secret sharing schemes
- Generic Construction of Linkable Ring Signature
- Dragonblood: A Security Analysis of WPA3's SAE Handshake
- The current state of affairs in 5G security and the main remaining security challenges
- Exploring the Monero Peer-to-Peer Network
- Discharged Payment Channels: Quantifying the Lightning Network's Resilience to Topology-Based Attacks
SarangNoether