Monero Research Lab Meeting - Wed 05 February 2025, 17:00 UTC

[Rucknium]

Location: Libera.chat, #monero-research-lab | Matrix

Time: 17:00 UTC Check in your timezone

Main discussion topics:

1. Greetings

2. Updates. What is everyone working on?

3. Prize contest to optimize some FCMP cryptography code.

4. Research on Autonomous System (AS) peer connection rules to reduce spy node risk.

5. Reliability of MRL technical note 0010.

6. Any other business

7. 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: Rucknium

Previous meeting agenda/logs:

#1148

[Rucknium]

Logs

< r​ucknium:monero.social > Meeting time! #1152

< r​ucknium:monero.social > 1) Greetings

< rbrunner > Hello

< c​haser:monero.social > hello

< j​berman:monero.social > waves

< v​tnerd:monero.social > hi

< s​yntheticbird:monero.social > hello

< r​ucknium:monero.social > 2) Updates. What is everyone working on?

< v​tnerd:monero.social > testing/fixing some timeout stuff in the epee tcp server

< r​ucknium:monero.social > me: I achieved a 15x speedup in some short but time-consuming portion of OSPEAD R code by re-writing it in Rust. Also working on analyzing a subnet de-duplication algorithm for selecting peer nodes to reduce the effectiveness of spy nodes.

< j​berman:monero.social > me: made significant progress on plugging FCMP++ into consensus and testing the full flow of tx construction -> node validates the tx. I have one core piece remaining to get it working locally (the balance check i.e. sum of inputs == sum of outputs), then touching up remains

< r​ucknium:monero.social > 3) Prize contest to optimize some FCMP cryptography code.

< j​berman:monero.social > We discussed the FCMP++ optimization contest in the NWLB group on Monday. I proposed an idea to re-scope the contest to a wider scope, and kayabanerve provided solid reasoning to NACK that idea

< j​berman:monero.social > I direct anyone following along to check that group for that proposal/discussion

< j​effro256:monero.social > Howdy, sorry I'm late

< j​effro256:monero.social > Me: Carrot integration. Today I'm working on FCMP++-ready input selection and plugging that into `wallet2

< r​ucknium:monero.social > #no-wallet-left-behind:monero.social is the room

< j​berman:monero.social > The next step on my end (still) is a test suite. To implement tests correctly, I need to profile the respective functions used in prove/verify/tree building, to make sure the benchmark tests in the contest capture exactly what we want to optimize

< s​yntheticbird:monero.social > sounds tiresome, what about a contest for the best test suite

< j​berman:monero.social > Apologies I've put off on my deliverables for the contest. I've been focusing more time and effort on the FCMP++ integration work

< v​tnerd:monero.social > you might want to publish what machine this will be verified on too

< r​ucknium:monero.social > I've read a little about Rust's single instruction, multiple data (SIMD) capability. Will SIMD be prohibited, since it could rely on CPU instructions sets that are not universal?

< j​berman:monero.social > I think it's a sound goal for the contest to have a generally applicable lib that doesn't have major speed-ups on one target machine versus another

< s​yntheticbird:monero.social > so contest is really aiming at algorithmic optimization rather code optimization

< s​yntheticbird:monero.social > rather than*

< rbrunner > That's a very good way to put it IMHO

< rbrunner > At least as the first approximation that sounds like a good explanation of the goal to me

< j​berman:monero.social > seems like a fair way to put it

< s​yntheticbird:monero.social > * release dopamine *

< rbrunner > After better algorithms you could still go on and optimize the code implementing them, of course

< s​yntheticbird:monero.social > rbrunner sounds good to me

< s​yntheticbird:monero.social > portability is the requirement for code optimization

< s​yntheticbird:monero.social > algorithmic is up to participant brains

< s​yntheticbird:monero.social > ah no i think jberman said there is some constraints on computed tables

< rbrunner > Yeah, that was one of the contentious points in the discussion. Allow C? Allow assembler? Allow unsafe Rust? For how much of a speedup? And so on

< rbrunner > Contestants could come up with a surprising number of things that are a bit problematic without a good contest description

< s​yntheticbird:monero.social > ofc. kinda excited to see what people are gonna submit

< r​ucknium:monero.social > Ok. More discussion on this? We can have more discussion when the tests get written.

< j​berman:monero.social > nothing from me

< r​ucknium:monero.social > 4) Research on Autonomous System (AS) peer connection rules to reduce spy node risk. monero-project/monero#7935

< s​yntheticbird:monero.social > also available as PR on cuprate side btw: Cuprate/cuprate#339

< r​ucknium:monero.social > I am analyzing an alternative peer selection algorithm. Instead of randomly choosing from candidate list of nodes that may be populated by many spy nodes on a few saturated /24 subnets (254 possible IP addresses in each /24 subnet), first de-duplicate the candidate list at the /16 subnet level (which are strict supersets of the /24 subnets) and then randomly choose a peer from t<clipped message

< r​ucknium:monero.social > he de-duplicated list.

< r​ucknium:monero.social > I did a network scan using boog900's tool and coded some simulations. My preliminary results say that the de-duplication algorithm brings the share of connections to spy nodes down to only 2 percent, compared to about 30 percent for the status quo method.

< r​ucknium:monero.social > Sounds great, but two potential downsides/side effects: 1) A spy node adversary can change their strategy to leasing subnet-distinct IP addresses instead of leasing whole subnets and 2) honest nodes in "popular" subnets would get fewer inbound connections and honest nodes in "lonely" subnets would get more inbound connections.

< r​ucknium:monero.social > (2) is a little hard to analyze because we need data on the number of nodes with closed inbound ports, which boog's tool would not be able to count. I'll cover that another time.

< r​ucknium:monero.social > On (1), honest Monero nodes are not perfectly dispersed across subnets. They are a little concentrated in subnets of VPS providers. Therefore, it might be possible that an adversary could turn the tables by only leasing subnet-distinct IP addresses instead of leasing whole subnets in bulk. Whether it is better for an adversary to try to turn the tables depends on the price premium<clipped message

< r​ucknium:monero.social > on leasing subnet-distinct IP addresses compared to bulk subnet leasing.

< r​ucknium:monero.social > I wrote a simple economic model and found the following:

< r​ucknium:monero.social > Let h_s be the total number of honest nodes that accept inbound connections, including nodes in the same /16 subnet.

< r​ucknium:monero.social > Let h_d be the number of distinct /16 subnets with at least one honest node that accepts inbound connections.

< r​ucknium:monero.social > Let w_s be the price per IP address when leasing whole /24 subnets at a time. (If the price to lease a subnet per month is 150 USD, then the price per IP address is 150/254 = 0.59 USD.)

< r​ucknium:monero.social > Let w_d be the price to lease one distinct IP address that is not in the same /16 subnet as other distinct IP addresses.

< r​ucknium:monero.social > According to my preliminary model, an adversary would try to "turn the tables" if w_d / w_s < h_d / h_s

< r​ucknium:monero.social > This is "nice" because the condition does not depend on the budget's adversary (which would have to be guessed), nor even on the absolute prices. Just the relative price. h_d and h_s can be estimated with a quick network scan, although of course it could change over time.

< r​ucknium:monero.social > What I see now is h_d / h_s = 1.36, based on current network data. That means that an adversary would try to turn the tables if the price premium on subnet-distinct IP addresses was 36% or less, compared to leasing subnets in bulk. IMHO, probably the price premium is higher than that, but I will do more investigation of that. Therefore, it is likely that a subnet de-duplicated a<clipped message

< r​ucknium:monero.social > lgorithm to select peers would reduce the effectiveness of spy nodes. According to preliminary results, of course.

< r​ucknium:monero.social > Thoughts on this research and the alternative peer selection algorithm?

< s​yntheticbird:monero.social > thoughts? good job.

< r​ucknium:monero.social > Ah, already saw a transcription error. The condition should be about h_s / h_d, not h_d / h_s

< rbrunner > Not sure I am on a good path of thought here, but wouldn't our better algorithm lead to very different incentives for the adversary?

< rbrunner > Say, in extreme, they have two choices, have their spy nodes more or less useless, or spend more money?

< r​ucknium:monero.social > rbrunner: Yes, exactly. I am analyzing at which point the incentives create conditions so that it is actually better to stay in the status quo peer selection algorithm.

< rbrunner > To buy addresses that make their nodes effective again, because dispersed in the IP space

< r​ucknium:monero.social > Since the adversary can react

< rbrunner > Ah, I see!

< s​yntheticbird:monero.social > on the verge of having monerod fetch the real time price of IP to change its peer selection algorithm dynamically

< r​ucknium:monero.social > According to my mode, the adversary's total budget does not affect whether one peer selection algorithm is better than the other

< r​ucknium:monero.social > model*

< j​effro256:monero.social > Here h_s and h_d are using the unit of /16 subnets, whereas w_s and w_d are using the unit of /24 subnets. Is this intended?

< r​ucknium:monero.social > According to a recent network scan, h_s = 2572 and h_d = 1895. These are honest nodes with open ports, not all honest nodes. So ether are 2572 total honest nodes with open ports, dispersed across 1895 /16 subnets

< r​ucknium:monero.social > Yes. In practice, the LinkingLion adversary is leasing /24 subnets.

< rbrunner > Do I understand correctly that the final intended outcome of this investigation is an advice whether now we should switch the algorithm, or stay put?

< s​yntheticbird:monero.social > rbrunner yes

< rbrunner > Alright, looking forward to this, very interesting

< r​ucknium:monero.social > An adversary can lease larger subnet chunks, but the bulk discount about /24 doesn't really get much better as you increase the subnet size. Some example: https://www.logicweb.com/bulk-ip-address-leasing/

< rbrunner > If I think that this all only takes place in IP4 space whereas the whole world should use IP6 for a long time already ...

< rbrunner > That would probably result in a different game, right? IP6

< r​ucknium:monero.social > For laypeople: confusingly, a /23 subnet is larger than a /24 subnet. A /24 subnet has 254 usable ip addresses and a /16 one has about 256^2 IP addresses.

< r​ucknium:monero.social > Yes, basically this anti-Sybil measure only works in the IPv4 protocol since IPv4 costs money since it's scarce (only about 4 billion total IPv4 addresses for the whole planet).

< r​ucknium:monero.social > AFAIK, Monero nodes have IPv6 is disabled by default to try to reduce the Sybil risk from IPv6

< rbrunner > Maybe a fresh look at the situation there that includies massive spying in the IP4 space would shift the arguments for that?

< r​ucknium:monero.social > The little economic model includes a simple game theory model where the two players each have two possible strategies to deploy. I am proving the Nash equilibrium.

< rbrunner > Slowly it must become a shame anyway that we are almost totally absent in IP6, no?

< s​yntheticbird:monero.social > to be fair ipv6 is part of these years open issues

< rbrunner > Maybe we can motivate vtnerd to look at this in some way :)

< r​ucknium:monero.social > I think enabling IPv6 by default would increase Sybil resistance only if (1) we care only about the current known adversary (i.e. LinkingLion) and (2) LinkingLion doesn't try to Sybil attack on IPv6 because it is just getting to spy on the Monero network as a "freebie" because it actually cares most about Bitcoin.

< r​ucknium:monero.social > These spy IP addresses were first noticed on the BTC network.

< s​yntheticbird:monero.social > spying on monero as a "freebie" => for a freebie they put substantial efforts into their proxy software

< r​ucknium:monero.social > By the way, the tidy w_d / w_s < h_s / h_d hold when we simplify the probability problem into draw-with-replacement (actually, we draw without replacement because you don't connect to the same node twice) and monerod already doesn't connect to a node in a /16 that it already has connected to (but it doesn't now do the de-duplication step).

< r​ucknium:monero.social > But the realistic case can be checked with simple Monte Carlo simulations

< d​oedl...:zano.org > rucknium: thats great news (30%->2%). Does game theory account for a sleepy, lazy opponent, too, who perceives a threat to Fiat as a whole (eventually) ?

< r​ucknium:monero.social > No. I don't know how the opponent's payoff functions would change if they are like that, if at all.

< j​effro256:monero.social > I'm thinking about how the deduplication would actually work in code. Do we only keep around one IP per /24 subnet ? If so, which one do we choose ? A spy node that is smart might actively try to be the first one to reach out to all the nodes to effectively blacklist the others on its /24 subnet. Or are you saying that we store all IP addresses, but treat them as one pickable obje<clipped messag

< j​effro256:monero.social > ct when doing peer selection?

< j​effro256:monero.social > IIRC there is a relatively low limit (or there used to be) on the number of peers stored in p2pstate.bin. We might want to increase that as long as we have asymptotically efficient peer selection algorithms

< r​ucknium:monero.social > jeffro256: The whitelist and graylist and their limits (1000 and 5000, respective, IIRC), complicate things a little. I have ignored that complication for now

< r​ucknium:monero.social > I would keep the lists as-is. Then do the de-duplication each time you select a new peer. You would have an ephemeral candidate list each time you activate the peer selection function.

< j​effro256:monero.social > If we're keeping all IP addresses, which is probably a good idea, we should expand the limits on that list IMO

< r​ucknium:monero.social > Of course, we could simulate the more complicated, realistic code.

< r​ucknium:monero.social > Or, deploy Shadow on the new 1TB RAM machine, with the two peer selection code versions :D

< r​ucknium:monero.social > Deploying shadow isn't a very serious suggestion in the short term since it would take time to figure out how to get it to work with monerod

< c​haser:monero.social > what is Shadow?

< r​ucknium:monero.social > But if we do want to get shadow set up, I have been thinking that we could hire the person who wrote ethshadow instead of trying to learn it from scratch

< r​ucknium:monero.social > chaser: A realistic network emulator that runs real application code, originally designed for Tor

< s​yntheticbird:monero.social > chaser: A userspace network syscall intercepter. Permit to simulate internet level networking on a program without the program actually communicating on the internet. It's extremely efficient and performant

< r​ucknium:monero.social > SyntheticBird: Have you looked into Shadow independently?

< s​yntheticbird:monero.social > Briefly, the promise really excite me

< d​oedl...:zano.org > would the use of the important whitelist be disabled for the first simulatios?

< r​ucknium:monero.social > My current basic simulations with R don't use the limited whitelist concept. It just assume that all nodes with open ports are on each node's "whitelist".

< d​oedl...:zano.org > i would rather drop dynamic peer discovery for first atempts and precalc static lists.

< r​ucknium:monero.social > For more info about how the whitelist/graylist work, see page 4 of https://eprint.iacr.org/2019/411.pdf It may be out of date

< r​ucknium:monero.social > 5) Reliability of MRL technical note 0010. https://www.getmonero.org/resources/research-lab/pubs/MRL-0010.pdf

< d​oedl...:zano.org > tx, will have a look

< r​ucknium:monero.social > In a Serai room, kayabanerve said that MRL-0010 is "unsound". When I asked if it should be retracted he said, "I don't remember if it's been updated in any way and don't care to argue for its retraction, just caution with it."

< r​ucknium:monero.social > Does anyone know anything about this?

< r​ucknium:monero.social > By the way, retracted doesn't mean it would be deleted from getmonero.org . Just that a note would be added saying that some major part of the paper is incorrect.

< c​haser:monero.social > no, other than being on the list of topics last week, totally news to me.

< r​ucknium:monero.social > I have a long-term goal in my mind of making the MRL technical notes more "research official" by getting DOIs (document object identifiers) assigned to them. That costs some money, though.

< c​haser:monero.social > in case thin unsoundness induced a vulnerability, which parts of Monero would be affected?

< r​ucknium:monero.social > I guess DOI means digital object identifier, not document object identifier.

< c​haser:monero.social > *this

< d​oedl...:zano.org > what happend to university contacts?

< r​ucknium:monero.social > I don't think MRL-0010 was used in Monero's protocol. I could be wrong.

< r​ucknium:monero.social > Contacts are ongoing

< r​ucknium:monero.social > Ok, well if someone knows something about MRL-0010, please bring it up after the meeting

< r​ucknium:monero.social > We'll end the meeting here.

< o​frnxmr:monero.social > Thanks ruck

< s​yntheticbird:monero.social > Thanks

< k​ayabanerve:matrix.org > MRL-0010 isn't used in Monero, a derivative of it used by some Monero atomic swap protocols.

< k​ayabanerve:matrix.org > This was discussed in MRL years ago if someone wants to search the archive for "PlasmaPower".

< k​ayabanerve:matrix.org > Having redownloaded the PDF, yes, it's unsound.

< k​ayabanerve:matrix.org > > Given this, we wish to prove that, given only the values xG′ and xH′ (and other proof

< k​ayabanerve:matrix.org > elements as needed), the discrete logarithm of each is a representation of the same integer. In particular, we

< k​ayabanerve:matrix.org > do not wish to reveal x to the verifier

< k​ayabanerve:matrix.org > The issue is the proof doesn't output xG', xH' yet xG'yG xH'zH

< k​ayabanerve:matrix.org > The discrete logarithm of the former over G' is not necessarily an equivalent integer to the discrete logarithm of the latter over H'

< k​ayabanerve:matrix.org > You need the two Schnorr PoKs well discussed since.

< a​ck-j:matrix.org > Sorry I missed the meeting. I looked into hosting platforms and Kaggle seems like a no-go unfortunately. The competition would need to have a machine learning component according to their requirements, which it doesn’t.

< a​ck-j:matrix.org > There isn’t any platforms specifically designed for what we are looking for but the closest I’ve found is HackerEarth, HackerRank, CodeChef, Codeforces

< c​haser:monero.social > kayaba: thank you. Element can't search for usernames, and I managed to find the message only from my matrix[dot]org account, but here it is. (Monerologs doesn't cover the period either). 2020-10-11 23:48 UTC:

< c​haser:monero.social > https://matrix.to/#/!toFcRZtpaiwiyapgVO:matrix.org/$4GGbCkt2TzVfujUW4Et2XhenNhTr0LidCw79NvoFbGE?via=matrix.org&via=monero.social&via=unredacted.org

< r​ucknium:monero.social > Thanks chaser. The freenode logger has it: https://freenode.monerologs.net/monero-research-lab/20201011

< c​haser:monero.social > (my link to the message doesn't work from a monero[dot]social account either...)

< d​oedl...:zano.org > rucknium: "2) honest nodes in "popular" subnets would get fewer inbound connections and honest nodes in "lonely" subnets would get more inbound connections."

< d​oedl...:zano.org > optimistically, given the data in https://eprint.iacr.org/2019/411.pdf this^ could have a net positive effect on resiliance imo.

< r​ucknium:monero.social > There are good things and bad things about it. You would have greater "decentralization" since there would be fewer connections to the centralized VPS providers. But 1) Honest node operators who run nodes on VPSes would have fewer connections, which means they would get txs and blocks with a little more latency. Of course, they could compensate for that by manually raising their n<clipped message

< r​ucknium:monero.social > umber of outbound connections.

< r​ucknium:monero.social > 2) Nodes that are alone in their subnets would have more connections, which may stretch their resources because the number of incoming connections is unlimited by default. During the tx spam last year, some node operators reduced their incoming connections. Hopefully, the bandwidth and CPU resources of connections will decrease when the proposed new tx relay process is implemented and deployed

< r​ucknium:monero.social > which is here: monero-project/monero#9334

< d​oedl...:zano.org > exactely. the network is complex enough, so that trial&error would be a scientific approach. the PR looks very helpful in this regard!