App backup deduplication research

[grote]

Currently, Seedvault stores all app data as it receives it by the system: one large block per app. Seedvault's storage encryption was developed in collaboration with the developers of well known backup tools as well as security researchers. It uses clever tricks to deduplicate data and allow restore of several backup snapshots while only storing the data once. In this ticket, we want to research how a similar concept could be applied to app backups as well.

• [ ] Research options for deduplicating app data and allowing different snapshots and faster integrity verification
• [ ] Write up finding in a research report and publish this in the project repository

[grote]

Some info how the system is preparing app data for backup:

• creating the tarball for app data happens in native code.
• tarballs include an app manifest written by AppMetadataBackupWriter.
• assembling the complete tarball probably happens in BackupAgent#fullBackupFileTree().
• Files are scanned using File#listFiles() which is not deterministic ([official docs](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/io/File.html#listFiles())). So two backup runs against the same data may produce different tarballs which is bad for deduplication. Sorting the files there may help.