15:02:59 MRL meeting in this room in two hours. 15:22:09 I can provide an update on the Generalized Bulletproofs security review 15:27:16 Aaron Feickert: Thank you. I will put you at the beginning of the "Research Pre-Seraphis Full-Chain Membership Proofs" agenda item. 16:16:03 Thanks Aaron! 16:17:12 It's actually a pretty interesting update, so stay tuned :D 17:00:21 👋 17:01:14 Meeting time! https://github.com/monero-project/meta/issues/999 17:01:19 Hi 17:01:23 1) Greetings 17:01:27 Hello! 17:01:29 hello 17:01:31 hello 17:01:31 Hello! 17:02:27 hi 17:02:35 hi 17:03:02 hi 17:04:08 2) Updates. What is everyone working on? 17:04:34 Me: Jamtis-RCT specs: https://gist.github.com/tevador/d3656a217c0177c160b9b6219d9ebb96 and FCMP++ reviews. 17:04:38 howdy 17:05:15 Me: (attempting) Reviewing FCMP-RCT and writing Seraphis integration code 17:05:48 Worked primarily on debugging the p2p ssl code, and now hopefully finishing up the first cut at lws remote scanning 17:06:02 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. 17:07:38 I've been working on the FCMPs specification and implementation. 17:08:23 <0​xfffc:monero.social> Hi everyone 17:08:32 Hi 17:10:32 <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. 17:12:09 3) Potential measures against a black marble attack. https://github.com/monero-project/research-lab/issues/119 17:13:08 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. 17:13:21 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. 17:13:37 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. 17:13:51 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. 17:14:48 Which optimization problem? 17:15:35 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. 17:16:30 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 17:17:20 The objective function is cost/effective_ring_size. You want to minimize that by choosing ring size and fee/byte. 17:18:46 More comments on potential measures against a black marble attack? 17:19:19 The numerical solution is a simple grid search basically. It makes nice contour plots :) 17:20:03 4) Research Pre-Seraphis Full-Chain Membership Proofs. https://www.getmonero.org/2024/04/27/fcmps.html 17:20:26 Aaron Feickert: You have updates on the Generalized Bulletproofs security proof progress 17:23:32 testing 17:23:33 Are these messages going through? 17:23:35 My Element client is acting funky 17:23:49 the "testing" message went through 17:23:51 Yes 17:23:52 I see them 17:23:58 and the two after that 17:24:02 OK, sorry about that 17:24:09 Yes, I have an update! 17:24:21 Cypher Stack has been reviewing the Generalized Bulletproofs design required for Curve Trees to work 17:24:36 We're about halfway through, and identified a minor issue 17:24:38 https://libera.monerologs.net/monero-research-lab/20240501 Aaron Feickert ;) 17:25:03 The issue is that the proving relation informally described by the authors doesn't quite work with the soundness proof 17:25:29 A solution is to modify how vector commitments are represented in the relation, which technically means they can use more generators 17:25:40 Modifying that, and updating the proofs accordingly, fixes things 17:25:42 But 17:25:52 This change comes with a free benefit 17:26:19 Because the commitments can use additional generators, we can add constraint matrices to the design, which could allow for more efficient proofs 17:26:51 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) 17:27:51 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 17:27:53 Is this size-efficient proofs or verification-time-efficient or both? 17:28:33 Mostly size 17:28:50 But could also be time (I haven't run the numbers on that portion) 17:29:22 So probably no worse performance on time than the original design? 17:29:41 Nope, and totally optional to use 17:29:59 Adding the matrices also has minimal impact on the complexity of the security analysis 17:30:07 (above the changes already required for the initial design fix) 17:31:46 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? 17:31:50 Anyway, this is all detailed in the report 17:32:21 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 17:33:04 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 17:33:09 We expect no change to the timeline 17:33:43 Fantastic. Thank you! 17:33:57 Like I said, the matrix change is very straightforward to include 17:34:21 "Anyway, this is all detailed in the report". Is this an internal draft or does it exist publicly? 17:34:28 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. 17:34:51 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 17:35:02 What does "bandwidth" mean? 17:36:23 tx size 17:37:13 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 17:37:35 without a size increase 17:37:56 (there are some subtleties though) 17:39:09 But barring anything unexpected, we expect that the report will provide a satisfactory security proof for the modified construction 17:39:14 More data in less bytes Rucknium 17:39:31 (and which reduces to the "original" GBP design trivially if desired/needed) 17:41:21 Heck, it might end up being useful enough to warrant submission to a conference /shrug 17:41:46 I'd have to see if the original author(s) would be interested in such a thing, but that's for another day 17:42:51 Do kayabaNerve and tevador want to give updates on FCMP++? 17:43:09 * m-relay quietly exits 17:43:17 Did anyone have time to review Jamtis-RCT? 17:44:06 I've only skimmed it so far 17:45:04 I need a few minutes to fully comment, sorry. 17:45:19 *before I can fully comment. 17:46:05 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. 17:46:05 Maybe while we wait I can throw in a quick question 17:46:08 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). 17:46:39 It means new address become about functionality, not privacy (barring that one remaining edge case) 17:46:44 Are Bulletproofs++ more or less "off the table" after that quite mixed result of the review, and the move to FCMPs with GBP? 17:47:58 I'd shelve BP++ for now, which were never explicitly posited for FCMPs. 17:49:35 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] 17:51:27 Yes, it should be faster than mul8, pending benchmarks. 17:52:10 It avoids at least 1 field inversion and 6 point doublings per output. 17:52:17 I have Python which is less than 100 lines for Ristretto. 17:52:24 Plus the Ristretto serialization is intended as a thin wrapper around existing Edwards operations 17:53:31 Yep 17:54:56 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. 17:56:15 Who would we get to review the divisors? I 17:56:23 I've started cleaning up the prior code ('productionizing it'), fixing edge cases and bugs, and making it something I'd endorse auditing. 18:00:03 jeffro256: Don't we have to prove the security of the divisors and then review the proofs? 18:00:58 On divisors, I've already solicited two quotes/statements of work. 18:01:26 Divisors come with a correctness proof. Arguably, we need it reviewed and an audit a literal protocol aligns with its mathematics. 18:02:03 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. 18:02:29 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. 18:03:20 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. 18:03:45 I probably have a page of latex which reduces to `a - b = 0; a - b + b = 0 + b; a = b` and similar 18:03:48 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? 18:04:00 (the first being the check, the last line being the statement, the intemediary being the proof) 18:05:04 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. 18:05:24 I've reviewed tooling and one of the entities I solicited a quote from is explicitly experienced with formally verifying circuits. 18:06:26 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. 18:07:39 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. 18:07:47 It's a whole thing, it's documented 18:08:27 Eagen's work does describe divisor construction, evaluation, and the challenge evaluation. We'd argue our gadget follows it. 18:08:47 Once I confirm the lack of notational issues, we'd have the spec within the LaTeX audited. 18:08:57 Later, we'd audit the impl to match the spec. 18:11:14 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) 18:11:43 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) 18:11:49 The tree has been the main discussion. 18:13:53 FFI = Foreign Function Interface? 18:14:06 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 18:14:13 Yes re: FFI 18:14:46 In summary, moving ahead in all aspects, and progress is going well. 18:14:47 More comments? Other topics? 18:16:08 We can end the meeting here. Thank you all! 18:18:36 Thank you everyone! Thanks Aaron Feickert ! Fascinating stuff