New idea

What if some nodes on the network signaled that they are willing to provide an extra bit of data to their peers upon request, which is this: if your node asks theirs to prove that a certain utxo is spent, they will provide that proof, if they have it, in the form of (1) the earliest transaction in the blockchain that spends that utxo (2) and a merkle proof proving that transaction is included in a certain block’s block header. Your node can then validate that transaction and validate the merkle proof – which even a pruned node can do.

How this helps

If your node connects to peers who signal that feature, then it does not need to store a full copy of the utxo set. The reason is this: suppose you discard some utxos, including utxo Q, and a new block comes in containing a transaction that claims to spend utxo Q. To validate it, you request from your peers a proof that utxo Q was spent. Per the trust assumption stated in Number 1, not all of your peers will withhold this data from you, so if the utxo was spent before the current block, you will learn of it, and that will prove that utxo Q was spent already, so the block is invalid; otherwise, utxo Q was not spent already, so the block is not therefore invalid.

Optimization

Nodes which use this technique could therefore prune their utxo set. To limit network requests, they could also keep a configurable amount of utxos, e.g. the most recently created 1 gigabyte of them, and prune the remainder. Then, if anyone spends an “old” utxo, use the method outlined above to recover it from your peers, and continue validation.