Add ability to use a statically generated ecmult context.

tdaede commented at 1:11 am on May 20, 2015: contributor

This vastly shrinks the size of the context required for signing on devices with memory-mapped Flash.

Tables are generated by the new gen_context tool into a header.

gmaxwell commented at 1:24 am on May 20, 2015: contributor

Cool!. You need to update secp256k1_ecmult_gen_context_clone too. (I haven’t run the code yet, but valgrind on the tests should have told you that you created a leak.

dcousens commented at 1:42 am on May 20, 2015: contributor

Is src/ the right place to put this? A clear separation of library code and tools is preferable IMHO.

tdaede force-pushed on May 20, 2015

tdaede commented at 4:14 am on May 20, 2015: contributor

@gmaxwell yup, fixed. @dcousens Tools like benchmarks are currently in src/. A related problem is that this patch currently does not work when cross compiling with autotools. Autoconf exports a HOSTCC variable, but Automake seems to have no easy way to mark an executable to use it. I’m not sure what standard procedure is here.

sipa commented at 4:20 am on May 20, 2015: contributor

Ping @theuni for cross-compilation help.

gmaxwell commented at 11:47 pm on May 20, 2015: contributor

@tdaede Gonna fix travis? :)

theuni commented at 11:54 pm on May 20, 2015: contributor

@sipa Thanks for the ping, will have a look.

tdaede force-pushed on May 21, 2015

theuni commented at 3:27 pm on May 22, 2015: contributor

I reworked this yesterday so that it builds on the host using a “dumb” config that is universal and requires no dependencies. In practice, that means building without HAVE_CONFIG_H, since those values represent the target’s config.

I also swapped out the big char array for a direct creation of a secp256k1_ge_storage_t using SECP256K1_GE_STORAGE_CONST’s as suggested by @gmaxwell, as that will alleviate endian issues. As far as I can tell, this should allow someone to target mipseb-linux from mingw-win64 (my typical farfetched cross-compile scenario).

My branch is here: https://github.com/theuni/secp256k1/tree/static-init I didn’t really bother cleaning it up, it needs some naming/spacing/etc cleanups, but after discussion with @tdaede on IRC, he’s just going to incorporate some of the changes into his work here.

sipa commented at 12:45 pm on June 13, 2015: contributor

ACK

sipa commented at 12:58 pm on June 13, 2015: contributor

I wonder what is the best solution: having contexts that don’t require a lot of memory, or having a fully static complete context in the first place (allowing passing context = NULL pointers, or having a secp2561_get_static_context function). The latter solution also solves some of the multithreading issues that some applications have with building a context without good reason, but disables the ability to blind the signing context.

voisine commented at 7:57 pm on June 13, 2015: contributor

I like the idea of context = NULL, I would use that.

DavidEGrayson commented at 4:50 pm on June 14, 2015: none

I don’t like the idea of context = NULL because it leaves no room for the user to specify anything about the context, like whether it can do verification. Also, the linker can probably not eliminate the static context when your program doesn’t use it, because that would involve the compiler proving that the context argument is never NULL.

tdaede commented at 6:44 pm on June 14, 2015: contributor

I think that the API should be the same, regardless of the implementation, so I don’t like passing in NULL context pointers.

This is also true of dyamically-generated but secretly-shared contexts. I don’t plan to address that use case in this patch, but it should be pretty easy to add without changing the API later.

sipa commented at 12:50 pm on July 1, 2015: contributor

@voisine I understand that maintaining a context in the caller is a serious complication for usage, but the problem here is that that model inherently means using the library in a suboptimal way (due to the inability to perform application randomness for blinding), so I’m still in the middle.

voisine commented at 8:00 pm on July 1, 2015: contributor

@sipa, it’s an extra complication, not sure if I’d call it serious, but would be nice to do without.

What’s the recommended practice with respect to blinding? I’m currently just using secp256k1_context_create. Should I also be using secp256k1_context_randomize? Is once per application launch sufficient, or is it desirable to re-randomize after each signature? Use separate randomized contexts for signing and verification?

tdaede commented at 8:18 pm on July 1, 2015: contributor

The obvious method for a shared context would just be a global variable holding the static context that is lazily initialized. Unfortunately, doing so requires threading primitives to be threadsafe.

This current patch just addresses a static context stored in ROM. I don’t think it’s in scope to address the other feature of a global context here.

sipa commented at 8:49 pm on July 1, 2015: contributor

Thomas: well I don’t think I want the complexity of two mechanisms to reduce memory footprint. This is the more flexible one, but slightly harder to use. On Jul 1, 2015 10:18 PM, “Thomas Daede” notifications@github.com wrote:

The obvious method for a shared context would just be a global variable holding the static context that is lazily initialized. Unfortunately, doing so requires threading primitives to be threadsafe.

This current patch just addresses a static context stored in ROM. I don’t think it’s in scope to address the other feature of a global context here.

— Reply to this email directly or view it on GitHub https://github.com/bitcoin/secp256k1/pull/254#issuecomment-117813932.

sipa commented at 3:45 pm on July 2, 2015: contributor

@voisine Well this library is experimental, and I would argue against using it for validation in any production system.

That said, your question makes it clear that the intended use isn’t clear. That should definitely be clarified in the header file and perhaps a README. I guess it should list this:

Do not create/destroy contexts for each call. Their creation is far slower than any library call, and part of their purpose is to reuse precomputed values across calls.
If you perform signing, you should call context_randomize after initialization of the context, and perhaps on a regularly basis (daily?).
When calling context_randomize pass in external entropy (perhaps from the operating system, perhaps from user input).
You are responsible for locking. After initialization, only context_randomize requires exclusive locked, but the caller is responsible for not calling any other functions that use the context during randomization.
If you do both validation and signing, you can either use a shared context for both, or separate contexts. One reason for using separate contexts if that for signing, calling context_randomize requires an exclusive lock on the context. If you need to do validation at the same time, it may be useful to separate them, so validation is not blocked by context randomization.

tdaede commented at 6:26 pm on July 2, 2015: contributor

So, for the other use cases here (hidden context sharing) I don’t really see any good way to implement them.

Using a global variable to store a context if one has already been initialized can cause locking issues. In addition, calls to randomize while some other thread is signing would lead to very bad things. So I don’t think there’s any good way to deduplicate contexts behind the application’s back.

So basically, I think the current patch’s implementation is fine (with room to add a static validation table later, when a slower and smaller table option is made).

Also, to be clear, this patch does not reduce memory footprint. Rather, it moves the footprint from RAM to ROM. On a desktop machine, it only bloats the size of the library.

in configure.ac: in 3e994e930e outdated

 95@@ -95,6 +96,11 @@ AC_ARG_ENABLE(endomorphism,
 96     AS_HELP_STRING([--enable-endomorphism],[enable endomorphism (default is no)]),
 97     [use_endomorphism=$enableval],
 98     [use_endomorphism=no])
 99+    
100+AC_ARG_ENABLE(ecmult_static_context,
101+    AS_HELP_STRING([--enable-ecmult-static-context],[enable ecmult static context for signing (default is no)]),

sipa commented at 11:26 am on July 3, 2015:

Static context is not really the right name - contexts are still dynamic, but some of their content is made static. How about –enable-static-precomputation ?

in src/ecmult_gen_impl.h: in 3e994e930e outdated

78@@ -75,6 +79,9 @@ static void secp256k1_ecmult_gen_context_build(secp256k1_ecmult_gen_context_t *c
79             secp256k1_ge_to_storage(&(*ctx->prec)[j][i], &prec[j*16 + i]);
80         }
81     }
82+#else
83+    ctx->prec = (secp256k1_ge_storage_t (*)[64][16])secp256k1_ecmult_static_context;

sipa commented at 11:28 am on July 3, 2015:

Is this cast necessary?

tdaede commented at 0:56 am on July 11, 2015:

It is necessary to prevent a warning. I suppose I could change the type of ctx->prec instead at compile time to be const.

in src/gen_context.c: in 3e994e930e outdated

0@@ -0,0 +1,63 @@
1+/**********************************************************************
2+ * Copyright (c) 2013, 2014, 2015 Pieter Wuille, Gregory Maxwell      *

sipa commented at 11:28 am on July 3, 2015:

I did not write this, as far as I know :)

pmconrad cross-referenced this on Jul 3, 2015 from issue Review use of libsecp256k1 contexts by pmconrad

sipa commented at 9:26 pm on July 8, 2015: contributor

Feel like addressing my nits above, @tdaede?

theuni commented at 0:09 am on July 11, 2015: contributor

@sipa You might have a look at https://github.com/theuni/secp256k1/tree/static-init2. Don’t bother looking at individual commits and keep in mind that it’s just a rough POC.

This makes the context (which really wouldn’t be a context anymore, it could be renamed to something more apt) const, so that it’s unaffected by blinding operations. Instead, a new blinding structure is passed in when needed.

Additionally, the initial blinding value is static to avoid race conditions for applications creating static contexts/blinds at startup. As a result, NULL could be passed in place of the blind, in which case the static blind would be used.

I believe this solves several issues at once:

No more worrying about races (hooray for solving racism :p). Since the context and initial blind are both const, only blind_randomize() could race.
You could add secp2561_get_static_context now if you wanted, since blinding is decoupled.
The create_blind() could potentially take an optional void* for secure storage space rather than allocating itself. I’m not sure if that would provide any realistic additional security though, at least not without reworking secp256k1_ecmult_gen_blind a good bit.

If you’re onboard with the concept, I’ll clean it up and keep working.

gmaxwell commented at 0:23 am on July 11, 2015: contributor

@theuni I don’t understand what advantage you see from the caller now having two contexts they must carry around.

Perhaps you expect them to create and destroy the blinding around each operation? If so this would somewhat undermine it; as it would lose the accumulation of unpredictability.

As a random aside, please don’t introduce any more “_t” named types in the interface. typedefs ending with _t are namespace reserved by posix.

tdaede force-pushed on Jul 11, 2015

theuni commented at 1:18 am on July 11, 2015: contributor

@gmaxwell It’s my understanding that the blinding should be randomized relatively rarely, roughly no more than a few times per day. It’s very possible that I’ve misunderstood that. As for type_t, noted. Thanks.

From my perspective, the advantage is flexibility. I think it’s pretty easy to imagine, for example, an application that could be generating keys in one thread and signing transactions in another. In that case, it would be advantageous to share a constants-only context but maintain per-thread blindings. They could then be rotated infrequently but still independently, without the risk of a collision.

It also solves @sipa’s problem above, so a create_static_context() could be created.

I know I mentioned this to you a while back and you weren’t in favor, I just wanted to put it into code to see what it might look like.

tdaede force-pushed on Jul 11, 2015

Add ability to use a statically generated ecmult context.

This vastly shrinks the size of the context required for signing on devices with
memory-mapped Flash.

Tables are generated by the new gen_context tool into a header.

fbecc38a89

Add travis build to test the static context. 733c1e695e

tdaede force-pushed on Jul 14, 2015

sipa commented at 3:10 pm on July 14, 2015: contributor

@theuni Thanks for your work, but I think there are more applications for context that are harder to integrate with it, like modifying memory usage, setting callbacks for errors, …

sipa merged this on Jul 14, 2015

sipa closed this on Jul 14, 2015

sipa referenced this in commit 5133f78651 on Jul 14, 2015

theuni commented at 4:53 pm on July 14, 2015: contributor

No worries. I discussed with @gmaxwell after commenting, and it’s clear now why that idea isn’t very helpful.

gmaxwell cross-referenced this on Jul 18, 2015 from issue secp256k1_ecmult_gen_context_build allocates 90KB on the stack by tdaede

douglasbakkum cross-referenced this on Oct 18, 2015 from issue variable sized precomputed table for signing by douglasbakkum

vikramrajkumar cross-referenced this on Jan 17, 2017 from issue Review use of libsecp256k1 contexts by vikramrajkumar

real-or-random referenced this in commit 96cd94e385 on Sep 5, 2019

Add ability to use a statically generated ecmult context. #254