ZFS does that with snapshots already. (ZFS is not encrypted, but the principle is the same)

I believe immutable trees would be the correct algorithm here.

The algorithm relies on a tree structure, where the leaves are the files. Every time a new snapshot is written, every leaf node changed writes a new path to the root node, while leaving the rest of the tree intact.

When a snapshot needs to be deleted, you just remove all the old root nodes and have a garbage-collection like-process delete all the old files.

EDIT: Look at example here: https://en.wikipedia.org/wiki/Persistent_data_structure#Tree... . When xs is deleted, nodes a,c,f can also be deleted.

EDIT2: I feel like I can never make posts like these while keeping it short and sweet, and adding enough details. ZFS can be encrypted, but accessing any files is right at its fingertips, not over a slow network connection. And there are caveats about how to encrypt the metadata, but you do not need to decrypt the whole backup to figure out what to do delete.

AFAIK that is exactly how restic works. You use `restic forget` to remove the roots (snapshots), then `restic prune` garbage collects unreachable blobs.

ETA: However, nearly all data in restic is encrypted. This includes the index files. So you still need to have the encryption key to look at snapshots and walk their trees.

If the backup server has access to the tree structure, then the backup isn't fully encrypted, or at least the metadata isn't. Now you need to have a conversation about what metadata is allowed to be stored unencrypted on the server and what metadata isn't. If you want a fully encrypted deduplicated backup system, I don't see how it's possible to prune without the ability to decrypt, because there's no way to know what needs to be pruned.

> ZFS is not encrypted

It certainly can be (as of zfzol 0.8, and oracle zfs has its own encryption scheme).

https://github.com/zfsonlinux/zfs/pull/5769

> (ZFS is not encrypted, but the principle is the same)

Neither.

The backup server should have information about when a particular backup was made, it should be able to prune based on backup date without having the ability to read any of the data inside the backup.

This doesn't make any sense when the backups are deduplicated (or incremental). A given file/block/whatever unit of data isn't uniquely associated with a single backup.

I assume the backups are incremental, so you cannot just toss old encrypted files without losing backed up files.

Worse, it's deduplicated, using a similar algorithm to git. You can forget old backups and theoretically that could be done without decrypting but deleting the actual data will require a decrypt.

It should be possible to have an index that says "this encrypted blob belongs to this particular snapshot". It introduces a "plain text" component of course, in that the snapshot information (name/date or whatever) is readable.

But then, I assume the way it is written, there are some blobs that belong to multiple snapshots, and some bits of blobs that belong to one snapshot but not another etc.

So given the implementation, it may not be possible, but it's still a drawback of this particular implementation that people should be aware of.

I'm no encryption expert, but depending on how the data is partitioned it can be easier to securely prune encrypted data than unencrypted data. For example, securely wiping an encrypted drive is as easy as tossing the key.

If you wish to "securely" wipe an encrypted drive, it's best to write over the old data a few times using randomly generated keys, tossing the keys each time you do a write over.

That sounds pointless. If you have real crypto, tossing the key (in a way that it cannot be recovered) is absolutely enough.

It's not pointless - it's pretty standard practice.

For example, although drives in Google Cloud are encrypted at rest, once they are decommissioned the drives are physically destroyed: https://cloud.google.com/security/deletion/#ensuring_safe_an...

> When a hard drive is retired, authorized individuals verify that the disk is erased by overwriting the drive with zeros and performing a multi-step verification process to ensure the drive contains no data.

Thanks. I guess the reason is to avoid future decryption due to either a new crypto attack or to avoid being vulnerable to potential errors in key generation.

This is massive overkill. Once is enough. If the drive is already encrypted, just wipe the key.

Perhaps by using homomorphic encryption?

https://en.wikipedia.org/wiki/Homomorphic_encryption

Couldn't the client just tell the server what to delete? Which would require only downloading an (encrypted) index of what data is in use, not downloading and reuploading the data itself.

I think that's what it does, but that downloading of encrypted indexes and comparing them takes time. Which is what was complained about.