Decide on a generator API

[kayabaNerve]

Per #32, specifically,

I think the generator side of this definitely needs some experimentation, because while there are logical reasons for choosing a particular generator as standard, they aren't as natural as the singular choice of Field::ONE.

yet reminded by #44, now proposing again extending the generator API, I'd like to consolidate discussion and provide a proposal.

The main reasons for the generator function are simply convenience. I'd assume most people using cryptography will always use a single generator. Not only is providing the presumed standard preventing acquiring it, it prevents having to pass it around everywhere. Defining a generator also opens optimizations such as #44. I believe my code lost 15% of its performance when I stopped using dalek's table...

The main issue is almost all points are usable as generators and there's many such reasons to use alternative generators, which I won't bother to iterate here. Removing the generator function to acknowledge this would negatively harm most users AND add frequently unnecessarily API complications as everyone now passes it around at every level.

My suggestion maintains the simple path, while offering further flexibility.

1. Don't make generator() const
2. Offer a (potentially-std only?) wrapper for Groups allowing overriding their generators

Ideally, in my 'I have not yet wrote a line of code to see how well this'd work' opinion, it'd be an RAII-style push to scope a distinct generator. Internally, I presume a static mut HashMap<ThreadId, Vec> could handle pushed generators? So long as the returned lock wasn't usable under async...

The benefit is that then, a theoretically Schnorr PoK crate, could simply call generator(), not needing to take in a generator in its API, yet still provide PoKs across any generator.

Due to the complexities of the latter, I'm not here to explicitly ask for it in group. Solely call for GENERATOR to remain non-constant. This doesn't conflict with #44, adding a non-const function, yet it's my thoughts on the matter. Of course, I'd love to hear @str4d's thoughts since they said experimentation was needed.

[tarcieri]

Do you want alternative generators defined at runtime or compile time?

The current Group::generator() method doesn't take a reference to anything and at best can reference global state. I'm not sure what use cases there are for it in its current state which wouldn't be possible if it were promoted to a constant.

If you want a generator picked at runtime, it seems like you'd need something like fn generator(&self)? And in that case, it seems like you'd want a separate trait like DynGroup or something.

Some actual use cases would be helpful here.

[kayabaNerve]

The proposal I stated was at runtime using a static, which does not require a self which would re-introduce the bound of passing it around the API. If a new trait is created, then crates will ignore it, and we return to the same issue.

The use case is one I mentioned.

There is some theoretical Schnorr crate. It does not know of multiple generators. It does not care. Group provides generator() so it calls generator(). This is simple to it and sufficient for all of its cases. It maintains the simplest possible API.

I do not want a Schnorr PoK over G. I want it over H, where H is some arbitrary point.

Instead of forking the Schnorr crate to take a generator at every API call, and edit all my uses of it to pass around a generator, for the specific code needing a differing generator, I am able to write:

{
  let diff_generator = WrappedGroup<G>::push_generator(H);
  schnorr::prove::<WrappedGroup<G>>::(...)
}

Technically, I believe that's a HashMap<TypeId, HashMap<ThreadId, Vec>>, and I have yet to posit the RAII handling as I have yet to actually work on this for any notable amount of time.

This should be feasible so long as generator remains a function. The moment generator is a constant I do not see this as feasible. If we create a distinct type, then instead of rewriting all crypto with a more convoluted API, I'll simply have to rewrite all crypto over DynGroup. My goal here is too, without most friction, integrate this use case into the Group trait alone, to prevent fragmentation while enabling naive libraries.

If Group does make this a constant, I may move my libraries over, or I may just use a wrapper type preserving it as a function and write my libraries around that. While I tried a generator API for the Schnorr crate, it was convoluted and unhealthy. The reason I gave up on it was knowing this was a possibility, and a clean fix. It's also, IMO, a strong reason to keep it as a function.

Would you care to comment the exact use cases for making it const? Without also moving scalarmul, I'm unsure what most benefit is. While there is some, the ability to define a secondary generator H as Hash(G), that'd require a const hash function which I believe is similar to requiring a const scalarmul.

That isn't to decry the work made on crypto-bigint. It's to say I'm unsure what the use case today for it being const is, when not only do I not believe in generator as a constant, yet keeping it a function offers this clean paths to libraries ignorant to the generator, offering the simplest possible developer experience on all ends. I assume there is the long term mul of all functions being const-accessible, and this is simply the next step. Perhaps then there's reason for DEFAULT_GENERATOR and generator()? They'd just have to be appropriately documented.

[tarcieri]

So concretely, the issue is that an associated constant can't refer to a static, correct?

I'm still a bit unclear what your use cases are for a static versus a constant. It would make sense if it were quite large and you wanted to avoid duplication, or if you needed to use something like lazy_static or once_cell to define it, but I still don't understand in what cases that would make sense.

The benefit is that then, a theoretically Schnorr PoK crate, could simply call generator(), not needing to take in a generator in its API, yet still provide PoKs across any generator.

"not needing to take in a generator in its API" implies to me it's some global constant known at compile time? If so, why not just use different types for different generators?

[kayabaNerve]

Not just for a theoretical use case, even though yes, I do have such a Schnorr crate, I support FROST across different generators at this time and have considered deployments requiring it. I found it simpler to define a wrapper trait with its own generator function than wrap the Point struct/re-define the entire Group impl.

---

Was about to add the above context before you responded.

Sure. Having the constant be a pointer through some Rust black magic would also solve this for me.

Just supporting all cases. Monero generates ad-hoc generators for its key images (used to prevent double spends). I do proofs around them in higher level protocols. Proving you have the key which was used in a specific input can be done by signing for its key image, which is done with a generator of H(output_key) (not known at compile time), or a DLEq proof of output_key, key_image. The Schnorr proof is more efficient.

Currently, to do a Schnorr proof, I'd have to tell the Schnorr signature its generator. With generator() being a function and a nice wrapper, the Schnorr lib is untouched, people just wanting classic signatures don't need to pass G::GENERATOR as an arg to every call, yet this higher-level protocol which does need it can simply push the per-key generator and have ALL libraries underneath, simply using generator(), use its defined generator.

It's about silently being able to use all crates out there, without increasing the API burden. While yes, this comes with safety concerns (should the generator be transcripted, does the lib use some constant relative to an expected generator...), it's also the best solution I have. The other solution is to literally never use G::GENERATOR, either always using a custom function OR always passing an argument, even when most use cases won't need the argument, making it spam.

[tarcieri]

Just supporting all cases. Monero generates ad-hoc generators for its key images do proofs around them in higher level protocols. Proving you have the key which was used in a specific input can be done by signing for its key image, which is done with a generator of H(output_key) (not known at compile time), or a DLEq proof of output_key, key_image. The Schnorr proof is more efficient.

Having a static method return the generator (versus something like a GroupParams with fn generator(&self)) seems like it would preclude actual runtime dynamism around the generator, and it seems like some of the cases you're describing would need that?

A static method seems rather inflexible and doesn't afford much you can't do at compile time.

[kayabaNerve]

If the message refers to a global static, it doesn't need to take in self. That global static can then specify the currently in-use generator. My specific proposal, for this nicety I don't necessarily propose under this library, is for it to manage a stack of generators. So while each lib may say use this generator as it builds some long statement, when that lib returns the generator it told whatever is below to use also finishes. Please see the type I sketched and commentary on the RAII pattern.

This absolutely should be possible using a global static and the current generator function.

[kayabaNerve]

I'd like to withdraw whatever I said ~2.75 years ago and solely advocate moving the generator to an independent type from the group element.

An example would be as follows,

struct Generator;
impl ProvidesGenerator<EdwardsPoint> for Generator {
  const GENERATOR: EdwardsPoint;
}

Yet this could also be implemented with the G: Group as an associated type, reducing the length of the type arguments.

struct GeneratorA;
impl GroupWithGenerator for GeneratorA {
  type Group = EdwardsPoint;
  const GENERATOR: EdwardsPoint = !;
}

At this time, libraries must entirely forgo generator (which is pleasant) or they must completely re-define an instance of the Group trait (which is quite verbose with all the arithmetic implementations). That's why I advocate for a minimal struct for it, wrapping the underlying G: Group, which becomes the new standard for what type argument to accept.