huzzah!

sarang: can 2of2SignCond from 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

Ooh, interesting question... I'll need to think a bit about that

Once I finish some more Gray code stuff :D

Ah, C++... whatever would I do without your segfaults

Spend much more time debugging.

It's probably related to a rewrite I did on the batch inverter to support matrices

Without that, you lose a ton of the Gray code efficiency gains

(batch inversion only requires a single scalar inversion, which is so cool)

translating your python gray code to c++ already sarang?

aye

The Python Gray code stuff works great for Arcturus and Triptych (albeit without batch inversion, since that code isn't for timing)

I'll be very eager to see what cargodog[m] learns from their Rust code

Right now they only use a binary Gray code on a base Groth/Kohlweiss library

Generalized Triptych/Arcturus require n-ary Gray codes (though right now the Triptych/Arcturus base is fixed at 2)

so you _could_ use binary Gray codes right now, but that's not flexible

and FWIW the way cargodog[m] uses the binary Gray codes isn't iterative, so I expect it's not optimally efficient as is

Hooray, solved

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!

Oh, no problem at all! You aren't obligated to work on it, of course

I'm merely curious to see the relative speedups at different parameters between C++ and Rust since they use such different libraries

Also: my Monero-focused implementation assumes that only proofs within the same transaction share an input anonymity set for batching purposes

whereas yours assumes sharing the set much more broadly

So that's one major difference

No appologies necessary, I was just offering an excuse for leaving you in the dark. This is a work of love, no obligation :)

Yes, this optimization really has the most to gain if the set can be shared as broadly as possible

Sure, but as has been noted, this has usability consequences in practice

which, as we discussed before, is not an easy problem to solve

heh, yep

jinx

:D

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

(since Triptych requires a proof per input)

I should dust off my (very poor) Rust skills and play around with your implementation

The Triptych C++ is working now, hooray, with benchmark results!

I am too. Once I get this write-up finished, I plan to build out a wide array of benches testing "real world" scenarios

Are you using the n-ary Gray code that I found?

Or another one?

Or a more general approach?

(since there isn't one n-ary Gray code)

I am using one of the papers linked in the Wiki, which I believe is the same paper you shared

it focuses on ternary, but lays the foundation for easy generalization

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

The paper I used had a general algorithm

But yeah, its initial example was base-3 IIRC

I used the algorithm in this paper: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.119.1344

Does Rust support anything akin to a Python generator?

Yeah, thats the paper. Sorry, I've been juggling too many papers lately. Indeed, it has a generalized algo

I built a generator for the Python example, but did a more hacky approach in C++ to do the same thing

It's just so darn convenient to iterate over a custom generator

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

agreed. Bundling the iteration logic into the iterator makes things incredibly smooth

OK, meaning a custom iterator?

yes, sorry

custom iterators

In Python, the generator is a function that has a `yield` statement that basically maintains internal state but returns the current iterated value

cool

So you can iterate over the function call without any messy state variables that need to be maintained between calls

You can also define iterators that permute from past iterators, which works nicely here

In C++ I fake it with global variables

Why would you need that?

ah, that sounds very handy

The verifier only does a single iteration

er, single iterator

So in Python, you do `for some_result in custom_iterator(parameters)`

and `custom iterator` has a `yield` when it needs to return its next result

I could have worded that better: One iterator, where each subsequent element is a permutation of the previous

What do you mean by permutation?

My iterator, for example, tracks the changed Gray digit, its old result, and its new result

and then the verifier uses that to identify which scalar-scalar mults to do

(there's a separate mechanism when it needs a given Gray code without iteration)

(the prover needs to do this)

Sorry for all the questions; I'm fairly new to Rust and don't use it often

Out of curiosity, did you find it really hard to read at first ?

No worries. My internet is quite slow, so sorry for lagged responses :)

sarang: Rust? Yes, very

(rust)

How much time till you could mostly read it, to follow the basic structure ?

I find Rust much easier to read

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

cargodog[m]: how so?

Some things are easier, sure

And I am also a C/C++ dev

but others seem easy only in hindsight

I suppose this is very person-dependent :)

I found it incredibly obscure every time I tried reading some.

For math stuff (since we are talking about math here), the biggest "readability" advantage is how Rust iterators and iterator adapters work

moneromooo: there are some things I still have trouble reading for structure

I can write a very complex mathematical relation, just as a short chain of iterator adapters, and it reads almost like readin LaTeX

cargodog[m]: how much of that is iterators in general?

Sounds like LISP...

Indeed, very much like Lisp

But with a much nicer performance/security tradeoff

I am not a Rust maximalist :)

HEh

I like the idea of RUst

But I do prefer it for this sort of work

I don't like using it to try out new things

It is slower for rapid prototyping, no doubt

But I appreciate how hard it makes it to shoot yourself in the foot, for sure

Yeah, I like Python for testing algorithms, since it's easy to iterate

haha!

(pun intended)

That's why I did my Gray stuff in Python first, and only then in C++

Python will run circles around Rust for quick prototyping

ya

but the way I use it is slow as molasses for curve operations

I'm sure that I'll use Rust more and more over time

:)

Hey gang

What does the core wallet use for the change address?

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)

index 0 of the current account.

Cool, that makes sense.

ty mooo

cargodog[m]: for Triptych 2-in transactions, the Gray method is slower until you move from 64 to 128 for the anon set

For 128, it's 1% faster =p

For 256, it's 2.7% faster

Running bigger anon sets now...

I feel gingeropolous 's excitement

6% faster for anon 1028

(2 inputs, again)

Running on 4 inputs, which implies better batching

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

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

but, theres a lot of steps before I get there, and that is a potentially never ending black hole

sarang: are those results with your C++ code?

"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

noted for next edition thanks Isthmus

Arcturus finished as well

how does it look?

Testing now :)

:(

noooo

For those interested:

Arcturus w/ Gray coefficients: github.com/SarangNoether/monero/tree/arcturus-gray

Triptych w/ Gray coefficients: github.com/SarangNoether/monero/tree/triptych-gray

The CI fails, but that appears to be a problem with the macOS configuration, not the code itself

Very nice!

cargodog[m]: for Triptych, there's definitely a clear threshold for when this starts being useful

Interesting. Why is it different?

Different from what?

Admittedly, I have spent more time focusing on Arcturus and base Groth

Are you implying it has a clearer threshold compared to Arcturus?

Perhaps I misunderstood

I mean that Gray is slower than non-Gray for smaller input sets, even for Arcturus

Ah understood. I thought you meant there was a notable difference in the threshold between the two proof schemes

Well, in Triptych the code currently inverts matrices on a per-proof basis

* cargodog dons his dunce cap

In Arcturus, it does them all at once

Of course, for Arcturus batching you can choose how you do this too

IIRC you invert per proof?

Not per batch?

I believe I invert over the entire batch. Let me confirm

And again, you're handling the idea of batching differently than I am, because of the implied use cases

but I see what you mean now.

You are assuming that multiple proofs share an input set

correct

I assume that multiple Triptych proofs share an input set _per transaction only_, and that Arcturus proofs (one per transaction) do not otherwise overlap

so YMMV

That is a more realistic assumption.

I intend to modify my library to make the assumption selectable (or add a separate API)

righto

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

below that, standard decomposition wind

*wins

above that, Gray wins

but not by much

Thats good to know. Its nice to put concrete numbers to this

for Triptych 4-input transactions, the crossover is between 2^5 and 2^6

same for Arcturus

I'll plot all this for tomorrow's meeting

fantastic. Can't wait :)

Feel free to build the code if you want to play around with it

If you do, I can point you to the right place for modifying the benchmarks

(not as easy as `cargo`...)

Oh, I should note that these tests also assume commitment offsets and balance proofs too

So they're accurate for complete transactions

not just the input proofs

sarang_: does Mac CI always fail or just once?

It failed regularly, but I hadn't rebased in a while

looks like package manager connection issues

should fix itself after a bit

fair enough

the code works, that's the important part

the check mark is a side benefit :D

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

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

I don't think it has to do with the code computation

although, the benefit would of course be marginal compared to large sets/batches

but with the iteration

which implies a nontrivial number of scalarmults

How so? It should require only 2 scalar mults

s/iteration/inversion

per exponent

Inversion requires ~200 scalarmults

ahhh yes... inversion..

plus more for the batch inversion

I was forgetting about that cost

this isn't needed at all for the non-Gray version

indeed. Good point.

So at some point, you gain more from the Gray iteration than you lose from the batch inversion

At any rate, I intend to explore this thoroughly, but that sounds likely to be the limiting factor

Yeah, and I don't see a way to eliminate it

~200 mults seems to be the best known addition ladder for ed25519 scalar inversion

Thats what I have seen too

I was forgetting about inversion... I'm too tired to make more progress today

But hey, FWIW after the crossover (which is negligible for large batches, probably), Gray wins!

Hehe

For something like Lelantus, it's a no-brainer to switch

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

Ok, Im off for today. I will try to stop by the meeting tomorrow

I'll send my work to Aram, their cryptographer

We've collaborated before on some Lelantus improvements