refactor: Avoid unsigned integer overflow in script/interpreter.cpp #29543

1. 
   hebasto commented at 10:06 am on March 3, 2024: member

   Although unsigned integer overflow is not undefined behavior, it’s preferable to eliminate the need for an UBSan suppression for it.

   ~This is an alternative to #29541.~

2. 
   DrahtBot commented at 10:06 am on March 3, 2024: contributor

   The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

   Code Coverage

   For detailed information about the code coverage, see the test coverage report.

   Reviews

   See the guideline for information on the review process.

   Type	Reviewers
   ACK	sipa
   Concept ACK	hernanmarino

   If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

   Conflicts

   Reviewers, this pull request conflicts with the following ones:

   • #29625 (Several randomness improvements by sipa)

   If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

3. DrahtBot added the label Refactoring on Mar 3, 2024
4. DrahtBot added the label Needs rebase on Mar 5, 2024
5. 
   Sjors commented at 5:51 pm on March 6, 2024: member

   Needs rebase. But see also the discussion in #29541. I would prefer narrowing the suppression to as little as possible, but without touching the ancient code.
6. refactor: Avoid unsigned integer overflow in `script/interpreter.cpp`

   Although unsigned integer overflow is not undefined behavior, it's
   preferable to eliminate the need for a UBSan suppression for it.

   754ba687cc
7. hebasto force-pushed on Mar 8, 2024
8. 
   hebasto commented at 10:47 am on March 8, 2024: member

   Needs rebase.

   Rebased.

   But see also the discussion in #29541. I would prefer narrowing the suppression to as little as possible…

   Anything in your mind without growing the diff up to 10+ lines?

   but without touching the ancient code.

   I still believe that the suggested diff is reviewable.

9. DrahtBot removed the label Needs rebase on Mar 8, 2024
10. 
    sipa commented at 4:45 pm on March 8, 2024: member

    ACK 754ba687ccc16bb609c9b22bc2d3bbf0a82d5bce

    This is consensus-critical code, so I’ve carefully verified that this change does not modify behavior:

    • The old code:
      • All invocations of stacktop() and altstacktop() use either a small negative integer literal (between -6 and -1) as argument, or small int values between -42 and -1 (in the OP_CHECKMULTISIG code).
      • We only support systems with 32-bit int and 32-bit or 64-bit size_t.
      • Thus, size_t (the output of stack.size()) is always an unsigned type of rank at least as high as int’s, which is sized.
      • Thus, a sum between int and size_t will involve an conversion to size_t of both inputs; for negative ints i, that conversion is 2^N + i, with N the size of size_t (32 or 64).
      • The overall sum stack.size() + (i) is therefor equal to 2^N + stack.size() + i, which due to the modular nature of the unsigned type size_t, equals (stack.size() + i) mod 2^N.
    • The new code:
      • For the same reasons as above (i) is a small strictly negative int, and thus (-i) is a small strictly positive int.
      • The same conversion to size_t happens, and thus stack.size() - (-i) is (stack.size() + i) mod 2^N.
11. 
    Sjors commented at 6:19 pm on March 8, 2024: member

    Anything in your mind without growing the diff up to 10+ lines?

    Not really, though the above proof by @sipa is also 10+ lines :-)

12. 
    maflcko commented at 12:55 pm on March 11, 2024: member

    Alternative (for context): https://github.com/bitcoin/bitcoin/pull/24214
13. 
    hebasto commented at 1:09 pm on March 11, 2024: member

    Alternative (for context): #24214

    Oh, I missed that.

14. 
    Sjors commented at 3:42 pm on March 11, 2024: member

    I find #24214 more readable, because it doesn’t use the double minus.
15. 
    hebasto commented at 8:11 pm on March 11, 2024: member

    I find #24214 more readable, because it doesn’t use the double minus.

    Happy to close this PR in favour of the reopened #24214.

16. 
    hernanmarino commented at 10:31 pm on April 12, 2024: contributor

    ACK to the idea of removing overflows in the code, but I was little worried of the implications of this. After reading @sipa ’s comment, it is definitely an ACK for me. Regarding the approach between this PR and #24214 , I am leaning towards this for the sole reason that 24214 is still closed, but i reviewed and also ACK that PR as well.
17. DrahtBot added the label Needs rebase on Jul 4, 2024
18. 
    DrahtBot commented at 11:21 am on July 4, 2024: contributor

    🐙 This pull request conflicts with the target branch and needs rebase.

Contributors
hebasto DrahtBot Sjors sipa maflcko hernanmarino

Labels
Refactoring Needs rebase