Proof of storage without requiring two copies

I'm looking for a way to do randomized integrity tests of my backups, because hashing it repeatedly involves a lot of time spent re-reading it off slow media. What I'm wondering is, is there an algorithm where I can test the integrity of a given file against a steeply shortened correlate of it, not unlike a hash, but employing random sampling instead of reading the entire file? (I'm using PoS interchangeably with Proof of Integrity in this post.) I understand that I can make a "deep" Merkle tree that treats large files as segmented (e.g. each next 16mb gets its own hash), but I would find it much more elegant to test with more fine-grained random selections and against a terser "hash" structure. I think of it like picrel - if I were to run a stand like this, for lunch I'd pick a random sandwhich to keep an eye on freshness. E.g. if I can pick one from the middle of the stack and not just a whole pile or one from the top, that's more reliable and costs me less.

It can't really be 'random' given that you need to preform the same hash on your original copy in order to make sure they match, Maybe you can create a function that maps hash values to file offsets (given a file size) and repeatedly rehash (using the the current hash and a hash of the contents of the file offset) to give you some pseudorandomness?

>>85770 >I understand that I can make a "deep" Merkle tree that treats large files as segmented (e.g. each next 16mb gets its own hash), but I would find it much more elegant to test with more fine-grained random selections and against a terser "hash" structure. i don't see the problem with this. make the block size smaller and then have the merkle tree have only 2 layers

>>85784 There is a problem with this, which is that I've terrabytes of data, including tons of small files, and multiple copies on diverse media, and intend to keep about 5 copies of the "index" with all the hashes. Meaning, the Merkle trees will get big as fuaaark. >>85777 Matching hashes is just one way to get a (statistical) proof of integrity. I want a system like zk-SNARK proofs of storage from filecoin: https://filecoin.io/blog/posts/zero-knowledge-and-the-filecoin-network/ BUT with a very, very much smaller storage requirement on the part of the proof requester. (And while zero knowledge is helpful in a related project, it's not a requirement for the problem I'm currently trying to tackle. I'm much more interested in reducing storage media wear.)

To clarify my issue with Merkle trees: I only need the level of guarantee against malicious and bitrot modification that a single SHA256 hash provides for a 8gb file. So if I have, say, 8mb blocks, and use 256 bit hashes, that is 128mb worth of hashes... while I only need 256 bits worth IF I read the whole file each time. That's bloating the storage requirement for my integrity verification index by a factor 1000. I believe there should be a way to make that factor orders of magnitude smaller, the Merkle tree is my worst-case for storage requirement. Also: The naive/single hash and Merkle tree solutions are both sensitive to replay attacks. I'd like to not have to trust my backup system to remain as friendly as it has proven itself to be thus far; so it shouldn't be possible for it to cache a set of proofs and throw away the backing data. Filecoin has a proof system that doesn't require this type of trust, but it only works when the verifier has their own copy of the data to generate proof requests with. I'm currently reading this paper and see I'm way behind current research and theory regardless: https://www.sciencedirect.com/science/article/pii/S2096720924000344 I suppose I'll implement Merkle trees and take a hike until that's done! Make *something* work before I ratchet up the quality... Thanks for the feedback!