i've always thought one could use the bitcoin blockchain as a base truth, and then create a synthetic ring signatures to create a synthetic monero blockchain with a known ground truth, and then apply whatever whatsits and hoozbangs to try and go from synthetic -> bitcoin

Meeting today at 18:00 UTC, No Wallet Left Behind in Matrix room.

tonz0fphun: "whereas the Authors provide some interesting arguments, those arguments are Hypotheses. There exists no evidence that the RingCT obfuscation mechanism is easy or possible to compromise." I don't agree with this in general. If the decoy selection algorithm is very different from user behavior, then guessing the real spend becomes likely.

Moser et al. (2018) showed that: moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=15

Before 2018, Monero had many privacy flaws. The decoy selection algorithm was very different from the real spend age distribution. Moser et al. (2018) just guessed that the most recent output in the ring was the real spend and they achieved 80% correct guesses.

How did they know the guesses were correct? They used another technique, sometimes called "chain reaction", that exploited the optional ring size (and possible 1-ring size) transactions to eliminate possible outputs using graph analysis. The technique is deterministic: With chain reaction you can say with certainty a certain ring member was the real spend.

Chain reaction was mostly fixed by enforcing a higher ring size and using RingCT to hide amounts. The "Guess Newest" heuristic is not very effective anymore since the decoy selection algorithm has changed.

tonz0fphun: The problem with using ACK-J's dataset is that it's not real users. A computer controlled the spending habits. Since a statistical or machine learning attack would usually exploit the difference between the decoy selection algorithm and real user behavior, the value of that dataset is limited. Still useful for certain purposes, but limited.

IMHO, it would be better to use the real Monero mainnet data for a clustering analysis. neptune has some software to extract Monero transaction data from the blockchain to put into a usable format. It requires some setup: github.com/neptuneresearch/ring-membership-sql

If you want to use mainnet data, we could figure out a way to get the data to you in a usable format.

Thanks for looking into the issue!

There are many other papers about this. I just don't want to flood you with them without your permission :)

@Rucknium feel free to send them to me in a PM. So basically you're saying that a simulation would not provide a synthetic dataset which is realistic enough? Does Neptune provide annotations? I'll have a look later tonight and see what I can get out of it.

What do you mean by annotations?

I will just post the papers here with commentary so others can see.

I am doing my own research on this issue, but I'm using traditional frequentist statistics. A machine learning approach is complementary and needed.

Is the mainnet data making associations between an obfuscated output and the real transaction?

That's what I mean by "annotation"

or "label"

No.

if it's not then I can't use it with supervised approaches, only unsupervised, hence why I would consider creating a synthetic dataset using a simulation

Exactly

Ok, fair enough

You would have to have an unsupervised technique

yeah, I would. I can try that, but that implies there's a relationship which is discoverable from some form of featurising, clustering, manifolding, etc. A Labelled approach would always be preferred in this scenario.

Monero's protocol guarantees that a true labeled approach is impossible. That's a good thing for user privacy :)

So there's no way for me to build a synthetic dataset by extracting meta-data, such as a group of transatictions, the majority of which are fake, and the actual one that is real (and all related meta)?

The minor except to that would be service providers that have access to some user traffic. Centralized exchanges would know which of the withdrawals are real spends. Is that useful? It would be a biased sample definitely.

tonz0fphun: I think rucknium is trying to say that we’ve gotten as close as we can testing supervised learning with synthetic datasets and we largely found no evidence of significant metadata leakage. An unsupervised approach seems more interesting to the research community at the moment and could be able to cluster user wallets, spending patterns, etc..

MyMonero has some info about user behavior too. That's a biased sample. They would not give it up even if it is for research to improve the protocol, I'm pretty sure.

xmrack: Yes

Ok, both fair points. IMHO a supervised approach will yield significantly better results. The caveat is that generating such a dataset is time-consuming, complex and possibly a large undertaking. For an unsupervised approach, I'll look into Neptune and whatever other datasets there are, and see how I can featurise them. However, bear in mind that such an approach will not yield the same insights, as it will be lacking

information that a supervised approach already contains. If that's something the community is ok with, then the real task is more of an "observationall" approach as to what can be inferred passively if that makes sense.

tonz0fphun: I think that would be wonderful

We have meetings every Wednesday at 17:00 UTC here in this room. It's text chat only. You could maybe get more feedback there. The currently-active MRL researchers working on statistical and machine learning attacks on Monero privacy are mostly me, xmrack , and isthmus .

isthmus: has found some cool things in the past using variations of DBSCAN if I remember correctly

tonz0fphun: you are 100% right with the time consuming part. I spent hundreds if not thousands of hours trying to find the best way to collect the datasets and featurize the results. After all that it was still no where close to perfect

I do like gingeropolous idea to add ring signatures to bitcoin transactions though

What's the advantage of doing that? I'm not criticising, my understanding of blockchain is somewhat limited. Isn't that a synthetic dataset manipulation?

It's synthetic but at least based on real user data on another real blockchain. xmrack 's project generated transactions based on some simple rules.

The bitcoin idea is "ok", but I'm not sure it's worth the effort at this point. If we had more labor resources, then yes we could allocate some to that idea.

<Rucknium[m]> "I am doing my own research on..." <- I did some ml stuff. Not an expert by any means (just some experience in chess programming), but I have some compute as well (not much, but enough)

If someone wants to transfer me some data, maybe I can check some stuff

(in chess now there's a problem of how to feature-ize data as well. Networks have to be very small for ab engines)

Ok, I'm happy to proceed with unsupervised, but I do like the idea of synthesizing a labelled dataset, because from there I can reverse the features (remove them one at a time) and infer which might be the one (or combination) that leaks information. But I do agree this is a considerably larger undertaking. If the Bitcoin transactions can be wrapped with ring signatures and then used to create such a dataset, then that would

be vastly simpler than setting up an experimental framework

Would be quite interesting to use Bitcoin data

Rucknium: you have studied the spending habbits of btc, ltc, and doge recently. Which do you think is closest to the spending habits of monero using the Moser de anonymized set as a baseline

Personally, I wouldn't use BTC but something with more Monero-like characteristics like LTC, BCH, or DOGE. Low fees. Lower tx volume than BTC.

Habits*

Lol great minds think alike

You would have to implement the decoy selection algorithm on those coins. I am almost finished with a math formula of the decoy selection algorithm. Put it on hold for a while.

xmrack: I don't know. Maybe I should try to answer that question. The Moser et al. (2018) data is old. You would want to compare the same time period. BCH didn't exist as a separate chain at that point by the way.

tonz0fphun: Here is that analysis, by the way: rucknium.me/html/spent-output-age-btc-bch-ltc-doge.html

Source code: github.com/Rucknium/OSPEAD/tree/mai…ral-Blockchain-Age-of-Spent-Outputs

Rucknium[m]: 👍️ I'll go through it too.

Here are the papers. Don't say I didn't warn you.

Mackenzie, A., Noether, S., & Monero Core Team. (2015). Improving obfuscation in the cryptonote protocol. moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=7

This paper is the first, to my knowledge, to write about the timing issue with decoy selection. It was released less than a year after the Monero blockchain began. In Section 3.1 Temporal Associations

Kumar, C., Tople, S., & Saxena, P. (2017), "A traceability analysis of monero’s blockchain." moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=21

This paper is pretty similar to the Moser et al. (2018) paper. Uses similar techniques.

Ye, C., Ojukwu, C., Hsu, A., & Hu, R. (2020). "Alt-coin traceability." moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=18

This paper analyzes Monero and Zcash. It re-runs the Moser analysis on newer data and finds that the Moser techniques are mostly ineffective against the improved Monero ring signature model with RingCT and a different decoy selection algorithm.

There are several papers that concentrate on chain reaction attacks. I read a few and shared my thoughts here: libera.monerologs.net/monero-research-lab/20220706#c117336

Chain reaction attacks probably aren't something that machine learning would be good at.

Anyway, they are probably ineffective at Monero's current ring size.

Here's another chain reaction paper that I didn't discuss in the link above: Vijayakumaran, S. (2021). "Analysis of cryptonote transaction graphs using the Dulmage-Mendelsohn Decomposition." moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=39

Ronge, V., Egger, C., Lai, R. W. F., Schröder, D., & Yin, H. H. F. (2021). "Foundations of ring sampling." moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=19

This paper gives a good formalization of the decoy selection problem. Basically, there are two options. There is "mimicking", which is what Monero tries to do currently. Match the real user behavior as much as possible.

Then there is "partitioning" or using a single "bin". Basically, "eliminate" the timing problem by always selecting ring members from a specific contiguous group of transaction outputs.

The main problem with partitioning is that the approximate time that you made your previous transaction would always be linked, even if the observer didn't know exactly which output was being spent. It would also be subject to targeted flooding or "black marble" attacks.

There is a conversation here about partitioning: libera.monerologs.net/monero-research-lab/20220829#c142533

Right now Monero uses no binning at all since we think ring size is too small for it to be done without tradeoffs being too steep.

In the draft of the Seraphis code binning is implemented. Basically a hybrid of mimicking and a strict partition. e.g. choose 16 bins of 8 ring members each for a total ring size of 128

Binning, as a hybrid strategy, has not been rigorously analyzed.

IMHO, many papers have been enthusiastic about partitioning because the authors are not statisticians and cannot figure out how to get a good mimicking decoy selection algorithm.

Deuber, D., Ronge, V., & Rueckert, C. (2022). "SoK: Assumptions underlying cryptocurrency deanonymizations". moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=97

Describes some techniques against bitcoin and Monero.

Otávio Chervinski, J., Kreutz, D., & Yu, J. (2021), "Analysis of transaction flooding attacks against Monero." moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=43

Flooding is a type of active attack against Monero privacy. Probably not too relevant to machine learning since ML is "passive" observation.

Some of us wrote a piece on the first documented flooding incident: mitchellpkt.medium.com/fingerprinti…ero-transaction-volume-a19cbf41ce60

Rucknium[m]: It could be active though, really you could use it for anythibg

Like iterative search

I think I linked you this before: My draft "paper" on how to estimate the real spend age distribution for creating a mimicking decoy selection algorithm: monero-project/research-lab #93

ghostway: Could you explain?

You did, yea

I am done with spamming papers :)

In passive observation, I guess you mean "hey this is some transactions, give me guesses". But this really isn't what you're trying to do. Just a little example of "active" predictions, is to change states. Like puct search (this is with perfect information games, but can be adapted after some thought on the specifics). You have a root node, according to some policy you sample the childrens, and then iteratively expand their

children (with a "value" prediction being a correction to that policy) all by trying to compromise between exploitation (you know this edge is probably better to do, so just visit it more) and exploration (maybe the other moves are ok as well, maybe they have a refutation). This is a very broad description and lacking many details. But gives the idea of what I'm trying to say

You change your own state, while gathering information and exploring deeper, trying to be efficient in sampling

Well, the Monero blockchain isn't a game in the game theoretic sense. Maybe something could be learned.

If you've heard of deepmind's alpha zero... It's that..

Is it useful form something that isn't a game?

Monero's blockchain isn't a game. There are players, but no strategies and no payoffs really. Maybe you could convince me that it can be formed as a game

Of course it's not a game easily. But intuitively (without much thought) it can be made out of this

Also, I was just making an example of puct. Another algorithm is probably needed, but using some graphs is the answer many times

That example being a way of using ml to fill unknowns iteratively whenever we get new data

Maybe isthmus has some thoughts. He has a chess repo on his GitHub: github.com/Mitchellpkt/Chess-Tactical-Vision

Lol, sure. I think you're a little too fixated on the chess thing, or you just don't agree with what I said about iteratively gathering clues

Btw, his issue on GitHub is quite easy to fix... Instead of & with the other's pieces when calculating attacks, just don't...

I don't mean to discourage. I'm trying to understand. I focus on traditional statistics instead of machine learning so I'm probably missing something.

time

yeah, using litecoin as a base truth would make sense. with bitcoin, you'd also have to "clean the data" with regards to coinjoins and other obfuscation techniques

i don't know how far down the graph analysis rabbit hole this effort would have to go. because on one extreme, you would need to trace all the activity on the chain to know the ground truth

though maybe just per transaction, knowing whether you can identify the true spend is enough

but at the end of the day, an open-source, free-for-anyone-to-use blockchain tracing tool would be beneficial

I don't know the techniques for that, but if you want, I'd be inclined to learn and write it (when I understand it...). Any resources?

Resources for open source blockchain tracing?

Blockchain tracing, heh

This is the best I'm aware of, but it's not maintained and I think it doesn't build anymore: github.com/citp/BlockSci

Oh, I misread the message

I meant resources, for techniques / how to develop those one

(how they developed them)

BlockSci was developed as a proof of concept for a paper. The link is in the GitHub repo

There are other papers, but....do you want me to post more papers?

Lol, do you want to open a: "rucknium paper tantrum" room?

Here's one paper. The nice thing about research papers is that they usually cite most of the relevant previous papers: arxiv.org/abs/2107.05749

Thanks!

I hope I'll be helpful in that space when I have a bit more timr

MOAR PAPERS

This is another good recent bitcoin tracing paper: arxiv.org/abs/2205.13882