Monero Research Lab Meeting - Wed 01 May 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. Updates. What is everyone working on?

3. Potential measures against a black marble attack.

4. Research Pre-Seraphis Full-Chain Membership Proofs.

5. Any other business

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

995

[vtnerd]

Small nitpick, the date is may 1st (there is no April 31st).

[AaronFeickert]

Small nitpick, the date is may 1st (there is no April 31st).

"If you will it, Dude, it is no dream."

[Rucknium]

"Where we're going, we don't need calendars." Thanks. Fixed.

[Rucknium]

Logs:

< r​ucknium:monero.social > Meeting time! https://github.com/monero-project/meta/issues/999

< tevador > Hi

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

< o​ne-horse-wagon:monero.social > Hello!

_< s​gp:monero.social >__ hello

< rbrunner > hello

< a​aron:cypherstack.com > Hello!

< h​into:monero.social > hi

< b​oog900:monero.social > hi

< v​tnerd:monero.social > hi

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

< tevador > Me: Jamtis-RCT specs: https://gist.github.com/tevador/d3656a217c0177c160b9b6219d9ebb96 and FCMP++ reviews.

< j​effro256:monero.social > howdy

< j​effro256:monero.social > Me: (attempting) Reviewing FCMP-RCT and writing Seraphis integration code

< v​tnerd:monero.social > Worked primarily on debugging the p2p ssl code, and now hopefully finishing up the first cut at lws remote scanning

< r​ucknium:monero.social > me: Starting to collect logs from people who set_log net.p2p.msg:INFO in monerod for analysis of possible node origin of the black marble flood transactions. Working on optimal ring size and fee/byte in terms of cost effectiveness during a black marble flood.

< k​ayabanerve:matrix.org > I've been working on the FCMPs specification and implementation.

< 0​xfffc:monero.social > Hi everyone

< u​ntraceable:monero.social > Hi

< 0​xfffc:monero.social > Me: did start working on performance suite and investigating ways to find bottleneck for rwlock. ( In parallel, I submit minor/simple PRs here and there ). Starting today I am full-time on Monero.

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

< r​ucknium:monero.social > If anyone has more comments about reasonable parameters for evaluating the cost effectiveness of raising ring size and/or increasing fee/byte to defeat black marble flooding ( https://github.com/monero-project/meta/issues/995#issuecomment-2077014407 ) , please tell me.

< r​ucknium:monero.social > If anyone was collecting net.p2p.msg:INFO log data for black marble flood analysis, especially during April 12, 13, and 15, please DM me for submission instructions.

< r​ucknium:monero.social > I evaluated the possibility of getting an analytical solution to the nonlinear optimization problem with inequality constraints by checking the Karush-Kuhn-Tucker conditions. IMHO, it is not worth the time to do that, but if someone has another opinion, please let me know. I already have a good, simple, numerical solution algorithm.

< r​ucknium:monero.social > The benefit of having an analytical solution is that we would have more information about the "deep" meaning of the optimization problem, could carry out comparative statics, etc.

< j​effro256:monero.social > Which optimization problem?

< r​ucknium:monero.social > I noticed there was more discussion on the GitHub issue about a network/node-based PoW requirement to send transactions. I won't be evaluating that idea since it would take a long time to consider all the complexity. I will evaluate a simple tx-PoW requirement to have a tx confirmed on the blockchain.

< r​ucknium:monero.social > jeffro256: Finding the best cost effectiveness in terms of user fee and node storage requirements for effective ring size when black marble flooding is occurring

< r​ucknium:monero.social > The objective function is cost/effective_ring_size. You want to minimize that by choosing ring size and fee/byte.

< r​ucknium:monero.social > More comments on potential measures against a black marble attack?

< r​ucknium:monero.social > The numerical solution is a simple grid search basically. It makes nice contour plots :)

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

< r​ucknium:monero.social > Aaron Feickert: You have updates on the Generalized Bulletproofs security proof progress

< a​aron:cypherstack.com > testing

< a​aron:cypherstack.com > Are these messages going through?

< a​aron:cypherstack.com > My Element client is acting funky

< r​ucknium:monero.social > the "testing" message went through

< u​ntraceable:monero.social > Yes

< rbrunner > I see them

< r​ucknium:monero.social > and the two after that

< a​aron:cypherstack.com > OK, sorry about that

< a​aron:cypherstack.com > Yes, I have an update!

< a​aron:cypherstack.com > Cypher Stack has been reviewing the Generalized Bulletproofs design required for Curve Trees to work

< a​aron:cypherstack.com > We're about halfway through, and identified a minor issue

< k​ayabanerve:matrix.org > https://libera.monerologs.net/monero-research-lab/20240501 Aaron Feickert ;)

< a​aron:cypherstack.com > The issue is that the proving relation informally described by the authors doesn't quite work with the soundness proof

< a​aron:cypherstack.com > A solution is to modify how vector commitments are represented in the relation, which technically means they can use more generators

< a​aron:cypherstack.com > Modifying that, and updating the proofs accordingly, fixes things

< a​aron:cypherstack.com > But

< a​aron:cypherstack.com > This change comes with a free benefit

< a​aron:cypherstack.com > Because the commitments can use additional generators, we can add constraint matrices to the design, which could allow for more efficient proofs

< a​aron:cypherstack.com > Adding these matrices is straightforward, and everything works fine even if you chose not to use them (just set them to zero and the algebra still works as expected)

< a​aron:cypherstack.com > I spoke with kayabanerve to confirm (a) that the original fix (which changes commitment generators) doesn't introduce any issues with Curve Trees, and (b) that the matrix addition could be helpful

< r​ucknium:monero.social > Is this size-efficient proofs or verification-time-efficient or both?

< a​aron:cypherstack.com > Mostly size

< a​aron:cypherstack.com > But could also be time (I haven't run the numbers on that portion)

< r​ucknium:monero.social > So probably no worse performance on time than the original design?

< a​aron:cypherstack.com > Nope, and totally optional to use

< a​aron:cypherstack.com > Adding the matrices also has minimal impact on the complexity of the security analysis

< a​aron:cypherstack.com > (above the changes already required for the initial design fix)

< r​ucknium:monero.social > The summary is that the original design appears to not work, but an adjustment to the design will probably work and will be even more size efficient. Your next move it to try to write a security proof for the adjusted design. Does this fit within the allocated labor time and funds?

< a​aron:cypherstack.com > Anyway, this is all detailed in the report

< a​aron:cypherstack.com > To be clear, it's only the original design's (informal) proving relation, which could be problematic for other uses that might require certain generators

< a​aron:cypherstack.com > The initial adjustment absolutely works, and the matrix addition is just being finalized and integrated easily into the existing security proof work already done and in progress

< a​aron:cypherstack.com > We expect no change to the timeline

< r​ucknium:monero.social > Fantastic. Thank you!

< a​aron:cypherstack.com > Like I said, the matrix change is very straightforward to include

< r​ucknium:monero.social > "Anyway, this is all detailed in the report". Is this an internal draft or does it exist publicly?

< k​ayabanerve:matrix.org > The decreased size usage does avoid increased verification time. If we have a set bandwidth target, we can either increase verification time OR increase bandwidth efficiency.

< a​aron:cypherstack.com > Oh, I should have said that it's included in the report as I'm writing it, and will therefore be included in the final report

< r​ucknium:monero.social > What does "bandwidth" mean?

< tevador > tx size

< a​aron:cypherstack.com > The effect of the matrix change is to double the number of vector commitment constraints for a given number of vector commitments included in a proof

< a​aron:cypherstack.com > without a size increase

< a​aron:cypherstack.com > (there are some subtleties though)

< a​aron:cypherstack.com > But barring anything unexpected, we expect that the report will provide a satisfactory security proof for the modified construction

< k​ayabanerve:matrix.org > More data in less bytes Rucknium

< a​aron:cypherstack.com > (and which reduces to the "original" GBP design trivially if desired/needed)

< a​aron:cypherstack.com > Heck, it might end up being useful enough to warrant submission to a conference /shrug

< a​aron:cypherstack.com > I'd have to see if the original author(s) would be interested in such a thing, but that's for another day

< r​ucknium:monero.social > Do kayabaNerve and tevador want to give updates on FCMP++?

* m-relay <a​aron:cypherstack.com> quietly exits

< tevador > Did anyone have time to review Jamtis-RCT?

< j​effro256:monero.social > I've only skimmed it so far

< k​ayabanerve:matrix.org > I need a few minutes to fully comment, sorry.

< k​ayabanerve:matrix.org > *before I can fully comment.

< tevador > We also discussed how to handle torsioned points in FCMPs and we came back to Ristretto, which was discussed here some time ago. Specifically, if we adopted Ristretto for point serialization, it could save a lot fo headache.

< rbrunner > Maybe while we wait I can throw in a quick question

< k​ayabanerve:matrix.org > I have yet to review JAMTIS RingCT but I'm extremely interested in the claim it mitigated Janus for existing addresses (except for main <-> subaddress relations).

< k​ayabanerve:matrix.org > It means new address become about functionality, not privacy (barring that one remaining edge case)

< rbrunner > Are Bulletproofs++ more or less "off the table" after that quite mixed result of the review, and the move to FCMPs with GBP?

< k​ayabanerve:matrix.org > I'd shelve BP++ for now, which were never explicitly posited for FCMPs.

< j​effro256:monero.social > What operations are involved in Ristretto decompressing, and is it faster than (mul x8) ? I saw tevador and kayabanerve have a little back and forth about that. [TBH i don't really care about tx builder side performance within reason]

< tevador > Yes, it should be faster than mul8, pending benchmarks.

< tevador > It avoids at least 1 field inversion and 6 point doublings per output.

< k​ayabanerve:matrix.org > I have Python which is less than 100 lines for Ristretto.

< a​aron:cypherstack.com > Plus the Ristretto serialization is intended as a thin wrapper around existing Edwards operations

< k​ayabanerve:matrix.org > Yep

< k​ayabanerve:matrix.org > The specification has incorporated feedback. I won't claim it's complete, as I want to implement the math behind the gadgets and ensure a lack of typos in that manner, but I don't expect major changes.

< j​effro256:monero.social > Who would we get to review the divisors? I

< k​ayabanerve:matrix.org > I've started cleaning up the prior code ('productionizing it'), fixing edge cases and bugs, and making it something I'd endorse auditing.

< r​ucknium:monero.social > jeffro256: Don't we have to prove the security of the divisors and then review the proofs?

< k​ayabanerve:matrix.org > On divisors, I've already solicited two quotes/statements of work.

< k​ayabanerve:matrix.org > Divisors come with a correctness proof. Arguably, we need it reviewed and an audit a literal protocol aligns with its mathematics.

< k​ayabanerve:matrix.org > We don't need a ZK proof, solely a soundness proof, as we execute it in a ZK context. The section on correctness covers what we'd call soundness.

< k​ayabanerve:matrix.org > And then the literal protocol, my draft proposal in the LaTeX I published, would be literally implemented (secure hash functions and so on) and audited.

< k​ayabanerve:matrix.org > Also, Rucknium, clarifying: one of the reasons I've been a bit annoying on not formally proving all of this, and instead solely auditing, is as vast sections of the math is primitive.

< k​ayabanerve:matrix.org > I probably have a page of latex which reduces to a - b = 0; a - b + b = 0 + b; a = b and similar

< j​effro256:monero.social > How "modular" is the application of divisors? Can we review the soundness of an isolated Prove/Verify divisor "algorithm", which then guarantees all uses under certain conditions is sound? Or do just have to have a full contextual working protocol before we can audit our implementation/use of divisors within that protocol?

< k​ayabanerve:matrix.org > (the first being the check, the last line being the statement, the intemediary being the proof)

< k​ayabanerve:matrix.org > But moving forward, the plan is to review/audit the divisor proof (review the theory which has a section on correction, audit our literal instantiation and impl), and formally verify said primitive math.

< k​ayabanerve:matrix.org > I've reviewed tooling and one of the entities I solicited a quote from is explicitly experienced with formally verifying circuits.

< k​ayabanerve:matrix.org > jeffro256: They're a concept. I wrote a 'gadget' which assumes a challenge function with proper transcripting (trivial to instantiate with GBPs). The gadget is then a black box.

< k​ayabanerve:matrix.org > Specifically, the gadget says there's some unreliable representation of a discrete logarithm which is usable to prove X = x G, for a public G, AND if x is reused, x1 = x2, where 1, 2 are the instance of use. The unreliability of the representation does not make it unreliable on reuse within a proof.

< k​ayabanerve:matrix.org > It's a whole thing, it's documented

< k​ayabanerve:matrix.org > Eagen's work does describe divisor construction, evaluation, and the challenge evaluation. We'd argue our gadget follows it.

< k​ayabanerve:matrix.org > Once I confirm the lack of notational issues, we'd have the spec within the LaTeX audited.

< k​ayabanerve:matrix.org > Later, we'd audit the impl to match the spec.

< k​ayabanerve:matrix.org > I'll also note my work has been proceeding at a much quicker rate than I would've expected. I'm wondering if that time will be saved OR paid for on the back end (there's always something that still needs to be done)

< k​ayabanerve:matrix.org > I've also been discussing with jberman about them starting their work on integration and topics such as FFI'ing, and what exactly is exposed over FFI (and what helpers provided)

< k​ayabanerve:matrix.org > The tree has been the main discussion.

< r​ucknium:monero.social > FFI = Foreign Function Interface?

< k​ayabanerve:monero.social > Also, performance if research holds is looking to be quite favorable and only with minor overhead to a variant using Seraphis's linking tag definition

< k​ayabanerve:monero.social > Yes re: FFI

< k​ayabanerve:matrix.org > In summary, moving ahead in all aspects, and progress is going well.

< r​ucknium:monero.social > More comments? Other topics?

< r​ucknium:monero.social > We can end the meeting here. Thank you all!

< j​effro256:monero.social > Thank you everyone! Thanks Aaron Feickert ! Fascinating stuff