Open Research Questions

[Rucknium]

This is an effort to construct a list of open research question relevant to Monero, as discussed in a recent MRL meeting. The purpose of this list is to:

1. Prioritize MRL efforts
2. Inform external researchers of key Monero questions
3. Maybe serve as a basis for Request For Proposal-style grantmaking in the future

This effort was in part inspired by a similar list put together by Grin.

Cat = Category. The categories are Privacy, Scaling, Decentralization, and User experience.
Imp = Impact, a subjective 1-10 measure of how important resolving the question is for Monero's goals.
Dif = Difficulty, a subjective 1-10 measure of how difficult resolving the question may be.

A collection of Monero-related research papers is available at MoneroResearch.info.

This list is a work in progress. Please give feedback below, including additional questions that should be added.

Question	Cat	Imp	Dif	Work in Progress	Links
Increase ring size	P,S	8	8	Seraphis; Triptych	#91; #92
Decoy selection algorithm (DSA) that closely matches the real spend age distribution	P	8	6	OSPEAD; Dynamic; Nonparametric	#93; #86
Advisability and feasibility of enforcement of DSA at the node and/or consensus level	P,D	6	4		#87
Advisability and implementation of binning for the DSA	P	6	4	@j-berman 's implementation	#84; #88
Decoy selection when transitioning transaction types	P	6	5		■
Advisability of churning and churning best practices	P,S,U	7	5
Defend against the Overseer Attack	P	7	9		■
Defend against the Flashlight/Poisoned Outputs/EAE/EABE Attack	P	7	9		■; ■; ■
Defend against the Tainted Dust Attack	P	7	9		■
Cross-ring output collisions: implications and solutions	P	2	3		■
Faster syncing of non-custodial wallets	S,U	7	8	View Tags	#73; ■
Reducing or eliminating 10 block lock with acceptable drawbacks	S,U	9	7		#85; #95; #102; ■; ■
Increase mining decentralization	S,D	7	7	p2pool; SolOptXMR
Determine if miners increasing block size is incentive-compatible from a game theory perspective	S,D	5	6		■; ■; ■; ■
Payment channels	S,U	6	7	Grease	■; ■; ■; ■; ■
Layer 2 solutions	P,S,D,U	8	9
Atomic swaps with every coin ever	D,U	8	8	BTC; ETH; BCH	■; ■; ■; ■; ■
Pruning of spent outputs	S,D	7	8		#69 zcash/zcash#4946
Private, untraceable transactions without ring signatures, but with acceptable tradeoffs	P	10	10	FCMP	■; #100
Post-quantum Security & Privacy	P	9	10		■; ■; ■; #105

[LocalMonero]

@Rucknium can we bump the importance of the 10-block-lock problem up to 9? The inability to spend unconfirmed coins is a massive pain point in Monero for a large number of reasons, ranging from basic consumer needs like buying two cups off coffee in the span of less than 20 minutes to enterprise applications like multisignature non-custodial service optimizations, so it seems more important than layer 2 solutions or swaps.

[Rucknium]

@LocalMonero Sure. Done.

[ChristopherKing42]

Suggestion: use polling to estimate user experience impact. Although for the other categories I think the Monero research lab are the experts, user experience is more subjective. For example, polling could be advertised on Reddit, on IRC, or even in popular wallets. It would be completely optional, of course. As part of the polling, we could also ask how heavy of a Monero user someone is, how tech savvy they are, etc... to see how it correlates to the questions.

[ChristopherKing42]

@LocalMonero

for a large number of reasons, ranging from basic consumer needs like buying two cups off coffee in the span of less than 20 minutes to enterprise applications like multisignature non-custodial service optimizations, so it seems more important than layer 2 solutions or swaps.

I don't understand. It seems that layer 2 solutions would also solve that and any other problems caused by the 10 block limit, so it would be strictly less impactful.

[endorxmr]

A followup question related to the DSA: what are (if any) the side-effects of hardforks/changes in the transaction protocol on the DSA, both in the short term (the initial transactions happening right after a fork) and in the long term (a very old output being upgraded to a newer format)?

[Rucknium]

@endorxmr : If the transaction format changes completely, like it will with Seraphis, then yes there are tricky issues around decoy selection. I'm not sure of all the details, but yes there will be a discontinuity and yes we will have to figure out how to deal with it so as to maximally protect user privacy. @UkoeHB , could you clarify this point?

[UkoeHB]

@Rucknium After the hardfork, new transactions spending new outputs will only be able to use new outputs as ring members. 'Transition' transactions will spend old outputs and create new outputs. Those txs will only use old outputs for ring members.

[UkoeHB]

@Rucknium Another information leak is 'when a tx is constructed'. This has two vectors: decoy selection (solvable with seraphis where you can defer making membership proofs until right before tx submission), fee granularity (see this analysis; mitigate-able by discretizing fees).

Fees can also lead to tx fingerprinting, which is also mitigated with discretization.

[HardenedSteel]

Should we add these to the roadmap page?

[chaserene]

@Rucknium inspired by the latest MRL meeting, could you add "Post-quantum cryptography"? and here's a would-be (to-be?) MRL paper as related resource:

Corbo, Krawiec-Thayer, Goodell: Evaluating cryptocurrency security and privacy in a post-quantum world

and what do you think about renaming "Private, untraceable transactions without ring signatures, but with acceptable tradeoffs" to "Global anonymity set with acceptable tradeoffs"? IMHO it describes the goal better.

and a resource for payment channels:

Sui, Liu, Yu, Qin: MoNet: A Fast Payment Channel Network for Scriptless Cryptocurrency Monero

[chaserene]

also this merge request to the post-quantum MRL paper's CCS, and especially this comment:

https://repo.getmonero.org/monero-project/ccs-proposals/-/merge_requests/142#note_10181

edit: and these as well:

koe: Implementing Seraphis (section 8.7, Forward secrecy against DLP-solver) (obviously the section may change in the future because the paper is a draft as of now)

tevador: Zero-cost post-quantum mitigations for Seraphis

edit2:

tevador: Consider Switch commitments for future supply security (#105)