Does this mean Tarsnap de-dupes before encrypting? That doesn't seem to make sense but I don't see any other reason going through their server would be required.
Tarsnap uses content based hashing too. The pipeline is basically: tar | chunk | encrypt | upload-new-chunks
The tarsnap server provides a transactional KV store-- "In order to create a new archive, the tarsnap client sends a "write transaction start" request, many "write data" requests, and a "commit transaction" request to the tarsnap server; deleting an archive is similar (except with a "delete transaction start" and "delete data" requests)." http://www.daemonology.net/blog/2008-12-14-how-tarsnap-uses-...
The tarsnap server provides a transactional KV store-- "In order to create a new archive, the tarsnap client sends a "write transaction start" request, many "write data" requests, and a "commit transaction" request to the tarsnap server; deleting an archive is similar (except with a "delete transaction start" and "delete data" requests)." http://www.daemonology.net/blog/2008-12-14-how-tarsnap-uses-...