Review this, is it accurate, are there errors:

I connected two Bitcoin Core nodes running on mainnet, one prefilling transactions to a node that only received `CMPCTBLOCK` announcements from its prefilling peer. Even though the intended effects of prefilling transactions are network-wide, and it would be nice to have some more complicated topologies and scenarios tested in e.g. [Warnet](https://github.com/bitcoin-dev-project/warnet), this basic setup can be used to validate some of the basic assumptions of the effects of prefilling:
1. Does prefilling work to prevent failed block reconstructions that otherwise require `GETBLOCKTXN->BLOCKTXN` roundtrips, irrespective of the cost of prefilling?
2. Does prefilling result in a net reduction on block propagation times?

# Latency and Bandwidth

Taking a simplified view, the latency for a receiver to hear an unsolicited message (the scenario we care about in block relay) consists of
transmission delay plus propagation delay: 
$$
\text{Latency} \approx \frac{\text{Data}}{\text{Bandwidth}} + \sim{\frac{1}{2}} * \text{Round-trip time}
$$

Any time compact block reconstruction fails because the receiver was missing transactions, an additional round-trip-time (RTT) of requesting missing transactions and receiving them (`GETBLOCKTXN->BLOCKTXN`) must be paid in order to complete reconstruction. Where $f$ is the probability for a block to fail reconstruction:

$$
\text{Latency} \approx \frac{\text{Data}}{\text{Bandwidth}} + \sim{\frac{1}{2}}\text{RTT} + f * \text{RTT}
$$

If we had perfect information about the transactions our peer will be missing, we should always send these along with the block announcements since we will pay basically the same transmission delay, minus the unnecessary round-trip. If we don't have perfect information, then the worst we can do is send transactions which our peer already knew about, while not sending them transactions they didn't know about, incurring the RTT anyways, plus the transmission time of the redundant data. Let's say we send $p$ extra prefill bytes, with each byte having a probability $n$ of being redundant and prefilling $p$ bytes gets us a reconstruction failure probability of $f_{p}$, then:

$$
\text{Latency} \approx \frac{\text{Data}}{\text{Bandwidth}} + \frac{p * n}{\text{Bandwidth}} + \sim{\frac{1}{2}}\text{RTT} + f_p * \text{RTT}
$$

Thus, in order in order for prefilling latency to be better than or equal to no-prefilling latency:

$$
\frac{p * n}{\text{Bandwidth}*\text{RTT}} \leq f_0 - f_p
$$

<details><summary>Derivation</summary>

If latency while prefilling is less than or equal to latency without prefilling, where $b$ is bandwidth, $r$ is the RTT, $d$ is the size of the CMPCTBLOCK without prefill, $p$ is the size of the prefill, and $f_p$ is the reconstruction failure rate at a given prefill size $p$:

$$
\frac{d}{b} + \frac{pn}{b} + \frac{1}{2}r + {f_p}{r} \leq \frac{d}{b} + \frac{1}{2}r + {f_0}{r}
$$

Subtracting the common terms $\frac{d}{b}$ and $\frac{1}{2}r$ from both sides:

$$
\frac{pn}{b} + {f_p}{r} \leq {f_0}{r}
$$

Subtracting ${f_p}{r}$ from both sides:

$$
\frac{pn}{b} \leq {f_0}{r} - {f_p}{r}
$$

Dividing both sides by $r$:

$$
\frac{pn}{{b} {r}} \leq {f_0} - {f_p}
$$

</details>

If we plug in some example values, prefilling 10KiB with a bandwidth of 5 MiB/s and an RTT of 50ms (.050s) and use a worst case $n$ of 1

$$
\frac{10\text{KiB}*1}{5 \text{MiB/s} * 0.050\text{s}} = 0.0488
$$

In this case, if prefilling improves reconstruction rates by at least 4.9% it is definitely better than not prefilling.

### Takeaways
I don't think proving that the above formula is satisfied is necessary for a prefilling solution, what I think it's useful for is building an intuition of the problem, and setting theoretical boundaries on how effective prefilling needs to be to be worth it.
- Nodes are likelier to suffer rather than benefit from prefilling that have smaller $Bandwidth * RTT$ (See [Bandwidth-delay product (BDP)](https://en.wikipedia.org/wiki/Bandwidth-delay_product) connections: e.g. nodes with low bandwidth and low ping. And nodes that have connections with large BDP's are likelier to benefit, e.g. high-bandwidth, and high-latency ("Long Fat Networks" as described in [RFC 7323](https://datatracker.ietf.org/doc/html/rfc7323#section-1.1))
- If the redundant broadcast probability $n$ is zero, prefilling is always worth it.

## TCP windows and the costs of prefilling.

But, the use of TCP in the Bitcoin P2P protocol complicates this, because a sender will not send data exceeding the TCP window size in a single round-trip. Instead, they will send up to the window size in data, wait for an `ACK` from the receiver, and then send up to `window` bytes after the data which was `ACK`ed. That means that if we exceed a single TCP window, we will have to pay an additional RTT in propagation latency (and a little bit of transmission latency for the overhead). And for each additional window we overflow, we will pay another RTT:

$$
\text{TCP Latency} \approx \frac{\text{Data}}{\text{Bandwidth}} + \sim{\frac{1}{2}}\text{RTT} + f * \text{RTT} + \lfloor{\frac{\text{Data}}{\text{Window Size}}}\rfloor\text{RTT}
$$

Note $\lfloor a \rfloor$ meaning `std::floor(a)`

Doing a similar dance as above, where $p$ is the prefill size and $f_p$ is the probability of reconstruction failure at prefill size $p$, and $n$ is the probability of a prefill byte being redundant:

$$
\frac{p*n}{\text{Bandwidth}*\text{RTT}} \leq f_0 - f_p + \lfloor{\frac{\text{Data}}{\text{Window Size}}}\rfloor - \lfloor{\frac{\text{Data}+p}{\text{Window Size}}}\rfloor
$$

### Overflowing current TCP window is always worse than doing nothing

The above formula establishes as a rule something which might have been intuited, that if the prefill causes us to exceed the current TCP window, then we will always do worse than if we hadn't prefilled, since:
1. $f_0 - f_p \leq 1$ since the smallest number $f_0$ can be is 0, and the largest number $f_p$ can be is 1.
2. $\lfloor{\frac{\text{Data}}{\text{Window Size}}}\rfloor - \lfloor{\frac{\text{Data}+p}{\text{Window Size}}}\rfloor \leq -1$ if the prefill overflows the current partially filled TCP window.
3. If $a \leq 1$ and $b \leq -1$, then $a + b \leq 0$, so the right hand side of the formula is $\leq 0$.
4. The left hand side of the equation will always be $\geq 0$, since none of the variables on the left side can ever be negative.
5. If $lhs \geq 0$ and $0 \geq rhs$, then $lhs \geq rhs$, so the left hand side will never be less than the right hand side, therefore prefilling will never be beneficial.

But, if we bound our prefill $p$ so that we never increase the number of TCP windows used, i.e.: $\lfloor{\frac{\text{Data}}{\text{Window Size}}}\rfloor - \lfloor{\frac{\text{Data}+p}{\text{Window Size}}}\rfloor = 0$ which, I believe is [easy](https://delvingbitcoin.org/t/stats-on-compact-block-reconstructions/1052/29) to do, we can use the exact same formula as above to decide whether or not prefilling is effective:

$$
\frac{p * n}{\text{Bandwidth}*\text{RTT}} \leq f_0 - f_p
$$

### Complication: TCP Retransmission
So far, U have assumed perfectly reliable networks and this isn't always the case, packets do get lost. But, I believe the problem above I've described in relation to prefilling is very similar to the problem that the designers of TCP had in selecting a static window size, and later, dynamic window sizes through congestion control algorithms those described in [RFC 5681](https://datatracker.ietf.org/doc/html/rfc5681) and [RFC 9438](https://datatracker.ietf.org/doc/html/rfc9438). Instead of the probability that a block reconstruction will fail, they deal with the probability that a packet will not arrive, in both cases, the consequence is an additional round-trip, and a core question is whether the marginal value of potentially saving a round-trip by packing in more data, is worth the risk that retransmission will be necessary anyways (or re-routing around low-quality connection). There are many other considerations for TCP congestion control algorithms, but I argue that we can outsource this question to the operating system's congestion control implementation, and trust that the congestion window provided by the operating system for a connection is a message size that is unlikely to lose any packets.

# Observation Setup

I connected a prefilling node to a prefill-receiving node, both with additional logging to measure things like TCP window sizes, and recorded measurements over 20 days[^1]

## Prefilling node
I ran one node with 0xB10C's prefilling branch([0xB10C/2025-03-prefill-compactblocks](https://github.com/0xB10C/bitcoin/commits/2025-03-prefill-compactblocks/)) with some additional logging ([davidgumberg/06-18-2025-0xB10C-prefill-branch-with-logging](https://github.com/davidgumberg/bitcoin/commits/06-18-2025-0xB10C-prefill-branch-with-logging/))

In summary, the prefilling node, during compact block reconstruction, [identifies as prefill candidates](https://github.com/0xB10C/bitcoin/commit/b381c1ed035f1f8cbc1a41fe383b8329e948a775) transactions that were in the block and not in its mempool. When sending CMPCTBLOCK's, it [passes the prefill candidates](https://github.com/0xB10C/bitcoin/commit/fd07f0164683572e0eeed1787711831859ef0fab) in the `PrefilledTransaction` structure of the `CMPCTBLOCK` announcement, [described](https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki#prefilledtransaction) in [BIP-0152](https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki). Presently, `PrefilledTransaction` is [only used](https://github.com/bitcoin/bitcoin/blob/b53fab1467fde73c40402e2022b25edfff1e4668/src/blockencodings.cpp#L25) by Bitcoin Core to prefill coinbase transactions.

## Prefill-receiving node
I ran another node on a branch which will only ask for and listen to `CMPCTBLOCK` announcements from manually added peers (https://github.com/davidgumberg/bitcoin/commits/5-20-25-cmpct-manual-only/). I made a manual connection from this node to the prefilling node, this node doesn't do any prefilling, but like every Bitcoin Core node today, it will parse and use `PrefilledTransaction`'s that it receives. No changes are required for nodes to enjoy the benefits/drawbacks of prefilling that their peers do, but I modified this node in order to measure the effects of receiving prefilled blocks in isolation.

## Config


[^1]: That is how long it took for `debug.log` to fill an 80GB disk with `-debug=net` on :)