@realn2s i was thinking about this with i believe @heptapodEnthusiast and we were both kind of unsure how to achieve collision resistance without indifferentiability but i am pretty sure i figured out a cheat code for this and it is basically to retain the entire tree of hash computations at all times, and then invent a tree hash for directory trees:
for file hashes, use a tree hash like BLAKE3 (i'm making some tiny changes personally) and just retain the entire hash computation tree. this will take something like C * log^2 n space for C = chunk size and n = number of chunks
for directory hashes, we need two components:
- something to mix together the top-level checksum from the entry's content with the entry name string. since we really do want to catch name changes that don't change the content we will have to think harder here. maybe up to a certain name length we just store the whole name in-place along with the hash value. the point is to get a standard-size hash value we can cast into an integer
- we use modular exponentation (i.e. diffie-hellman) to commutatively hash the directory entries
that's it!
it should be possible to store the resulting hash tree in a fixed amount of space per directory entry, and you can limit the size of the transmitted hash tree by just stopping your bread-first search after some point
then you get a certificate that not only indexes into a remote object db, it's also self-certifying