When I last looked at tarsnap, I got the impression that it's a smart compressed rsync - apparently I was wrong.
bup has a FUSE frontend, that exposes every backup set as a complete file system (also through http and ftp, but the file system angle is the most useful in my opinion). Does tarsnap have something comparable? I'm going to look at it again.
No, Tarsnap is designed for backups rather than random access -- it does things like cryptographically signing archives, which is obviously only possible if you have a concept of "this archive" vs. "that other archive".
(You can extract subsets of files, as per normal tar functionality, though, and Tarsnap only downloads the files you want plus the 512-byte tar headers it needs so that it can figure out which files match your specifications.)
In that case, I did not just describe tarsnap, or at least - did not intend to.
bup _is_ designed for backup rather than random access. But it is easy enough to make those backups look like read-only file systems (bup includes an FTP server, HTTP server and FUSE module that expose a backup set through the respective protocol or as a filesystem).
But since bup builds on git, and a bup backup set is actually a git repository, you get all the git related stuff for free - e.g. bup supports cryptographic signatures in the repository by way of git's signing support -- although, for now, the "bup" command does not implement them (so, if you want to sign or verify the signature, you'll have to use git on the repository rather than bup)
Bup's deduplication is comparable to rsync's (and it reuses rsync's main tool for that). If you change a byte in the middle of a 100MB file, you'll likely need to transfer ~16k to or from backup (compared to the other version of the same file). That's also true if a byte was inserted in the middle of the file. And if you backup 100 copies of a 100MB file, was just a few bytes changed in each file compared to each other file - you'll need less than 150MB of space/storage, rather than the 10GB or so without deduplication.
You just described Tarsnap.