> 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