secp256k1_ecmult_gen_context_build allocates 90KB on the stack

[tdaede]

secp256k1_ge_t prec[1024];
secp256k1_gej_t precj[1024]; /* Jacobian versions of prec. */

Microcontrollers have expensive SRAM and cheap Flash. These should be turned into precomputed tables, at least as an option.

[DavidEGrayson]

There is already a discussion happening in issue #189 about how to make this library work well on microcontrollers. I suspect it would be best to just have a precomputed context that is neither created nor destroyed, and gets stored in flash, but I haven't looked into it.

[laanwj]

Precomputing the tables and storing them in the executable could also help in the libbitcoinconsensus case, where we don't really want a dynamically allocated context.

[gmaxwell]

Precomputing verify would be very undesirable-- it's 1.3MB with current settings (which are optimal for performance, when enough memory is available).

Libbitcoinconsensus really should be really using a context in order to avoid the constant dynamic memory allocations all through its internals which it currently has.

[laanwj]

The context brings a lot of issues for users, and risks to use more memory in total. Every client of secp256k1 makes its own context, all lugging along 1.3MB of the same read-only data. Say a program uses both secp256k1 directly and through libbitcoin_consensus. This means (at least) two contexts. Passing an existing secp256k1 context to libbitcoin_consensus would leak implementation details. Also it is not clear whether the libbitcoin_consensus contexts may be shared between threads. If not, this is 1.3MB per thread. If they can, this needs to be documented well as it is bound to cause confusion. Hence I much prefer stateless, context-less functions.

[sipa]

Yes, contexts are sharable between threads.Only function that modify them need exclusive access (randomize being the only one currently).

[tdaede]

There are actually two problems here: One is that signing context initialization currently uses the size of the context, plus over 90K of temporary data. In my case, the temporary data causes me to exceed my RAM budget. The second is that, in some use cases (including mine), I have memory-mapped Flash that can store the contexts instead. This totally avoids the problem of context initialization.

I am not sure it is worth trying to reduce the temporary RAM usage, because the devices where that is the problem generally also have memory-mapped Flash.

[DavidEGrayson]

The STM32F205RE microcontroller on the TREZOR has 512 KB of flash and 128 KB of RAM, and it is capable of doing ECDSA signing. So hopefully a signing-capable context can be made to fit within that amount of flash. Of course, the smaller we can make it, the better.

I imagine you would run a utility on your computer that uses libsecp256k1 to generate a (randomized?) context for signing, and then it would save it in the form of C code which can be compiled by the cross-compiler for the microcontroller.

[sipa]

Yes, the best solution IMHO is to have a compile-time option to have a pre-built context in the binary.

[gmaxwell]

DavidEGrayson: the current signing context is 65536 bytes, and it can be trivially adjusted to whatever size makes sense. The size grows exponentially for linear increases in performance-- I've thought it would be good to support a mode that uses less but since realizing that all the current mid sized microcontrollers have memory mapped flash it hardly seems worth carrying around extra support code for smaller sizes.

Tdaede suggested on IRC that he was thinking about making a tool that uses the current precomp code to write out a header, and having a switch to use the prefabricated header; which I said sounded good at least for the signing context.

[gmaxwell]

Fixed by #254