Monero Research Lab Meeting - Wed 08 May 2024, 17:00 UTC

Logs:

< rucknium:monero.social > Meeting time! https://github.com/monero-project/meta/issues/1003

< chaser:monero.social > hello

< rucknium:monero.social > 1) Greetings

< aaron:cypherstack.com > Hello!

< jberman > waves

< tevador > Hi

< one-horse-wagon:monero.social > Hello.

< vtnerd:monero.social > Hi

< 0xfffc:monero.social > hi everyone

< rucknium:monero.social > 2) Updates. What is everyone working on?

< tevador > FCMP related work. I did an analysis of Ristretto and we had some discussions with kayabaNerve how to simplify the tree hashing.

< jberman > me: started FCMP integration (initial task is working on the tree in C++ = table design, code flow, and tests). The async scanner PR (faster scanning) was also merged into ukoe's Seraphis lib, going to start making bite-sized PR's to monero core over the next week in preparation. Also opened a new CCS

< rucknium:monero.social > me: Working on the fee/ring size tradeoff to deter or defeat black marble flooding. And started working on using the Dulmage-Mendelsohn decomposition to analyze black marble flooding combined with "chain reaction analysis" from Section 4 "Chain reaction graph attacks" of https://github.com/Rucknium/misc-research/blob/main/Monero-Black-Marble-Flood/pdf/monero-black-marble-flood.pdf

< vtnerd:monero.social > Me: Lws-remote-scanning still. Expect to be finished this week, unless I hit another snag

< kayabanerve:monero.social > As I said in NWLB, I worked extensively on FCMPs. The spec has been iterated with feedback, the GGBP updates made, and two auditors plan to submit SoW within two weeks. I meet a third today and have also distinctly discussed work with CS.

< 0xfffc:monero.social > Me: Wasted a lot of time last week. I am submitting minor PRs here and there. But overall my main task is performance benchmarking suite and then fixing the locking bottleneck we have.

< rucknium:monero.social > 3) Potential measures against a black marble attack https://github.com/monero-project/research-lab/issues/119

< rucknium:monero.social > For the fee/ring size tradeoff, I am computing these metrics for the most cost-effective fee/ringsize response to a specific adversary budget:

< rucknium:monero.social > Adversary budget, nominal ring size, fee/byte, effective ring size when flooded by adversary's budget, user's cost for 2in/2out tx, user's tx size for 2in/2out tx, average block size (no flooding), Block size (continuous flooding), one year of blockchain growth (each combination of unpruned/pruned and no flooding/continuous flooding).

< rucknium:monero.social > Any other metrics I should compute?

< tevador > tx verification time

< jeffro256:monero.social > Howdy

< rucknium:monero.social > How can we get that? Have a private testnet with a specific modified ring size and do benchmarks?

< chaser:monero.social > Rucknium I think that's doable without any networking element

< kayabanerve:monero.social > Sorry, for a brief reminder, what's the ring size 40 verification time?

< tevador > CLSAG benchmarks probably can be done without a private testnet

< rucknium:monero.social > Verification time in practice and in theory may be different.

< tevador > I think the seraphis github issue had some benchmarks

< kayabanerve:monero.social > Yes and no. There's the unchanging verification time, and then the prep time.

< rucknium:monero.social > If we just want to do theoretical verification time, I am ok with that, too. There is time to read the data from storage, too.

< kayabanerve:monero.social > It's probably best to simulate the prep time off the mainnet DB?

< tevador > https://github.com/monero-project/research-lab/issues/91

< kayabanerve:monero.social > (So no actual testnet, just a DB)

< chaser:monero.social > tevador: that's quite a killer reference hardware koe used there

< rucknium:monero.social > Tell a monero wallet to construct a K ring member tx from the mainnet database and then verify it? Ok. But probably it is better for someone else to code that since that's definitely not my comparative advantage.

< rucknium:monero.social > IMHO the March suspected spam showed that monerod has hidden bottlenecks, so actual performance can be different from theoretical.

< kayabanerve:monero.social > Grootle is 17ms no batching for 128. CLSAG is 24ms for 40?

< tevador > https://github.com/monero-project/monero/blob/master/tests/performance_tests/sig_clsag.h

< rucknium:monero.social > Ok. I will use koe's CLSAG benchmarks for now. If a C++ programmer wants to run more realistic benchmarks, that would be wonderful.

< rucknium:monero.social > I started testing with a Rust implementation of the Dulmage-Mendelsohn decomposition released with this paper: Vijayakumaran (2023) "Analysis of Cryptonote transaction graphs using the Dulmage-Mendelsohn decomposition." https://moneroresearch.info/index.php?action=resource_RESOURCEVIEW_CORE&id=39

< rucknium:monero.social > I am having some problems with the tests, but I don't know if it is a problem with the data I am submitting to the algorithm or if the algorithm is just slow (it is single-threaded for now).

< rucknium:monero.social > That's all I have on this agenda item. Anything else on this item?

< chaser:monero.social > kayabanerve the benchmarks in koes's Seraphis paper are very close to 24 ms for a no-batch CLSAG 40

< chaser:monero.social > https://raw.githubusercontent.com/UkoeHB/Seraphis/master/seraphis/Seraphis-0-0-18.pdf#page=18

< rucknium:monero.social > 4) Generalized Bulletproofs Security Proofs https://github.com/cypherstack/generalized-bulletproofs/releases/tag/final Aaron Feickert

< aaron:cypherstack.com > Yes!

< aaron:cypherstack.com > kayabanerve identified an issue with the generalization in the report

< aaron:cypherstack.com > It had to do with cross-terms in inner products

< aaron:cypherstack.com > A fix was identified that works, but isn't as efficient as we'd hoped with the original idea

< aaron:cypherstack.com > The report has been updated to reflect this; I reissued the tag so existing links point to the right one (but the full git history is there)

< aaron:cypherstack.com > Kudos to kayabanerve for the find

< kayabanerve:monero.social > Clarifying, the additional functionality isn't as efficient.

< tevador > What is the performance impact?

< kayabanerve:monero.social > The originally expected functionality is maintained for all intents and purposes.

< aaron:cypherstack.com > Right

< kayabanerve:monero.social > We went from a

< kayabanerve:monero.social > 2 + 2(c//2) poly

< kayabanerve:monero.social > To a

< kayabanerve:monero.social > 2 * (1 + c) poly

< kayabanerve:monero.social > Yet we can halve the amount of needed c.

< jberman > (rucknum : if you want complete end-to-end daemon testing with a larger ring size, then this PR is a good reference for what needs to change on the C++ side for the daemon to allow larger ring sizes if you get someone available to do that https://github.com/monero-project/monero/pull/8178/files)

< kayabanerve:monero.social > Except for branches which demand a full c to themselves.

< rucknium:monero.social > jberman: Thanks. I remembered when you worked on the August 2022 hard fork you said that the ring size 11 -> 16 increase was not as simple as changing a few numbers in the code.

< kayabanerve:monero.social > We can preserve the original formula without the new features. The new formula and new functionality is overall more efficient.

< tevador > So everything is going according to the plan or better.

< kayabanerve:monero.social > For GGBPs? Yes

< tevador > I think we can move on to general FCMP discussion.

< rucknium:monero.social > 5) Research Pre-Seraphis Full-Chain Membership Proofs. https://www.getmonero.org/2024/04/27/fcmps.html

< tevador > An interesting find was that Ristretto doesn't actually help us to remove torsion completely. So we decided to go with the simpler solution of mul8.

< kayabanerve:monero.social > The spec, gadgets, layers, and circuit are done. There's some cleanup I want to do on the top-level FCMP code and I need to support aggregate input proofs (which is multiple calls to the circuit).

< kayabanerve:monero.social > Performance is extremely hard to benchmark. I said I could not do a production grade lib and would only do one sufficient for working with.

< tevador > Also the membership proof was simplified to proving that (+/-K,+/-I,+/-C) is in the tree. So we ignore the signs. This allows us to remove the complexity of "permissible points".

< rucknium:monero.social > Possible downside of torsion is that someone can write a Monero tx construction implementation that has a torsioned tx that the consensus verification would consider valid, but it would be fingerprintable, right? Like the strange txs that dangerousfreedom found?

< tevador > A side effect is that people will be able to "spend" -C, so effectively burn funds. But we don't see any issues with that.

< kayabanerve:monero.social > I had the goal of 35ms in a batch of 10, the prior estimate. We are now clocking as low as 35ms for one and 10ms in a batch of 10. I hope a new Helios/Selene impl would get us ~2x further.

< kayabanerve:monero.social > Rucknium: FCMPs torsion clears everything.

< rucknium:monero.social > tevador: is it possible that a mathematics reviewer or a code auditor would see issues with that?

< tevador > It should be reviewed during the audit, but I can't imagine what the problem would be.

< kayabanerve:monero.social > To be clear, that does not preventing outputs with torsion. It just limits the torsion to that and that alone.

< kayabanerve:monero.social > The more notable change of what tevador is discussing is the redefinition of key images from the point L to just the x coordinate.

< tevador > re: torsion. Using Ristretto without torsion clearing actually reduces the anonymity set to 1/4 of the chain (all keys with the same torsion as the masked key).

< tevador > So we need torsion clearing.

< tevador > Yes, we are redefining key images by dropping the sign bit. Should be safe.

< kayabanerve:monero.social > And Ristretto offers less torsion clearing (2 steps not 3), but that's not worth it.

< tevador > I think there will be a migration of the key images table during the update. That's the most efficient solution.

< rucknium:monero.social > The table in LMDB?

< tevador > Yes.

< rucknium:monero.social > jeffro256: Any comments on this LMDB key images table migration? ^

< kayabanerve:monero.social > It halves the amount of spendable outputs.

< kayabanerve:monero.social > It means we need to ensure our address protocol can not only output uniqur keys yet keys with unique abs values.

< kayabanerve:monero.social > We either need a LMDB migration OR to double our reads (one for +, one for -).

< kayabanerve:monero.social > We may already need a migration. Are key images global or per pool?

< jberman > what pool are you referring to there?

< kayabanerve:monero.social > Amount

< tevador > Global

< jberman > ^global

< kayabanerve:monero.social > Historical outputs are denominated.

< kayabanerve:monero.social > Great, then we can either do 2x reads or a migration.

< jberman > migration is fine

< tevador > Btw, the migration of key images is effectively a soft fork. It makes double spend validation stricter.

< kayabanerve:monero.social > It's justifications are on the gist, but it removes a minor DoS vector re: permissibility.

< kayabanerve:monero.social > Crafted points could very feasibly trigger hundreds (thousands?) of additions on accumulation.

< tevador > And it removes a lot of complexity from the specs and the implementation.

< rucknium:monero.social > Monero hard forks are usually also soft forks, right? AFAIK, the definition of the two types of forks is that a hard fork allows new txs that used to be not valid and a soft fork prohibits types of txs that used to be valid.

< tevador > Soft fork makes some previously valid transactions invalid, but previously valid remain valid.

< kayabanerve:monero.social > Monero hard forks are hard.

< jberman > handling compatibility between old nodes <> updated nodes before fork height sounds a bit tricky, but fine. sounds like we may have to keep the old table around up until the fork height

< kayabanerve:monero.social > The addition of BP+ wouldn't be accepted by old nodes so BP+ was a HF.

< kayabanerve:monero.social > Same with view tags, as we didn't use TX extra.

< tevador > Correction: newly valid are also previously valid

< jberman > or at least, nodes would need to keep key images around that don't pass the stricter height up until the fork height

< jberman > stricter check*

< tevador > Only if we expect someone to spend both KI and -KI. Otherwise both give the same result.

< tevador > and producing both KI and -KI as valid key images implies solving the DLP

< kayabanerve:monero.social > Due to the existence of the usage of a Htp tbc.

< kayabanerve:monero.social > If we had a constant generator for key images, that would not be the case.

< kayabanerve:monero.social > But since we use a hash to point, key images are binding to all components of the output key.

< tevador > For example, when we fixed the octuple spending bug, we do the same check also for key images before the fix.

< tevador > So we don't need to keep the less strict rule for old outputs. That was my point.

< jberman > ok I follow, migration sounds fairly straightforward

< tevador > Anyways, all this is just a performance optimization. AFAICS the math checks out.

< kayabanerve:monero.social > In total, FCMP++s have had a lot of work done on development, have hit performance goals without the proper curve impls, and are moving steadily ahead on research.

< jberman > integration moving full steam ahead as well

< rucknium:monero.social > Fantastic. Any other business?

< syntheticbird:monero.social > In the current trajectory, should we expect full public release in 1.5 years as planned ?

< jberman > integration I think is still complete-able within 6 months fwiw

< rucknium:monero.social > We can end the meeting here. Thanks everyone.

< chaser:monero.social > any retrospective thoughts on the May 3 consolidation flood, when we had a ~8 hour constant stream of 150/2's (https://i.opnxng.com/r/Monero/comments/1ci9l7g/in_todays_flood_attack_on_the_network/)? is there any indication that it's related to the March flood? are there any potential privacy implications or new insights into DDoS vectors? it still troubles me how this caused major

< chaser:monero.social > disruption to some nodes.

< nioCat > there is another consolidation event today and the backlog is presently being cleared

< chaser:monero.social > nice catch. it's interesting that it's around the same of the week.

< alex:agoradesk.com > The consolidation flood really affects nodes a lot. Feels like a DoS vector.

< alex:agoradesk.com > Moreso than the tx flood aka black marble attack.

monero-project / meta

Monero Research Lab Meeting - Wed 08 May 2024, 17:00 UTC #1003

999