-
Isthmus
@sarang - agree, seems fine to update with a citation, link, and the file checksum.
-
Isthmus
Maybe sign it for good measure
-
sarang
I would be very surprised if someone decided to compromise the archive!
-
Isthmus
Surprise targets are the best targets
-
Isthmus
I wouldn't be surprised if an unscrupulous totalitarian government compromised some low-security academic servers to ensnare or dox citizens bypassing firewalls and information control
-
koe
is there any documentation regarding how bulletproofs were implemented in Monero? I see some code references to the original bulletproofs paper, but aside from that my understanding is there were various implementation choices made.
-
koe
btw sarang I did take advantage of your ZtM commit regarding updated encrypted amount format, thanks!
-
koe
ZtM2 is coming along nicely, just finished a narrative rework that Im very happy with
-
koe
most of what remains is just bulletproofs and multisig (admittedly leaving the hardest parts for last)
-
koe
ah and the dastardly new weight/fee system
-
sarang
What bulletproof questions do you have koe?
-
koe
nothing specific right now, just want to collect a list of documents
-
sarang
Ok
-
sarang
How much detail are you intending?
-
koe
not sure yet
-
sarang
Getting into the weeds in the math for bulletproofs is probably not useful for the reader
-
koe
hopefully on a similar level to mlsag etc
-
koe
but I did get half-way through that Alex document, and it's VERY TEDIOUS
-
sarang
Which?
-
koe
-
sarang
I don't think that would really be needed IMO
-
koe
I gave up on the condensed vector knowledge proof lol. In any case it would be nice to, at minimum, write down the algorithm used.
-
koe
maybe some comments about how it works
-
koe
maybe translate Adam's document into a supplement or appendix
-
sarang
The bulletproofs paper does a good job of detailing
-
sarang
Hooray, Triptych is already on the IACR archive:
eprint.iacr.org/2020/018
-
koe
congrats!
-
dEBRUYNE
sarang: Would you mind posting that on Reddit with a little description / explainer?
-
sarang
Sure, will do it when not on mobile
-
sarang
I didn't expect it to be posted so quickly
-
dEBRUYNE
All right, thanks
-
sarang
Sometimes takes a couple of days
-
selsta
almost 2020/020
-
sarang
Ikr
-
sarang
I was hoping...
-
koe
btw one thing to keep in mind for these logarithmic size systems is in Monero there is still a linear component, namely the ring member offsets which are at least 1 byte. Probably not significant on the order of 100 member rings, but 1000 member rings it becomes a lot.
-
koe
probably average 2-3 bytes each based on varint representation
-
koe
I have a hard time imagining the utility of 10^3+ order rings anyway..
-
moneromooo
With small ring sizes, you can still have proofs that my incoming monero can't have originated from this particular output. With large ring sizes, this becomes less possible faster.
-
moneromooo
s/my/your/
-
sarang
koe: all the analysis that I've posted has noted that size estimates do not include anonymity set representations
-
sarang
However, the use of fixed sets of outputs can reduce this, as well as take advantage of security benefits from binning (see e.g. the Miler paper)
-
sarang
-
koe
that's good to hear, it's easy to overlook
-
sarang
Omniring in particular mentioned the use of "squeeze-a-crowd"-style efficient representation, but this is tricky to do when you have a more complex output selection distribution (as we do)
-
sarang
But as an example, to have a 100-ring, you might instead use 10 separate 10-element fixed sets, and your representation is now approximately the same size as it is now
-
koe
interesting
-
sarang
There are a few other subtle points to this, such as verifiably randomizing the sets to avoid malicious packing
-
sarang
but that's straightforward to do
-
sarang
koe: one part of Triptych that I like (and which is shared by RCT3 and one version of Omniring) is that there's no longer a need to hash all the outputs in the anonymity set anymore
-
sarang
For a large anon set, it'd be a significant time sink or require caching of the hashes in advance
-
koe
yeah I was wondering about that
-
sarang
The new image format uses a particular PRF introduced by (I think) Dodis
-
sarang
This is what complicates multisig, since you have to invert the signing key to generate the linking tag
-
sarang
Even in the form of Omniring that uses the current image format, there's still an inversion in the proof :(
-
koe
where there's a will there's a way!
-
sarang
Yeah, there's a method to do the inversion that's been worked out
-
sarang
it's not as straightforward as you'd like
-
sarang
Requires some homomorphic public-key stuff
-
koe
I need to escape before yall do something crazy!
-
sarang
-
sarang
(should not be considered secure or production-ready)
-
sarang
It's also markdown-based math, which is not great to read =p
-
selsta
sarang: Can you also add a comment on Reddit what Triptych could mean in the future? :)
-
sarang
"Maybe something; maybe nothing"
-
selsta
but I guess that’s not scientific
-
selsta
lol
-
sarang
done
-
selsta
ty
-
sarang
also added links to other relevant preprints
-
sarang
Link to TeX source for the paper, in case it's useful to anyone:
github.com/SarangNoether/skunkworks/blob/triptych/paper/iacr.tex
-
sgp_
did you make a similar graph for transaction verification?
-
sarang
I did not, since verification complexity was only listed for multiscalar-type operations
-
sarang
Didn't think it would be a totally fair comparison
-
sarang
The table provides that complexity
-
koe
sgp_ just train your mind to dream in logarithm
-
sgp_
sarang koe my mind is trying to turn the table into a graph :)
-
koe
good work, brainmail it to me when you're done!
-
sarang
Keep in mind as well that the table is only for the signatures/proofs
-
sarang
It's not a full representation of what's needed for something akin to an RCT transaction structure
-
sgp_
I'm looking for an informal, dummied-down, non-scientific, realistic graph of verification time
-
sgp_
"this is drunk, outspoken sarang making a graph on a board" quality
-
sarang
You'd need to include a lot of other stuff for a full comparison, like balance computation and other auxiliary information like range proofs
-
sarang
Heh
-
sarang
The material in my sublinear branch includes this stuff
-
sgp_
brb making a graph :p
-
sarang
From the sublinear data?
-
sgp_
yeah
-
sarang
Keep in mind that the sizes/times scale differently based on transaction in/out structure
-
sarang
so it's really hard to make universal comparisons
-
sgp_
yeah fair
-
sarang
I don't want to make informal claims that are interpreted more broadly than they should be
-
sgp_
I just need some visualization
-
sarang
the verification complexity that I listed is more realistic IMO
-
sarang
even though less practical since we don't just include a sig/proof in txns on chain
-
koe
it's pretty opaque
-
koe
to most eyes
-
sgp_
what values should I use for k?
-
sarang
It's not a variable. It's a notation for the complexity of a multiscalar multiplication operation
-
sarang
Depends on the implementation relative to things like hash to point ops
-
sarang
Since CLSAG uses a lot of these hashing ops
-
sarang
Boo, just realized the table from the Triptych paper does not include my batching complexity numbers
-
sarang
I'll update and revise on IACR
-
sarang
In fact, I should include batching data for common and separate anonymity sets across the batch
-
» sarang gets to work
-
sarang
^ suraeNoether
-
suraeNoether
Lmk when it's done! I didnt review the tables as closely as the proofs :(
-
sarang
Thought I had included the batch versions in the paper, but I must have forgotten
-
sarang
Fortunately it's easy to revise on IACR, and I believe it would appear instantly
-
sarang
and I suppose that's part of the point of preprints
-
moneromooo
Batching is only used for the txes since last embedded hash when syncing historical data. So it may not be that big a loss.
-
sarang
?
-
sarang
I mean that I didn't include the data on batching in the table of the paper
-
sarang
It's accounted for in the full-txn analyses I did
-
sarang
The paper has proof-only data that does not include range proofs, multi-input stuff, etc.
-
sarang
to have a more fair comparison
-
sarang
but the narrative of the paper says batching is included, which is wrog
-
moneromooo
I did not mean to make a comment about the paper, sorry if it sounded that way.
-
sarang
ah ok
-
sarang
nvm
-
sarang
New preprint on application of SHA-1 collisions:
eprint.iacr.org/2020/014
-
sarang
Also: don't forget this week's research meeting will be tomorrow (Wednesday) one hour later than previously (now 18:00 UTC)