> But as you've observed, the failure probabilities are rather high,
> especially if an active attacker targets nodes carrying less commonly
> available blocks.

Wouldn't the solution be for nodes to use whatever mechanism an attacker uses to determine less commonly available blocks and choose to store a random percentage of them as well as their deterministic random set?

IE X blocks end of chain (spv bootstrap), Y% deterministic random set, Z% patch/fill set to deter attacks