I hope it proves useful :)

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.

Hopefully I can get around to implementing the generalized `n`-ary Gray encoding scheme in my Arcturus implementation soon.

cargodog[m]: you might have to write your own (n,k) Gray encoding

Fun times!

I have a method from a paper

but have yet to integrate it into the scalar product computation

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

Or rather, not the Gray code it claims (and not one that would be useful here anyway)

cargodog[m]: it would be interesting to know the benefits you see from the Gray code method for varying `N`

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

So you have a fixed number of multiplications per inversion (something like 20 each)

Does this potential optimization help with verification time?

In theory yes

but I think it will depend highly on `N`

and for smaller `N` I expect the benefits are only negligible because of the reliance on inversions

N.. is the number of?

Group elements in the proof, corresponding to the anon set size

So larger ring size -> better speedup?

Well, I need to verify some initial results that cargodog[m] found with a related proving system

The issue is that scalar-scalar operations are _so_ much faster than scalar-group operations

and so you need to get rid of a _lot_ of scalar-only operations to make a difference

and inversions aren't free

sounds promising, even if the speedup is not confirmed yet

Yeah, it's a really clever idea, don't get me wrong :)

But I'm super curious to know how the benefit changes with `N`

I have code that will generate the underlying Gray codes, and now need to implement this into the Arcturus verifier

(it would also apply to Triptych)

It would apply to these scalar computations: github.com/SarangNoether/skunkworks…urus/arcturus/arcturus.py#L375-L388

Replacing the n-ary decomposition with an iterative Gray n-code

And there would be a few additional optimizations related to scalar squarings too