secp256k1_ecmult_gen_context_build allocates 90KB on the stack #251

1. 
   tdaede commented at 8:00 am on May 15, 2015: contributor

   0secp256k1_ge_t prec[1024];
   1secp256k1_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.

2. 
   DavidEGrayson commented at 4:27 pm on May 15, 2015: none

   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.
3. 
   laanwj commented at 7:32 am on May 16, 2015: member

   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.
4. 
   gmaxwell commented at 7:50 am on May 16, 2015: contributor

   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.

5. 
   laanwj commented at 8:08 am on May 16, 2015: member

   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.
6. 
   sipa commented at 3:22 pm on May 16, 2015: contributor

   Yes, contexts are sharable between threads.Only function that modify them need exclusive access (randomize being the only one currently).
7. 
   tdaede commented at 8:54 pm on May 18, 2015: contributor

   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.

8. 
   DavidEGrayson commented at 0:25 am on May 19, 2015: none

   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.

9. 
   sipa commented at 0:30 am on May 19, 2015: contributor

   Yes, the best solution IMHO is to have a compile-time option to have a pre-built context in the binary.
10. 
    gmaxwell commented at 0:35 am on May 19, 2015: contributor

    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.

11. 
    gmaxwell commented at 11:25 pm on July 18, 2015: contributor

    Fixed by #254
12. gmaxwell closed this on Jul 18, 2015

    ---

13. douglasbakkum cross-referenced this on Oct 18, 2015 from issue variable sized precomputed table for signing by douglasbakkum
14. real-or-random referenced this in commit 96cd94e385 on Sep 5, 2019

Contributors
tdaede DavidEGrayson laanwj gmaxwell sipa