-
cargodog[m]
I hope it proves useful :)
-
cargodog[m]
You are welcome to use it as you see fit, and you'll find all related work licensed very permissively (mostly MIT license). Any citation may simply refer to my pseudonym.
-
cargodog[m]
Hopefully I can get around to implementing the generalized `n`-ary Gray encoding scheme in my Arcturus implementation soon.
-
sarang
cargodog[m]: you might have to write your own (n,k) Gray encoding
-
sarang
Fun times!
-
sarang
I have a method from a paper
-
sarang
but have yet to integrate it into the scalar product computation
-
sarang
The method I've seen linked to is C code from a wikipedia entry, but it appears to be incorrect and doesn't actually generate a Gray code at all
-
sarang
Or rather, not the Gray code it claims (and not one that would be useful here anyway)
-
sarang
cargodog[m]: it would be interesting to know the benefits you see from the Gray code method for varying `N`
-
sarang
You're replacing a larger number of scalar-scalar multiplications by a much smaller number of them, but are including inversions instead... and those inversions are internally computed using optimized chains
-
sarang
So you have a fixed number of multiplications per inversion (something like 20 each)
-
selsta
Does this potential optimization help with verification time?
-
sarang
In theory yes
-
sarang
but I think it will depend highly on `N`
-
sarang
and for smaller `N` I expect the benefits are only negligible because of the reliance on inversions
-
selsta
N.. is the number of?
-
sarang
Group elements in the proof, corresponding to the anon set size
-
selsta
So larger ring size -> better speedup?
-
sarang
Well, I need to verify some initial results that cargodog[m] found with a related proving system
-
sarang
The issue is that scalar-scalar operations are _so_ much faster than scalar-group operations
-
sarang
and so you need to get rid of a _lot_ of scalar-only operations to make a difference
-
sarang
and inversions aren't free
-
selsta
sounds promising, even if the speedup is not confirmed yet
-
sarang
Yeah, it's a really clever idea, don't get me wrong :)
-
sarang
But I'm super curious to know how the benefit changes with `N`
-
sarang
I have code that will generate the underlying Gray codes, and now need to implement this into the Arcturus verifier
-
sarang
(it would also apply to Triptych)
-
sarang
-
sarang
Replacing the n-ary decomposition with an iterative Gray n-code
-
sarang
And there would be a few additional optimizations related to scalar squarings too