_ecmult_wnaf relies on int being at least 32 bits #1769

1. 
   real-or-random commented at 10:00 am on November 7, 2025: contributor

   The current secp256k1_ecmult_wnaf needs the unstated and unchecked assumption that int has at least 31 value bits when it VERIFY_CHECKs that w <= 31. In practice, we call it only with WINDOW_A == 5 and WINDOW_G == ECMULT_WINDOW_SIZE where the latter is configurable in the range 2..24.

   A consequence of this “bug” is that the code fails on a 16-bit platform if you set ECMULT_WINDOW_SIZE > 16. I don’t think we need to support this, but code without unchecked assumptions is bad. So I suggest that we rewrite the function to use int32_t instead of int even if we don’t use my macro approach. (We can keep the “bit position” arguments and variables int.)

   Alternatively, we could add the assumption that INT_MAX >= INT32_MAX but this forbids 16-bit platforms, and the code seems to work on them in principle; see #792 (comment).

   Originally posted by @real-or-random in #1761#pullrequestreview-3432695127

2. real-or-random added the label bug on Nov 7, 2025
3. real-or-random assigned Copilot on Nov 7, 2025
4. 
   real-or-random commented at 10:23 am on November 7, 2025: contributor

   Let’s try some AI stuff… 🤷
5. real-or-random unassigned Copilot on Nov 11, 2025
6. real-or-random assigned Copilot on Nov 11, 2025
7. 
   real-or-random commented at 8:34 pm on November 11, 2025: contributor

   Alternatively, we could add the assumption that INT_MAX >= INT32_MAX but this forbids 16-bit platforms

   Now that I think about it again, we should do this anyway. As long as we don’t test on 16-bit platforms, we should simply add this assumption.

   About testing on 16-bit platforms: Of course, we should not consider 16-bit platforms a target. Perhaps testing will give us insights about hidden assumptions in our code. But I doubt that these insights will be very useful if they are specific to small ints. If we can make the assumptions true by adding INT_MAX >= INT32_MAX to assumptions.h, then let’s just do that.

   We may still want to change the types in secp256k1_ecmult_wnaf. Using an int32_t instead of int will also make the code easier to read. In particular, it will be much clearer that VERIFY_CHECK(w <= 31) is the right thing to do.

8. 
   real-or-random commented at 8:20 pm on November 12, 2025: contributor

   it will be much clearer that VERIFY_CHECK(w <= 31) is the right thing to do.

   And yet, it’s not the right thing. :)

   If int carry == 1, then the function does carry << w, i.e., 1 << 31 and this is UB (signed overflow). This is another edge case that we should fix!

9. real-or-random renamed this:
   `_ecmult_wnaf` relies on `int` having at least 32 value bits
   `_ecmult_wnaf` relies on `int` being at least 32 bits
   on Nov 18, 2025

Contributors
real-or-random

Labels
bug