Monero Research Lab Meeting - Wed 22 January 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. Some preliminary results from OSPEAD research into improved decoy selection algorithm.

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

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:

#1142

[chaserene]

date-agnostic alternative time zone calculator (works regardless of daylight saving time shifts):
https://www.timeanddate.com/worldclock/meeting.html?p1=1440

[Rucknium]

Logs

< r​ucknium:monero.social > MRL meeting in this room in two hours.

< s​yntheticbird:monero.social > The legend once said that it was meeting time...

< rbrunner > Indeed

< s​yntheticbird:monero.social > 1. Greetings (unofficial)

< j​berman:monero.social > waves

< rbrunner > Here :)

< s​yntheticbird:monero.social > hello

< a​rticmine:monero.social > Hello

< c​haser:monero.social > hello

< s​yntheticbird:monero.social > 2. Updates. What is everyone working on?

< b​oog900:monero.social > ping Rucknium

< s​yntheticbird:monero.social > Rucknium:

< j​effro256:monero.social > Howdu

< s​yntheticbird:monero.social > I propose if rucknium isn't there at :10 we run a wheel to decide who is moderator

< 0​xfffc:monero.social > Hi everyone. I am off. But I will be reading the meeting silently.

< j​effro256:monero.social > Me: PR reviews and improving the Carrot library flow

< c​haser:monero.social > SyntheticBird: you've already assumed that role :)

< s​yntheticbird:monero.social > alright if you insist chaser * proceed to act shy *

< a​rticmine:monero.social > I have been working on scaling algorithm for FCMP. The consensus part is done. I am working on the fee part

< a​rticmine:monero.social > Reviewing the BCH scaling algorithm.

< a​rticmine:monero.social > I am also reading Highjacking Bitcoin. Many assumptions there on both sides

< j​berman:monero.social > me: updated the FCMP++ WIP PR with the latest (includes wallet sync, improved tree build time, and a demo of calling prove/verify over the FFI. latest builds passing with tobtoht's help): monero-project/monero#9436

< s​yntheticbird:monero.social > 3. Prize contest to optimize some FCMP cryptography code.

< s​yntheticbird:monero.social > jberman:

< s​yntheticbird:monero.social > (tell me if im switching too quickly)

< j​berman:monero.social > good pace to me :)

< j​berman:monero.social > A list of tasks todo for the contest:

< j​berman:monero.social > 1) Write a test suite for the competition

< j​berman:monero.social > 2) Finalize contest specs/details

< j​berman:monero.social > 3) Decision on where to host the competition

< j​berman:monero.social > 4) How to accept submissions? (private or public)

< j​berman:monero.social > 5) Decision on how to raise funds

< j​berman:monero.social > 6) Who to get involved to judge the final submissions

< j​berman:monero.social > 7) Decide on timeline/dates

< j​berman:monero.social > 8) Plan to attract talent

< j​berman:monero.social > Starting with 1, I'm happy to take a stab at this and will try to have a test suite ready by next MRL meeting (unless any takers want to give it a go)

< j​berman:monero.social > I figure we can discuss some of these details today, like 3/4/5

< j​berman:monero.social > On where to host the contest, could be as simple as a github repo, or create a new website. The latter would take more effort but would be nice to have in attracting talent. Here was a comparable contest site kayaba linked in a past meeting: https://www.zprize.io/

< rbrunner > Regarding 3): Maybe it's not glorious at all, but for exchanging info, progress reports, a simple GitHub issue could do

< rbrunner > Why a whole repo? So people can submit their code there?

< j​berman:monero.social > Ya, the repo could host the test suite as well, it would be clear how to submit code to win the contest by cloning the repo

< rbrunner > Alright

< j​berman:monero.social > ah I should also link kayabanerve 's exisitng draft repo for the contest: https://github.com/kayabaNerve/fcmp-plus-plus-optimization-competition/tree/main

< j​berman:monero.social > Can start from there

< j​effro256:monero.social > As for 4, if we're using something like a Github repo, we need to make sure that as the contestants are pushing code, that they can't see the others' code, so we prevent plagiarism

< s​yntheticbird:monero.social > Re 3): a website would only possible if people are available to make it (i'm not sorry), would need to ask at monero-website.

< s​yntheticbird:monero.social > Re 4): Allowing anonymous submission is always preferable.

< plowsof > having the code private - but confirmed test results public would prevent someone from running the attempt through an LLM and submitting a slightly different variation under an alias to claim any runner up prizes

< s​yntheticbird:monero.social > Re 5): CCS as always?

< plowsof > although the people who submit attempts could still do that :)

< j​berman:monero.social > ya, the runner up part seems tricky since it leaves room for gaming

< j​berman:monero.social > private submissions could be a patch to the repo submitted privately to an email

< rbrunner > A website for 3) would be cool, but well, we can't even move our "New GetMonero.org" forward, so ...

< j​berman:monero.social > anon submissions definitely should be allowed imo too

< j​berman:monero.social > repo sounds fine to me

< Rucknium > Hi! Sorry. Had unexpected problems.

< rbrunner > I think "making noise" in the right circles for the contest could be much more important than some nice website

< s​yntheticbird:monero.social > Hi Rucknium, we were at 3.

< j​berman:monero.social > anyone against a repo?

< a​rticmine:monero.social > Sounds to me like a reasonable approach

< s​yntheticbird:monero.social > same

< j​berman:monero.social > great

< j​berman:monero.social > anyone against private submissions via patch via email, feel free to speak up :)

< rbrunner > GitHub doesn't offer something there? Private repos that you can open for select persons?

< rbrunner > Maybe even if, too complicated

< j​berman:monero.social > so contestants fork the repo, keep their fork private and share with judge(s)

< j​berman:monero.social > seems reasonable. either would work

< j​berman:monero.social > on the decision to raise funds, there is also the general fund which ofrnxmr has voiced reasoning to utilize in the past. figure it's worth discussion compared to a CCS

< rbrunner > Hmm, maybe a CCS could already be a part of "making noise"

< s​yntheticbird:monero.social > If Core is willing to give GF should be better.

< s​yntheticbird:monero.social > rbrunner not sure, people external to monero may not care about CCS.

< rbrunner > Do we already have an idea of the sum that we might offer?

< s​yntheticbird:monero.social > it will just be a "Look we're crowdfunding our super context"

< s​yntheticbird:monero.social > contest*

< s​yntheticbird:monero.social > From the repo:

< s​yntheticbird:monero.social > > The best submission for an optimized helioselene will be awarded 50 XMR. The second best submissions will be awarded 25 XMR.

< s​yntheticbird:monero.social > > The best solution for an optimized ec-divisors will be awarded 150 XMR. The second best submission will be awarded 75 XMR.

< rbrunner > That's a bit at the low end if you ask me ... If I compare how much we paid for specialist time for reviews and audits

< j​effro256:monero.social > Agreed

< rbrunner > Although it's always sooo easy to spend other peoples' money :)

< s​yntheticbird:monero.social > i'm sure general fund will do just fine

< j​berman:monero.social > How about 500 XMR for ec divisors 1st place (close to $100k), 200 XMR for helioselene 1st place? kayaba likely has greatest context into amount of work it might take for participants, so this is a bit stabbing in the dark. But it's also a fairly important element we very much so want to see optimized

< j​berman:monero.social > also, 2nd place getting half is definitely a lot when 2nd place could potentially be gamed by 1 participant with anon submissions

< rbrunner > If the GF can fund that, why not.

< c​haser:monero.social > if needed, I'm sure a CCS could fill in a funding gap. last year's CCS's proved that the community is more than willing to fund efforts to make FCMP++ succeed. we even had a private actor step up and fund research outside the CCS.

< j​berman:monero.social > it seems there is some rough support to request the GF to fund (or help fund) the contest as well. we can let that marinate until next week

< s​yntheticbird:monero.social > Perfect

< j​effro256:monero.social > How much XMR is estimated to be left over from the FCMP++ research fund?

< s​yntheticbird:monero.social > 4. Some preliminary results from OSPEAD research into improved decoy selection algorithm.

< s​yntheticbird:monero.social > Rucknium

< Rucknium > Attack success = correctly guessing the real spend in the ring.

< Rucknium > Recall that the theoretical minimum attack success through completely random guessing would be 1/16 = 6.25%

< Rucknium > According to my estimates, an adversary could take advantage of the divergence between the real spend age distribution and the status quo decoy distribution to achieve an attack success probability of 23.5%, on average, since the August 2022 hard fork. This corresponds to an effective ring size of 4.2

< Rucknium > With a new improved, fitted decoy distribution, we can get that probability down to 7.6 percent, corresponding to an effective ring size of 13.2

< Rucknium > What is the relevance of this after FCMP activation? There will be a backup method to construct FCMP txs that requests the FCMP Merkle tree paths as a set of decoys from a (potentially spying) remote node. So this distribution can be used for that.

< Rucknium > I will probably publicly release all OSPEAD-related documents and code around February 20.

< Rucknium > At least one thing that I could use wider feedback on is how quickly do we think the ecosystem implemented the off-by-one patch. I tried to measure it statistically, but I got unsatisfactory results because the difference between the patched and unpatched distributions is so small.

< Rucknium > However, it is important to get it right since it affects the real spend estimate of the youngest spendable block, which is probably the most common block to spend from.

< Rucknium > Right now I just assume a linear trend from the date of release of the patch to the end of the dataset (now October 2024), assuming 75% adoption by the end.

< c​haser:monero.social > 4.2? damn. is that attack viable today? and what does such an attack take to execute?

< Rucknium > Yes, continues to be viable. Some weeks it would be even more efefctive, some weeks less. Depends on what the real spend age distribution is each week.

< Rucknium > To execute the attack you need an estimate of the real spend age distribution

< a​rticmine:monero.social > There is also the possibility of combining this with clustering algorithms

< c​haser:monero.social > alright, but how does an adversary arrive at a good estimate of the real spend age distribution?

< Rucknium > The larger the divergence between the real spend age distribution and the decoy distribution, the higher the attack success probability.

< s​yntheticbird:monero.social > jeffro256: according to CCS repo there is 1537 XMR left

< s​yntheticbird:monero.social > (continue on ospead)

< Rucknium > Through the techniques I developed in the OSPEAD research

< c​haser:monero.social > Artic: feel free to expand on clustering algorithms

< a​rticmine:monero.social > The best example is the leaked Chainalysis video

< Rucknium > This is why the estimate of the real spenddistribution is a double-edged sword. It would allow you to set a better decoy distribution, but it also allows an adversary to attack user privacy.

< Rucknium > The attack sucess estimate I quoted is about single-ring attack effectiveness. When a tx has multiple rings, the correlations between them can be leveraged.

< c​haser:monero.social > Rucknium: I see. and this potential attack will become publicly viable, retroactively, when OSPEAD is published, right?

< j​berman:monero.social > "according to CCS repo there is 1537 XMR left" -> working on an estimate for how much we expect to be leftover after all tasks completed

< Rucknium > There's a paper on MoneroResearch.info by Borggren about the inter-ring correlations.

< Rucknium > chaser: yes

< a​rticmine:monero.social > The co spend heuristic was used to overcome ring signatures of 16. The cluster has to be larger than the effective ring size. If one lowers the effective ring size to say 5 then the cluster size needed is much lower

< Rucknium > In fact it would not be difficult for me to write a bit of code to try to guess the real spend in all rings since August 2022

< rbrunner > What's the importance of the August 2022 hardfork? Just the start date of your investigation? Or something "wrong" since only that?

< Rucknium > Just the start date

< Rucknium > that jberman implemented

< Rucknium > No good reason to go back further than that, but you could

< Rucknium > It took about two weeks of computation time to do the two years of data

< Rucknium > On a 64 thread machine

< rbrunner > Hmm, wouldn't several decoy selection algorithms in use make things more difficult for an adversary?

< Rucknium > And that's after I sped up one of the main steps by 240x compared to the original implementation :D

< j​effro256:monero.social > Perhaps going back further, when ring size was small, would help the more recent results, since one could eliminate very old decoys from new rings when the spend is known-ish?

< Rucknium > rbrunner: exactly. 70% of my R&D was spend on solving the problem with multiple decoy selection algorithms being used in the wild.

< a​rticmine:monero.social > It has to be ideally statistically indistinguishable from the actual spend distribution

< Rucknium > Spending very old outputs is very rare, though

< j​effro256:monero.social > Fair

< a​rticmine:monero.social > The output selection algorithm.

< c​haser:monero.social > 4.2 is very bad, IMHO. a severe reduction in the effective privacy of ringCT transactions. this could be way less for the 2024 March suspected spam period.

< s​yntheticbird:monero.social > have more than 2 outputs and you are screwed

< a​rticmine:monero.social > I have to leave for another meeting. Will review the discussion late.

< Rucknium > Sorry it took this long, but MRL decided that a new decoy selection algorithm probably could not safely be deployed without a hard fork, so other near-term priorities were put ahead of the research frequently

< s​yntheticbird:monero.social > waves

< s​yntheticbird:monero.social > Rucknium: ack.

< rbrunner > I think we got it pretty right with priorities. E.g. looking at the spam wave more or less in real time was indeed important.

< s​yntheticbird:monero.social > We're near over the hour, last topic

< s​yntheticbird:monero.social > 5. Research on Autonomous System (AS) peer connection rules to reduce spy node risk.

< Rucknium > Like I said in the previous meeting, any devs or resaerchers that want to see the report before Feb 20 can DM me for a copy.

< Rucknium > I read four papers on Tor's resistance to traffic correlations at the AS level

< Rucknium > Since we're at the hour, I'll discuss them next meeting I think

< c​haser:monero.social > rbrunner: I agree.

< rbrunner > Sounds reasonable.

< Rucknium > My plan now is to figure out the cost structure that an adversary would encounter if they wanted to defeat an AS diversity rule by leasing IP addresses.

< rbrunner > Also something like a double-edged sword :) You do the budgeting for the adversaries :)

< Rucknium > Basically, is there a big discount from leasing many IP addresses from a single AS, compared to leasing many IPs from many ASes

< b​oog900:monero.social > FWIW I have been running my tool to find proxies and they are still running nodes on the banned IPs

< s​yntheticbird:monero.social > Probably because many don't have the ban list

< Rucknium > Thanks for the update, boog

< b​oog900:monero.social > "running nodes"

< s​yntheticbird:monero.social > """make it so that we can communicate with a node""" * wink * * wink *

< s​yntheticbird:monero.social > Alright is there anything someone wish to add ?

< Rucknium > Recently I emailed Fanti, the lead author of the Dandelion++ paper, asking her option on the Clover paper (D++ alternative) and countermeasures to node proxies. I'll share info when I have it.

< s​yntheticbird:monero.social > ack. thx for the efforts Rucknium

< s​yntheticbird:monero.social > We can end meeting there. Thanks everyone.

< Rucknium > Thanks for stepping in, syntheticbird :)

< s​yntheticbird:monero.social > np it boost my ego

< s​needlewoods:monero.social > you did a good job SyntheticBird, thanks everyone

< j​berman:monero.social > thanks all

< j​berman:monero.social > a comment Rucknium : the DSA would also be useful for the jamtis-RCT light wallet tier (so light wallets wouldn't need to download all elems necessary to re-build the tree), which imo should still be on the roadmap

< Rucknium > Good point :)

< j​berman:monero.social > Estimating 200 XMR for remaining EC divisors work, 50-200 XMR for gadgets formal verification (hand wave guess from other tasks), and 6 audits of varying complexity hand-waved at 50-200 XMR each also (perhaps more if we want multiple rounds). That's a pretty large range that could feasibly use the remaining fund of 1537 XMR. Seems unlikely that would occur and we'll likely end up

< j​berman:monero.social > with funds leftover, but I figure it makes sense to keep the XMR from the research fund reserved for the work drafted out in the CCS and not re-purpose it

< r​ottenwheel:unredacted.org > Rucknium: but this is not happening anymore because of forthcoming FCMP++ and CARROT network upgrade, correct?

< 3​21bob321:monero.social > ^