Monero Research Lab Meeting - Wed 18 October 2023, 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: Reducing 10 block lock: Investigate possibility of reducing 10-blocks lock research-lab#102 (comment)

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:

#908

[plowsof]

Logs

< Rucknium > Meeting time! #910

< Rucknium > 1) Greetings

< rbrunner > Hello

< v​tnerd:monero.social > Hi

< j​effro256:monero.social > Howdy

< Rucknium > 2) Updates. What is everyone working on?

< j​effro256:monero.social > I put a PR out to modify decoy selection monero-project/monero#9023

< Rucknium > me: Reported nonstandard fee privacy issue to Exodus. They fixed it in the Desktop wallet. Mobile fix still being worked on: https://www.reddit.com/r/Monero/comments/176e1zr/privacy_advisory_exodus_desktop_users_update_to/ . Reviewing jeffro256's guide to wallet2's decoy selection algorithm and converting it to math formulas.

< j​effro256:monero.social > How did you initially find out that it was Exodus with the nonstandard fees?

< j​effro256:monero.social > B/c they're close source, right?

< j​effro256:monero.social > Was it wrong enough that you could just see it just by eyeballing it?

< Rucknium > I suspected it was exodus since they released their first working Monero version after the August 2022 hard fork at about the same date that the txs with the specific fee values started to appear.

< Rucknium > Then I sent some transactions with the wallet.

< Rucknium > I think they just had the wrong tx size. The UI showed tx size about 12 Kb for 1in/2out. If you used that incorrect size to calculate fees, then it would have used 20 nanoneros per byte, which is the standard minimum fee.

< j​effro256:monero.social > Oh okay nice

< v​tnerd:monero.social > Me: mostly subaddressses, but also answering questions for someone doing a 10k account stress test on LWS.

< v​tnerd:monero.social > LWS will be enterprise ready in the not distant future it looks like

< j​effro256:monero.social > That's awesome to hear !

< j​effro256:monero.social > So the stress test went well?

< j​effro256:monero.social > also btw @vtnerd did you have questions about monero-project/monero#9023? I saw you commented on it the other day. Also, I have to apologize for sidelining my review of the serialization read interface; it's next on my list

< v​tnerd:monero.social > No, it failed lol. But they didn't know if was the frontend or backend yet. But we'll find out over the next month or so, and have it fixed

< v​tnerd:monero.social > Worse case it's in some LWS<->monerod interaction

< Rucknium > 3) Discussion. What do we want to discuss?

< o​frnxmr:monero.social > ```

< o​frnxmr:monero.social > any follow up questions/issues for CypherStack regarding the new scope for the bp++ peer review? : https://repo.getmonero.org/monero-project/ccs-proposals/-/merge_requests/413/diffs

< o​frnxmr:monero.social > ```

< o​frnxmr:monero.social > from plowsof

< rbrunner > Do I get it that this is waiting for word from Core?

< o​frnxmr:monero.social > From mrl

< rbrunner > Ah, you mean about the modified scope

< o​frnxmr:monero.social > Yes sir

< rbrunner > Not about the financing

< o​frnxmr:monero.social > Right

< rbrunner > In this case I am on the same side as you: No clue, not being a cryptographer ...

< Rucknium > As a non-cryptographer, the scope changes sound fine to me, except I don't know how important "Optimized binary range proofs" is. Is that a major part of what BP++ uses to get space and verification time savings?

< plowsof > ive also shared feedback from zksecurity with koe/jberman - exploratory work on seraphis papers. $10k/week for 2 months (80k) - "deliverables" hard to define but they are open to discussion / setting up a scope of work

< Rucknium > Doing a quick search in the paper: "However, while this motivating example provides an intuition for why a norm relation can be preferable over an inner product relation, it turns out that in practice, it is almost always more efficient to use a BP++ reciprocal range proof instead of a BP++ binary range proof."

< Rucknium > So would Monero use a BP++ reciprocal range proof?

< Rucknium > "For most ranges, the reciprocal range proof is substantially more efficient for the prover and the verifier than a binary range proof. However for some small ranges with B − A < 28, a binary range proof can be more efficient."

< Rucknium > "28" should be 2^8

< Rucknium > kayabaNerve, would Monero use a binary range proof or a reciprocal range proof? Is it OK that the security proof of the binary range proof for BP++ won't be reviewed by CypherStack?

< Rucknium > I plotted the number of transactions that fit the Exodus Desktop fee pattern for the last 8 weeks: https://github.com/Rucknium/misc-research/blob/main/Monero-Nonstandard-Fees/images/Exodus-txs-after-fix-release.png

< Rucknium > The fixed Exodus Desktop wallet version was released on October 10. A week later, txs with the Exodus fee have been cut by about 50%. From 600 per day to 300 per day.

< rbrunner > Probably getting better of time. Funny how the number of transactions vary predictably over the week. Monday is especially busy, it seems :)

< rbrunner > *over time

< Rucknium > 1. This is pretty conclusive evidence that it was Exodus Desktop wallets creating those transactions. 2. This is the first statistical analysis on the amount of time it takes for users to update their Monero wallets. Obviously, users of other wallets would update at a different pace.

< j​effro256:monero.social > Does the exodus desktop app auto-update ?

< Rucknium > The lower tx volume for Saturday-Sunday in the Exodus plot is similar to the tx volume for the whole blockchain.

< Rucknium > I think the update behavior depends on OS. Different for Windows/Mac/Linux

< Rucknium > Exodus releases a new version every two weeks on a schedule.

< Rucknium > If wallet2 is updated, there are two steps: 1) Wallet developers who use wallet2 update to the new wallet2 code. 2) Users update their wallets.

< Rucknium > Users who use the GUI or CLI wallet would update "directly" to wallet2

< Rucknium > Anything else to discuss?

< j​effro256:monero.social > That CCS is to review the paper only right?

< j​effro256:monero.social > (This is my first time looking at the CCS)

< Rucknium > Yes. It is to review the paper's mathematics.

< j​effro256:monero.social > vtnerd, you've already done play implementations of bp++ yeah?

< j​effro256:monero.social > vtnerd, you've already done PoC implementations of bp++ yeah?

< j​effro256:monero.social > I wonder if we should leave out batch verification from the scope ....

< v​tnerd:monero.social > no it was unfinished unfortunately, I didn't know how to do the last part. I was hoping the newer paper would clarify some things. Or I could just do a port from the secp code

< Rucknium > The CCS proposal is supposed to review what exists in the paper, not create new mathematics. Doing batch verification would require new mathematics I think.

< j​effro256:monero.social > > To improve verifier performance, the BP

< j​effro256:monero.social > paper suggests a few optimizations, such as using a single multi-exponentiation, batch verification, and an

< j​effro256:monero.social > efficient method to compute scalars. The first two optimizations can be directly translated to BP++, but

< j​effro256:monero.social > the method to compute scalars has to be slightly adapted from BP’s inner product argument to BP++’s

< j​effro256:monero.social > norm linear argument. All three optimizations have been implemented in the benchmarked code.

< j​effro256:monero.social > It seems that there is an analagous, already-implemented way to do batch verification in bp++

< j​effro256:monero.social > Even if not explicitly mentioned how in the paper

< j​effro256:monero.social > Does Cypherstack do code reviews as well or just maths?

< Rucknium > They have done code reviews before.

< Rucknium > Maybe the question is "does BP++ batch verification have a security proof?"

< Rucknium > Does the original BP paper have a security proof for batch verification?

< v​tnerd:monero.social > I dont recall any, but I wasn't looking for it either

< j​effro256:monero.social > is the newer paper the one that is linked here ? https://eprint.iacr.org/archive/2022/510/20230717:163509

< j​effro256:monero.social > Or is that the older one ?

< j​effro256:monero.social > There's been one revision on this entry

< Rucknium > That's the latest version on the IACR website: https://eprint.iacr.org/archive/versions/2022/510

< Rucknium > We will end the meeting here. Discussions on the BP++ review CCS can continue.

< j​effro256:monero.social > Looking thru the BP paper, there's no security proof per se, but a rather simple algebraic argument

< j​effro256:monero.social > If that really can be extended as easily to BP++, then it may not put much burden on the reviewers as compared to verifiying everything else

< j​effro256:monero.social > To be more precise, someone could formally write down the analogous argument for why batch verification is the same algebraically, with "high probability", as verifying each individually, and then we could increase the scope from the paper to the paper plus the batch verification argument

< j​effro256:monero.social > I wish the original authors of the paper had expanded upon that in the paper, or else cited the previous work in that case, but I can't be too picky

< k​ayabanerve:matrix.org > Rucknium @Rucknium:monero.social: the reciprocal range proof, I believe, letting us skip the binary range proof proof so long as it isn't the basis of the reciprocal proof's proof.

< k​ayabanerve:matrix.org > Batch verification is trivial.

< k​ayabanerve:matrix.org > For any protocol which defines it's verification as group element G1 == G2, redefinition to G1 - G2 == 0 is possible.

< k​ayabanerve:matrix.org > Batch verification is just, for a list of G1 and G2s, selecting random scalars to weight the G1s and G2s so they can't mingle.

< k​ayabanerve:matrix.org > The performance benefit is that you don't have G1/G2. You have terms summing to them. Multi-scalar multiplications produce summed results far faster than individual components can be calculated.

< Rucknium > That sounds like "The revised BP++ review scope is OK"

Automated by this