17:02:12 <Rucknium[m]> UkoeHB: Do you want to start the meeting?
17:03:59 <rbrunner> His usual "Meeting in 1 hour" announcement was also missing ...
17:05:10 <Rucknium[m]> I will start: Meeting time!
17:05:23 <shalit[m]> Hello! how are you all doing?
17:05:24 <Rucknium[m]> "Agenda": https://github.com/monero-project/meta/issues/844
17:05:29 <Rucknium[m]> Hi
17:05:31 <rbrunner> Yeah, hello
17:07:10 <vtnerd> hi
17:07:22 <Rucknium[m]> Updates: what is everyone working on?
17:07:34 <jeffro256[m]> Howdy
17:08:43 <vtnerd> zerofconf in LWS (mainly), and some slow progress on bp++
17:08:52 <jeffro256[m]> I've been working on making PR https://github.com/monero-project/monero/pull/8815 more efficient 
17:08:57 <Rucknium[m]> I am running Monte Carlo tests on the OSPEAD estimator. Just 10 iterations at a time for now. If anyone has opinions about what distributions I can test it with, suggest them. I mean some set of decoy selection algorithms and real spend distributions.
17:08:58 <vtnerd> Im becoming more confident Ill be able to complete it, if only the requests for LWS die down
17:09:51 <shalit[m]> I'm still working on writing storeEnote to disk
17:10:31 <jeffro256[m]> Rucknium[m]: Have you looked into trying to obtain real user data to test distributions against ? 
17:11:21 <vtnerd> I imagine that would be fairly difficult
17:11:33 <Rucknium[m]> jeffro256: Like BTC and LTC, and BCH and DOGE?
17:11:43 <Rucknium[m]> Yes that's a good idea. 
17:12:29 <jeffro256[m]> Just like people voluntarily opting into a survey where e.g. you have their viewkeys and you ask them to just spend their XMR how they normally would 
17:12:47 <jeffro256[m]> Also  yeah looking at BTC on-chain data could be interesting 
17:13:05 <Rucknium[m]> The view key idea is too subject to selection bias IMHO
17:13:34 <jeffro256[m]> Probably true 
17:14:05 <vtnerd> the paper that recommended the exponential distribution also looked at ring_size=0 in early Monero for some help
17:14:20 <Rucknium[m]> I have the data for BTC, etc already. Look at section 8 (page 32) of the PDF linked here: https://github.com/monero-project/research-lab/issues/93
17:14:20 <vtnerd> iirc the distribution was similar to BTC
17:15:27 <Rucknium[m]> What about decoy selection distributions? wallet2 (or a simplified version) of course...but what else?
17:15:29 <jeffro256[m]> Another option is you could have people voluntarily show you their bank accounts and you translate that somehow into how a UTXO based wallet would spend the funds. Still have the selection bias, but there's generally more data to work with per person 
17:15:34 <ghostway[m]> <Rucknium[m]> "I am running Monte Carlo tests..." <- Hello, late for the party, what do you think on getting data from users? For ground truth. Maybe from other cryptocurrencies, if those are viable
17:15:56 <ghostway[m]> Oh, I see jeffro has already suggested that, lol
17:18:43 <UkoeHB> Sorry, forgot to say I’m not available for the meeting today.
17:18:58 <ghostway[m]> Is the bridge dead ...?
17:19:12 <vtnerd> ghostway[m]: no
17:19:37 <jeffro256[m]> <vtnerd> "the paper that recommended the..." <- Ring size=0? *shudders*
17:19:52 <vtnerd> yeah early Monero had no constraints on ring size
17:20:02 <rbrunner> Optionally yes
17:20:07 <vtnerd> so a bunch of people leaked the real spend early on
17:20:13 <jeffro256[m]> I faintly remember the debates about making the rings fixed size right as I was getting into Monero
17:22:14 <Rucknium[m]> Devs out there is wallet land can help inform about those nonstandard decoy selection algorithms.
17:23:00 <Rucknium[m]> I don't mean exact specifications (of course that would be very nice), but an idea of the general shape of those distributions.
17:23:26 <jeffro256[m]> Speaking on nonstandard decoy selection algorithms, I just made a CCS proposal to rewrite the reference decoy selection code 
17:23:48 <jeffro256[m]> I think it's warranted in this code because the current decoy selection code is so untestable 
17:23:54 <jeffro256[m]> *in this case
17:25:01 <jeffro256[m]> Basically every meaningful decoy selection bug can be exposed in the testing phase by looking at statistical anomalies. These big selection bugs were not caught because it's a PITA to write test cases for methods baked into the monolithic wallet2 
17:25:39 <jeffro256[m]> I want to know if anyone disagrees with me on this 
17:25:54 <Rucknium[m]> It would be very nice to have someone who knows C++ to derive the specification-in-practice of wallet2's DSA.
17:26:14 <Rucknium[m]> My other plan was for me to do it.
17:27:19 <Rucknium[m]> This is a critical piece of code. It needs close attention. For reference on how it's critical for privacy, please see the quotes from several papers on the first page of that PDF I linked above
17:28:01 <vtnerd> jeffro256[m]: https://github.com/vtnerd/monero-lws/blob/master/src/util/random_outputs.cpp
17:28:19 <vtnerd> I recall doing _mostly_ what wallet2 did, but there may be some variance for older outputs
17:28:34 <Rucknium[m]> The paper that xmrack  posted (thanks) yesterday, which I would like to discuss, says "Monero differs from our experiment mainly in two ways: 1) Their approximation on the source account distribution is some Ŝ_t different from our S_t , which is a code-induced distribution that cannot be expressed analytically...."
17:28:57 <Rucknium[m]> Even external researchers are "complaining" about wallet2.
17:29:40 <ghostway[m]> Rucknium[m]: https://github.com/monero-project/monero/blob/master/src/wallet/wallet2.cpp#LL1014C1-L1061C3 is this it?
17:29:57 <jeffro256[m]> vtnerd: At a glance, this seems much much much better than get_outs, thanks for the link
17:30:11 <jeffro256[m]> MyMonero also had the off-by-one bug, correct?
17:30:43 <vtnerd> correct - although they may have copied the implementation in lws
17:31:40 <Rucknium[m]> ghostway: I don't know if that's the exact lines. jeffro256 , could you comment?
17:32:18 <jeffro256[m]> Thanks just the gamma picker, which is used within decoy selection 
17:32:47 <ghostway[m]> Oh I see, okay. What's the exact thing, do you have that on-hand?
17:33:50 <jeffro256[m]> Function get_outs() Lines 8165-8778
17:34:08 <ghostway[m]> Thanks
17:35:58 <jeffro256[m]> It also does RPC retrieval and caching of enote information, but all relevant logic is in that function (besides the gamme picker itself)
17:37:39 <ghostway[m]> I can see that... Oof, 600 line function 
17:38:13 <jeffro256[m]> Fr, it's bad
17:38:32 <jeffro256[m]> Hey @vtnerd, is line going to be changed soon? https://github.com/vtnerd/monero-lws/blob/ba218f7b361ea61cc8061de1a34ac14b472bf497/src/util/gamma_picker.cpp#L79
17:39:02 <jeffro256[m]> Just skimming, but I think that logic keeps the 10-block-lock decoy selection bug alivr 
17:39:05 <jeffro256[m]> *alive 
17:41:22 <vtnerd> jeffro256[m]: the release branch has the fix but master does not. I dont remember why at the moment
17:43:04 <jeffro256[m]> The release branch of LWS?
17:43:11 <vtnerd> no sorry that is the fix
17:43:38 <vtnerd> the end iterator is not inclusive
17:45:05 <jeffro256[m]> Oh okay I see it 
17:47:28 <Rucknium[m]> Thanks to xmrack for finding Chow, Egger, Lai, Ronge, & Woo (2023) "On Sustainable Ring-based Anonymous Systems" https://eprint.iacr.org/2023/743.pdf , which was posted May 23.
17:47:44 <Rucknium[m]> This research group continues to produce interesting papers relevant to Monero.
17:47:59 <Rucknium[m]> I read the paper except for the appendix, cryptography-heavy parts (which I think are just describing RingCT) and the section on an application to social media.
17:48:09 <Rucknium[m]> My comments:
17:48:20 <Rucknium[m]> 1) AFAIK, this is the first paper that discusses the possibility of "pruning of spent outputs" in my list of Monero open research questions (MRL issue #94).
17:48:31 <Rucknium[m]> 2) Their "garbage collector" of spent outputs would require, in practice, a partitioning decoy selection algorithm (DSA). That means each ring would be "one big bin". Each big would be a contiguous set of outputs. The bins would be disjoint sets.
17:48:45 <Rucknium[m]> 3) The garbage collection procedure with partitioning DSA is very simple: You garbage collect the whole bin if the number of transaction inputs that reference the bin equal the size of the bin.
17:48:57 <Rucknium[m]> 4) There is an alternative garbage collector for a mimicking decoy selection algorithm (or another DSA that is not partitioning), which is what Monero has to tried to have. It's basically to run the Dulmage-Mendelsohn Decomposition to see if any sets of outputs can be proven to be spent.
17:49:08 <Rucknium[m]> 5) This alternative does not collect much garbage at all (and maybe none) at Monero's ring size and transaction volume. That's why they say Monero is "unsustainable". Monero can not really prune outputs in its current form.
17:49:22 <Rucknium[m]> 6) My opinion: The partitioning DSA + Garbage collector is vulnerable to malicious parties simply producing a single output in each bin and never spending them. Then the garbage can never be collected and pruning does not happen after all. What do you think?
17:49:34 <Rucknium[m]> 7) Something that this paper made me realize is that if Monero has a partitioning DSA then it would need to be required at the protocol level since otherwise nonstandard DSA could be pulling decoys from "bags of black marbles" that are already provably spent.
17:49:45 <Rucknium[m]> 8) Disadvantages of a partitioning DSA are discussed here: https://libera.monerologs.net/monero-research-lab/20220829#c142533
17:50:35 <ghostway[m]> I see on line 9894 it passes tx.selected_transfers, what a terrible name to also have a m_transfers. What is even m_transfers? Don't tell me it's keeping a history of recent transactions.... That's what it looks like in process_new_transaction, at least
17:55:17 <vtnerd> Ive never thought about a garbage collection system, but the requirement of it being "baked-in" does seems likely
17:56:12 <Rucknium[m]> This Chow et al. (2023) paper...with a partitioning DSA, it at least gives the possibility of pruning spent outputs in a ring signature system, which AFAIK would not be possible with global membership proofs like trustless zk-SNARKS.
17:56:48 <ghostway[m]> <Rucknium[m]> "5) This alternative does not..." <- What about when seraphis rolls around? And let's assume demand will rise
17:57:18 <jeffro256[m]> > On the negative side, we show empirically that Monero, one of the most popular anonymous
17:57:18 <jeffro256[m]> cryptocurrencies, is unlikely to be sustainable without altering its current ring sampling
17:57:18 <jeffro256[m]> strategy. The main subroutine is a sub-quadratic-time algorithm for detecting used accounts
17:57:18 <jeffro256[m]> in a ring-based anonymous system.
17:57:32 <Rucknium[m]> Larger ring size and higher tx volume reduces opportunities for GC with a mimicking DSA
17:58:09 <jeffro256[m]> From a wobbly not-technical intuitive view, that quote makes it seem like the randomness of Monero decoy selection would have to be degraded somewhat to acheive usable garbage collection results 
17:58:33 <Rucknium[m]> Check figures 11 and 12 (page 25) in the paper
17:58:36 <jeffro256[m]> Is that correct?
17:59:37 <Rucknium[m]> jeffro256: The "degradation" is one ring = one bin. Disjoint bins
18:00:18 <Rucknium[m]> But the partitioning DSA has certain privacy benefits (but some disadvantages). This research group and others have theoretical results about that.
18:00:23 <Rucknium[m]> in other papers
18:01:09 <ghostway[m]> jeffro256[m]: > <@jeffro256:monero.social> > On the negative side, we show empirically that Monero, one of the most popular anonymous... (full message at <https://libera.ems.host/_matrix/media/v3/download/libera.chat/8e9735f245223af5e2a16f7f52d9dbf42f3effed>)
18:01:56 <ghostway[m]> Unless they also came up with an algorithm for that with another ring scheme
18:02:36 <Rucknium[m]> IMHO, one of the reasons this research group (and a few others) prefers partitioning DSAs is that they don't see a way to discover a good mimicking DSA. There is a good way: OSPEAD
18:02:43 <jeffro256[m]> Is the benefit basically the point of binning in the first place? That if an observer knows/thinks a transaction spends an output within a certain small timeframe, if you clumps the input ring members around that time (as opposed to only having one from that time), then the observer doesn't learn as much information about potential spends within that time period
18:03:09 <jeffro256[m]> On the other hand, if the external observer didn't already know a finer time period, now they do...
18:04:16 <Rucknium[m]> jeffro256: Yes, that's the main privacy benefit. An adversary would know that it's one of the outputs in that "bin" period, but would have no useful timing information to discover _which one of those_. But the adversary would know the approximate time that the original output was produced. That would be a problem for certain threat models.
18:05:55 <Rucknium[m]> An active adversary could also launch an active black ball attack where they pack the bin of a targeted person's output with outputs produced by the adversary.
18:06:26 <Rucknium[m]> So the adversary sees the target's tx in the mempool and briefly floods the mempool witt their txs
18:06:32 <ghostway[m]> Wouldnt that defeat the whole purpose of binning? Did they combat that in the paper?
18:07:10 <jeffro256[m]> The main problem I think with ONLY using binning is that people don't all transact uniformly over days/weeks/years. Everyone naturally has cycles of activities, and having decoy selection reveal the approximate time of the true spend can reveal a lot more information for people who don't transaction within the cycle that the majority does, basically creating multiple anonymity puddles 
18:07:43 <jeffro256[m]> That paper is incredibly interesting though
18:08:45 <Rucknium[m]> ghostway: See section 2.1.2 (Page 269) of https://moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=19
18:08:57 <Rucknium[m]> Ronge, V., Egger, C., Lai, R. W. F., Schröder, D., & Yin, H. H. F. (2021). Foundations of ring sampling. 
18:09:08 <Rucknium[m]> They say it's a risk.
18:09:56 <ghostway[m]> Thanks
18:10:00 <Rucknium[m]> ^ This paper is referenced by the prune-outputs paper as the reasoning that the privacy with a partitioning DSA is good.
18:11:56 <Rucknium[m]> They also say that a very good mimicking DSA is also good for privacy, but they don't know how to estimate one.
18:12:46 <ghostway[m]> I guess that's when opseed comes in? 
18:13:12 <Rucknium[m]> OSPEAD. Yes
18:14:57 <Rucknium[m]> "We emphasize that although Theorem 6.2 shows that the optimal anonymity is always almost achievable up to a constant factor, the result is mostly of theoretical interest, because it requires the knowledge of an estimation ˆS of the signer distribution S. Even if it is possible to obtain a reasonable estimation ˆS of S, a questionable assumption, S may change over time, e.g., due...
18:15:08 <Rucknium[m]> "to economic bubbles and recessions, and depends on the free will of users. For a good and practical sampler we recommend the partitioning sampler in Section 6.3."
18:15:24 <Rucknium[m]> ^ That's from Ronge et al. (2021)
18:16:29 <Rucknium[m]> Let's end the meeting here. Thanks for attending. Discussion about DSAs can continue, obviously.
18:17:04 <jeffro256[m]> Thanks Rick
18:17:18 <jeffro256[m]> *Rucknium lol
18:17:19 <ghostway[m]> Thanks, have a great night/day
18:17:31 <shalit[m]> Thanks!
18:26:39 <UkoeHB> Thanks for summarizing the paper Rucknium[m]
19:54:28 <merope> Rucknium: I have a hypothetical scenario to ponder. Let's take into consideration the recent off-by-one ring selection bug: right now, if we assume that all wallets use either the old buggy wallet2 implementation (ie they haven't updated yet), or the new fixed implementation (ie they have updated), then an external observer could try to tell the two apart, and potentially discern a real spend in some cases - right?
19:54:28 <merope> If so: would it make sense for a subgroup of users to construct some transactions that *look* like the old buggy implementation, but actually aren't (because they're spending some random older outputs, while still following the regular DSA for the rest of the decoys)? And how many rings or transactions of that kind would it take to "ruin" this specific heuristic?
19:55:43 <merope> And similarly, would it be a viable strategy to use in the future, should any more issues with the DSA arise?
20:00:15 <merope> I.e. keep a stash of outputs of various ages, to be used to generate just enough noise on chain when a problematic heuristic is discovered
20:54:14 <jeffro256[m]> <merope> "Rucknium: I have a hypothetical..." <- > <@endor00:matrix.org> Rucknium: I have a hypothetical scenario to ponder. Let's take into consideration the recent off-by-one ring selection bug: right now, if we assume that all wallets use either the old buggy wallet2 implementation (ie they haven't updated yet), or the new fixed implementation (ie they have updated), then an external observer could try to tell the two
20:54:14 <jeffro256[m]> apart, and potentially discern a real spend in some cases - right?
20:54:14 <jeffro256[m]> > If so: would it make sense for a subgroup of users to construct some transactions that *look* like the old buggy implementation, but actually aren't (because they're spending some random older outputs, while still following the regular DSA for the rest of the decoys)? And how many rings or transactions of that kind would it take to "ruin" this specific heuristic?
20:54:14 <jeffro256[m]> My 2 cents: since the new implementation is not guaranteed to ever choose 10-block old decoys, in instances where no 10 block old ring members are present within a tx, it is already ambiguous whether this transaction was created by the new or the old implementation
20:55:23 <jeffro256[m]> <merope> "And similarly, would it be a..." <- If there's a larger, more easily visible statistical schism between the two implementations, this might be more necessary IMO
21:03:59 <Rucknium[m]> I mostly agree with jeffro256 on both points.
21:05:21 <Rucknium[m]> And it's not certain whether there are other nonstandard DSAs that did not have the off-by-one error.
21:06:05 <Rucknium[m]> Exodus Wallet has an independent implementation that tries to implement the gamma distribution.
21:10:05 <Rucknium[m]> https://www.reddit.com/r/Monero/comments/wm5th1/comment/ik1zhj3/
21:10:22 <Rucknium[m]> "We deviate from Monero slightly. We perform the typical gamma with shape parameter 19.28 rate 1.61 but the resolution is on a block level. We randomly sample the blocks using the gamma distribution and then once a block has been selected another random sample using a uniform distribution within the block to retrieve the final mixin output."
21:10:35 <Rucknium[m]> "We call it "custom core". This differs from Monero Core if my memory serves me right, they have a global index for all the outputs and they perform the random sample with gamma distribution based on the individual outputs."