secp256k1 icon indicating copy to clipboard operation
secp256k1 copied to clipboard

Published 20 hours ago • verified publisher icon bitcoin-core

Function to compute optimal ecmult_multi scratch size for a number of points

Open jonasnick opened this issue 6 years ago • 5 comments

@DavidBurkett requested to allow computing the optimal scratch size for Schnorr batch verification (https://github.com/ElementsProject/secp256k1-zkp/issues/69). This PR is a prerequisite but also contains a bunch of other fixups.

Other than adding the new function this PR refactors scratch space handling in ecmult_impl to improve code quality, tests and documentation.

The biggest part of this PR is to make computing the scratch size and its inverse more precise by not assuming maximum padding when aligning, but rather using the actual padding. This is not strictly necessary but removes a leaky abstraction and makes testing easier.

jonasnick avatar Jun 12 '19 21:06 jonasnick

I made a couple of changes and in order to avoid adding code that is deleted in later commits I force pushed, sorry. Summary of the changes:

  • added function alloc_size to scratch space to compute actual size allocated for a given number of objects
  • fixed bug in strauss_max_points (thanks @real-or-random) that vastly underestimated the number of points actually fitting into the scratch space. Also added test which would have caught this issue.
  • added a verify check to ensure that the space required for a single point/entry is smaller than the worst case padding

jonasnick avatar Jun 16 '19 19:06 jonasnick

Concept ACK, I still need to go over the logic changes.

sipa avatar Jul 23 '19 19:07 sipa

needs rebase

real-or-random avatar Apr 07 '21 12:04 real-or-random

Rebased and polished quite a bit. Also added fix for bug in master that we noticed before iirc. So to make sure it gets in I opened #1004.

Still, I didn't fully try to understand how this PR works. Also, it seems like ecmult_multi_scratch_size doesn't give the exact optimal result. That's because a scratch space of size pippenger_scratch_size(n_points, bucket_window) it may happen that strauss_max_points(error_callback, scratch), n) (the actual batch size) is smaller than n_points.

jonasnick avatar Nov 06 '21 20:11 jonasnick

I rebased this to see how master affects this PR. Will still need to address review comments and add better explanations to the commits.

jonasnick avatar Jan 30 '22 17:01 jonasnick