-
cargodog[m]
Hi all. Long time lurker here. I wanted to share an Arcturus implementation I am working on. I hope to demonstrate some competitive performance benchmarks to maybe stir some more interest. I already have numbers outperforming Lelantus on a modest laptop. Anyways, I figured I would share if anyone finds it useful.
-
cargodog[m]
Disclaimer: This library is just a toy, so not recommended for serious use.
-
cargodog[m]
-
moneromooo
Thanks, sounds interesting
-
sarang
Nice! But Arcturus is not a ring signature scheme :)
-
mikerah[m]
Is there a policy against job posting on this chat?
-
cargodog[m]
<sarang "Nice! But Arcturus is not a ring"> Ah, indeed, calling it a "ring signature" is inaccurate! Stayed up too late hacking code the last few days, and didn't put enough time into the docs 🥴
-
Isthmus
Welcome, cargodog[m] 👋
-
cargodog[m]
Thanks Isthmus 👋
-
sarang
cargodog[m]: Does the code support batch verification with common input sets?
-
sarang
mikerah[m]: job posting?
-
mikerah[m]
<sarang "mikerah: job posting?"> I'm hiring and I know the expertise in this group is what I'm looking for
-
sarang
I guess I don't have a problem with it being brought up in this channel, but I don't know how other people feel about that
-
sarang
Could certainly mention in #monero-research-lounge to be safe
-
moneromooo
IMHO if it's just a one liner with a link to something that really is about related research, it's fine. It's when people repeatedly spam the same thing several times it gets irritating.
-
sarang
I agree
-
mikerah[m]
Thanks sarang and moneromooo
-
mikerah[m]
Here it is:
iacr.org/jobs/item/2294 . I'm hiring for a Research Engineer (more emphasis on the Engineer part). If interested, you can send an email to careers⊙hc with the subject line "Research Engineer" along with your resume and something interesting you've built or published
-
sarang
Another very minor update to the Arcturus preprint:
eprint.iacr.org/2020/312
-
sarang
-
sarang
and the diff for the previous, more substantial, update:
SarangNoether/skunkworks 12f4579
-
sarang
I'd make the same update to Triptych too, but this would push it over the page limit for ESORICS
-
sarang
because apparently page limits are still a necessary thing for some reason :/
-
sarang
No change to security or anything, just better explanation of the completeness proof
-
cargodog[m]
sarang: Indeed it does support batch verification. The default verification method (`ArcturusGens::verify()`) allows you to provide a batch of proofs that share the same anonymity set. Im currently working on improving the docs to make this more understandable.
-
cargodog[m]
I realize comparing Arcturus to Lelantus is not "apples to apples", but using a similar config (anonymity set of 65535, 3 inputs per TX, 3 ouptuts per TX), I was able to outperform the numbers published in the Lelantus paper on my comparable laptop. Im not confident in my benchmarks yet, soI don't want to share numbers and make bold claims yet, but initial results are very promising. Arcturus really is
-
cargodog[m]
beautifully efficient :D
-
sarang
cargodog[m]: did you use a similar Lelantus implementation, with the same underlying curve library?
-
cargodog[m]
sarang: oops, forgot to tag you in my response
-
cargodog[m]
No I did not, hence all my disclaimers and reluctance to share concrete numbers :)
-
cargodog[m]
I am only basing this off of the numbers published in the Lelantus paper. My goal now is to get Lelantus building and provide more meaningful comparison
-
sarang
Ahok
-
kenshamir[m]
" (ArcturusGens::verify()) allows you to provide a batch of proofs that share the same anonymity set"
-
kenshamir[m]
Does this mean that if I wanted to create a tx, I could use every previous output as a decoy?
-
sarang
Yeah, I didn't put much weight on the comparison numbers in the Lelantus preprint for that reason
-
kenshamir[m]
Granted that everyone else does it too
-
sarang
I always prefer op counts for this reason
-
sarang
Unless there are implementations with common libraries and (ideally) optimization methods
-
kenshamir[m]
So essentially everyone in the block uses the same anonymity set, and the nodes batch verify every transaction
-
sarang
kenshamir[m]: one option is to use multiple fixed input sets, so proofs sharing even some of the fixed sets could get some benefit from partial batching
-
cargodog[m]
kenshamir: Technically yes, but while Arcturus is leap years ahead of anything else, very large anonymity sets still take a long time to prove/verify. I was able to get proof/verification on the order of milliseconds with an anonymity set of ~65535 outputs, but that seems to be a practical upper limit (IMO) that could be used in real time transaction processing
-
sarang
And depending on the input selection method, proofs in nearby blocks/transactions are more likely to share such inputs
-
cargodog[m]
<sarang "Yeah, I didn't put much weight o"> Indeed. And looking at op counts alone, Arcturus is a clear winner :D
-
sarang
:D
-
sarang
I hope the preprint and/or Python/C++ implementations were clear and useful!
-
sarang
I'd welcome any comments or suggestions you have on them
-
sarang
esp. since Arcturus is not currently under consideration for publication
-
kenshamir[m]
This has definitely got me interested in Articus :D
-
sarang
(that damn hardness assumption...)
-
kenshamir[m]
Sorry still can't spell
-
sarang
kenshamir[m]: I am Articus!
-
kenshamir[m]
*Arcturus
-
cargodog[m]
I worked mostly off the preprint. It was like reading a paint by numbers guide. Very easy to follow :D
-
sarang
No, I am Articus
-
sarang
Nice! I have yet to look into the code, but will try to do so today
-
kenshamir[m]
No...
-
kenshamir[m]
I am Articus!
-
sarang
I'm especially interested to see how you implemented batch weighting etc.
-
sarang
My Python proof-of-concept implementation shows one way to do it that reduces to a single multiscalar multiplication
-
cargodog[m]
Hardness assumption is actually my primary motivation here. I hope if I can put forth some impressive numbers, that may attract more eyes to the protocol, and hopefully some of those eyes can give us confidence (or debunk) the hardness assumption
-
sarang
with maximal generator reuse
-
sarang
I assume you do this as well for efficiency
-
sarang
cargodog[m]: awesome!
-
sarang
I was really disappointed that the initial Arcturus reviewer didn't do a better job with their supposed counterexample, which was incomplete and frankly really shoddy work
-
cargodog[m]
Yes, maximal generator reuse
-
kenshamir[m]
In Arcturus, what is the bottleneck for large anonymity sets?
-
sarang
Verification is still linear in input set size
-
sarang
technically O(n/lg(n))
-
cargodog[m]
the `ArcturusGens` provides a context of generators that can be largely reused
-
sarang
cargodog[m]: I meant between verification equations
-
sarang
e.g. all the commitment stuff contains reusable generators
-
sarang
so you can verify Eqs. 1 and 2 in half the time
-
sarang
(half-ish)
-
sarang
Again, I should just read the damn code =p
-
cargodog[m]
The practical issue I find, is coming up with a construct that allows users to build TXs with a shared set, without revealing information about their members within the set.... I'm not sure theres an easy solution to this
-
sarang
Lelantus' method is to use a windowed common input set
-
sarang
They have a blog post about it somewhere
-
sarang
I don't recall the exact link
-
cargodog[m]
sarang: yes, maximal reuse between proofs. The bit commitments (eq1&2) cannot share gens IIRC, but much of the rest of the proofs share common generators
-
sarang
Sure they can
-
sarang
The tensor commitments all use fixed generators
-
sarang
Those can be weighted together within a proof, and between proofs
-
sarang
And of course you have a few other global generators in Eqs. 3-5
-
sarang
but those are minimal
-
cargodog[m]
Lelantus windowed approach seems untenable to me (no hate). They claim a window of ~65k UTXOs will last 12 months, but they expect 16K minimum before you can spend out of the set... so wait 3 months to spend an output? This also breaks down as you consider a chain that might scale to much larger volumes
-
cargodog[m]
Ah, I misspoke. I share generators for the bit commitments, but I verify them individually
-
cargodog[m]
eq3-5 are verified in aggregate
-
sarang
Why not combine 1-2 together, and then between proofs?
-
sarang
That's a pretty easy way to shave off some time
-
sarang
It's small compared to the number of total curve points for large sets, but it's not nothing :D
-
cargodog[m]
I do combine 1-2 together, but I wasn't sure if I could aggregate across proofs and still have the same guarantee that each proof was only committing to a single input at a time (instead of some malformed comittment to many bits)
-
cargodog[m]
I would love to hear I am wrong in this assumption :D
-
sarang
You apply random weights, just like you do between equations
-
cargodog[m]
ah duh!
-
sarang
ya
-
cargodog[m]
great point
-
sarang
The weighting method is identical across all combinations :)
-
cargodog[m]
Thanks, I will add that to my list of improvements!
-
sarang
and then you just sit down and write out how to combine the common gens
-
kenshamir[m]
cargodog: Which backend did you use for the benchmarks?
-
sarang
So yeah, you only need to use any generator exactly once in the multiscalar multiplication
-
kenshamir[m]
I'm hesitant to look over the code, as I would like to make an implementation when I'm free to see where our ideas diverged
-
cargodog[m]
I am using a SIMD backend for the underlying curve library (Ristretto group on Ed25519) and ASM_SIMD backend for the Blake2 implementation, which I use for the indexed hash function
-
sarang
Not Blake3 yet?
-
sarang
=p
-
sarang
(I don't know if there is a good standard implementation of that yet)
-
cargodog[m]
Not yet:D
-
sarang
The speed benefits for Blake3 look insane
-
cargodog[m]
I could get into a long discussion about selecting hash methods, but probably not fruitful here :p
-
sarang
lol, how so
-
sarang
For speed, or security in particular use cases?
-
cargodog[m]
Most Blake3 improvement comes from multi-threaded processing of large sets
-
sarang
I wonder if that was used in the numbers I saw :/
-
sarang
I did know about the parallelization benefits
-
sarang
but assumed this wasn't part of comparisons
-
sarang
Maybe that was not the case
-
cargodog[m]
but on small sets, its practically similar to Blake2b
-
sarang
Blake2 it is!
-
sarang
heh
-
sarang
At any rate, surely that's peanuts compared to the bulk of the curve operations
-
kenshamir[m]
cargodog: was there anything you found difficult while implementing Arcturus? Speaking in general. Always nice to hear problems when implementing cryptography or maybe some general "gotchas" that you did not expect
-
cargodog[m]
My understanding was their published numbers leveraged parallelization, and their point was that wasn't possible with other hash functions. Which is great, no doubt! But not an apples to apples comparison, and not perfect for all situations
-
sarang
boo
-
cargodog[m]
Peanuts indeed :D
-
sarang
But I suppose it's still really helpful for large data
-
sarang
It's so cool to see another implementation in place!
-
cargodog[m]
kenshamir: Hard to say. ZK proofs are generally not "easy", but I found the Arcturus paper quite easy to follow compared to other proof systems
-
sarang
My Python implementation was just an easy proof-of-concept for the algebra, and to demonstrate it
-
sarang
The C++ implementation is useful for timing, but uses the Monero libraries
-
sarang
I suppose the batching was perhaps more tricky, since it wasn't specifically written out?
-
sarang
I thought about it, but figured reviewers would just request to have that removed anyway
-
cargodog[m]
I actually never say your Python implementation. I'd love to take a look. Have a link?
-
sarang
-
cargodog[m]
Batching was the most difficult piece to wrap my head around
-
sarang
Huh, looks like I didn't implement cross-proof batching after all... thought I had
-
sarang
but I only do intra-proof combinations
-
sarang
I should do cross-proof too
-
sarang
Yeah, batching ends up becoming an irritating game of keeping track of weights and combinations
-
sarang
Note that the Python one uses a custom curve library and isn't intended for security or speed, just as a demo
-
cargodog[m]
I have to step out for now o/
-
cargodog[m]
I will check back later if you have any questions. Also, feel free to drop an issue on github (or even submit a patch :D). My contact email can also be found in the project Cargo.toml
-
sarang
I also show in that code how to embed secret data in proofs for later extraction, using a common PRNG seed
-
sarang
Thanks cargodog[m]
-
cargodog[m]
I look forward to that!
-
sarang
I might update the preprint to include that embedding stuff
-
sarang
Gah, I never pushed the weighting stuff in the Python at all... I'll do that
-
sarang
It's in the C++ timing code though
-
sarang
How silly
-
sarang
-
sarang
If you're interested cargodog[m], feel free to stop by next Wednesday at 17:00 UTC to the research meeting here, where you'd be welcome to share your code to more people
-
sarang
I wonder if anyone else has been working on Lelantus implementations in Rust, which could be useful for comparison if there are common-ish benchmarks
-
sarang
But hot dang, it'd be neat if Arcturus was more efficient in practice :D
-
gingeropolous
i thought arcturus used some moon math assumptions and thats why its sorta been a maybe
-
sarang
It does use a new and untested cryptographic hardness assumption
-
sarang
But as cargodog[m] said, having some solid numbers for comparison could help to get additional eyes on it
-
gingeropolous
indeed.
-
sarang
FWIW I consider the assumption to be pretty reasonably
-
sarang
It just doesn't cleanly reduce to a more standard tested assumption
-
sarang
s/reasonably/reasonable
-
monerobux
sarang meant to say: FWIW I consider the assumption to be pretty reasonable
-
selsta
Could such an assumption get audited?
-
sarang
goot bot
-
moneromooo
good researcher
-
sarang
Ehhhh not really
-
moneromooo
:o
-
sarang
Such assumptions acquire confidence with time and a lot of people poking them with sticks
-
sarang
A thorough audit from qualified cryptographers could certainly be a step in that direction
-
sarang
Fortunately both Triptych and Arcturus have essentially identical verification complexity
-
sarang
it's the proof size that shows a difference
-
sarang
Submitting the preprint for additional review will also help
-
sarang
I should add some additional narrative around the assumption, to avoid a repeat of the first reviewer, who I really don't think read it completely (and certainly didn't actually work out their counterexample in full)
-
sarang
Oh, cargodog[m]: another note that may be of interest to you
-
sarang
You can actually do a single hash execution for the `mu` terms instead of one each, and substitute a field multiplication instead
-
sarang
So instead of `mu_k = hash(stuff,k)` for each `k`
-
sarang
You set `mu = hash(stuff)` and then define `mu_k = mu^k`
-
sarang
and you can define the former iteratively
-
sarang
So if your scalar ops are sufficiently faster than your hash function, you can shave some time off that
-
sarang
I demo this in the C++ code that I linked
-
» sarang updates the preprint too
-
sarang
Note that there's nothing wrong with the original method, except the speed difference
-
sarang
s/former/latter
-
monerobux
sarang meant to say: and you can define the latter iteratively
-
sarang
good bot
-
sarang
Not my day for typos :(
-
ArticMine
<sarang> it's the proof size that shows a difference <---- Which begs the question can we increase the penalty free block weigh if needed and go ahead with Triptych?
-
dEBRUYNE
I think he is referring to the proof size difference between Triptych and Arcturus
-
ArticMine
Yes this is my point
-
ArticMine
We can compensate for this if needed by increasing the penalty free block weight above 300000 bytes
-
sarang
I suppose... but I meant that all other things being equal, it's obviously better to choose a smaller proof size...
-
sarang
Also note that proof size and verification do not scale the same
-
sarang
it's similar to how bulletproofs scale
-
sarang
log size, linear verify
-
ArticMine
When the confidence in the assumption becomes more mainstream we can them move from Triptych to Arcturus
-
sarang
Heh, we haven't moved to Triptych
-
ArticMine
Triptych is still way better than the current situation
-
ArticMine
What concerns me is a form of paralysis here
-
ArticMine
For example tune Triptych to close to the current verification time, and then determine a ring size and proof size. We can then make a reasonable judgment as to whether the change is worthwhile
-
ArticMine
By tune I mean set the Triptych parameters
-
sarang
I have yet to hear anything about practical multisig concerns, which I have asked about many times
-
ArticMine
You mean Triptych breaks or may break multisig?
-
gingeropolous
ArticMine, i agree. I feel like optimizations will be found for triptych, or moore's law will come along
-
gingeropolous
but im just a guy with opinions
-
sarang
It requires more complex crypto that implies different library functionality, as I have discussed many times
-
ArticMine
Yes but, if Triptych is not on the radar then support for multisig is not likely to be addressed
-
rbrunner
sarang: I think I managed to miss all your questions about "practical multisig concerns" and "different library functionality". Is this about handling multisig which might more complicated still, or about math and crypto?
-
rbrunner
Even more complicated handling would not worry me too much, I am of the opinion that for any sensible multisig you need some good tools anyway
-
moneromooo
AFAIK it's possible, but requires using Paillier (or similar name) crypto, which is fairly new IIRC (or at least the scheme using this crypto is). So a chunk of new crypto code.
-
sarang
Paillier is well understood but assumes math on arbitrary RSA groups
-
sarang
This functionality is required for safely computing the necessary proof components for multisig key images
-
rbrunner
Do I correctly read that as "a lot of work to implement" and "possibly needs audits"?
-
sarang
So it's not just additional crypto primitives, it's entirely different library support for non-ed25519 stuff
-
sarang
a _lot_ of work
-
sarang
and yes, would _absolutely_ need external review
-
rbrunner
I see
-
rbrunner
Well, as of now multisig is a somewhat unloved step-child, but who knows, maybe one day it becomes all the rage, with Monero's importance slowly but steadily ramping up
-
sarang
but FWIW current multisig doesn't use the multi-round work that suraeNoether and I wrote in our threshold multisig paper anyway...
-
sarang
but at least that stuff is all 25519
-
sarang
Note that Omniring, Arcturus, Triptych, RCT3 all require a similar approach
-
sarang
One version of Omniring maintains the current key image structure, but still requires some nonstandard operations in the proofs
-
rbrunner
And all this in hardcore C++ ...
-
sarang
So yeah, any discussion of a real implementation of this stuff, if multisig is desired, requires a heck of a lot of additional longer-term planning and work
-
sarang
If you don't need multisig, it's much easier
-
rbrunner
Yes, was thinking about this, you can't say "for the next half year or so multisig takes a break". Either it's there from the start, or it goes overboard, I would say
-
moneromooo
I think we have to have multisig if it'd be possible to send to a current multisig address and that multisig address would not otherwise be able to spend the monero.
-
moneromooo
If that's not the case, there's a choice.
-
ArticMine
<sarang> So yeah, any discussion of a real implementation of this stuff, if multisig is desired, requires a heck of a lot of additional longer-term planning and work <---- How transferable would this work be to Arcturus for example?
-
sarang
The math used to compute the key image is identical between Triptych, Arcturus, and RCT3
-
rbrunner
Just for curiousity: Would it help if we give up tx uniformity, i.e. multisig tx have some different structure in the blockchain? Or is this an altogether stupid question?
-
moneromooo
atm, a node can't tell if a spender is multisig or not. So you'd have to allow CLSAG and triptych.
-
sarang
Plus there's a joint computation of the output secret key, which means a joint computation of the key image
-
rbrunner
Is that bad, terrible, or a catastrophe? Such a "double protocol solution"
-
ArticMine
So then it can make sense to do the multisig work for Triptych and then move to Arcturus for example
-
sarang
Avoiding Paillier means the players all learn the full secret key, and can arbitrarily spend without other players' consent in a race condition
-
rbrunner
That's definitely bad :)
-
sarang
The tricky part is that the current key image format is linear in the secret key
-
sarang
These new constructions are not linear in the secret key
-
sarang
This is much more efficient, but means you can't get away with simple linear combinations anymore
-
sarang
You need a particular inversion trick
-
sarang
You also need some additional zkps
-
sarang
It gets complicated
-
rbrunner
It's already what I would call complicated today ...
-
sarang
Well, it would become much more so
-
rbrunner
Splendid
-
rbrunner
I can easily imagine a scenario where we try to build our "loose consensus", and that will then result in giving up multisig, with a subsequent shit storm from people in the shadows so far, and also regret later on
-
ArticMine
I believe we need a more defined course of action, even if this comes down to the slow increase in ring size via the sequence of primes
-
ArticMine
I do not belive give up multisig is the way to go
-
rbrunner
Yeah, but who knows which way opinion would sway, with fast Triptych introduction without multisig in front of the eyes
-
rbrunner
It's mightily tempting
-
rbrunner
That's why I worry about that political stuff
-
ArticMine
The sequence of primes can take care of the political stuff and put pressure on the adversaries. The reason I like it is because of technology is not static either
-
rbrunner
"Sequence of primes" simplifies the crypto and the math?
-
moneromooo
No.
-
ArticMine
What I mean is increasing the ring size under the current implementation at each HF to the next prime number
-
rbrunner
Ah, alright
-
sarang
The prime number thing is merely a coincidence, or a whimsical design choice
-
sarang
but nothing to do with the math
-
ArticMine
Of course
-
rbrunner
So no new protocol for possibly a long time then
-
moneromooo
Cointelegraph: "Usage of primes in Monero is merely a coincidence"
-
rbrunner
And maybe some breakthrough on the way?
-
sarang
Depends if someone really wants to implement Paillier and the associated multisig protocol
-
rbrunner
Lol
-
rbrunner
Really wants, and really does :)
-
sarang
Basic Triptych and Arcturus prove/verify functionality is already implemented in the codebase
-
sarang
Intra-transaction batching for Triptych, too
-
ArticMine
<sarang> Depends if someone really wants to implement Paillier and the associated multisig protocol <--- So this is then the holdup for Triptych?
-
sarang
The primary one
-
ArticMine
What else?
-
sarang
There are other design choices around input anonymity set size, input binning
-
sarang
Output set migration
-
gingeropolous
could the 2 protocol solution have legs? Standard transaction -> triptych. multisig -> CLSAG.
-
gingeropolous
i mean, i have no data, but i can claim no one uses multisig
-
sarang
This would effectively separate the output set
-
sarang
The key image types are different
-
ArticMine
... and complicate migration
-
rbrunner
Migration from where to where?
-
sarang
You wouldn't be able to select old pre-Triptych outputs for rings
-
rbrunner
I mean, if you are basically free to use whichever protocol suits your fancy today
-
sarang
Since you can't test old and new key images together
-
rbrunner
This all does not sound very funny. No radically different ideas to the rescue? Some completely different approach with the same end result: Things only move if m/n people give green light, *somehow*?
-
sarang
I would love a method that didn't require a cooperative inversion to compute a joint key image
-
sarang
but it doesn't work
-
rbrunner
I mean, Bitcoin multisig looks so simple, and so elegant, but I am sure Sarang comes up with an argument why that does not work for Monero in almost zero time :)
-
sarang
Because Bitcoin authorizes transactions using script conditions
-
sarang
Monero authorizes transactions using only signatures
-
rbrunner
So we introduce scripts!!! (ducks and covers)
-
sarang
Changing that would still require the key image stuff, unless the protocol were radically changed in a way that's almost certainly hugely unsafe
-
rbrunner
No, seriously, I start to wonder what is the least bad of all solutions
-
rbrunner
Are signatures, quite in general, safer than scripts? Or does that comparison make no sense?
-
sarang
It enables the signer ambiguity
-
gingeropolous
not that it matters, but the rational put forth in the great whitepaper is "The scripting system in Bitcoin is a heavy and complex feature. Itpotentiallyallows one to createsophisticated transactions [12], but some of its features are disabled due to security concerns andsome have never even been used [13"
-
rbrunner
Hmm, wouldn't we need only a small part of it for supporting multisig?
-
sarang
Keep in mind that with the way outputs exist today, you need to be able to compute key images to avoid double-spend attempts
-
rbrunner
Basically "This tx must have x valid signatures". And then the signatures themselves.
-
sarang
and the key image part is what makes newer constructions complicated
-
moneromooo
You'd need to be able to tell those sigs aren't from the same keys.
-
rbrunner
Too bad I never was really able to grok key images
-
gingeropolous
its sorta just like hashing a file. its a fingerprint of a given key. so you can detect if there are duplicates.
-
sarang
Everyone has an additive share of the output secret key, and you need to compute a particular group element using the inverse of the sum of those shares
-
sarang
that's the new key image format
-
rbrunner
You'd need to be able to tell those sigs aren't from the same keys. <--- Is that solved in Bitcoin, or one of said potential problems?
-
moneromooo
Keys are public in Bitcoin.
-
rbrunner
Ah.
-
rbrunner
Makes sense.
-
gingeropolous
well i put up a super sophisticated reddit poll to see if multisig is worth holding up ringsize a bajillion
-
rbrunner
Don't you dare :)
-
UkoeHB_
wow even more sophisticated than I expected
-
gingeropolous
lol
-
sarang
Hopefully people don't answer for themselves...
-
sarang
"Yes, and I keep my key in a box at this bank..."
-
rbrunner
-
zkao
-
midipoet
well that's a conversation and a half in here. has been a while since we had that sort of natter.
-
sarang
Yep, and I have a working example in Python of the key image construction too
-
sarang
-
kenshamir[m]
@sarang is it not possible to delegate some parts to a zk proving system like bulletproofs?
-
kenshamir[m]
<sarang "Depends if someone really wants "> I’m also guessing that this would preferably be in C++?
-
sarang
Delegate in what way?
-
sarang
The players need compute the key image
-
kenshamir[m]
<sarang "Delegate in what way?"> Not entirely sure, I haven’t looked over the protocol yet, was thinking there were some parts which could be put into a zero knowledge proof
-
kenshamir[m]
A trivial example would be to make the key image set a sparse merkle tree and prove in zero knowledge that the key that was just computed is not in the tree
-
kenshamir[m]
A different example would be to offload the rangeproof portion to a zkproof, but I think bulletproofs may have the best verification time for rangeproofs with a trustless setup
-
sarang
Oh I see what you mean
-
cargodog[m]
sarang: Thanks for the good ideas. I'll try to drop by the next dev meeting and share there.
-
cargodog[m]
* cargodog frantically takes notes
-
cargodog[m]
sarang: Here is another moderate performance optimization that may be useful to anyone implementing. Not sure if its relevant enough to describe it in the paper, but perhaps its of interest.
-
cargodog[m]
It applies to any proof based on the "One out of Many" construction by Groth & Kohlweiss. IIRC, in a previous work, I observed ~5% performance improvement, but that work was not an apples to apples comparison with Arcturus.
-
cargodog[m]
-
cargodog[m]
The point is to iteratively compute set coefficients over Gray coded indices, instead of the usual binary number sequence.... it takes a small tweak to generalize it to `n-ary` proofs, but its worth the effort
-
sarang
Ooh that's interesting...
-
sarang
Thanks cargodog[m] !!
-
sarang
I'll take a look
-
sarang
Any previous work I should cite on this?
-
cargodog[m]
Nothing formal. Just a proof of concept implementation in another project.
-
cargodog[m]
It saves roughly `m/2` scalar multiplications per inclusion proof... which can add up quickly for large set sizes
-
sarang
I'm surprised that would lead to 5% improvement... was that in verification or proving?