Do they ask for exactly one random byte for every 4mb hashed block?

For a <4mb file, if you just guessed a random byte and try 256 times, wouldn't you probably get it right at least once?

Still, they could easily change the scheme to ask for more bytes to reduce the chance of a correct guess, plus it would be hopeless for large files.

They could give you a sufficiently long random salt and ask you to calculate the hash of the salt and block contents. This scheme seems to be secure.