Merkle proofs for storage providers is the right call. You basically want proof-of-storage the same way Bitcoin wants proof-of-work: make cheating more expensive than honesty. If a provider loses your data and you can prove it on-chain, that's game theory doing the enforcement instead of lawyers. The hard part is making the economics work for small files without the overhead eating you alive.