headersync: do parameter search at runtime #35642

In future commits, the logic in the headerssync-params.py tool will be
made significantly faster, and integrated into the Bitcoin Core node
software itself and run at runtime.

To prepare for that, remove all output from the tool beyond the actual
computation result:
* Drop the printing of the search parameters being explored, because
  the search will become fast enough to not need progress output, and
  because it interferes with tests.
* Drop the final memory configuration to maximally encapsulate the
  computation logic.
* Drop memory_usage's now-unused second and third return values (the
  per-scenario breakdowns that only the removed output consumed); it
  now returns just the peak memory usage.

RANDOMIZE_OFFSET was a configurable option, introduced in the early
stages of the headers-presync work to investigate whether randomizing
the commitment offset was worth it. As that turned out to be the case,
the actual implementation ended up using it all the time.

Thus, remove the configurable and treat it as always True, making the
logic slightly simpler.

This moves the computationally expensive part of the optimization
search into a function that only depends on 3 quantities:
- The maximum number of headers a chain can have.
- The number of known valid headers in the main chain.
- The (fractional) number of headers an attacker is allowed to insert
  into a victim's database per attack.

The goal is to make it possible to introduce tests in later commits
that cover the hard part, without hardcoding config parameters that
would invalidate the tests if changed.

It is possible to have multiple adjacent period values for which the
peak memory usage is identical. The current randomized search will find
a random one in this case, which is not great for testing.

Add a postprocessing step that finds the minimum period value for the
optimal found peak memory usage value, so the result is deterministic.

Also make the attack_rate early-exit more robust: rather than comparing
a single batch's contribution against the accumulated rate, compare a
bound on the sum of all remaining batches. This gives a stronger
guarantee that the reported solution is actually the optimal one, and
it also turns out to be needed for the results to stay identical across
the optimizations in later commits.

ASSUME_CONVEX assumes the period-to-memory-usage mapping (at the optimal buffer
size for each period) is convex, which lets the search discard whole ranges of
periods at once. It defaulted to True and was only ever run that way; the False
path existed solely as a slower fallback with a stronger guarantee.

Drop the option and always assume convexity, simplifying the search. A later
commit replaces this random search entirely with a solver that finds the true
optimum directly, without any convexity assumption, so the stronger-guarantee
fallback is not needed in the meantime.

This adds a collection of 50 randomly generated test vectors to the
tool. This is in preparation for converting the code to C++ and
applying significant optimization, while remaining confident that the
behavior does not change.

The test vectors are chosen to be inputs that are close to ones where
the optimal output changes, to test the accuracy of the calculation.

Run with pypy3, which evaluates the search far faster than CPython:

    pypy3 contrib/devtools/headerssync-params.py --selftest

This adds a C++ implementation of the headerssync-params.py tool's
parameter search logic to headerssync.cpp directly, together with its
unit test vectors. The tool's commentary explaining the goals of the
search is copied along with it.

This is rather inefficient for now, but will be optimized in further
commits. Because of that, the unit test only checks one randomly chosen
vector per run for now; a later commit makes the computation fast
enough to check all of them on every run.

The attack rate averages the not-yet-detected probability over all
{period} randomized commitment offsets. Doing so with an explicit loop
over the alignments costs O(period) per processed batch. This can be
computed much more efficiently however, by counting how many choices
for the alignment have floor(forged_headers / period) commitments, how
many have ceil(forged_headers / period), and weighting both
accordingly. This results in just an O(1) cost per batch.

The find_bufsize algorithm takes two arguments that help its search: a
minimum bufsize to consider, and an upper bound on the amount of
memory.

After the changes in the next commit, these will not be needed anymore.
Get rid of them beforehand here.

Replace the randomized search over all candidate periods with a faster
deterministic algorithm:

Step 1: Solve the continuous relaxation of the problem, where period and
        bufsize can be arbitrary real numbers, and round the resulting
        period to an integer. This can be done efficiently using
        Newton-Raphson iterations.
Step 2: Compute the bufsize and peak memory usage corresponding to that
        rounded period.
Step 3: Scan the remaining integer periods whose peak memory usage could
        still be at or below the peak memory usage reached so far.

The continuous optimum in Step 1 is only used as a starting point: a bad
guess makes Step 3 scan more candidate periods, but cannot affect the
result.

This also makes the computation fast enough that the unit test can check
all test vectors on every run again, instead of one randomly chosen one.

So far, the headers sync parameters are committed to the repository,
as part of the chain parameters. This requires maintainers to
occasionally recompute them, based on a prediction of how long the
release is likely to be used.

With the code for the optimization algorithm ported to C++ and
integrated in headerssync.cpp, it becomes possible to instead do this
computation at runtime. This is less work, with fewer ways for
maintainers and reviewers to get it wrong, and automatically adjusts
based on clock time.

For now, the computation is relatively slow (seconds), but the next
commits will introduce optimizations to reduce that time
significantly.