Inside Bitcoin

251        # also give up.
252        max_buf = (max_mem - (MINCHAINWORK_HEADERS // period)) // COMPACT_HEADER_SIZE
253        if max_buf < min_bufsize:
254            return None
255        if attack_rate(period, max_buf, attack_headers)[0] >= attack_headers:
256            return None
257        # If it is sufficient, that's an upper bound to start our search.
258        succ_buf = min_bufsize - 1
259        fail_buf = max_buf
260
261    # Then perform a bisection search to narrow it down.
262    while fail_buf > succ_buf + 1:
263        try_buf = (succ_buf + fail_buf) // 2
264        if attack_rate(period, try_buf, attack_headers)[0] >= attack_headers:
265            succ_buf = try_buf
266        else:
267            fail_buf = try_buf
268    return fail_buf
269
270
271def optimize(when):
272    """Find the best (period, bufsize) configuration."""
273
274    # When period*bufsize = memory_scale, the per-peer memory for a mainchain sync and a maximally
275    # long low-difficulty header sync are equal.
276    memory_scale = (find_max_headers(when) - MINCHAINWORK_HEADERS) / COMPACT_HEADER_SIZE
277    # Compute approximation for {bufsize/period}, using a formula for a simplified problem.
278    approx_ratio = lambert_w(log(4) * memory_scale / ATTACK_HEADERS**2) / log(4)
279    # Use those for a first attempt.
280    print("Searching configurations:")
281    period = int(sqrt(memory_scale / approx_ratio) + 0.5)
282    bufsize = find_bufsize(period, ATTACK_HEADERS, when)
283    mem = memory_usage(period, bufsize, when)
284    best = (period, bufsize, mem)
285    maps = [(period, bufsize), (MINCHAINWORK_HEADERS + 1, None)]
286    print(f"- Initial: period={period}, buffer={bufsize}, mem={mem[0] / 8192:.3f} KiB")
287
288    # Consider all period values between 1 and MINCHAINWORK_HEADERS, except the one just tried.
289    periods = [iv for iv in range(1, MINCHAINWORK_HEADERS + 1) if iv != period]
290    # Iterate, picking a random element from periods, computing its corresponding bufsize, and
291    # then using the result to shrink the period.
292    while True:
293        # Remove all periods whose memory usage for low-work long chain sync exceed the best
294        # memory usage we've found so far.
295        periods = [p for p in periods if find_max_headers(when) // p < best[2][0]]
296        # Stop if there is nothing left to try.
297        if len(periods) == 0:
298            break
299        # Pick a random remaining option for period size, and compute corresponding bufsize.
300        period = periods.pop(random.randrange(len(periods)))
301        # The buffer size (at a given attack level) cannot shrink as the period grows. Find the
302        # largest period smaller than the selected one we know the buffer size for, and use that
303        # as a lower bound to find_bufsize.
304        min_bufsize = max([(p, b) for p, b in maps if p < period] + [(0,0)])[1]
305        bufsize = find_bufsize(period, ATTACK_HEADERS, when, best[2][0], min_bufsize)
306        if bufsize is not None:
307            # We found a (period, bufsize) configuration with better memory usage than our best
308            # so far. Remember it for future lower bounds.
309            maps.append((period, bufsize))
310            mem = memory_usage(period, bufsize, when)
311            assert mem[0] <= best[2][0]
312            if ASSUME_CONVEX:
313                # Remove all periods that are on the other side of the former best as the new
314                # best.
315                periods = [p for p in periods if (p < best[0]) == (period < best[0])]
316            best = (period, bufsize, mem)
317            print(f"- New best: period={period}, buffer={bufsize}, mem={mem[0] / 8192:.3f} KiB")
318        else:
319            # The (period, bufsize) configuration we found is worse than what we already had.
320            if ASSUME_CONVEX:
321                # Remove all periods that are on the other side of the tried configuration as the
322                # best one.
323                periods = [p for p in periods if (p < period) == (best[0] < period)]
324
325    # Return the result.
326    period, bufsize, _ = best
327    return period, bufsize
328
329
330def analyze(when):
331    """Find the best configuration and print it out."""
332
333    period, bufsize = optimize(when)
334    # Compute accurate statistics for the best found configuration.
335    _, mem_mainchain, mem_timewarp = memory_usage(period, bufsize, when)
336    headers_per_attack, _ = attack_rate(period, bufsize)
337    attack_volume = NET_HEADER_SIZE * MINCHAINWORK_HEADERS
338    # And report them.
339    print()
340    print(f"Given current min chainwork headers of {MINCHAINWORK_HEADERS}, the optimal parameters for low")
341    print(f"memory usage on mainchain for release until {TIME:%Y-%m-%d} is:")
342    print()
343    print(f"        // Generated by headerssync-params.py on {datetime.today():%Y-%m-%d}.")
344    print( "        m_headers_sync_params = HeadersSyncParams{")
345    print(f"            .commitment_period = {period},")
346    print(f"            .redownload_buffer_size = {bufsize},"
347          f" // {bufsize}/{period} = ~{bufsize/period:.1f} commitments")
348    print( "        };")
349    print()
350    print("Properties:")
351    print(f"- Per-peer memory for mainchain sync: {mem_mainchain / 8192:.3f} KiB")
352    print(f"- Per-peer memory for timewarp attack: {mem_timewarp / 8192:.3f} KiB")
353    print(f"- Attack rate: {1/headers_per_attack:.1f} attacks for 1 header of memory growth")
354    print(f"  (where each attack costs {attack_volume / 8388608:.3f} MiB bandwidth)")
355
356
357analyze(TIME)
358