I'm not aware of any Proof-of-Storage systems but Storj and similar projects are combining blockchain cryptocurrency with p2p storage.
It's an interesting idea.
Happy to jump in as the founder of one of these, Sia. We build consensus using proof of work, and then we throw some smart contracts on top of the consensus system to build a secure marketplace for cloud storage.
The result so far has been really potent. On the Sia network today, raw storage (pre-redundancy) costs about $0.30 per TB. Performed intelligently, you only need about 2x redundancy, putting the total cost at less than 1/10th of Amazon glacier.
I project that as the network grows, demand will catch up to supply more and the price will settle closer to $2 / TB / Mo for raw storage.
I can answer any questions.
I was thinking something like write a bunch of random numbers to disk, and prove that you have the ability to retrieve any of them at will.
This is obviously not a complete solution. I was asking if anyone knew of any such system.
A positive, not negative, feature of the system is you must be able to rewrite all the storage each time. So the faster your can write the more blocks you win, but also the more storage you have the more blocks you win (and it's a tradeoff between them).