00:11:03 <gingeropolous> huzzah!
10:36:30 <maybefbi> sarang: can 2of2SignCond from https://eprint.iacr.org/2019/595.pdf be replaced with 2-of-3 MLSTAG from Zero to Monero 2.0? The third partcipant can be the yG =Y, which if Bob figures out before block t, he can spend the escrowed output of the DLSAG
14:09:54 <sarang> Ooh, interesting question... I'll need to think a bit about that
14:10:04 <sarang> Once I finish some more Gray code stuff :D
15:15:33 <sarang> Ah, C++... whatever would I do without your segfaults
15:17:03 <moneromooo> Spend much more time debugging.
15:17:51 <sarang> It's probably related to a rewrite I did on the batch inverter to support matrices
15:18:34 <sarang> Without that, you lose a ton of the Gray code efficiency gains
15:18:47 <sarang> (batch inversion only requires a single scalar inversion, which is so cool)
15:18:55 <TheCharlatan> translating your python gray code to c++ already sarang?
15:19:00 <sarang> aye
15:19:19 * moneromooo suggests ASAN
15:19:23 <sarang> The Python Gray code stuff works great for Arcturus and Triptych (albeit without batch inversion, since that code isn't for timing)
15:20:37 <sarang> I'll be very eager to see what cargodog[m] learns from their Rust code
15:20:52 <sarang> Right now they only use a binary Gray code on a base Groth/Kohlweiss library
15:21:13 <sarang> Generalized Triptych/Arcturus require n-ary Gray codes (though right now the Triptych/Arcturus base is fixed at 2)
15:21:26 <sarang> so you _could_ use binary Gray codes right now, but that's not flexible
15:21:48 <sarang> and FWIW the way cargodog[m] uses the binary Gray codes isn't iterative, so I expect it's not optimally efficient as is
15:44:03 <sarang> Hooray, solved
15:44:21 <cargodog[m]> Glad to hear your C++ implementation is coming along! Sorry, work/family life has been relentless these last few days, so I haven't made as much progress as I would've hoped. Pesky work, getting in the way of the important things!
15:45:12 <sarang> Oh, no problem at all! You aren't obligated to work on it, of course
15:45:47 <sarang> I'm merely curious to see the relative speedups at different parameters between C++ and Rust since they use such different libraries
15:47:11 <sarang> Also: my Monero-focused implementation assumes that only proofs within the same transaction share an input anonymity set for batching purposes
15:47:20 <sarang> whereas yours assumes sharing the set much more broadly
15:47:25 <sarang> So that's one major difference
15:47:29 <cargodog[m]> No appologies necessary, I was just offering an excuse for leaving you in the dark. This is a work of love, no obligation :)
15:48:14 <cargodog[m]> Yes, this optimization really has the most to gain if the set can be shared as broadly as possible
15:48:31 <sarang> Sure, but as has been noted, this has usability consequences in practice
15:48:34 <cargodog[m]> which, as we discussed before, is not an easy problem to solve
15:48:38 <sarang> heh, yep
15:48:39 <sarang> jinx
15:48:51 <cargodog[m]> :D
15:49:11 <sarang> But at any rate, I'm initially interested to see at what point we see benefits sharing only within transactions, which would use only 1 or 2 Triptych proofs, and 1 Arcturus proof
15:49:19 <sarang> (since Triptych requires a proof per input)
15:49:43 <sarang> I should dust off my (very poor) Rust skills and play around with your implementation
15:50:00 <sarang> The Triptych C++ is working now, hooray, with benchmark results!
15:50:04 <cargodog[m]> I am too. Once I get this write-up finished, I plan to build out a wide array of benches testing "real world" scenarios
15:50:22 <sarang> Are you using the n-ary Gray code that I found?
15:50:24 <sarang> Or another one?
15:50:27 <sarang> Or a more general approach?
15:50:33 <sarang> (since there isn't one n-ary Gray code)
15:51:18 <cargodog[m]> I am using one of the papers linked in the Wiki, which I believe is the same paper you shared
15:51:34 <cargodog[m]> it focuses on ternary, but lays the foundation for easy generalization
15:51:49 <cargodog[m]> fyi, I am almost done with a first draft of the paper. Once I started including the necessary background info for the uninitiated, things got a bit wordy
15:51:56 <sarang> The paper I used had a general algorithm
15:52:08 <sarang> But yeah, its initial example was base-3 IIRC
15:52:58 <sarang> I used the algorithm in this paper: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.119.1344
15:53:27 <sarang> Does Rust support anything akin to a Python generator?
15:53:33 <cargodog[m]> Yeah, thats the paper. Sorry, I've been juggling too many papers lately. Indeed, it has a generalized algo
15:53:47 <sarang> I built a generator for the Python example, but did a more hacky approach in C++ to do the same thing
15:54:24 <sarang> It's just so darn convenient to iterate over a custom generator
15:54:46 <cargodog[m]> Im not as fluent in Python, but Rust iterators can be used to create "generators", which is what I am using in my binary impl
15:55:09 <cargodog[m]> agreed. Bundling the iteration logic into the iterator makes things incredibly smooth
15:55:09 <sarang> OK, meaning a custom iterator?
15:55:22 <cargodog[m]> yes, sorry
15:55:24 <cargodog[m]> custom iterators
15:55:38 <sarang> In Python, the generator is a function that has a `yield` statement that basically maintains internal state but returns the current iterated value
15:55:44 <sarang> cool
15:56:10 <sarang> So you can iterate over the function call without any messy state variables that need to be maintained between calls
15:56:18 <cargodog[m]> You can also define iterators that permute from past iterators, which works nicely here
15:56:20 <sarang> In C++ I fake it with global variables
15:56:29 <sarang> Why would you need that?
15:56:30 <cargodog[m]> ah, that sounds very handy
15:56:36 <sarang> The verifier only does a single iteration
15:56:41 <sarang> er, single iterator
15:57:10 <sarang> So in Python, you do `for some_result in custom_iterator(parameters)`
15:57:24 <sarang> and `custom iterator` has a `yield` when it needs to return its next result
15:57:27 <cargodog[m]> I could have worded that better: One iterator, where each subsequent element is a permutation of the previous
15:58:02 <sarang> What do you mean by permutation?
15:58:19 <sarang> My iterator, for example, tracks the changed Gray digit, its old result, and its new result
15:58:36 <sarang> and then the verifier uses that to identify which scalar-scalar mults to do
15:58:48 <sarang> (there's a separate mechanism when it needs a given Gray code without iteration)
15:58:53 <sarang> (the prover needs to do this)
15:59:13 <sarang> Sorry for all the questions; I'm fairly new to Rust and don't use it often
15:59:36 <moneromooo> Out of curiosity, did you find it really hard to read at first ?
15:59:40 <cargodog[m]> No worries. My internet is quite slow, so sorry for lagged responses :)
15:59:45 <sarang> sarang: Rust? Yes, very
15:59:45 <moneromooo> (rust)
16:00:20 <moneromooo> How much time till you could mostly read it, to follow the basic structure ?
16:00:24 <cargodog[m]> I find Rust much easier to read
16:00:31 <sarang> It was also tricky since the language itself seems to evolve quickly, meaning it was super irritating get anything to run properly and have consistency between features
16:00:36 <sarang> cargodog[m]: how so?
16:00:40 <sarang> Some things are easier, sure
16:00:45 <cargodog[m]> And I am also a C/C++ dev
16:00:48 <sarang> but others seem easy only in hindsight
16:01:05 <sarang> I suppose this is very person-dependent :)
16:01:26 <moneromooo> I found it incredibly obscure every time I tried reading some.
16:01:46 <cargodog[m]> For math stuff (since we are talking about math here), the biggest "readability" advantage is how Rust iterators and iterator adapters work
16:01:50 <sarang> moneromooo: there are some things I still have trouble reading for structure
16:02:04 <cargodog[m]> I can write a very complex mathematical relation, just as a short chain of iterator adapters, and it reads almost like readin LaTeX
16:02:06 <sarang> cargodog[m]: how much of that is iterators in general?
16:02:18 <moneromooo> Sounds like LISP...
16:02:33 <cargodog[m]> Indeed, very much like Lisp
16:02:52 <cargodog[m]> But with a much nicer performance/security tradeoff
16:03:07 <cargodog[m]> I am not a Rust maximalist :)
16:03:14 <sarang> HEh
16:03:17 <sarang> I like the idea of RUst
16:03:18 <cargodog[m]> But I do prefer it for this sort of work
16:03:23 <sarang> I don't like using it to try out new things
16:03:42 <cargodog[m]> It is slower for rapid prototyping, no doubt
16:03:48 <sarang> But I appreciate how hard it makes it to shoot yourself in the foot, for sure
16:03:57 <sarang> Yeah, I like Python for testing algorithms, since it's easy to iterate
16:03:57 <cargodog[m]> haha!
16:04:00 <sarang> (pun intended)
16:04:32 <sarang> That's why I did my Gray stuff in Python first, and only then in C++
16:04:53 <cargodog[m]> Python will run circles around Rust for quick prototyping
16:04:58 <sarang> ya
16:05:22 <sarang> but the way I use it is slow as molasses for curve operations
16:05:58 <sarang> I'm sure that I'll use Rust more and more over time
16:05:59 <sarang> :)
16:10:50 <Isthmus> Hey gang
16:10:50 <Isthmus> What does the core wallet use for the change address?
16:10:50 <Isthmus> I spent a while perusing ZtM but this isn't mentioned (which makes sense since it's an implementation decision and not part of the protocol)
16:11:24 <moneromooo> index 0 of the current account.
16:11:45 <Isthmus> Cool, that makes sense.
16:11:46 <Isthmus> ty mooo
16:59:07 <sarang> cargodog[m]: for Triptych 2-in transactions, the Gray method is slower until you move from 64 to 128 for the anon set
16:59:37 <sarang> For 128, it's 1% faster =p
17:00:24 <sarang> For 256, it's 2.7% faster
17:02:01 <sarang> Running bigger anon sets now...
17:18:31 <nioc> I feel gingeropolous 's excitement
17:19:39 <sarang> 6% faster for anon 1028
17:19:44 <sarang> (2 inputs, again)
17:21:46 <sarang> Running on 4 inputs, which implies better batching
17:41:27 <cargodog[m]> Yeah with only 2 inputs, I expect you to see an improvement above a certain set size (sounds like that threshold is 128 for your curve library), but no real "overwhelming" improvement
17:42:34 <cargodog[m]> Honestly, once I get all of this formalized, and once I've come up with some good performance numbers demonstrating the batching benefit, I want to research ways to maximize set overlap to improve batching
17:43:02 <cargodog[m]> but, theres a lot of steps before I get there, and that is a potentially never ending black hole
17:43:26 <cargodog[m]> sarang: are those results with your C++ code?
17:45:31 <cargodog[m]> "more performant" curve libraries (e.g. one whose point operations are relatively fast) will notice more of a benefit, because scalar operations will have more of an effect
18:20:00 <UkoeHB_> noted for next edition thanks Isthmus
19:38:38 <sarang_> Arcturus finished as well
19:41:00 <UkoeHB_> how does it look?
19:42:39 <sarang_> Testing now :)
19:42:39 <monerobux> Test failed
19:42:43 <sarang_> :(
19:42:44 <sarang_> noooo
19:54:01 <sarang_> For those interested:
19:54:15 <sarang_> Arcturus w/ Gray coefficients: https://github.com/SarangNoether/monero/tree/arcturus-gray
19:54:25 <sarang_> Triptych w/ Gray coefficients: https://github.com/SarangNoether/monero/tree/triptych-gray
19:55:43 <sarang_> The CI fails, but that appears to be a problem with the macOS configuration, not the code itself
20:00:46 <cargodog[m]> Very nice!
20:01:29 <sarang_> cargodog[m]: for Triptych, there's definitely a clear threshold for when this starts being useful
20:01:57 <cargodog[m]> Interesting. Why is it different?
20:02:07 <sarang_> Different from what?
20:02:20 <cargodog[m]> Admittedly, I have spent more time focusing on Arcturus and base Groth
20:02:59 <cargodog[m]> Are you implying it has a clearer threshold compared to Arcturus?
20:03:12 <cargodog[m]> Perhaps I misunderstood
20:04:16 <sarang_> I mean that Gray is slower than non-Gray for smaller input sets, even for Arcturus
20:04:56 <cargodog[m]> Ah understood. I thought you meant there was a notable difference in the threshold between the two proof schemes
20:05:12 <sarang_> Well, in Triptych the code currently inverts matrices on a per-proof basis
20:05:16 <cargodog[m]> * cargodog dons his dunce cap
20:05:18 <sarang_> In Arcturus, it does them all at once
20:05:27 <sarang_> Of course, for Arcturus batching you can choose how you do this too
20:05:35 <sarang_> IIRC you invert per proof?
20:05:39 <sarang_> Not per batch?
20:06:07 <cargodog[m]> I believe I invert over the entire batch. Let me confirm
20:06:10 <sarang_> And again, you're handling the idea of batching differently than I am, because of the implied use cases
20:06:13 <cargodog[m]> but I see what you mean now.
20:07:07 <sarang_> You are assuming that multiple proofs share an input set
20:07:18 <cargodog[m]> correct
20:07:33 <sarang_> I assume that multiple Triptych proofs share an input set _per transaction only_, and that Arcturus proofs (one per transaction) do not otherwise overlap
20:07:43 <sarang_> so YMMV
20:08:11 <cargodog[m]> That is a more realistic assumption.
20:08:35 <cargodog[m]> I intend to modify my library to make the assumption selectable (or add a separate API)
20:08:59 <sarang_> righto
20:09:23 <sarang_> Well, under that assumption, you only see benefits for 2-input transactions between input set size 2^6 and 2^7 for Triptych and Arcturus
20:09:35 <sarang_> below that, standard decomposition wind
20:09:37 <sarang_> *wins
20:09:43 <sarang_> above that, Gray wins
20:09:49 <sarang_> but not by much
20:10:00 <cargodog[m]> Thats good to know. Its nice to put concrete numbers to this
20:10:11 <sarang_> for Triptych 4-input transactions, the crossover is between 2^5 and 2^6
20:10:56 <sarang_> same for Arcturus
20:11:01 <sarang_> I'll plot all this for tomorrow's meeting
20:11:14 <cargodog[m]> fantastic. Can't wait :)
20:11:25 <sarang_> Feel free to build the code if you want to play around with it
20:11:42 <sarang_> If you do, I can point you to the right place for modifying the benchmarks
20:11:49 <sarang_> (not as easy as `cargo`...)
20:12:20 <sarang_> Oh, I should note that these tests also assume commitment offsets and balance proofs too
20:12:29 <sarang_> So they're accurate for complete transactions
20:12:35 <sarang_> not just the input proofs
20:18:48 <selsta> sarang_: does Mac CI always fail or just once?
20:19:17 <sarang_> It failed regularly, but I hadn't rebased in a while
20:22:48 <selsta> looks like package manager connection issues
20:23:04 <selsta> should fix itself after a bit
20:23:26 <sarang_> fair enough
20:23:31 <sarang_> the code works, that's the important part
20:23:36 <sarang_> the check mark is a side benefit :D
20:50:48 <cargodog[m]> sarang_: I was just thinking about the performance cross-over between Gray/non-Gray, and I am surprised Gray doesn't win every time. I will look at your code later, but the Gray code iteration logic can be done very efficiently in native words (if we assume N < 2^64 =p), and then used in the polynomial evaluation of scalars
20:51:29 <cargodog[m]> I will try to get some numbers to "put my money where my mouth is", but I thought you should know I'm not yet ready to say its not helpful for small sets/batches
20:51:47 <sarang> I don't think it has to do with the code computation
20:51:47 <cargodog[m]> although, the benefit would of course be marginal compared to large sets/batches
20:51:50 <sarang> but with the iteration
20:51:56 <sarang> which implies a nontrivial number of scalarmults
20:52:14 <cargodog[m]> How so? It should require only 2 scalar mults
20:52:14 <sarang> s/iteration/inversion
20:52:14 <monerobux> sarang meant to say: but with the inversion
20:52:19 <cargodog[m]> per exponent
20:52:25 <sarang> Inversion requires ~200 scalarmults
20:52:27 <cargodog[m]> ahhh yes... inversion..
20:52:38 <sarang> plus more for the batch inversion
20:52:44 <cargodog[m]> I was forgetting about that cost
20:52:47 <sarang> this isn't needed at all for the non-Gray version
20:53:00 <cargodog[m]> indeed. Good point.
20:53:22 <sarang> So at some point, you gain more from the Gray iteration than you lose from the batch inversion
20:53:27 <cargodog[m]> At any rate, I intend to explore this thoroughly, but that sounds likely to be the limiting factor
20:53:40 <sarang> Yeah, and I don't see a way to eliminate it
20:53:54 <sarang> ~200 mults seems to be the best known addition ladder for ed25519 scalar inversion
20:54:10 <cargodog[m]> Thats what I have seen too
20:54:41 <cargodog[m]> I was forgetting about inversion... I'm too tired to make more progress today
20:55:56 <sarang> But hey, FWIW after the crossover (which is negligible for large batches, probably), Gray wins!
20:56:31 <cargodog[m]> Hehe
20:56:53 <sarang> For something like Lelantus, it's a no-brainer to switch
20:58:46 <cargodog[m]> Indeed.. Monero has been my first focus, but it would probably be a good idea to share this work with them. At minimum they may have useful suggestions/criticisms
20:59:28 <cargodog[m]> Ok, Im off for today. I will try to stop by the meeting tomorrow
21:03:14 <sarang> I'll send my work to Aram, their cryptographer
21:03:20 <sarang> We've collaborated before on some Lelantus improvements