Closed Rucknium closed 1 year ago
Logs
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.
Automated by this
Location: Libera.chat, #monero-research-lab | Matrix
Join the Monero Matrix server if you don't already have a Matrix account.
Time: 17:00 UTC Check in your timezone
Main discussion topics:
Greetings
Discuss: Consider removing the tx_extra field.
Discuss: Exploring Trustless zk-SNARKs for Monero's payment protocol.
Improvements to the decoy selection algorithm ( Decoy Selection Algorithm - Areas to Improve, Binning PoC, OSPEAD ) @j-berman @Rucknium
Seraphis. ( UkoeHB's Seraphis Proof of Concept work, Seraphis repo ).
MRL Meta: "Cat herding", i.e. prioritization of research areas and features. Active recruitment of technical talent, MRL structure, funding (@Rucknium & others) MoneroResearch.info repository of Monero-related research papers, Reddit discussion
Any other business
Confirm next meeting agenda
Please comment on GitHub in advance of the meeting if you would like to propose an agenda item.
Logs will be posted here after the meeting.
Meeting chairperson: UkoeHB
Previous meeting agenda/logs:
841