FiloSottile / edwards25519

filippo.io/edwards25519 — A safer, faster, and more powerful low-level edwards25519 Go implementation.
https://filippo.io/edwards25519
BSD 3-Clause "New" or "Revised" License
131 stars 30 forks source link

Add function analogous to ScalarBaseMult for any Point #28

Open WernerVasquez opened 2 years ago

WernerVasquez commented 2 years ago

ScalarBaseMult uses a precomputed table, basepointTable, to speed up multiplications. It precomputes the table once when it is called the first time. Since multiplying the base point by a scalar is so frequent, it makes sense to perform this optimization.

There are other projects out there which frequently reuse other points. Monero is an example. In addition to the base point, it uses H to make Pedersen commitments. Upcoming protocol changes use even more such points.

It would be very helpful if a generic version of ScalarBaseMult existed. Perhaps it could be called ScalarMultPrecompute.

How I see this function working, is it would take a Point and a Scalar as its arguments. It would have a map of all previously precomputed points. It would check if the Point had been already precomputed and if not it would precompute it and add it to the map.

I use your library in a project of mine. While I have been able to do many things merely importing your project (and not forking it), this is one thing I cannot do (without forking it).

I would greatly prefer not to fork anything so fundamental as an ed25519 library.

WernerVasquez commented 2 years ago

I have written example code here

https://gist.github.com/WernerVasquez/c6f72fcb592042a287c76aec540a3bb0

This includes two ways to use the concept, one is a bit slower but may be useful

WernerVasquez commented 2 years ago

I have implemented these changes here:

https://github.com/WernerVasquez/edwards25519/tree/Additional_Precompute_Capability

I think it has improved the package overall.