BIP332: Stale Tip Relay #2241

This can be left to the reference implementation section.

The URL here is the temporary experimental featureid, not just a reference implementation link. BIP 434 requires an unassigned experimental feature to use a globally unique identifier, such as its repository URL. I’ll clarify that distinction and move the standalone implementation link to the Reference Implementation section.

For features published as a BIP, the featureid SHOULD be the assigned BIP number, eg "BIP434", or be based on the BIP number (eg, "BIP434v2" where the "v2" suffix covers versioning, or "BIP434.3" where the ".3" suffix covers part 3 of the BIP). For experimental features that do not (yet) have a BIP number assigned, some other unique identifier MUST be chosen, such as a URL to the repository where development is taking place, or the sha256 digest of some longer reference.

It's weird to expect an specification proposal might not get a number… Why not specify BIPxxx for now an update when a number is assigned, without the conditional?

Actually, this gets confusing here: the feature is called staletip everywhere, but the serialization in BIP434 featureid part of the message should be BIPxxx?

staletip is the descriptive feature name and P2P message command. It isn’t the serialized BIP 434 featureid. The experimental implementation currently uses the repository URL as its globally unique featureid, and the published specification will the BIP number. I’ll make that distinction explicit.

Since the feature is versioned, this slack is really needed? I mean, why not accept EXACTLY one byte with the two expected values?

Good point :). BIP 434’s versioned feature IDs give us a clean way to make future changes. I’ll update the specification to require one byte with value 0x00 or 0x01.

Nodes implementing this specification MUST use BIP 434 to negotiate support before

headers that do not become part of the node's active chain. This BIP defines a new
optional peer-to-peer (P2P) `staletip` message for announcing recent stale chain tips to

I think your specification should start here, after all, the new message is the whole point of the specification. The subsections that came before are details (parametrization) or negotiation. Not only, the previous subsection makes mention to the staletip message, but it was never defined before this point which makes the text confusing.

Fair enough. I’ll move the staletip message definition, including the CompressedHeader format, to the start of the Specification section.

This is already required as per BIP434, AFAIK. Since BIP434 is required, I don't see the need to repeat it's mechanisms in this document.

Removed it.

"post-handshake" isn't obvious?

I think oldest to newest may by confusing here without a proper definition. I believe you meant something like "in chain order" (in the order they would appear if connected to the best chain). But even this can be confusing, e.g. what do I do if I have two different stale blocks that refer to the same previous block? I'm not sure the best solution, maybe order they lexicographically.

It is defined in line 147, but the raised issue seems to still persist.

Updated to in chain order

How can a remote node ensure that?

The sender can determine this from its per-peer header state. A fork_point is known if it is an ancestor of a block previously announced by the receiver OR of a header the sender previously sent on the same peer. I can clarify this if that’s not clear in the spec.

Aren't you assuming an internal implementation detail from Core? Other implementations like btcd, floresta or libbitcoin all maintain that information?

That's a fair push back How's this then -

Nodes sending a staletip message MUST have a basis for expecting the receiver to know the fork_point. How this is determined is implementation-specific. For example, the sender may use block or header announcements previously exchanged with the receiver on the same connection.

Aren't you assuming an internal implementation detail from Core?

I think this spec should state that that compliant nodes SHOULD always announce their latest tip to staletip peers, either by a CMPCTBLOCK message, a HEADERS message, or an INV message, even if that peer had already announced the same block; and should use this information when provided by a staletip peer to calculate the appropriate fork point.

a 1, 3, 5 or 9 byte `CompactSize`, then serialize each member of the vector. Only

This is somewhat out of place: the previous and the following paragraphs both refer to the have_block field.

Should be very rare on mainnet, but I believe this should work well on the testnets as well. And there, stale blocks are quite frequent, so this is a bad assumption.

This is a good point. @w0xlt @ajtowns - We'll probably have repeated announcements ion testnet if the feature is enabled. Do you think this warrants reserving a 1-byte ID in BIP 324. It would save 12 bytes per message.

I have a different patchset to make BIP324 message type id assignment automatic and not need specifying/coordinating; https://github.com/ajtowns/bitcoin/tree/202605-bip324-id

Repetition of the negotiation section?

Again, I don't see how this can be asserted.

Can't this create a DoS vector somehow?

Yes. The intent was only to avoid punishing a peer for a one-off message that exceeds implementation-specific policy limits. Repeated messages can be treated as abuse, so I’ve clarified that implementations may rate-limit or disconnect peers that repeatedly exceed those limits.

add any new valid headers to their block database.

Isn't this an internal implementation detail? A specification for networking messages should specify the observable behavior between peers, not what they do internally with the messages.

Removed that part of the sentence :)

Can't this open a DoS vector?

DoS vectors for p2p are for processing time or memory/disk usage or amplification attacks where we receive a small amount of garbage data and then send a large amount of garbage data to other peers as a result. The bandwidth it takes to send the message isn't a DoS vector, because there's a million ways to send data to a p2p node, and you can't prevent all of them.

SHOULD request missing block data for the announced stale branch in the normal

Sounds that MAY would work better here. What if I already have that specific stale block, SHOULD I request it again?

What if I already have that specific stale block

Spec says "SHOULD request missing block data". If the node already has that stale block, its data is not missing and should not be requested again.

It assumes there's only one stale branch, which is probably not true in testnet and may even happen in mainnet. The design can deal with more than one competing branch?

Each staletip message describes one linear branch. If there are multiple competing branches, the sender will have to send a separate message for each one. I’ll clarify this in the spec.

Not sure this is necessary and potentially implies maintaining this code in the specification over time.

I think having the reconstruction algorithm in the specification is helpful. That said, it doesn’t need to be C++, so I’ve replaced it with pseudocode.

This clarification seems useful. See other comment about ordering.

what is the reason for choosing 1000 blocks when Bitcoin Core, as the most used implementation, would reject any header more than ~144 blocks old (GetAntiDoSWorkThreshold)? With the current implementation, it seems that these older headers would be sent out but would not be accepted by the peer by default. Or does the BIP intend to recommend that participating peers accept headers to their database within STALETIP_RECENT_WINDOW, basically recommending to lower the 144 block threshold?

Just a round number; more inspired by the average interval between stale blocks on mainnet (so that there's a decent chance a new node using this feature would see data fairly quickly) than anything else.

ok, but I find it not ideal to ask for stale headers and then immediately discard them because they are too old to satisfy GetAntiDoSWorkThreshold.

STALETIP_RECENT_WINDOW number is arbitrary. 1000 blocks gives monitoring nodes roughly seven days to discover staletip data.

With the current implementation, it seems that these older headers would be sent out but would not be accepted by the peer by default.

Good catch, this might've been an oversight in the PoC implementation. Staletip relay path should probably define a separate bounded acceptance policy.

ok, but I find it not ideal to ask for stale headers and then immediately discard them because they are too old to satisfy GetAntiDoSWorkThreshold.

Right, but that's a problem with the implementation, not the spec? (Beyond the spec noting the interaction to help implementers avoid pitfalls, anyway)

I think 48 hours / 288 blocks hours is likely enough for a stale tip to propagate to 99% of interested nodes just via extra-block-relay-only connections if only 1% of listening nodes support stale tip relay, and 24 hours / 144 blocks is likely enough if ~2.5% of listening nodes support the feature. Those numbers are worse if the extra-block-relay-only connections fail frequently due to addrman poisoning, or better if there are enough stale tip relay nodes that they form connected components in the p2p network. Also better if non-listening nodes are participating. So to me, that says changing this to recommend 144 wouldn't be overly concerning, but I'd still lean towards 1000 to maximise propagation chance to anyone interested.

def propogate(lnodes, support, blks):
    probes = blks*2 # 10min blks, 5min extra-b-r-o-conn
    have = [False]*int(lnodes*support)
    t = len(have)
    assert t > 1
    have[0] = True
    for _ in range(probes):
        for i in range(t): # each node makes a probe
            k = int(random.random() * lnodes) # who does i connect to?
            if k < t and (have[i] or have[k]): # staletip relay?
                have[i] = have[k] = True
    return sum(have)/t
    
sum(propogate(20000, 0.01, 144) for _ in range(20))/20
# 0.542 -- 54% of staletip relay nodes see the stale tip with 1% sat over 144 blocks
sum(propogate(20000, 0.01, 288) for _ in range(20))/20
# 0.9894999999999999 -- 99% of staletip relay nodes see the stale tip with 1% sat over 288 blocks
sum(propogate(20000, 0.025, 144) for _ in range(20))/20
# 0.9994999999999999 -- 99% of staletip relay nodes see the stale tip with 2.5% sat over 144 blocks
sum(propogate(20000, 0.003, 1000) for _ in range(20))/20
# 0.9991666666666668 -- 99% of staletip relay nodes see the stale tip with 0.3% sat over 1000 blocks

I was just thinking that in the context of the increased peer limit of Bitcoin Core, this could be even more reliable if blocks-only peers optionally participate in stale tip relay. Perhaps this BIP could make a recommendation whether stale tips should be announced on blocks-only connections or not.

Right, keeping 1000 blocks in the spec gives stale tips a better chance to propagate while adoption is low. Implementations can still apply stricter local limits. I’ll add a note that implementations reusing their normal header-processing path should ensure its admission policy is compatible with its staletip recency window.

blocks-only peers optionally participate in stale tip relay

I don't think block-relay-only mode is documented in a BIP anywhere (treating it as a node configuration details rather than a standard), so it seems slightly weird to introduce it as a BIP-worthy concept here?

I think stale tip relay/announcements should be done on block-relay-only connections, because that allows the extra-block-relay-only connections to make the p2p graph dynamic for the purposes of this message, making it more likely to achieve wide distribution.

In the common case it is the block where the stale branch diverges from the receiver's active chain.

I think this might be slightly ambiguous. In the example

A -> B -> C -> D    < best chain
          \
           D'                < stale branch

it is clear from the definition above that the fork_point is C, but one could interpret this sentence as saying that the fork_point is D'.

Instead, I would say:

In the common case, it is the last common block before the stale branch diverges from the receiver's active chain.

Thanks for taking the time to review.

In the common case, it is the last common block before the stale branch diverges from the receiver's active chain.

Agree this is clearer. I'll update it.

nit: I think MAX_RETAINED_STALETIPS should get its own paragraph, instead of being joned at the end of STALETIP_RECENT_WINDOW's paragraph. I would split in two paragraphs.

What happens when a node already has MAX_RETAINED_STALETIPS stale tips stored and receives a new one? Should it ignore the new tip, or evict an existing one?

Should probably be called "ADVERTISED" (or similar) rather than "RETAINED" -- (except for pruning) core retains all the stale tips it has, eg. Advertising the 10 stale tips with most accumulated work, and in the case of a tie, dropping the oldest is probably reasonable for ensuring the tips most likely to be involved in a reorg are available.

Choosing randomly would probably maximise the number of tips available to the network, particularly if it were re-randomized per connection.

Should it ignore the new tip, or evict an existing one?

I think the exact policy can remain local to the implementation. Agree with AJ, a reasonable policy would be to keep the tips with the most cumulative proof of work.

• A new tip with more work would replace the lowest-work entry.
• Among tips with equal work, the most recently learned tips would be retained.
• A new tip with less work than every existing entry could be ignored.

Should probably be called "ADVERTISED" (or similar) rather than "RETAINED"

MAX_ADVERTISED_STALETIPS sounds more like a lifetime or per-peer announcement limit. How about MAX_STALETIP_RELAY_SET_SIZE?

I can also include a line when expanding on that constant -

A node's stale-tip relay set is the set of stale tips currently selected for later announcement.

Wouldn’t one of the interesting uses for this BIP be to map the many branches of testnet4?

Good point. I can see mapping competing branches on testnet4 being useful. Do you think the BIP should avoid prescribing a difficulty threshold for testnet3 and testnet4 and leave it entirely to local policy? We could drop these two recommendations and rely on the general proof-of-work, rate-limiting, and resource-bound requirements instead.

Difficulty one blocks can be created at a rate of ~200/s per TH/s, so a map that includes those doesn't seem very useful, and likely opens you up to a disk filling attack: make your diff-1 alternative blocks contain 1MvB worth of txs that conflict with the main chain. They're only listed as MAY and SHOULD requirements, so you could still do this while complying with the bip, though.