That's not exactly rocket science these days (see bup). What you're paying for with tarsnap is making it totally rock solid and as usual the last 90% of the work is also 90% of the cost.
The query that suxnoll responded to supposed that you have 400 GB of data with small deltas. But that's only possible if you're filling your harddrive with files created from random noise from /dev/random and updating all your files monthly by more random noise.
Actually, combining crypto and dedupe in such a way that the server can never tell what's on the client computer but the client can still reliably pick what's changed and dedupe it?
That's honest-to-goodness computer science. And Colin is the guy who invented this stuff.