05:34:19 <jberman[m]> People have also expressed interest in research into churning (https://libera.ems.host/_matrix/media/r0/download/libera.chat/05d4379652f27d8b2016dd7cf531d07b9c172ef2)
05:34:38 <jberman[m]> 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?)
05:35:22 <jberman[m]> 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
05:35:42 <jberman[m]> The optimal way to churn would be to create a path between the 2 points that blends in with all the other paths
05:35:42 <jberman[m]> The worst way to churn would be to create a path between the 2 points that is exceptionally unusual
05:36:27 <jberman[m]> 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)
05:36:27 <jberman[m]> 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.")
05:36:57 <jberman[m]> 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
07:03:37 <sech1> jberman I'm afraid it's an NP-hard problem to find _all_ paths between 2 nodes in a directed graph
07:04:32 <sech1> 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)
07:07:34 <sech1> I'm not even sure it's in NP class because how can you check in polynomial time that it's indeed _all_ paths?
07:09:45 <merope> 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.
07:09:45 <merope> 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)
07:17:43 <sech1> 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
07:18:48 <sech1> many churns over shorter intervals (like a week) are probably traceable with high probability
07:20:23 <sgp_1> the reasonable application should be as follows in my opinion:
07:20:55 <sgp_1> someone buys XMR on a KYC exchange and withdrawals to their noncustodial wallet. This withdrawal should be considered a poisoned output
07:21:05 <sgp_1> then they spend over the course of a month or whatever
07:21:20 <sgp_1> then they deposit back to the KYC exchange
07:22:08 <sech1> 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.
07:22:17 <sgp_1> 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
07:23:16 <sgp_1> 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
07:24:26 <sgp_1> 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
07:26:45 <sech1> 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
07:26:59 <merope> 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
07:27:41 <sech1> I didn't read Rucknium's submission, sorry if I accidentally stumbled on the same thing :D
07:28:06 <merope> <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
07:28:31 <merope> <sech1> "many churns over shorter..." <- Also it would be nice to quantify this
07:29:02 <sech1> to quantify this, we need to list properties of fully random "Monero gamma-distribution" graphs
07:29:08 <sgp_1> 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)
07:29:20 <sech1> like how long paths can get, what's the average path length between 2 connected vertices etc.
07:30:36 <merope> 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?
07:31:17 <sgp_1> clearly I chose 1 week and 2 months arbitrarily, but yeah I wanted 1 further away than the other
07:32:01 <merope> Ooops, I was still thinking in terms of separation by distance, not by time
07:32:31 <merope> But yeah, that would be another interesting scenario
07:33:13 <sech1> 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
07:34:04 <merope> Then again - if someone actually did 100 churns, what are the odds that anyone else could figure it out?
07:34:24 <sgp_1> 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
07:34:41 <sech1> if 100 connected transactions are improbable on a truly random graph and this 100-churn chain is fully uncovered
07:34:51 <sech1> *then this 100-churn chain is fully uncovered
07:36:56 <sgp_1> The reason I'm framing it this was is because jberman 's scenario assumes someone knows a point 1 and a point 2
07:37:11 <sgp_1> This was we can take arbitrary points and see if there is noise in practice
07:37:55 <Rucknium[m]> One of the Noethers was working on this churning question at a very abstract level. Anyone know if there is a draft available?
07:38:05 <sgp_1> And see if there is a certain time period whereby there is another formed path >x% of the time
07:38:27 <sgp_1> Rucknium[m]: It's public but it's totally unusable, let me see if I can find it
07:39:01 <Rucknium[m]> Unusable, eh?
07:39:37 <sgp_1> If you find use of it I will be very, very impressed
07:39:44 <Rucknium[m]> jasminks and isthmus are working on some related theoretical work.
07:41:21 <Rucknium[m]> My main barrier here is that my understanding of graph theory is pretty limited.
07:46:20 <sgp_1> Was here https://github.com/b-g-goodell/research-lab/tree/matching/source-code/matching
07:46:58 <sgp_1> Will look into further later
07:48:38 <merope> sgp_1: It's empty? Or is it a private repo?
07:51:03 <sgp_1> My guess is that it was made private. I'll ask tomorrow
07:51:13 <ErCiccione> We have a suggestion for a "transaction weight" moneropedia entry. Feedbacks appreciated: https://github.com/monero-project/monero-site/pull/1461#issuecomment-931294988
07:51:14 <sgp_1> Here's some more context https://web.getmonero.org/2020/01/15/mrl-meeting.html
10:24:58 <coinstudent2048[> <Rucknium[m]> "My main barrier here is that..." <- atomfried I'll just do a mention because he/she did graph theory.
13:33:08 <atomfried[m]> <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
13:34:32 <atomfried[m]> for example a grid graph using the manhattan metric between nodes has lots of shortest paths between two nodes
13:35:56 <sech1> Monero graph has more edges than manhattan-like graphs
13:36:06 <sech1> so it's probably even more paths there
13:36:44 <atomfried[m]> asuming that we assign to each edge the same weight, yes this would also be my educated guess
13:58:35 <spackle[m]> 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?
13:58:35 <spackle[m]> 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?
14:00:05 <spackle[m]> I'm guessing that isn't an option as a check against double-spends.
14:00:33 <sech1> double spends are done against key images, not outputs
14:01:09 <sech1> *are checked
14:14:20 <spackle[m]> Understood. It is interesting to consider the maximum density that one can pack a churning candidate into a given number of blocks.
14:22:03 <carrington[m]> Seth For Privacy could you please update the channel topic to show the meeting next week
14:27:42 <Rucknium[m]> carrington: Did you see my suggestion for a new agenda item?
14:27:42 <Rucknium[m]> https://github.com/monero-project/meta/issues/616#issuecomment-931896977
14:29:50 <carrington[m]> I hadn't but I think it sounds very relevant. I'll add it shortly
14:34:22 <sethsimmons> <carrington[m]> "Seth For Privacy could you..." <- Will do
15:54:38 <Rucknium[m]> We should recruit this guy:
15:54:38 <Rucknium[m]> https://medium.com/@nbax/tracing-the-wannacry-2-0-monero-transactions-d8c1e5129dc1
15:57:43 <sech1> so he basically found a transaction with multiple input (consolidation tx) which was known as easy to track since long time ago
16:00:08 <Rucknium[m]> 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.
16:00:57 <Rucknium[m]> I am maybe biased since he cited our work on the tx volume anomaly :P
16:04:25 <UkoeHB> 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?
16:06:00 <Rucknium[m]> Well, examine churning would be a good start. Have him submit a CCS or something
16:16:55 <UkoeHB> funding request for Seraphis PoC: https://repo.getmonero.org/monero-project/ccs-proposals/-/merge_requests/256
16:20:25 <Rucknium[m]> UkoeHB: Fantastic. I'm glad you decided to submit the CCS. 💪
16:23:04 <rbrunner> Seconded.
16:25:09 <UkoeHB> 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.
16:30:13 <sethsimmons> <UkoeHB> "funding request for Seraphis PoC..." <- Very glad to see this!
16:30:25 <sethsimmons> Shared on Twitter as well, do you mind sharing it on Reddit UkoeHB?
16:30:28 <sethsimmons> If not I can post it.
16:32:40 <Rucknium[m]> UkoeHB: Thanks! It is now fixed :)
16:47:30 <sethsimmons> UkoeHB: I posted on Reddit: https://www.reddit.com/r/Monero/comments/pzbytc/seraphis_a_promising_nextgen_transaction_protocol/
18:06:11 <selsta> How much would a Lelantus Spark audit apply to Seraphis?
18:07:08 <selsta> I know that's difficult to quantify...
18:07:51 <selsta> I guess that can only be said once an audit is done.
19:17:36 <UkoeHB> Not sure, would depend on scope
20:45:12 <carrington[m]> Is the idea to have separate audits of the theory and the implementation eventually?
20:45:50 <UkoeHB> Peer review of the paper, audit of the implementation.
20:49:07 <carrington[m]> What I mean is, are we likely to try to raise funds for multiple paid audits? I can see that Bulletproofs+ had two audits
20:49:53 <UkoeHB> Seems wise to do so, or at least focused audits for different components.
20:50:37 <UkoeHB> The Groth/Bootle proof is quite hefty, although not nearly as challenging as bulletproofs.