I'm glad that people enjoyed the article :- )

Please note that there have been two minor revisions since initial publication (though neither impacting the overall conclusion)

1. Clarified some imprecise language, where I said “churn” when what I meant was to `transfer` repeatedly to wallet(s) controlled by yourself.

2. The ability to ascertain that a transaction doesn’t have any subaddress recipients based on the absence of additional keys does not apply to 2-output transactions (only to 3+ outputs). So the comments about primary and subaddresses have been removed. h/t @UkoeHB for catching this

Let me know if you catch anything else, or have ideas for extensions.

Has anyone on the Monero side of things considered an openly developed chain analysis software? Being able to determine how far software can go, and what patterns are effective, would be a valuable piece of knowledge for XMR as a whole.

The one concern I'd have with such a project would be the inability to keep up if Monero successfully evolves its technology, while I'm notably thinking of Triptych.

But the software is out there to some degree by some people. A public form, which at best serves as proof of the software's impracticality as well as red team research, can't really make the situation worse.

(standard disclosure policy on issues would still be followed, of course)

kayabaNerve: I am currently red-teaming Monero. And BCH CashFusion. Everyone is getting the red team treatment :)

Rucknium[m]: Have any information on that/published work?

I did hear about your CashFusion work which we've also discussed :P

Open development of chain analysis software for Monero would seem too risky. What if we stumble upon something truly harmful?

"standard disclosure policy"

Would you rather we never do and someone else does?

kayabaNerve: I recently submitted a 28-page document to Monero's Vulnerability Response Process via HackerOne

Oh, the recent mixin selection commentary?

Tbc, I'm not saying I've read, or even have access to (I do not), the doc. I just remember that event coming up a few weeks ago

You can check the #monero-dev logs from 24-48 hours ago for some limited open discussion about it.

It involves the mixin selection algorithm, yes.

Thanks for the heads up. I do stand by believing open analysis tools would be beneficial. The sole question is it worth the benefit, given the difficulty of creating one.

"What if we stumble upon something truly harmful?", you say as you have already stumbled upon something worth improving and accordingly improved Monero :P

kayabaNerve: I don't think it would be too difficult.

kayabaNerve: Right, but if it happened in the open, Monero's adversaries would already have access to it. Instead, I am working on a "patch"

For basic commentary? Surely not. For multi-TX analysis and getting close to the best accuracy possible? Definitely.

Except Monero's adversaries already have access. It's we who don't.

They have access to knowledge that hasn't necessarily been created yet?

That's my stance. We know one company actively working on such software, and I'd presume 1-2 more. Combined with the... IRS was it? bounty and them selling access...

They have access to internal research on Monero's privacy, a direct profit incentive never to report it, and tooling created via their research which allowed practical refinement and continuation of their research.

We have some level of research, obviously, yet we haven't taken the next step into practical application and confirming hypothesis of de-anonymizing XMR, in order to better understand viable attacks and optimal pattern analysis. If we knew optimal pattern analysis, we could more efficiently design a new pattern.

Right now, we're left discussing theory and paper, with no consideration for the practicality of how XMR is used. I know I've made TXs within 30 minutes of each other as I've moved funds. Papers don't cover such real world aspects in regards to what percentage of TXs exhibit sloppy behavior AND what percentages can be calculated from that (except perhaps basic commentary on "these are bad").

Any paper which does would likely have implemented chain analysis scripts to provide their extended commentary.

And what's that? Chain analysis software? :O

kayabaNerve: Let's agree to disagree about the open development part. I'm working on what you're talking about, if I understand you correctly:

I will submit a CCS proposal to execute it within the next few days

It wouldn't necessarily have to be open. It's just a founding principle of OSS and the best way to get participants and review.

Tbc, I'm suggesting you publicize your findings... post-patch

Same disclosure policy.

Like you're saying you want to keep this private until researched and improved. Great. I support that.

The problem with post-patch disclosure is that the blockchain is forever. Past txs remain vulnerable. in the recent discussion in #monero-dev , selsta suggested that my attack should not be published. I agree with selsta on this one.

I'm not suggesting we just push to Git all new functions and tuning parameters. I'm suggesting a CA tool with established theory for use as a branching off point by teams for new attacks. If they achieve incremental improvements with no fix immediately available, it's submitted. If they start getting incredibly high success rates, that's a major issue, and the relevant channels occur. Post-patch, the tooling is published, and the

cycle begins again.

The problem with never disclosure is no one can learn from what happened and it'll just happen again.

Combined with the fact blockchains suck for privacy and we need to accept that, not run away from it. Quantum computers will destroy all of this anyways, no?

So we're already discussing a... 20 year timeline until we lose all privacy?

I am not sure. This is really my first foray into white hat hacking, I suppose

And if we adopt a quantum secure privacy algorithm, which I'd immensely love, we're still faced with entropy issues IIRC.

So all of this has a timeline. The question is do we accelerate the timeline in order to ensure everyone can learn from it to do better, or we do effectively lie to users

If there's legitimately a security issue you have, right now, that's extremely effective for CA purposes, that extent of it must be disclosed in order to maintain a fair community. While I agree that's distinct from how, I don't believe anyone as large as ChainAnalysis would have an issue reviewing every single change on Git and picking it up. From there, it's not really a secret. More just something that isn't talked about often.

This will lead to a lack of education and application

I think if and when a patch is developed and deployed, and we fully understand everything, it could be appropriate to release a general advisory to users about what types of past transactions may be vulnerable.

That's my stance, anyways. Will read up in #monero-dev

kayabaNerve: Look, these decisions are "above my paygrade". I am inexperienced in all of this.

As one other note, doesn't mixing selection by choosing 10 random mixins and walking away, without context on where the real mixin will be comparatively?

Rucknium[m]: This is a public channel and I'm laying out my thoughts not only to try to sway you to some degree, yet in case anyone else read through this and has something to comment.

Could you rephrase your question?

When selecting the 11 ring members, doesn't XMR: 1) Take the real mixin. 2) Select 10 random mixins after just being told to grab 10 random mixins, without any idea where the real one is. 3) Combine the two.

I do understand the actual process of selecting those 10 mixins is complicated. I'm commenting it doesn't use any context of what the real mixin is.

Unless I forget/misread the relevant code.

Yes. But the read spend and the mixins have, in a sense, metadata. One element of this metadata is how hold each input is. The flawed mixin selection algorithm from pre-2018 was exploited by the analysis of Moser et al. (2018) An Empirical Analysis of Traceability on the Monero Blockchain

Or a title to that effect

ahem, "how old each input is"

... that's my comment.

I got "hold" on the brain, apparently.

I was going to say an extremely simple comment/question of "Why don't we select 11 mixins randomly, substituting the real one for the closest fake one?"

On the topic of quantum secure privacy algorithms,

They are selected randomly.

... 11

Not 10. 10 are selected randomly.

Ok, imagine a simple thought experiment. And this thought experiment isn't too different from how Monero used to work in the bad old days:

Mixins are selected. Every output on the blockchain since the genesis block is eligible, with equal probability, to being selected....

Now, typical users actually spend their received coins within, say, a week of receiving them. In that case, an attacker could guess that the real spend was just the most recent ring member.

That's it. That's the problem in a nutshell

If I randomly select a mixin from the past month, yet have my real TX in the last month, there's now two outputs from the last month. If that's statistically unlikely using the standing mixin selection algorithm, then it's a giant red flag the real mixin is one of those two. IIRC, the current mixin algorithm has no context on the real output. I'm asking, both as a naive comment and trying to learn, if randomly selecting all 11 and

Since the "fake" mixins would all be much older than the real spent output

then substituting the real one for the closest fake one would help or not. That said, I'm truly not a statistician and can't comment on current distribution/selection, so this may just be very over my head, leaving me to discuss red team theory.

I know this.

I promise you, I do know this.

I don't know how the current algorithm works, as it's been ages since I've read up on it (and even then decided it was too complicated to impl for my own work before performing a naive selection algorithm). I do know what it looks like to send up such a signal flare though.

I also do remember the mixins must have an average age < X, which was healthy to see.

So you're saying that some info on the real spend should be used to select the mixins? My intuition is that would lead to an attacker having greater probability of detecting the real spend, since the mixins would in some ways have a pattern linked wit the real spend.

Yes and no. Selection wouldn't be changed at all. The amount selected would be.

Then, if there's something randomly within the last 30 minutes (already statistically likely to be the real send), there's not two entries from within the last 30 minutes (almost definitely one of those two). There's just one, as it replaces its closest randomly selected entry.

It was a probably naive idea I wanted to throw out there as I found it odd it wasn't already done that way.

Because seriously, I am not the person to do any statistical analysis here. I trust you for that if I ever need it ;)

But I did want to discuss red team management and I am interested in learning more about the theory, which I have a basic understanding of. That's why my naive suggestion is also a question.

Because you absolutely may be right that changing a randomly selected item, used in the context-dependent calculation of all randomly selected items, with a fixed position after the fact may reduce the security of the randomly selected items. I'd love to hear about that :)

jberman is working on something experimental that may be somewhat close to what you are saying:

And I'd trust someone else to do the stat analysis and decide if it's more or less secure than the risk of getting 2 outputs within the last X amount of time :p

I did see that, and yeah, it's basically what I'm discussing. Minimizing overlap between random and actual. I just described an algorithm which wouldn't need to be run twice in my comment

So sounds like if I want to learn more, that's THE issue. Thanks :)

kayabaNerve: So the issue with your idea, as stated, is that...I'm finding it hard to explain. Basically, there is equal probability, in some sense, that a mixin will be "far" from the real spend or "near" the real spend. The mixins are selected independently from the specified distribution baked into the Monero code. The random selection is also independent of the real spend.

So even though proximity isn't a risk, such proximity isn't an issue, as it'll randomly happen or randomly not happen, therefore not changing the odds of such an occurrence in any way flaggable for CA software

I think you bring up some interesting ideas that are worth turning over in the head, though. I'd never turn down a new idea from a stats layperson, since there could be something I am overlooking.

*is a risk

Is that what you were trying to say?

Yeah, so the real spend and a mixin may be very close. Also, any two mixins (or three, four, etc.) may also be close. An attacker cannot really know, just from the simple information of closeness, that one "close" ring member is areal spend when it is next to another ring member. At least that's what comes to mind

Yeah. I do know enough cryptography to understand that ;)

Yet also, the one comment you linked is precisely amount ensuring distribution and limiting proximity. There's a key factor here IMO. The real output isn't random.

That's why it serves as such a flare if you spend an output from 11 blocks ago. Very low chance of randomness, very high chance of human behavior.

Which is why if you have 2 such outputs... it means you either hit the random chance twice (much smaller than hitting it once) OR the static element collided with the random one.

kayabaNerve: The real output _is_ random

It is random by a stochastic process of human behavior

Not when humans are impatient creatures and active users of the network frequently use it limiting the age of their coins.

I do understand it's not perfectly determinable and it's not absolute. I'm saying humans have a different pattern than a random selection algorithm, naive or intelligent

That's still random. It just has a distribution where the age of the real spends is quite young

I think it depends on the definition of random. Arguably, only the horrific og naive impl was "random".

kayabaNerve: What I'm saying is that this problem can be fixed with sufficient insight into the problem. I believe I have sufficient insight. That's what I'm working on.

I'd call the new algo here random, ofc, yet I'd hesistate to call human behavior sufficiently random.

But again, not my field, so I would defer to you ;)

It can be considered sort of semantics. Since my field is economics, which is the study of human behavior under conditions of scarcity, it is natural in my discipline to call certain aspects of human behavior random or probabilistic.

Anyways. The end point of my naive suggestion, which I do think is naive and I've spent too much time arguing on given my limited knowledge (there's some thereom about this), is the collision of a random and a human patterns may be more fingerprintable than the existence of one human pattern alone, due to the multiplicative odds in place (1% * 1% is far less than 1%). Hence why I brought up a way to reduce such collisions. My

suggestion is a very naive way to ensure distribution a-la j-berman added a post check before before even deciding the full ring in question, by generating an extra random element to be replaced (though a post check would likely be more comprehensive)

I get and agree with that. I just stop at calling it random in summary :p

But yes, I've spent far too long talking about things I don't fully understand. I'll try to read through the issue in question over the next couple days, and appreciate you talking me through this. It helped me :) Thank you.

No problem. We need to look at this issue from all angles since it it so, so important for user privacy. You provided yet another angle :)

libera.monerologs.net/monero-dev/20210925#c31867 is the start of the #monero-dev conversation, right?

Yes. Unfortunately, it sort of popped up in the middle of a heated discussion. meh

I'll keep my thoughts on that out of here :P Just wanted to confirm and provide a more direct link for anyone who reads through and also wants to read the other convo. Thanks for confirming

atomfried[m]: are you looking at optimizing `ge_scalarmult_p3()`? It seems to be the main blocker for a theoretical speedup in Groth/Bootle proofs.

i can have a look but i cannot promise anything. Is there a docu and or tests what this function should actually do? i dont want to fuck this up :D

Ah, this is part of the core crypto library (added 9yrs ago). I'm not sure what docs it's based on...

Maybe this one: eprint.iacr.org/2007/286.pdf

<Rucknium[m]> "rupee: I can make it available..." <- rupee : Ok, it's been more than an hour lol. In fact isthmus is going to clean up his Python code, neptune plans to make the SQL code and data available, and I will probably combine my R code with isthmus's repository. So it will take a few more days, but hopefully it will be worth the wait :)

Awesome, thanks for the follow up

In Computer Science, what is meant by "heuristic", used as a noun? Feel free to just respond with a link.

A good guess.

An educated guess.

But algorithmic.

Like, a good heuristic for guessing the real spend in an old monero ring is to pick the last member of that ring :D

I see. Thank you. Heuristic is sort of used pejoratively in economics, and rarely used at that. But I see it being used a lot in these papers.

moneromooo: I figure I should ask you this beforehand: It is ok if I quote you in my CCS proposal? I mean, I suppose I don't need to ask permission, but I'm just doing it as a courtesy.

Specifically, this: "[Fixing the mixin selection algorithm] is important. It's the weakest part of monero."

From libera.monerologs.net/monero-dev/20210925#c31927

Sure.

Ok great