[icebraining]

Dunno about SpiderOak, but the way Tarsnap does it, is that as blocks are encrypted and uploaded, the client keeps metadata about them locally (presumably an hash, size, etc). Then that metadata is also encrypted and uploaded to the server. When it wants to upload more blocks, it just looks at that metadata and skips duplicated blocks, updating only the metadata to point to the existing block.

[cperciva]

All of that is correct, but more to the point: Client data is deduplicated before it is encrypted.