Document / assert non-portable assumptions #792

1. 
   real-or-random commented at 10:46 pm on August 8, 2020: contributor

   I think it’s reasonable to require a two’s complement implementation (we could verify it in a configure script, and in unit tests)

   If you really have some exotic system, then you might not run ./configure or the tests either. I think the safest way is to use some C static assert hack e.g., https://stackoverflow.com/a/56742411. These looks very ugly but they work and the ugliness is hidden behind a macro. We should also check other simple assumptions such as sizeof(int) == 4 etc. Alternatively, we could perform some self-tests at context creation time, and call the error callback if they fail. The simple ones will be optimized away by the compiler, and we should have some kind of self-test anyway if we want to implement a SHA256 override (see the discussion in #702).

   Originally posted by @real-or-random in #767 (comment) @gmaxwell notes there that the static assert hack may not be the best idea.

2. 
   real-or-random commented at 10:58 pm on August 8, 2020: contributor

   (edit: keeping a up-to-date list here)

   • Right shifts https://github.com/bitcoin-core/secp256k1/blob/d567b779fe446fd18820a9d2968ecb703c8dea19/src/ecmult_const_impl.h#L19
   • size of size_t, see for example https://github.com/bitcoin-core/secp256k1/blob/770b3dcd6f1edb0a6355a55d92b7bea1e9524042/src/ecmult_impl.h#L51 (also in contrib, see https://github.com/bitcoin/bitcoin/pull/10657/files)
   • sizeof(int) <= 4, otherwise uint32_t x uint32_t multiplication could result in signed overflow (This is even absurder when you state it this way.)
   • if we’re pedantic then maybe also CHAR_BITS
   • endianness (cannot be checked at compile-time, a SHA256 self-test would cover this unless we have a SHA256 override)
   • I would not be surprised if we assume sizeof(int) >= 4 somewhere.

   This is a shot in the dark but @roconnor-blockstream do you know some more?

3. real-or-random cross-referenced this on Aug 13, 2020 from issue Check assumptions on integer implementation at compile time by sipa
4. 
   gmaxwell commented at 5:19 pm on August 13, 2020: contributor

   size of size_t, see for example

   Might be better to make that config macro get size_t’s bits and base the limit on that. Otherwise its reducing portability for unexposed configurability.

5. 
   real-or-random commented at 6:07 pm on August 13, 2020: contributor

   size of size_t, see for example

   Might be better to make that config macro get size_t’s bits and base the limit on that. Otherwise its reducing portability for unexposed configurability.

   Sorry, I can’t follow. Which macro?

6. 
   gmaxwell commented at 6:36 pm on August 13, 2020: contributor

   https://github.com/bitcoin-core/secp256k1/blob/770b3dcd6f1edb0a6355a55d92b7bea1e9524042/src/ecmult_impl.h#L58 the window_size absurd maximum of 24 is driven by size_t overflow.
7. 
   practicalswift commented at 6:33 am on August 16, 2020: contributor

   Here are some assumptions that come to my mind immediately: … This is a shot in the dark but @roconnor-blockstream do you know some more?

   FWIW, these assumptions are asserted in Bitcoin Core:

   https://github.com/bitcoin/bitcoin/blob/master/src/compat/assumptions.h

8. 
   gmaxwell commented at 6:58 am on August 16, 2020: contributor

   I would not be surprised if we assume sizeof(int) >= 4 somewhere

   Nope, test_fixed_wnaf_small has some bugs where it uses 32-bit values as int arguments, but other than that and the multi-ecmult tests (which need some fixes to reduce memory usage before I can tests) the tests pass on a 16-bit platform. (nor have I run recovery or ecdh tests yet, but – generally seems like it works)

9. 
   real-or-random commented at 2:49 pm on September 9, 2020: contributor

   We have a SHA256 self-test now (#799).
10. 
    real-or-random commented at 11:21 am on September 17, 2020: contributor

    https://github.com/bitcoin-core/secp256k1/blob/770b3dcd6f1edb0a6355a55d92b7bea1e9524042/src/ecmult_impl.h#L58 the window_size absurd maximum of 24 is driven by size_t overflow.

    I tried to make that work but it’s not that easy. In the precompiler we don’t have sizeof (and we can’t emulate it because struct padding is unknown etc). In the static assert hack, we can’t check for overflow. Maybe it’s best to simply set the maximum to something like 10 if SIZE_MAX is smaller than UINT32_MAX. That’s not precise but should be good enough in practice. What window size did you use for your 16-bit tests?

    Nope, test_fixed_wnaf_small has some bugs where it uses 32-bit values as int arguments

    Are you willing to fix these?

11. 
    real-or-random commented at 2:23 pm on September 17, 2020: contributor

    ok @roconnor-blockstream suggests something along the lines of

    ECMULT_TABLE_SIZE(WINDOW_G) <= SIZE_MAX / sizeof((*((secp256k1_ecmult_context*) NULL)->pre_g)[0]).

    Indeed, this should do it if we additionally check that the shift within ECMULT_TABLE_SIZE does neither overflow int nor size_t (the code uses size_t for memory sizes but then int for array indices).

12. real-or-random cross-referenced this on Sep 17, 2020 from issue Add static assertion that uint32_t is unsigned int or wider by real-or-random
13. real-or-random referenced this in commit bb1f54280f on Sep 26, 2020

Contributors
real-or-random gmaxwell practicalswift