
dEBRUYNE
sarang: I see, thanks

xmrmatterbridge
<rbrunner7> As far as I can understand the results of the preprint sarang linked late last night, things look pretty good for what Monero successively implemented over the last 3 years.

UkoeHB_
sarang: for Arcturus, with one shared ring for each signature, if there are 10 inputs and eg ring size 256, would there be 2560 total ring members? Rather than 256 total ring members.

sarang
In your example, only 256 outputs would be referenced/used for the anonymity set

sarang
Arcturus proves that the signer controls a subset of the anonymity set (along with other statements relating to linking tags and balance), rather than a single element of the set

sarang
The idea is that it replaces a signature _per spend_ with a signature _per transaction_

sarang
Instead of `k` separate 1of`N` signatures, it's a single `k`of`N` signature

sarang
UkoeHB_: worth noting that there's nothing stopping you from making a rule that, say, higher`k` signatures must have higher `N` too, or something like that

sarang
The security model says nothing about this

UkoeHB_
Im just thinking about verification/scaling for N/k.

sarang
Note that `k` separate Triptych 1of`N` proofs scale roughly the same as a single `k`of`N` Arcturus proof (for reasonable `k`)

sarang
in verification time

sarang
not in size

sarang
Verification depends almost entirely on the number of group elements involved

sarang
and if you use a common anon set in Triptych, you're not adding that many new generators (but you are adding some per proof)

sarang
For reasonable `k`, though, that's mostly overshadowed by `N` >> `k`

moneromooo
So the more outputs someone spends in a tx, the more likely they each ring member is to be actually spent ?

moneromooo
ie, if someone spends 128 outputs in a tx, we know they're all spent ?

moneromooo
er, 256.

UkoeHB_
ah so in Triptych you can get a lot more ring members total for the same verification cost?

UkoeHB_
e.g. with >2 inputs

sarang
moneromooo: this would be the same as if you had a 256spend transaction with the same 256 ring members across all signatures

sarang
UkoeHB_: Triptych and Arcturus have essentially the same verification cost

moneromooo
Such a ring would mean we know the'yre all spent. So I'll take htat as a yes.

sarang
moneromooo: yes; if `k` == `N` in Arcturus, all members of the anon set would be known to be spent in that transaction (assuming unique linking tags etc.)

sarang
UkoeHB_: you can compare the relationships between `k` and `N` with the performance tests in my `monero/arcturus` and `monero/triptych` branches

sarang
Those also include balance proofs

sarang
UkoeHB_: does that explanation make sense?

UkoeHB_
yeah I think I got it

sarang
It's kinda like in Bulletproofs, how multiple proofs have a common portion and a perproof portion

sarang
and provided that the common portion is much larger than the perproof portion, batching is beneficial

sarang
*more beneficial

sarang
It's similar in Triptych verification with a common anon set

UkoeHB_
right, Im just thinking about binning techniques and the differences between Arcturus and Triptych

sarang
Any time you have linear combinations to zero with common generators, you can batch and see a benefit

sarang
Yeah, I had asked about that a while ago and have had it in the back of my mind for a while

sarang
FWIW Triptych still works fine if you use separate anon sets per spend, but of course you lose basically all the benefits of batching

sarang
(not entirely due to how multiexp works, but almost entirely)