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.