People have also expressed interest in research into churning (libera.ems.host/_matrix/media/r0/do…79652f27d8b2016dd7cf531d07b9c172ef2)

Gonna spam my thoughts on it because I think it's an interesting problem and think others would find it interesting too (and maybe I'm thinking about it wrong?)

I think the best place to start with researching it would be to just randomly pick an output in the chain at point A, then pick another random output a certain number of blocks later at point B (maybe a week later?), then determine the expected number of paths (and hop characteristics of each path) between the 2 points

The optimal way to churn would be to create a path between the 2 points that blends in with all the other paths

The worst way to churn would be to create a path between the 2 points that is exceptionally unusual

So the research would necessarily involve determining expected paths between 2 points in the chain. I think it could be generalized to say with ring size X, Y outputs per block, you would expect Z paths between points that are a certain distance apart (where average hop size is A with variance B)

Then the optimal way to churn would factor in those variables ("Hey user, if you plan to spend in a week, churn this output at block N, N + 143, N + 352, etc.")

Clearly there are a ton of variables at play, but maybe starting to look at chain data and making inferences along the above lines could be a good starting point. That's all i got

jberman I'm afraid it's an NP-hard problem to find _all_ paths between 2 nodes in a directed graph

and given the size of Monero transaction graph... It's probably easier to find all shortest paths using Floyd–Warshall algorithm, but it will still be very slow (cubic complexity)

I'm not even sure it's in NP class because how can you check in polynomial time that it's indeed _all_ paths?

I think a better starting point would be to pick a random output A, and then pick one of its subsequent outputs B, 2-3 transactions directly downstream from it.

After all, the odds of two random points in the graph being connected are very slim - what we're really interested in is how many alternative paths there are between two *connected* points with only 0 or 1 intermediate nodes (EAE and EABE scenarios)

6 churns fan out to more than a million transactions. 1 million is 40 days worth of transactions currently. So 6 churns with random intervals over in total 40-50 days should be safe enough

many churns over shorter intervals (like a week) are probably traceable with high probability

the reasonable application should be as follows in my opinion:

someone buys XMR on a KYC exchange and withdrawals to their noncustodial wallet. This withdrawal should be considered a poisoned output

then they spend over the course of a month or whatever

then they deposit back to the KYC exchange

on the other hand, daily tx volume is ~25000 which is enough for 3 churns within 24 hours. So it probably depends on how long you want to make your churn chain.

the exchange should be able to piece together with a relatively high success rate what the tx graph looked like. That said, noise is unpredictable and could be large, so at the end of the day it is still anyone's guess

and they could try to use this graph to see if they can associate any of the intermediary txs with any shared info from their information-sharing partners, which ideally would include the merchants you used to purchase things from

obviously this takes many assumptions, I'm just spelling out an example where someone specifically knows the start and ends points, and what sort of analysis may be performed

also we need to consider how long paths can get on a random graph with gamma distribution Monero uses. If paths with length > 20 (for example) are statistically impossible on a random graph with V vertices and E edges then most likely it's the real flow of funds

Yep, hence my suggestion to pick a random output and then another one a few txes downstream: see how many alternate paths between the two, how many other paths come out of A, and how many other lead to B (with the same depth). Rinse and repeat for a large sample of A and B

I didn't read Rucknium's submission, sorry if I accidentally stumbled on the same thing :D

<sech1> "6 churns fan out to more than..." <- This would be a nice conclusion to reach: x churns every n days based on tx volume

<sech1> "many churns over shorter..." <- Also it would be nice to quantify this

to quantify this, we need to list properties of fully random "Monero gamma-distribution" graphs

I think a primitive test would be to select 1000 outputs at point 1, and then for each of those outputs, see how many of them connect with 1+ and 2+ paths to 1000 outputs around point 2 (let's say ~1 week) and 1000 outputs around point 3 (let's say ~2 months)

like how long paths can get, what's the average path length between 2 connected vertices etc.

sgp_1: Nice! Also parametrized by the number of days between the two points A and B: presumably two points more days apart have more paths between them - but is this actually true?

clearly I chose 1 week and 2 months arbitrarily, but yeah I wanted 1 further away than the other

Ooops, I was still thinking in terms of separation by distance, not by time

But yeah, that would be another interesting scenario

yes, thinking about path length a bit more... If someone does 100 churns (even over months), it literally paints a target on this chain of transactions

Then again - if someone actually did 100 churns, what are the odds that anyone else could figure it out?

this would be a different test to see if an initial output at point 1 would connect with another arbitrary output at points 2 and 3 (of specified lengths away), and how many possible paths would exist

if 100 connected transactions are improbable on a truly random graph and this 100-churn chain is fully uncovered

*then this 100-churn chain is fully uncovered

The reason I'm framing it this was is because jberman 's scenario assumes someone knows a point 1 and a point 2

This was we can take arbitrary points and see if there is noise in practice

One of the Noethers was working on this churning question at a very abstract level. Anyone know if there is a draft available?

And see if there is a certain time period whereby there is another formed path >x% of the time

Rucknium[m]: It's public but it's totally unusable, let me see if I can find it

Unusable, eh?

If you find use of it I will be very, very impressed

jasminks and isthmus are working on some related theoretical work.

My main barrier here is that my understanding of graph theory is pretty limited.

Was here github.com/b-g-goodell/research-lab…/tree/matching/source-code/matching

Will look into further later

sgp_1: It's empty? Or is it a private repo?

My guess is that it was made private. I'll ask tomorrow

We have a suggestion for a "transaction weight" moneropedia entry. Feedbacks appreciated: monero-project/monero-site #1461#issuecomment-931294988

Here's some more context web.getmonero.org/2020/01/15/mrl-meeting.html

<Rucknium[m]> "My main barrier here is that..." <- atomfried I'll just do a mention because he/she did graph theory.

<sech1> "and given the size of Monero..." <- there can exists graphs for which there are exponential many shortest paths between two nodes s,t just sayin

for example a grid graph using the manhattan metric between nodes has lots of shortest paths between two nodes

Monero graph has more edges than manhattan-like graphs

so it's probably even more paths there

asuming that we assign to each edge the same weight, yes this would also be my educated guess

Something I am curious about that is related to churning, is there anything preventing an output used in one transaction being used as a decoy in other transactions in the same block?

Say you had a particular output you wanted to obscure as much as possible, and you send a genuine transaction along with a large set of other/unrelated transactions that you forced to select the same output as a decoy. Would 50 transactions in the same block that all have the output you are concerned with be allowed?

I'm guessing that isn't an option as a check against double-spends.

double spends are done against key images, not outputs

*are checked

Understood. It is interesting to consider the maximum density that one can pack a churning candidate into a given number of blocks.

Seth For Privacy could you please update the channel topic to show the meeting next week

carrington: Did you see my suggestion for a new agenda item?

I hadn't but I think it sounds very relevant. I'll add it shortly

<carrington[m]> "Seth For Privacy could you..." <- Will do

We should recruit this guy:

so he basically found a transaction with multiple input (consolidation tx) which was known as easy to track since long time ago

I mean I'm not saying his work was particularly difficult to carry out. It just reflects dedication, depth of knowledge of Monero, attention to detail, technical skills, ethics (he disclosed a vulnerability to ShapeShift before publishing), and some time availability.

I am maybe biased since he cited our work on the tx volume anomaly :P

Looks like that guy has a company that "provides consulting services on a variety of cryptocurrency-related topics including forensics." What do you want to recruit (hire) him to do?

Well, examine churning would be a good start. Have him submit a CCS or something

funding request for Seraphis PoC: repo.getmonero.org/monero-project/ccs-proposals/-/merge_requests/256

UkoeHB: Fantastic. I'm glad you decided to submit the CCS. 💪

Seconded.

Rucknium[m]: to get your proposal in the gitlab description, you have to paste it there manually. Use the `Edit` button in the upper right corner.

<UkoeHB> "funding request for Seraphis PoC..." <- Very glad to see this!

Shared on Twitter as well, do you mind sharing it on Reddit UkoeHB?

If not I can post it.

UkoeHB: Thanks! It is now fixed :)

UkoeHB: I posted on Reddit: reddit.com/r/Monero/comments/pzbytc…mising_nextgen_transaction_protocol

How much would a Lelantus Spark audit apply to Seraphis?

I know that's difficult to quantify...

I guess that can only be said once an audit is done.

Not sure, would depend on scope

Is the idea to have separate audits of the theory and the implementation eventually?

Peer review of the paper, audit of the implementation.

What I mean is, are we likely to try to raise funds for multiple paid audits? I can see that Bulletproofs+ had two audits

Seems wise to do so, or at least focused audits for different components.

The Groth/Bootle proof is quite hefty, although not nearly as challenging as bulletproofs.