The crossover happens between 32 and 64

Crossover? Do you mean verification time for 64-ring size triptych is greater than 11-ring CLSAG, while 32-ring is less?

Do verification estimates include the time to decompress ring members (one time keys and commitments)? They are stored compressed in the database

If you really mean decompress, it's trivial. If you mean lookup, it depends so much on I/O latency that it doesn't really make sense.

They include the decompression

Oh, wait. You mean 32 byte to ge_p3 ? Nevermind then...

Yes that's what I meant

Whoops, had the wrong CLSAG/MLSAG ring param

^ fixed

So... even faster now ? :)

Is that version with one multiexp, or still using several ?

Still several

<[keybase] seddd>: Tript64 only taking 2x clsag time O.O O.O gotta love log-scaling functions

<[keybase] seddd>: v exciting, good work sarang!

moneromooo: those numbers are on a faster machine than before :)

Builds faster

Etc.

Thanks sarang. These numbers back up my original skepticism about ring sizes >128. Could we even accept >64?

<[keybase] seddd>: one question: is D_precomp offset as input to the key image? re: github.com/moneromooo-monero/bitmon…b/clsag/src/ringct/rctSigs.cpp#L208

<[keybase] seddd>: D* not D_precomp

UkoeHB_: we'll have to see, once it's better optimized and properly accounts for batching

seddd: the standard key image is computed the same as previously

<[keybase] seddd>: ok, so is D the key image for the decoy keys? confused because thought I was the key image, am I being dumb?

Yes D is the auxiliary key image for the commitment to zero

And the offset is for storage in the blockchain. Do mul8 during verification, which ensures it's in the right elliptic curve subgroup

<[keybase] seddd>: thanks UkoeHB_ :)

The precomp terms are used for later internal point operations

<[keybase] seddd>: thanks sarang :)

I am curious what bridge is this room using for keybase? Matterbridge? And would it be possible to speak with bridge maintainer. It would be interesting to set uo a similar thing for the kovri/sekreta channeks. Cheers.

I feel like I heard that idea somewhere else, and maybe it has been rejected before. Anyway, bringing it back

Additional optimizations to Triptych verification: SarangNoether/monero 20e581d

Brings 16-Triptych verification down from 4070 us to 3140 us

(On the same machine, 11-CLSAG is 5659 us and 11-MLSAG is 6789 us)

This does not account for batching

32-Triptych becomes 5300 us, and 64-Triptych becomes 9460 us

Did you try pippenger out of curiosity ?

Not yet. I still have work to do on multiexp stuff, including algorithm selection and generator cachine

s/cachine/caching

FWIW the multiexp data entries have a ctor that do the frombytes for you.

32- and 64-Triptych is still Ring Signatures, basically?

Triptych is a zero-knowledge proving system that is used as a multidimensional linkable ring signature

At some point the term "ring signature" becomes more fuzzy, since the security definitions change a bit

are you coding up Triptych because it is the most promising of the new RingCT schemes or because you wrote the paper for it and want the timing?

If you mean "prover-specified signer ambiguity set" then yes

I think it's currently quite promising, and wanted actual data for comparison

ok, it does indeed sound promising

Ok, so for purposes of privacy, can I in laymans terms get a grasp on e.g. n-Triptych vs 11-Bulletproofs vs Zcash?

Bulletproofs serve an entirely different purpose in the transaction protocol from the signatures

oh wait. again *facepalm* never mind

restating: Ok, so for purposes of privacy, can I in laymans terms get a grasp on e.g. n-Triptych vs 11-ring sigs of today vs Zcash? <-- better

Depends entirely on the risk/threat model

A ring signature, absent external data, provides signer ambiguity among its specified input set

and zcash does the sam, but the "input set" is basically the entire set of all existing transactions?

If you're talking strictly about shielded operations only (with no transparent interactions), then (absent external information) the ambiguity set is all previous shielded outputs

But

I am.

Much like how many older Monero outputs can be marked as proven-spent or likely-spent, there are related heuristics that can be applied to Zcash transparent operations too

right

So "all previous outputs" is not really accurate either

All depends on how you operate

That being said, the "safe" set of possible outputs for Zcash is very large

Worth noting again that the size of the ambiguity is important, but certainly not the only thing that impacts privacy in practice

moneromooo: looks like Pippenger doesn't take effect until ringsize 128

at least according to the data you had for bulletproofs testing

Hmm wait, I might be misreading how the limits are used

Straus/Pippenger crossover is at N=32

Really depends whether the number of scalar/point pairs is the same for MLSAG and triptych.

(per ring member)

Caching might affect this crossover once implemented

Triptych reduces to a single multiexp

static inline rct::key multiexp(const std::vector<MultiexpData> &data, size_t HiGi_size)

yep

This comparison data is already interesting, even if not fully optimized

So far, it indicates that 16-Triptych runs in 46% of the time of 11-MLSAG, and 55% of the time of 11-CLSAG

Timing comparison: usercontent.irccloud-cdn.com/file/Q4H8BTy9/timing.png

Size comparison: usercontent.irccloud-cdn.com/file/cNTwOQ6M/size.png

Gray lines are centered at the 11-MLSAG point on each plot as a visual guide

nice

so triptych always wins re: verification time

So the intersection of the Triptych line and the horizontal gray line shows the point at which Triptych exceeds the current size/time of 11-MLSAG

sarang: bulletproofs had a nice blog post written by you, I think Triptych would also be worthy of a blog post :)

once you have the numbers

There are still some additional optimizations to mak

s/mak/make

I wanted to have these plots available to give at least an initial comparison

selsta: +1

Also nice to have a blog that we can point people to

Even if it will likely take quite some time before implemented

before/if

But I agree; I'll write up a post once I have more finalized data

FWIW if multisig weren't an issue, it'd be reasonably straightforward to deploy

stupid multisig

sarang: I remember you finding a solution for multisig though

Or is my memory betraying me? :P

Yes, but it requires non-ed25519 math

i mean, would it be crazy to have both protocols, triptych for standard txn and a CLSAG for multisig?

It needs operations in general RSA groups

oh wait one of them requires a thing

Which, I guess, is difficult to implement

gingeropolous: That would also make transactions stand out :P

FWIW verification does not require any non-ed25519 math

well yeah, but multisigs already stand out don't they?

^ :

Afaik no

no needed ;. maybe

i feel like semicolons are underused

Anyway, there are still some optimizations to be made for those numbers, including some generator caching and batching input keys across signatures from the same transaction

So don't treat that data as canonical by any means