Use trivial algorithm in ecmult_multi if scratch space is small #592

pull jonasnick wants to merge 1 commits into bitcoin-core:master from jonasnick:ecmult_multi_use_trivial changing 2 files +37 −15

jonasnick commented at 10:50 AM on February 27, 2019: contributor

ecmult_multi already selects the trivial algorithm if the scratch space is NULL. With this PR the trivial algorithm is also selected if the scratch space is too small to use pippenger or strauss instead of returning 0. That makes it more easier to avoid consensus relevant inconsistencies just because scratch space construction was messed up.
real-or-random commented at 3:19 PM on February 27, 2019: contributor
I think that's a good idea. But the drawback is that now you won't notice that you use the slow algorithm. Do you think we can somehow get the best of both worlds, i.e., fall back to the trivial algorithm but somehow indicate that something is wrong? I don't see a convincing way to do this:
- we cannot just print a warning from the library
- we can't use the current callbacks because they'll abort the process (and introducing another callback for that single case is probably overkill)
- maybe using a second non-failing return value? (also not great and changes the API)
jonasnick commented at 3:52 PM on February 27, 2019: contributor

But the drawback is that now you won't notice that you use the slow algorithm

You have that problem anyway even without this PR because you can have a scratch space which only fits a single point. Or if you make a scratch space fitting 2 points but you have a 1000 to multiply.

You'll notice that you're using a slow algorithm if you benchmark your program which presumably you do if you use ecmult_multi or batch_verify. You might have a problem if the size of the scratch space is attacker controlled and you assume something about timings of ecmult_multi, but this PR is a strict improvement in that case. I don't have anything against multiple return values per se, but it's not a panacea because you need to make implementer check for the various error types.
real-or-random commented at 6:18 PM on February 27, 2019: contributor

utACK

in src/ecmult_impl.h:1156 in af755dfb9e outdated

1154 | @@ -1155,13 +1155,14 @@ static int secp256k1_ecmult_multi_var(const secp256k1_ecmult_context *ctx, secp2
1155 |      /* Compute the batch sizes for pippenger given a scratch space. If it's greater than a threshold
1156 |       * use pippenger. Otherwise use strauss */

real-or-random commented at 6:19 PM on February 27, 2019:

not this PR but could add note here that explains that strauss will require more space than pippenger

jonasnick commented at 3:14 PM on March 18, 2019:

fixed

gmaxwell commented at 7:14 PM on February 27, 2019: contributor

Concept ACK.

I share the concern that users will get poor performance by surprise, but I think the right way for us to address that would be to in the future provide an API that doesn't require manual scratch space handling, even at the expense of wasting memory. "Fast by default".

In the absence of that, I'd much rather it fail slow than fail fail.
jonasnick force-pushed on Mar 18, 2019
Use trivial algorithm in ecmult_multi if scratch space is small 9ab96f7b12
real-or-random commented at 3:22 PM on March 18, 2019: contributor

utACK 9ab96f7
gmaxwell merged this on May 25, 2019
gmaxwell closed this on May 25, 2019
gmaxwell referenced this in commit 40839e21b9 on May 25, 2019
sipa cross-referenced this on Jun 9, 2020 from issue Update libsecp256k1 subtree by sipa
fanquake referenced this in commit 8c97780db8 on Jun 13, 2020
sidhujag referenced this in commit 8a3a072968 on Jun 13, 2020
ComputerCraftr referenced this in commit b98f1c6e6c on Jun 16, 2020
UdjinM6 referenced this in commit 9d36ba6570 on Aug 10, 2021
5tefan referenced this in commit 8ded2caa74 on Aug 12, 2021
gades referenced this in commit d855cc511d on May 8, 2022

Contributors

jonasnick

real-or-random

gmaxwell