suggestion regarding quantum computers, just wanted to share this here because i'm not sure how many follow the issue tracker

braindead stupid

derive qc keys from the same seed, so when the private keys are broken, can switch to the qc keys?

when the private keys are broken, that means anything derived from that seed is broken too

anyway, the seed only provides 128 or 256 bits of entropy. pq keys need much more input

the suggestion is nonsense.

meeting 1.25hr

meeting time monero-project/meta #717

1. greetings

hello

hello

Hi

Hello

Hello

Hi

2. updates, what has everyone been working on?

I read cover-to-cover Yu, Au, and Esteves-Verissimo (2019) "Re-Thinking Untraceability in the CryptoNote-Style Blockchain"; Ronge et al. (2021) "Foundations of Ring Sampling"; and Egger et al. (2022) "On Defeating Graph Analysis of Anonymous Transactions".

We now have over 100 papers on MoneroResearch.info :)

I could finally code all the main crypto functions in Python to verify that there is no inflation happening :)

My code now works for all type of transactions. I just implemented one version of Bulletproofs as it works for verifying the transactions types 3,4 and 5. Maybe there are some optimizations to do on it and that's what I will be doing in the next two months. I will improve the algorithms, website (www.moneroinflation.com) and compare the performance with the C++ code. Now I believe I can say that I have an idea about what

is happening with Monero :)

me: I implemented a generator factory and switched the BP+ (new file: BP+2) and Grootle proofs to use it. Sharing proof generators improves verification batching slightly, and hopefully is a good investment for future batching needs/opportunities. I also evaluated implementing ristretto again, and again concluded it is too large an implementation/maintenance/cross-implementation support burden to dive into.

dangerousfreedom: excellent work!

BP+ almost around the corner to keep you busy :)

UkoeHB: Oh, really? I thought some people (Kayabanerve) said that Ristretto would be faster and more secure. It is not the case for Monero then?

not much faster, and only more robust not more secure (can get same security properties with careful design using plain ed25519(

looked deeper into pool pruning funkiness while reviewing 8076 and submitted 8415 to harden the pruning logic, looked into the deadlock of 8410 with not much luck yet unfortunately (putting it on the back-burner for now), and this one is fun: moving over to creating a new PR for 7760 to resolve merge conflicts + do a little style cleaning while I'm there (all credit still given perfect-daemon for the PR...)

there are maybe 20-40 lines of code that would be materially impacted by switching to ristretto, but like 2-4k lines of diff to switch probably

Rucknium[m]: Did you encounter anything really suprising while on this reading streak?

I had skimmed some of those papers before, so nothing eye-popping. Yes, I'd like to discuss them if there are no other pressing matters.

sure we can move on

3. discussion

Well, a small eye-pop. Egger et al. (2022)'s main result is based on two unproven conjectures. When I skimmed, I thought that it rested on on a fully-proven basis.

the unproven conjectures being?

Well, some bound on a probability. Basically, they say that there has not been enough attention paid to _finite_ graphs in the graph theory literature, so they make some conjectures and show that they hold with "reasonable" parameters.

Apparently there is plenty of graph theory on infinite graphs. But they base all results on a specific size of a "user" set. With Monero, the "user" set would be all output public keys

I also don't fully understand their definition of epsilon-security (Definition 3.4). If anyone is bored and wants a challenge, I invite them to figure out what it really means.

I can't figure out if it means probability of a _single_ deterministic de-anonymization, or some sort of average amount of reduction in the anonymity set of the "users".

Literally right now it reads as "probability of an algorithm". Probability that the algorithm does what, exactly?

But anyway, all three papers recommend a binning or partitioning decoy selection algorithms, with a single "bin". I was trying to understand their justification since I have some healthy skepticism of binning.

Ronge et al (2021) say that maybe a combined binning and mimicry DSA is a good idea, which is what Seraphis is doing at the moment. But they don't analyze that suggestion rigoriously.

The main practical problems with a single bin are:

1) It would ossify the 10-block lock (or X-block lock) since users would have to wait for some M set of outputs to be confirmed on the blockchain, since the output set would be "partitioned"

2) Targeted flooding or "black marble" attacks. If an adversary knew that a target user had broadcasted a tx at a specific time, then they could flood the mempool with theit=r own marked outputs at that specific time.

Mainly I think that these papers like partitioning since it is easy to analyze. Yu et al. (2019) says that determining the resistance of an arbitrary DSA to graph-based attacks is a `#P-complete` problem, which is believed to be even harder than a NP problem

Ronge et al. (2021) gives a lower bound of the privacy of a mimicking DSA. The bound is acceptable, I think. So mimicry is "fine".

yeah you always leak the timing of when your input was created with a single bin, seems like a no-go to me

Right. That, too. The papers sort of wave that away. Yu et al. (2019) explicitly says "assuming no timing info leaks any useful info".

Egger et al. (2022) gives us a specific number for how many ring members would be needed to be secure against graph-based attacks (with a given number of outputs), but in the case that we were using a partitioning DSA.

it's not a viable assumption for a generic privacy solution

how many do they say?

24 ring members I think. But of course that bound does not take into account EAE attack, for instance. So Seraphis should not stop at 24

The formula is on page 3, second column of moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=28

But that is based on two conjectures

Those conjectures are "probably true", IMHO. I do not have a lot of graph theory knowledge, though.

they say 'random directed graphs', but real graphs are not random (things like EAE, change output chains, repeat customers, etc.)

You can probably "squeeze" that away in their bounding by taking the DSA as sampling uniformly on the partitions.

They also usefully consider the anonymity reduction of flooding/black marble attacks.

They say (under their framework) that a beta proportion of black marbles will lead to a beta proportional reduction in anonimity.

So not exponential or multiplicative or anything, which is good.

Section 7.2 On Black Marble Attacks

hmm yeah that's useful context

ok, are there any other topics to cover during this meeting?

It would confirm some of our bak-of-the-envelope calculations on how severe flooding would have had to be in last year's flood incident to substantially reduce user privacy. That discussion also fed into the 11 -> 16 ring size hard fork change.

UkoeHB: Do you some good resources to understand Seraphis? Could you send me later?

know*

dangerousfreedom: there is mainly just the paper (a bit outdated) github.com/UkoeHB/Seraphis

at some point the monerokon video about balance recovery will come out (I hope), but the slides are here github.com/MoneroKon/meta/blob/main/slides/2022/talks.md

and of course the monerotopia video youtube.com/watch?v=XbMLK-aarKU

UkoeHB: This one I saw. Nice work!

So if l understand this correctly. Ballpark doubling the number of outputs via flooding would reduce the privacy by a factor of two

ArticMine: Yes, if Monero were using their one-bin/partitioning DSA. How their results map onto Monero's actual DSA is not clear. My intuition tells me that the result probably holds approximately. In other words, these graph-based (i.e. chain reaction or "cascading") attacks probably would have a proportional impact with our current DSA.

The overall purpose of these three papers is to put a bound on the potency of graph-based attacks on Monero and similar protocols.

This can be very helpful in tuning the growth of the short term median over the long term median in the scaling formulas

Especially with Seraphis

And ring size of 64 or higher

If anyone wants to see a recent empirical paper on the effectiveness of graph-baed attacks, see Vijayakumaran, S. 2021. Analysis of cryptonote transaction graphs using the dulmage-mendelsohn decomposition

"For pre-RingCT outputs in Monero, the DM decomposition technique performs better than existing techniques. For RingCT outputs in Monero, the DM decomposition technique has the same performance as existing techniques, with only five out of approximately 29 million outputs being identified as spent. "

"To study the effect of hard forks on Monero RingCT output traceability, we used information from four Monero hard forks. The DM decomposition technique is able to trace only 62,809 out of approximately 26 million RingCT transaction rings. Our results are further evidence supporting the claim that Monero RingCT transactions are mostly immune to traceability attacks. "

that's the end of the meeting, thanks for attending everyone

Thanks

If I understand things correctly, the DM decomposition is the most powerful known attack at this time, but those other three papers I mentioned are meant to put a bound on the potency of any graph-based attack, even attacks not yet discovered.

Interesting approach

Thanks

what was the relevance of hardforks, information leaked by the old chain continuing to be used?

same inputs used with different decoys on different forked chains