UkoeHB: Do you want to start the meeting?

His usual "Meeting in 1 hour" announcement was also missing ...

I will start: Meeting time!

Hello! how are you all doing?

"Agenda": monero-project/meta #844

Hi

Yeah, hello

hi

Updates: what is everyone working on?

Howdy

zerofconf in LWS (mainly), and some slow progress on bp++

I've been working on making PR monero-project/monero #8815 more efficient

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.

Im becoming more confident Ill be able to complete it, if only the requests for LWS die down

I'm still working on writing storeEnote to disk

Rucknium[m]: Have you looked into trying to obtain real user data to test distributions against ?

I imagine that would be fairly difficult

jeffro256: Like BTC and LTC, and BCH and DOGE?

Yes that's a good idea.

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

Also yeah looking at BTC on-chain data could be interesting

The view key idea is too subject to selection bias IMHO

Probably true

the paper that recommended the exponential distribution also looked at ring_size=0 in early Monero for some help

I have the data for BTC, etc already. Look at section 8 (page 32) of the PDF linked here: monero-project/research-lab #93

iirc the distribution was similar to BTC

What about decoy selection distributions? wallet2 (or a simplified version) of course...but what else?

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

<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

Oh, I see jeffro has already suggested that, lol

Sorry, forgot to say I’m not available for the meeting today.

Is the bridge dead ...?

ghostway[m]: no

<vtnerd> "the paper that recommended the..." <- Ring size=0? *shudders*

yeah early Monero had no constraints on ring size

Optionally yes

so a bunch of people leaked the real spend early on

I faintly remember the debates about making the rings fixed size right as I was getting into Monero

Devs out there is wallet land can help inform about those nonstandard decoy selection algorithms.

I don't mean exact specifications (of course that would be very nice), but an idea of the general shape of those distributions.

Speaking on nonstandard decoy selection algorithms, I just made a CCS proposal to rewrite the reference decoy selection code

I think it's warranted in this code because the current decoy selection code is so untestable

*in this case

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

I want to know if anyone disagrees with me on this

It would be very nice to have someone who knows C++ to derive the specification-in-practice of wallet2's DSA.

My other plan was for me to do it.

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

jeffro256[m]: github.com/vtnerd/monero-lws/blob/master/src/util/random_outputs.cpp

I recall doing _mostly_ what wallet2 did, but there may be some variance for older outputs

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...."

Even external researchers are "complaining" about wallet2.

Rucknium[m]: github.com/monero-project/monero/bl…wallet/wallet2.cpp#LL1014C1-L1061C3 is this it?

vtnerd: At a glance, this seems much much much better than get_outs, thanks for the link

MyMonero also had the off-by-one bug, correct?

correct - although they may have copied the implementation in lws

ghostway: I don't know if that's the exact lines. jeffro256 , could you comment?

Thanks just the gamma picker, which is used within decoy selection

Oh I see, okay. What's the exact thing, do you have that on-hand?

Function get_outs() Lines 8165-8778

Thanks

It also does RPC retrieval and caching of enote information, but all relevant logic is in that function (besides the gamme picker itself)

I can see that... Oof, 600 line function

Fr, it's bad

Hey @vtnerd, is line going to be changed soon? github.com/vtnerd/monero-lws/blob/b…bf497/src/util/gamma_picker.cpp#L79

Just skimming, but I think that logic keeps the 10-block-lock decoy selection bug alivr

*alive

jeffro256[m]: the release branch has the fix but master does not. I dont remember why at the moment

The release branch of LWS?

no sorry that is the fix

the end iterator is not inclusive

Oh okay I see it

Thanks to xmrack for finding Chow, Egger, Lai, Ronge, & Woo (2023) "On Sustainable Ring-based Anonymous Systems" eprint.iacr.org/2023/743.pdf , which was posted May 23.

This research group continues to produce interesting papers relevant to Monero.

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.

My comments:

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).

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.

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.

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.

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.

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?

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.

8) Disadvantages of a partitioning DSA are discussed here: libera.monerologs.net/monero-research-lab/20220829#c142533

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

Ive never thought about a garbage collection system, but the requirement of it being "baked-in" does seems likely

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.

<Rucknium[m]> "5) This alternative does not..." <- What about when seraphis rolls around? And let's assume demand will rise

> On the negative side, we show empirically that Monero, one of the most popular anonymous

cryptocurrencies, is unlikely to be sustainable without altering its current ring sampling

strategy. The main subroutine is a sub-quadratic-time algorithm for detecting used accounts

in a ring-based anonymous system.

Larger ring size and higher tx volume reduces opportunities for GC with a mimicking DSA

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

Check figures 11 and 12 (page 25) in the paper

Is that correct?

jeffro256: The "degradation" is one ring = one bin. Disjoint bins

But the partitioning DSA has certain privacy benefits (but some disadvantages). This research group and others have theoretical results about that.

in other papers

jeffro256[m]: > <@jeffro256:monero.social> > On the negative side, we show empirically that Monero, one of the most popular anonymous... (full message at <libera.ems.host/_matrix/media/v3/do…5f245223af5e2a16f7f52d9dbf42f3effed>)

Unless they also came up with an algorithm for that with another ring scheme

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

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

On the other hand, if the external observer didn't already know a finer time period, now they do...

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.

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.

So the adversary sees the target's tx in the mempool and briefly floods the mempool witt their txs

Wouldnt that defeat the whole purpose of binning? Did they combat that in the paper?

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

That paper is incredibly interesting though

ghostway: See section 2.1.2 (Page 269) of moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=19

Ronge, V., Egger, C., Lai, R. W. F., Schröder, D., & Yin, H. H. F. (2021). Foundations of ring sampling.

They say it's a risk.

Thanks

^ This paper is referenced by the prune-outputs paper as the reasoning that the privacy with a partitioning DSA is good.

They also say that a very good mimicking DSA is also good for privacy, but they don't know how to estimate one.

I guess that's when opseed comes in?

OSPEAD. Yes

"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...

"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."

^ That's from Ronge et al. (2021)

Let's end the meeting here. Thanks for attending. Discussion about DSAs can continue, obviously.

Thanks Rick

*Rucknium lol

Thanks, have a great night/day

Thanks!

Thanks for summarizing the paper Rucknium[m]

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?

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?

And similarly, would it be a viable strategy to use in the future, should any more issues with the DSA arise?

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

<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

apart, and potentially discern a real spend in some cases - right?

> 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?

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

<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

I mostly agree with jeffro256 on both points.

And it's not certain whether there are other nonstandard DSAs that did not have the off-by-one error.

Exodus Wallet has an independent implementation that tries to implement the gamma distribution.

"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."

"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."