Variable time normalize #137

1. 
   sipa commented at 2:52 am on December 5, 2014: contributor

   This may not be worth it; I measure around a 0.8% speedup for verification.
2. 
   gmaxwell commented at 2:47 am on December 6, 2014: contributor

   I’m inclined to take even ‘small’ improvements like this as they’ll have a greater relative impact as other things are improved. I still need to test and reason about this some more.
3. 
   gmaxwell commented at 1:13 pm on December 6, 2014: contributor

   Adding instrumentation to check the normalized debugging variable right now tells me that 10% of the calls to normalize during a bench_verify call were provably already normalized (assuming the instrumentation isn’t wrong).

   This seemed awful high to me, so I instrumented it to find out what the backtrace was when it was already normalized. Turns out that in secp256k1_gej_add_ge_var at group_impl.h:305 it’s always normalized, well, no shock:

   0    secp256k1_fe_t u1 = a->x; secp256k1_fe_normalize_var(&u1);
   1[... no access to u1 ...]
   2    secp256k1_fe_normalize_var(&u1);
   

   This is responsible for 99.72% of the already verified calls. I created #139 for this. I’m doubting that it will make a huge benchmark difference, but it might be useful to check.

4. sipa force-pushed on Dec 6, 2014
5. Variable time normalize 39bd94d86d
6. sipa force-pushed on Dec 6, 2014
7. 
   gmaxwell commented at 1:02 pm on December 7, 2014: contributor

   ACK.
8. sipa merged this on Dec 7, 2014
9. sipa closed this on Dec 7, 2014

   ---

10. sipa referenced this in commit 6a9901e15b on Dec 7, 2014

Contributors
sipa gmaxwell