Quite a few people have tried; AFAIK, no one has succeeded. There are storage-based blockchains, but they just use traditional proof-of-work with storage-focuse

Quite a few people have tried; AFAIK, no one has succeeded. There are storage-based blockchains, but they just use traditional proof-of-work with storage-focused smart contracts. In most schemes I'm aware of, the nodes are storing useful data. But perhaps you are suggesting that they store arbitrary data, e.g. deterministically generated data? My colleague and I wrote a paper about something like this a while ago. We called it "proof of capacity." The basic idea is that you deterministically generate a bunch of hashes based on some seed. Then, at a later time, you are "challenged" to return one of the hashes. Pretty standard so far, but here's the trick: you aren't asked to return, say, the hash at index i. Instead, you are challenged to provide the hash lexicographically closest to some random hash X. This obviously requires sorting the generated hashes, which is why you can't just regenerate them on the fly. And you can get a rough estimate of the node's capacity by seeing how close their hash is to hash X: the more capacity, the more hashes, and thus the closer their hash will approach X.