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, the memory bound will not
be needed anymore. Get rid of it beforehand here, keeping the
min_bufsize argument and the tracking that feeds it.

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

Step 1: Solve the continuous relaxation of the problem, where period and
        bufsize can be arbitrary real numbers, using Newton-Raphson
        iterations, and round the resulting period to an integer.
Step 2: Try all integer periods within 2 of that rounded value, and
        return the one whose corresponding bufsize results in the lowest
        peak memory usage.

Unlike the randomized search, this is not guaranteed to find the exactly
optimal configuration, as the true integer optimum could in principle
fall outside the range tried in Step 2. It is however guaranteed to be
very close: rounding the continuous solution to integers increases its
memory usage by only a tiny fraction, and the continuous optimum is a
lower bound on what any integer solution can achieve. In practice the
difference does not appear to materialize at all: the result matches the
exact optimum for all test vectors.

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.

The algorithm's continuous relaxation relies on max_headers being
larger than 2 * minchainwork_headers, which any consistent clock
satisfies by a wide margin. Assume() this in the optimizer, and clamp
in ComputeHeadersSyncParams, so that mocked or badly wrong clocks
cannot produce degenerate inputs (which could otherwise fail to
converge).

The Newton-Raphson step can overshoot arbitrarily -- even to negative
gamma values -- when the continuous optimum lies at a tiny period, from
where subsequent iterations would degenerate into NaNs. Clamp gamma to a
broad range on every iteration to keep it well-defined.

Each candidate period's bufsize search is seeded with the result for
the previous period, minus one: the required bufsize can only grow as
the period increases, and the safety margin of one means that even a
floating-point-level violation of that argument cannot affect the
result.

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.

Tests that construct many PeerManager instances can avoid recomputing
the parameters each time by passing a precomputed value through
PeerManager::Options. The fuzz targets that construct one per iteration
pass a fixed constant, which both avoids the recomputation and makes
their behavior independent of the (mocked) clock at construction time.

Add two fuzz targets covering the headers sync parameter optimizer over
the entire range of legal inputs, asserting that the resulting
configuration is sane (and, implicitly, that the computation terminates
without crashing or throwing):

- headers_sync_params_inner exercises ComputeHeadersSyncParamsInner
  directly. minchainwork_headers is a block height and thus fits an int;
  max_headers must exceed twice that (which the caller guarantees by
  clamping) and is at most 6 headers/s over the longest timespan any
  clock can produce; attack_headers is parametrized logarithmically as a
  number of bits of security asked from the commitment structure, whose
  legal range follows from the optimizer's continuous relaxation.

- headers_sync_params exercises ComputeHeadersSyncParams with any
  timespan a clock -- even a mocked or badly wrong one -- can produce,
  and any int-height minchainwork_headers.

Both targets check that the returned period is positive and no larger
than the minimum-chainwork chain, and that the redownload buffer covers
at least one commitment period whenever the acceptable attack rate is
low enough to require any commitment verification at all (which it
always is for the rates ComputeHeadersSyncParams uses).