Earlier quoted context omitted.
Tarsnap splits data into context-dependent chunks, then compares them via their hashes to figure out what new data needs to be uploaded.
This is interesting, because the size of a file's encrypted chunks now leaks information about the file's plaintext. I suppose you have some minimum chunk size, and that's one way to keep from leaking too much information as a fraction of the overall file size. But if a file is modified many times, it seems to me that you'd have to be very careful not to leak a substantial amount of data to a clever attacker. Have yo…
That doesn't mean that it's impossible, of course; just that it would require someone smarter than me. ;-)