Tighter verification bounds in mul/sqr #167

pull peterdettman wants to merge 1 commits into bitcoin-core:master from peterdettman:mul-sqr-verify changing 2 files +86 −86

peterdettman commented at 9:44 am on December 17, 2014: contributor

I reviewed the VERIFY_BITS bounds-checking for 32bit and 64bit mul/sqr implementations, finding various places where stricter bounds can be specified (I found no cases of over-strictness).
sipa commented at 11:55 am on December 17, 2014: contributor

So, the numbers I came up for the verification are to the extent possible, “mechanical”, meaning that you only need to look at previous bounds of input variables, and the operations done on them, to obtain the new ones. Those are very likely not the smallest possible ones, but their only purpose is for review/testing to assure that no overflows happen. I’d like to keep the numbers that way, as they are easy to verify locally (“pick a random piece of a lines of code, and verify that - assuming former bounds are correct - the newer ones are correct to”).

Is this what you’re doing too, or actually trying to find the strictest bounds possible?
peterdettman commented at 2:20 pm on December 17, 2014: contributor

I did strict calculations where they were already present. There are at least a couple of larger corrections which should at least be made (relating to products of the top limb(s)), which kind of led me to review the rest. Most of the rest is reasoned like e.g. a quantity is 63 bits because it is the sum of 5 30x30-bit products, which actually “leaves room for” 3 more 60-bit values, the carry-in accounts for only one of them, so this extra add fits too… this sort of reasoning. It depends on more information than just the previous VERIFY_BITS statement, so probably this is what you’d rather not have?.
Tighter verification bounds in mul/sqr 82872d9dcd
peterdettman force-pushed on Dec 23, 2014
gmaxwell added this to the milestone initial release on Aug 31, 2015
real-or-random commented at 9:22 am on November 24, 2020: contributor

This is ages old, and I agree with @sipa that there’s no point for this in the current code. (And 6 years later we’re more confident in the current code. :) There’s #811 and #815 of course, but these are separate efforts.

Closing this. Feel free to object.
real-or-random closed this on Nov 24, 2020
real-or-random removed this from the milestone initial release (1.0.0-rc.1) on Nov 24, 2020

Contributors
peterdettman sipa real-or-random