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

[Rucknium]

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:

1. Greetings

2. Discuss: How to confirm security of Monero's multisignature protocol? Do we need mathematical security proofs, and can we get them? Info:

• Brandon Goodell and Sarang Noether (2018) "Thring Signatures and their Applications to Spender-Ambiguous Digital Currencies"
• Monero multi-signature patch review by Inference
• Rust alternative implementation by @kayabaNerve

3. Discuss: Exploring Trustless zk-SNARKs for Monero's payment protocol. What are the bottlenecks for potential implementation?

4. Improvements to the decoy selection algorithm ( Decoy Selection Algorithm - Areas to Improve, Binning PoC, OSPEAD ) @j-berman @Rucknium

5. Seraphis. ( UkoeHB's Seraphis Proof of Concept work, Seraphis repo ).

6. 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

7. Any other business

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

#954

[plowsof]

Logs

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

< k​ayabanerve:matrix.org > 👋

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

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

< k​ayabanerve:matrix.org > 👋

< rbrunner > hello

< dukenukem > Hola.

< vtnerd > hi

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

< k​ayabanerve:matrix.org > I implemented GBPs into the FCMP repository. Variety of comments available from that.

< r​ucknium:monero.social > me: OSPEAD. Related, I am pretty sure that the late December 2023 increase in tx volume ( https://bitinfocharts.com/comparison/monero-transactions.html#3m ) was someone spending many outputs as quickly as possible. The ring member age distribution shifted to be much younger than usual. In other words, probably spam like July-Aug 2021.

< r​ucknium:monero.social > kayabanerve: You can save more time by explaining acronyms on first mention.

< vtnerd > me: working on block difficulty computation in the "chain hardening" mode in lws. Still not sure the mode is worth it because I don't plan on having 2+ daemons for point of reference like p2p has

< k​ayabanerve:matrix.org > The primary note is my impl is still ongoing. The circuit needs rearchitecture. The low level optimizations no longer still apply.

< k​ayabanerve:matrix.org > The next comment is it may yield 2-6x performance increases more than expected. I was hoping for 35ms a proof. It may be a small fraction of that.

< vtnerd > but basically Im trying to make sure the chain is valid with a certain level of difficulty, to make false chains from the daemon harder

< k​ayabanerve:matrix.org > GBPs = Generalized Bulletproofs

< k​ayabanerve:matrix.org > FCMPs = Full Chain Membership Proofs

< r​ucknium:monero.social > kayabanerve: Did you see this paper? https://eprint.iacr.org/2024/047 "On Efficient and Secure Compression Modes for Arithmetization-Oriented Hashing". Anything applicable?

< r​ucknium:monero.social > vtnerd: Similar to bitcoin SPV wallet?

< k​ayabanerve:matrix.org > Their abstract is wrong :C

< r​ucknium:monero.social > Not a good start

< k​ayabanerve:matrix.org > Just the claim Monero uses this.

< r​ucknium:monero.social > What makes GBP "generalized"? Why is ordinary BP a special case?

< vtnerd > yes, its likely similar. monero-lws is designed to run 24/7, so its got a better chance at detecting timestamp frauds

< k​ayabanerve:matrix.org > So we perform a Pedersen hash for free.

< k​ayabanerve:matrix.org > Technically, there's the overhead of the second proof needed for its output, and the blinding we need go transfer said values.

< k​ayabanerve:matrix.org > The unblinding is done in-circuit and is... 1.25 gates * 161 trits? 250 gates (which are R1CS constraints). I hope to get that to 1.

< k​ayabanerve:matrix.org > *200 gates.

< r​ucknium:monero.social > 3) Discussion. What do we want to discuss?

< k​ayabanerve:matrix.org > They're 258 constraints for their smallest space Rucknium. It's competitive, yet don't believe it'd be faster, even though it'd remove the overhead of the other proof.

< k​ayabanerve:matrix.org > (sorry if I went too far into the math there)

< r​ucknium:monero.social > ^ That's referring to the paper I posted?

< k​ayabanerve:matrix.org > *They're 231

< rbrunner > You wrote of a probable spam attack late December. How long did that last?

< rbrunner > (Maybe not an attack, but spam.)

< k​ayabanerve:matrix.org > Yeah. It uses ~15% more constraints. It would let us avoid a second proof, if we trust their hash function. That may be a fair trade off EXCEPT I'm planning to further reduce our constraints and we don't have our hash function take more time as the base does (they do. More elements hashed, more steps taken).

< r​ucknium:monero.social > rbrunner: About two weeks. Shorter than the July-Aug 2021, which was 6 weeks I think. https://bitinfocharts.com/comparison/monero-transactions.html#3m

< rbrunner > I see. And I was hoping people start to buy each other Christmas gifts with Monero en masse ...

< k​ayabanerve:matrix.org > So there's a bit of technical commentary which would need a full PoC to properly compare (2w-1m of work?). I don't think it'll end up more competitive and it has a fundamentally distinct security analysis.

< r​ucknium:monero.social > Here was our analysis of the 2021 incident: https://mitchellpkt.medium.com/fingerprinting-a-flood-forensic-statistical-analysis-of-the-mid-2021-monero-transaction-volume-a19cbf41ce60

< rbrunner > I wonder what a spam wave of only 2 weeks should be "good" for

< r​ucknium:monero.social > The tx volume chart has a similar shape, too. Spike to double the tx volume, then gradually decrease back to the usual tx volume.

< k​ayabanerve:matrix.org > Distinctly, I'd like to raise an idea to note, though I apologize for how I've already spoken quite a bit as I vocalized my analysis of that paper.

< k​ayabanerve:matrix.org > Class groups. They're an extremely weird niche of cryptography I used for a side project. I'm also half convinced they're the solution to everything.

< k​ayabanerve:matrix.org > We can trustlessly define a class group such that we can operate on arbitrary ECC elements, scalars or field elements, within an EC-like abstraction.

< k​ayabanerve:matrix.org > https://eprint.iacr.org/2022/419 is a constant sized, logarithmic verification time, ZK SNARK premised on them.

< dukenukem > rbrunner: as Rucknium said, the ring member age distribution shifted to be much younger than usual. Deanonymization in a targeted set of txs., or specific tx., maybe?

< k​ayabanerve:matrix.org > I'll make a research issue for it. No discussion is justified at this time. I just want to have people be aware of the term "class groups".

< r​ucknium:monero.social > Yes, the spam incident can be a black marble attempt, but just double the tx volume isn't going to help an adversary much.

< rbrunner > "solution to everything" meaning finding use in FCMPs as well?

< r​ucknium:monero.social > On a different topic: koe did Seraphis performance tests for tx verification ( monero-project/research-lab#91 (comment) ). But would things be different if storage I/O was part of the verification time? I assume that raising ring size to 128 from 16 would increase the storage I/O requirements because monerod would have to pull all those outp<clipped message

< r​ucknium:monero.social > ut public keys from the LMDB for each ring sig verification.

< r​ucknium:monero.social > RavFX 🤐 (RavFX) has brought this up.

< r​ucknium:monero.social > And how does Curve Trees compare in I/O requirements?

< k​ayabanerve:matrix.org > rbrunner: the fact there's a trustless, constant sized, logarithmic verification time SNARK means all proofs we want can be done. At worst, they'd just be horrible garbage with a million statements due to operating over non-native arithmetic.

< k​ayabanerve:matrix.org > Class groups do enable people to find subgroups of order of any prime. This was applied in CL15 for an encryption scheme as the discrete log problem is easy for their subgroups. I'm double checking now if native arithmetic was enabled within Dew, or if that's future research.

< k​ayabanerve:matrix.org > Even if Dew offers it, it won't beat a proper ECC construction, nor do I believe it'd beat a properly applied IVC construction. Class groups are ~2000 bits. Orders of magnitude slower, yet also with currently unique features.

< k​ayabanerve:matrix.org > If ECC is a round hole, and we ever have a square peg, we can hammer it in with class groups. That's the main comment at this time.

< r​ucknium:monero.social > Do you just have to get the Merkle root from the database?

< k​ayabanerve:matrix.org > They have O(1) storage complexity to verify proofs.

< k​ayabanerve:matrix.org > They just need the tree root. There's no random reads from disk.

< k​ayabanerve:matrix.org > We'd define said root as the root for 10 blocks ago, and once a block is 10 deep, update the tree with that block's new enotes. That does require ECC operations, and my PoC delayed said operations until all enotes were added to demonstrate a batch update.

< r​ucknium:monero.social > Maybe the Seraphis I/O performance can be tested once devs in #no-wallet-left-behind:monero.social have a Seraphis database.

< r​ucknium:monero.social > I mean Seraphis with 128+ rings

< k​ayabanerve:matrix.org > I also guess the tree edges, which are the elements updated, will be concise enough to fit into memory.

< rbrunner > Yeah, I don't see anybody building something like a simulation just for such a speed test. Testing can probably indeed start if we have a Seraphis testnet running.

< r​ucknium:monero.social > Anything more to discuss?

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

Automated by this