Any chain with low enough fees, even without, can be spammed by data that just lives forever at no cost.
Just use real storage costs bro
There's an Ethereum paper that basically just resorts to "set some arbitrary and low price and just leave it there," which will need adjusting from the social layer, thus isn't robust.
Stateless solutions remove the problem altogether (not really)
AFAIK any accumulator requires that members of the accumulated state have up to date proofs sent to them - that means every block every user needs a specific updated member-proof sent their way.
This interactivity requirement is heavy, and might cost more than just storing the data itself, while also requiring greater involvement from nodes; a user can't just keep their transaction and spend it later, they have to keep updating their membership proof.
The reason market-driven solutions are so hard is for two reasons:
1) Every node must have the complete unspent transaction set.
2) The transactions you want to expire don't give input to a pricing mechanism.
Sharding solved this a long time ago
Sure, if you can shuttle the lowest value transactions and dust to a shard, you've unburdened the other shards by what has been. But who runs the shit shard? And other pressing concerns (like sharding UX).
ZK Proofs
ZK Proofs are great and will revolutionize light clients, but you still need to generate proofs over the full set of unspent transactions, which means it needs to be maintained.
Filecoin!
Filecoin is made to support non-universal state. Blockchain transactions must be known by every node, a challenge Filecoin doesn't need to meet.
Has anyone solved this problem without just hardcoding a price or pretending it isn't a major issue or relying on muh governance?