An ecmult_gen for user-defined generators

[victorshoup]

If I understand correctly, ecmult_gen computes x * G for a specific generator G using a pre-computed table T_G that depends on G.
Looking at the code, it seems that all the logic is there to compute other tables T_H for any generator H.
Would it be reasonable to ask for a version of ecmult_gen that worked for an arbitrary generator H using a table T_H pre-computed by the user and passed into the function?
I have applications where this would be nice to have.
I don't think such a function exists right now, but please correct me if I'm wrong.

While I'm asking, is there or would it be easy to build a function like ecmult_gen that uses a pre-computed table to speed things up but doesn't try to hide the secret scalar x?

[sipa]

Would it be reasonable to ask for a version of ecmult_gen that worked for an arbitrary generator H using a table T_H pre-computed by the user and passed into the function?

Do you imagine this to be something done at runtime, or at compile time? The current ecmult_gen code expects a single fixed table, but the exhaustive-small-group tests use a dynamically-constructed one. Supporting additional generators, whether static or dynamic, will need some way to pass a pointer to the table around, but that wouldn't be too much work I think.

As for scope, we tend to think of libsecp256k1 as a high-level library whose public API implements protocols, not primitives, and the internal implementation is whatever is needed for those. So in that sense, absent a new module for a protocol we intend to support, it wouldn't be a great fit.

I don't think such a function exists right now, but please correct me if I'm wrong.

Indeed, except internally in tests_exhaustive.c, where a (tiny subgroup of) a different curve over the same field is used for testing purposes.

While I'm asking, is there or would it be easy to build a function like ecmult_gen that uses a pre-computed table to speed things up but doesn't try to hide the secret scalar x?

The "normal" ecmult() function includes this functionality; it does a multi-base multiplication with a separate scalar for the generator (so $a_0 P_0 + a_1 P_1 + \ldots a_{n-1} P_{n-1} + g G$, for scalars $a_0, \ldots, a_{n-1}, g$). With $n=0$, you get a pure gG multiplication, which does use a compile-time generated table as well (a different one from the one used by ecmult_gen, though).

---

Benchmarks (see ./bench_ecmult):

Benchmark                     ,    Min(us)    ,    Avg(us)    ,    Max(us)    

ecmult_gen                    ,    11.8       ,    11.9       ,    12.0    
ecmult_const                  ,    28.0       ,    28.1       ,    28.5    
ecmult_0p_g                   ,    15.6       ,    15.6       ,    15.8    

ecmult_gen and ecmult_const are constant-time, the rest are variable time. ecmult_const works with an arbitrary base point, without any precomputation. ecmult_0p_g is benchmarking a pure generator multiplication with ecmult(). Actually, I'm quite surprised that is slower than ecmult_gen! It hasn't been specifically optimized for pure generator multiplication, but still...

[victorshoup]

Thanks @sipa for your reply! Sorry for the delay on my part.

I understand your point of view on what is and isn't included in the API.
That said, I'm interested in building bleeding edge non-standard protocols and primitives :-)
It would be nice to have a highly optimized library of primitives available for this.
Of course, I understand the wisdom of not "rolling your own" crypto, but I am in a position to take such risks with some confidence...at least for academic prototyping and benchmarking purposes.
Maybe there is different library you would recommend?
Or I could fork this one, but that is not something I really want to do either.

[sipa]

That said, I'm interested in building bleeding edge non-standard protocols and primitives :-)
It would be nice to have a highly optimized library of primitives available for this.

Yes, I understand. There has been some work to expose a "hazmat" more low-level API in the library, for people who want access to more fine-grained operations and willing to take the risks that entails, see #1635, but there isn't much progress.

Of course, I understand the wisdom of not "rolling your own" crypto, but I am in a position to take such risks with some confidence...at least for academic prototyping and benchmarking purposes.

Yes of course, I know who you are. (I'm Pieter, we met at Chaincode Labs a while ago). I also don't think discouraging experimentation is a goal on itself - but in libsecp256k1 we're at least aiming to make sure the easier way of implementing things is the safer one to avoid accidental foot-shooting.

Maybe there is different library you would recommend?

No experience with it myself, but I do know about https://github.com/LLFourn/secp256kfun at least (Rust, not C).

[victorshoup]

On my laptop (Apple M1 Max), I get:
Benchmark , Min(us) , Avg(us) , Max(us)

ecmult_gen , 15.6 , 15.7 , 16.0
ecmult_const , 30.3 , 30.6 , 30.9
ecmult_1p , 23.6 , 23.7 , 23.8
ecmult_0p_g , 16.6 , 16.7 , 16.8

So const is about 2x gen, which is about the same as 0p_g.
So that's not bad...
Maybe this is good enough...