-
gingeropolous
huzzah!
-
maybefbi
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
-
sarang
Ooh, interesting question... I'll need to think a bit about that
-
sarang
Once I finish some more Gray code stuff :D
-
sarang
Ah, C++... whatever would I do without your segfaults
-
moneromooo
Spend much more time debugging.
-
sarang
It's probably related to a rewrite I did on the batch inverter to support matrices
-
sarang
Without that, you lose a ton of the Gray code efficiency gains
-
sarang
(batch inversion only requires a single scalar inversion, which is so cool)
-
TheCharlatan
translating your python gray code to c++ already sarang?
-
sarang
aye
-
» moneromooo suggests ASAN
-
sarang
The Python Gray code stuff works great for Arcturus and Triptych (albeit without batch inversion, since that code isn't for timing)
-
sarang
I'll be very eager to see what cargodog[m] learns from their Rust code
-
sarang
Right now they only use a binary Gray code on a base Groth/Kohlweiss library
-
sarang
Generalized Triptych/Arcturus require n-ary Gray codes (though right now the Triptych/Arcturus base is fixed at 2)
-
sarang
so you _could_ use binary Gray codes right now, but that's not flexible
-
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
-
sarang
Hooray, solved
-
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!
-
sarang
Oh, no problem at all! You aren't obligated to work on it, of course
-
sarang
I'm merely curious to see the relative speedups at different parameters between C++ and Rust since they use such different libraries
-
sarang
Also: my Monero-focused implementation assumes that only proofs within the same transaction share an input anonymity set for batching purposes
-
sarang
whereas yours assumes sharing the set much more broadly
-
sarang
So that's one major difference
-
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 :)
-
cargodog[m]
Yes, this optimization really has the most to gain if the set can be shared as broadly as possible
-
sarang
Sure, but as has been noted, this has usability consequences in practice
-
cargodog[m]
which, as we discussed before, is not an easy problem to solve
-
sarang
heh, yep
-
sarang
jinx
-
cargodog[m]
:D
-
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
-
sarang
(since Triptych requires a proof per input)
-
sarang
I should dust off my (very poor) Rust skills and play around with your implementation
-
sarang
The Triptych C++ is working now, hooray, with benchmark results!
-
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
-
sarang
Are you using the n-ary Gray code that I found?
-
sarang
Or another one?
-
sarang
Or a more general approach?
-
sarang
(since there isn't one n-ary Gray code)
-
cargodog[m]
I am using one of the papers linked in the Wiki, which I believe is the same paper you shared
-
cargodog[m]
it focuses on ternary, but lays the foundation for easy generalization
-
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
-
sarang
The paper I used had a general algorithm
-
sarang
But yeah, its initial example was base-3 IIRC
-
sarang
-
sarang
Does Rust support anything akin to a Python generator?
-
cargodog[m]
Yeah, thats the paper. Sorry, I've been juggling too many papers lately. Indeed, it has a generalized algo
-
sarang
I built a generator for the Python example, but did a more hacky approach in C++ to do the same thing
-
sarang
It's just so darn convenient to iterate over a custom generator
-
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
-
cargodog[m]
agreed. Bundling the iteration logic into the iterator makes things incredibly smooth
-
sarang
OK, meaning a custom iterator?
-
cargodog[m]
yes, sorry
-
cargodog[m]
custom iterators
-
sarang
In Python, the generator is a function that has a `yield` statement that basically maintains internal state but returns the current iterated value
-
sarang
cool
-
sarang
So you can iterate over the function call without any messy state variables that need to be maintained between calls
-
cargodog[m]
You can also define iterators that permute from past iterators, which works nicely here
-
sarang
In C++ I fake it with global variables
-
sarang
Why would you need that?
-
cargodog[m]
ah, that sounds very handy
-
sarang
The verifier only does a single iteration
-
sarang
er, single iterator
-
sarang
So in Python, you do `for some_result in custom_iterator(parameters)`
-
sarang
and `custom iterator` has a `yield` when it needs to return its next result
-
cargodog[m]
I could have worded that better: One iterator, where each subsequent element is a permutation of the previous
-
sarang
What do you mean by permutation?
-
sarang
My iterator, for example, tracks the changed Gray digit, its old result, and its new result
-
sarang
and then the verifier uses that to identify which scalar-scalar mults to do
-
sarang
(there's a separate mechanism when it needs a given Gray code without iteration)
-
sarang
(the prover needs to do this)
-
sarang
Sorry for all the questions; I'm fairly new to Rust and don't use it often
-
moneromooo
Out of curiosity, did you find it really hard to read at first ?
-
cargodog[m]
No worries. My internet is quite slow, so sorry for lagged responses :)
-
sarang
sarang: Rust? Yes, very
-
moneromooo
(rust)
-
moneromooo
How much time till you could mostly read it, to follow the basic structure ?
-
cargodog[m]
I find Rust much easier to read
-
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
-
sarang
cargodog[m]: how so?
-
sarang
Some things are easier, sure
-
cargodog[m]
And I am also a C/C++ dev
-
sarang
but others seem easy only in hindsight
-
sarang
I suppose this is very person-dependent :)
-
moneromooo
I found it incredibly obscure every time I tried reading some.
-
cargodog[m]
For math stuff (since we are talking about math here), the biggest "readability" advantage is how Rust iterators and iterator adapters work
-
sarang
moneromooo: there are some things I still have trouble reading for structure
-
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
-
sarang
cargodog[m]: how much of that is iterators in general?
-
moneromooo
Sounds like LISP...
-
cargodog[m]
Indeed, very much like Lisp
-
cargodog[m]
But with a much nicer performance/security tradeoff
-
cargodog[m]
I am not a Rust maximalist :)
-
sarang
HEh
-
sarang
I like the idea of RUst
-
cargodog[m]
But I do prefer it for this sort of work
-
sarang
I don't like using it to try out new things
-
cargodog[m]
It is slower for rapid prototyping, no doubt
-
sarang
But I appreciate how hard it makes it to shoot yourself in the foot, for sure
-
sarang
Yeah, I like Python for testing algorithms, since it's easy to iterate
-
cargodog[m]
haha!
-
sarang
(pun intended)
-
sarang
That's why I did my Gray stuff in Python first, and only then in C++
-
cargodog[m]
Python will run circles around Rust for quick prototyping
-
sarang
ya
-
sarang
but the way I use it is slow as molasses for curve operations
-
sarang
I'm sure that I'll use Rust more and more over time
-
sarang
:)
-
Isthmus
Hey gang
-
Isthmus
What does the core wallet use for the change address?
-
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)
-
moneromooo
index 0 of the current account.
-
Isthmus
Cool, that makes sense.
-
Isthmus
ty mooo
-
sarang
cargodog[m]: for Triptych 2-in transactions, the Gray method is slower until you move from 64 to 128 for the anon set
-
sarang
For 128, it's 1% faster =p
-
sarang
For 256, it's 2.7% faster
-
sarang
Running bigger anon sets now...
-
nioc
I feel gingeropolous 's excitement
-
sarang
6% faster for anon 1028
-
sarang
(2 inputs, again)
-
sarang
Running on 4 inputs, which implies better batching
-
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
-
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
-
cargodog[m]
but, theres a lot of steps before I get there, and that is a potentially never ending black hole
-
cargodog[m]
sarang: are those results with your C++ code?
-
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
-
UkoeHB_
noted for next edition thanks Isthmus
-
sarang_
Arcturus finished as well
-
UkoeHB_
how does it look?
-
sarang_
Testing now :)
-
monerobux
Test failed
-
sarang_
:(
-
sarang_
noooo
-
sarang_
For those interested:
-
sarang_
-
sarang_
-
sarang_
The CI fails, but that appears to be a problem with the macOS configuration, not the code itself
-
cargodog[m]
Very nice!
-
sarang_
cargodog[m]: for Triptych, there's definitely a clear threshold for when this starts being useful
-
cargodog[m]
Interesting. Why is it different?
-
sarang_
Different from what?
-
cargodog[m]
Admittedly, I have spent more time focusing on Arcturus and base Groth
-
cargodog[m]
Are you implying it has a clearer threshold compared to Arcturus?
-
cargodog[m]
Perhaps I misunderstood
-
sarang_
I mean that Gray is slower than non-Gray for smaller input sets, even for Arcturus
-
cargodog[m]
Ah understood. I thought you meant there was a notable difference in the threshold between the two proof schemes
-
sarang_
Well, in Triptych the code currently inverts matrices on a per-proof basis
-
cargodog[m]
* cargodog dons his dunce cap
-
sarang_
In Arcturus, it does them all at once
-
sarang_
Of course, for Arcturus batching you can choose how you do this too
-
sarang_
IIRC you invert per proof?
-
sarang_
Not per batch?
-
cargodog[m]
I believe I invert over the entire batch. Let me confirm
-
sarang_
And again, you're handling the idea of batching differently than I am, because of the implied use cases
-
cargodog[m]
but I see what you mean now.
-
sarang_
You are assuming that multiple proofs share an input set
-
cargodog[m]
correct
-
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
-
sarang_
so YMMV
-
cargodog[m]
That is a more realistic assumption.
-
cargodog[m]
I intend to modify my library to make the assumption selectable (or add a separate API)
-
sarang_
righto
-
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
-
sarang_
below that, standard decomposition wind
-
sarang_
*wins
-
sarang_
above that, Gray wins
-
sarang_
but not by much
-
cargodog[m]
Thats good to know. Its nice to put concrete numbers to this
-
sarang_
for Triptych 4-input transactions, the crossover is between 2^5 and 2^6
-
sarang_
same for Arcturus
-
sarang_
I'll plot all this for tomorrow's meeting
-
cargodog[m]
fantastic. Can't wait :)
-
sarang_
Feel free to build the code if you want to play around with it
-
sarang_
If you do, I can point you to the right place for modifying the benchmarks
-
sarang_
(not as easy as `cargo`...)
-
sarang_
Oh, I should note that these tests also assume commitment offsets and balance proofs too
-
sarang_
So they're accurate for complete transactions
-
sarang_
not just the input proofs
-
selsta
sarang_: does Mac CI always fail or just once?
-
sarang_
It failed regularly, but I hadn't rebased in a while
-
selsta
looks like package manager connection issues
-
selsta
should fix itself after a bit
-
sarang_
fair enough
-
sarang_
the code works, that's the important part
-
sarang_
the check mark is a side benefit :D
-
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
-
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
-
sarang
I don't think it has to do with the code computation
-
cargodog[m]
although, the benefit would of course be marginal compared to large sets/batches
-
sarang
but with the iteration
-
sarang
which implies a nontrivial number of scalarmults
-
cargodog[m]
How so? It should require only 2 scalar mults
-
sarang
s/iteration/inversion
-
monerobux
sarang meant to say: but with the inversion
-
cargodog[m]
per exponent
-
sarang
Inversion requires ~200 scalarmults
-
cargodog[m]
ahhh yes... inversion..
-
sarang
plus more for the batch inversion
-
cargodog[m]
I was forgetting about that cost
-
sarang
this isn't needed at all for the non-Gray version
-
cargodog[m]
indeed. Good point.
-
sarang
So at some point, you gain more from the Gray iteration than you lose from the batch inversion
-
cargodog[m]
At any rate, I intend to explore this thoroughly, but that sounds likely to be the limiting factor
-
sarang
Yeah, and I don't see a way to eliminate it
-
sarang
~200 mults seems to be the best known addition ladder for ed25519 scalar inversion
-
cargodog[m]
Thats what I have seen too
-
cargodog[m]
I was forgetting about inversion... I'm too tired to make more progress today
-
sarang
But hey, FWIW after the crossover (which is negligible for large batches, probably), Gray wins!
-
cargodog[m]
Hehe
-
sarang
For something like Lelantus, it's a no-brainer to switch
-
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
-
cargodog[m]
Ok, Im off for today. I will try to stop by the meeting tomorrow
-
sarang
I'll send my work to Aram, their cryptographer
-
sarang
We've collaborated before on some Lelantus improvements