Now, I will list the problems we have encountered along the way.
First, you need problem suppliers. Blockchain does not need a problem supplier, hash puzzle is adjustable.
Second, proof-of-whatever must be very easy to verify. I mean the ratio between solving proof-of-whatever and verifying it must be really high. Unfortunately, read mapping is not a problem like that. Yes it is still NPC but verification takes way longer time than what is required.
Finally, privacy concerns. You must use encrypted, anonymized and distributed data. Current read mapping techniques do not accommodate to such needs. There are proposals[1] to satisfy these requirements but they do focus on hybrid cloud techniques which means network bandwidth is not a concern for them. However, blockchain applications are greatly concerned with network bandwidth.
*edit: references