commit 36d2d3d52dd240d0982bb54ba027784defbe8350
parent 2186f753d98149e1e10bc226b759c02ab2694c95
Author: Iván Ávalos <avalos@disroot.org>
Date: Mon, 17 Aug 2026 23:52:15 +0200
Reapply "dd92: add threat model and limitations sections"
This reverts commit 5b107137c83b914a9676e4b15e916b58e634a2c1.
Diffstat:
1 file changed, 97 insertions(+), 45 deletions(-)
diff --git a/design-documents/092-incremental-backup-sync.rst b/design-documents/092-incremental-backup-sync.rst
@@ -50,7 +50,9 @@ Requirements
* **Confidenciality/E2EE:** No information about the contents of the wallets
should be accessible or derivable by any third-party who lacks control over
- the wallet, including the backup service.
+ the wallet, including the backup service. Any potential metadata
+ leakage—such as backup file sizes, upload frequencies, or timing
+ patterns—should be minimized to the highest extent possible.
* **Incrementality:** The solution should minimize network usage and bandwidth
by incrementally uploading and fetching updates to the global state when
possible, limiting the situations where a full backup or restore is
@@ -59,6 +61,30 @@ Requirements
can be decrypted or retrieved from the backup after its deletion, including
the evidence that such information was deleted.
+.. _threat-model:
+
+Threat model
+============
+
+The design protects the confidentiality of the wallet's backup contents
+against any party that does not hold the wallet's backup encryption key,
+including the backup service itself. Blocks and blobs are end-to-end
+encrypted with keys derived from secrets that only the user's wallets know,
+so neither a passive network observer nor the operator of the backup service
+can learn anything about the contents of a backup from the data they can
+access.
+
+Within this model, the backup service is trusted to honor deletion requests
+and to not retain deleted blocks nor previous versions of updated blocks. The
+protocol does **not** defend against a service that fails to do so: while
+such a service still cannot decrypt the retained data, it can defeat the
+plausible deniability requirement by preserving evidence that certain
+information once existed in the backup, and countering this would be
+impractical for an incremental, multi-device protocol. Users must therefore
+trust the sync server operator in such cases, as well as to refrain from
+misusing the metadata that the protocol necessarily exposes to it (see
+:ref:`limitations`).
+
Proposed solution
=================
@@ -66,10 +92,10 @@ Backup and synchronization service
----------------------------------
Insertions and updates to objects in the wallet database are collected in a
-temporary buffer. Certain events in schedules in the wallet will trigger the
-incremental backup process, where this buffer will be serialized, encrypted
-into a kilobyte-padded block, assigned a random UUID, and finally uploaded to
-the backup service, along with the UUIDs of the previous and next block (when
+temporary buffer. Certain events in schedules in the wallet trigger the
+incremental backup process, where this buffer is serialized, encrypted into a
+kilobyte-padded block, assigned a random UUID, and finally uploaded to the
+backup service, along with the UUIDs of the previous and next block (when
applicable), and the hashes of all the large binary objects (blob) that are
referenced in the batch, which are expected to be encrypted and uploaded
beforehand to a separate hash-indexed object store.
@@ -110,37 +136,39 @@ beforehand to a separate hash-indexed object store.
}
Double-linked list block store
-~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+------------------------------
-The sync server will maintain a double-linked list in its database, as well as
-references to the global first and last block (useful for full restores), and
-is trusted to update the list. Via INSERT, DELETE and REPLACE operations,
-wallets can upload blocks and manipulate the linked list in accordance with
-their internal CRDT logic.
+The sync server maintains a double-linked list in its database, as well as
+references to the global first and last block (useful for full restores). Via
+INSERT, DELETE and REPLACE operations, as well as a signature to authenticate
+the operation, wallets can upload blocks and manipulate the linked list in
+accordance with their internal CRDT logic.
The sync server itself makes no decisions based on the content of the blocks,
-since it can only see the blocks in their encrypted form. Wallets must
-therefore maintain a local, unencrypted version of the block store by fetching
-missing blocks from the server and assembling them in the correct order.
+since it can only see them in their encrypted form. Wallets must therefore
+maintain a local, unencrypted version of the block store by fetching missing
+blocks from the server and assembling them in the correct order, verifying
+block signatures in the process in order to detect tampering or corruption.
Furthermore, wallets are responsible of ensuring that all deletion operations
provide plausible deniability by retroactively redacting the deleted objects
from all the blocks where they appear or are referenced, and uploading the
-changes to the sync server, which is in turn expected to not retain any
-deleted blocks or previous versions of updated blocks.
+changes to the sync server, which is in turn trusted (see :ref:`threat-model`)
+to honor deletion requests and not retain any deleted blocks nor previous
+versions of updated blocks.
During the synchronization process, wallets can either download the entirety
of the linked list (full sync), or fetch only the missing and updated blocks
by comparing their contents with the ones in the sync server by means of a
-reconciliation mechanism that will be discussed in further sections.
+reconciliation mechanism (read :ref:`sync-data-structures`).
Block format
-++++++++++++
+~~~~~~~~~~~~
-Each block will consist of a 2-byte version number, a random 24-byte nonce,
-an 8-byte serial, and a gzip-compressed JSON object with its length. The
-block will be padded up to the next whole kilobyte for privacy reasons. A
-block whose length is already a multiple of a kilobyte is not padded further.
+Each block consists of a 2-byte version number, a random 24-byte nonce, an
+8-byte serial, and a gzip-compressed JSON object with its length. The block is
+be padded up to the next whole kilobyte for privacy reasons. A block whose
+length is already a multiple of a kilobyte is not padded further.
The nonce is 24 bytes because that is exactly what `secretbox`_ takes, which
lets a block be encrypted under its own nonce.
@@ -153,11 +181,11 @@ never its serial. A wallet checks the serial when it decrypts a block and
refuses to apply a block whose serial is lower than the last one it saw for
that block, which makes a rolled-back (replayed) block detectable.
-Encryption will be performed on the block using symmetric authenticated
-encryption via libsodium's `secretbox`_ function, with a 32-byte key derived
-from the wallet's backup encryption key and the nonce of the block, which in
-the final implementation should be shareable between any wallets that the
-user wishes to add to the synchronization group.
+Encryption is performed on the block using symmetric authenticated encryption
+via libsodium's `secretbox`_ function, with a 32-byte key derived from the
+wallet's backup encryption key and the nonce of the block, which in the final
+implementation should be shareable between any wallets that the user wishes to
+add to the synchronization group.
.. note::
@@ -183,7 +211,7 @@ user wishes to add to the synchronization group.
+----------------------------+
Block store API
-+++++++++++++++
+~~~~~~~~~~~~~~~
The account key is the base32-encoded Crockford representation of an
EdDSA public key that identifies the backup account. All upload
@@ -600,14 +628,14 @@ hash.
A database error occurred.
Hash-indexed object store
-~~~~~~~~~~~~~~~~~~~~~~~~~
+-------------------------
All static large binary objects (blobs) referenced in a new block generated by
the wallet are required to be uploaded separately to the sync server in
encrypted form before the actual referencing block is uploaded.
-Blobs will be stored in a hash-indexed object store with a reference count of
-zero, which will increase with every referencing block that is uploaded to the
+Blobs are stored in a hash-indexed object store with a reference count of
+zero, which increases with every referencing block that is uploaded to the
block store. Any blobs with a reference count of zero will be deleted from the
server after a preconfigured expiration period.
@@ -617,11 +645,11 @@ is unsure whether a blob is already present can simply upload it again.
The stored contents of an existing UID are never replaced.
Blob format
-+++++++++++
+~~~~~~~~~~~
-Similar to blocks, each blob will consist of 2-byte version number, the 4-byte
+Similar to blocks, each blob consists of 2-byte version number, the 4-byte
data length, the gzipped data, and a padding to the next whole kilobyte. The
-blob will be encrypted using a key derived from the wallet's backup encryption
+blob is then encrypted using a key derived from the wallet's backup encryption
key and the hash of the unencrypted file:
.. code-block:: text
@@ -657,7 +685,7 @@ blob is only ever uploaded once.
+----------------------------+
Object store API
-++++++++++++++++
+~~~~~~~~~~~~~~~~
Objects are scoped to the account: a UID is only ever visible to the
account that uploaded it.
@@ -750,8 +778,8 @@ insertion operations (“increments”) for a particular database entity
// ...
}
-When a backup operation is triggered, this buffer will be processed into a
-block and emptied. The resulting block will be assigned a random UUID,
+When a backup operation is triggered, this buffer is processed into a block
+and subsequently emptied. The resulting block gets assigned a random UUID,
appended to the local linked-list, and uploaded to the backup service.
Since the operations in a given wallet may conflict with operations in the
@@ -2793,6 +2821,36 @@ An earlier ``backup-error`` notification type (``BackupOperationError``)
was part of a legacy backup proof of concept and has been removed in
favor of the ``error`` phase of ``backup-status``.
+.. _limitations:
+
+Limitations
+===========
+
+While the design minimizes the metadata that the backup service is exposed
+to, some leakage is inherent to the protocol and cannot be avoided in a
+practical way. The service necessarily learns how many blocks and blobs an
+account holds, how much data is uploaded and downloaded, and when these
+operations take place. Kilobyte padding ensures that the size of an
+individual block or blob reveals little about the contents it carries, but it
+cannot conceal the overall volume of activity, the number of operations
+performed, nor their distribution in time. In particular, the number of
+blocks in an account grows with every performed operation, so the block count
+itself is a lower bound on the amount of activity that cannot be disguised by
+padding.
+
+Timing patterns are particularly hard to hide. Backups run at critical points
+of wallet operations and on a periodic schedule, and some of these critical
+points correlate with user behavior in ways a curious service could exploit:
+for example, a backup forced right before a withdrawal hints that a withdrawal
+is about to occur, and one taken right after a payment hints that a payment
+just happened. The frequency of periodic backups can be reduced and their
+timing jittered to make such inferences harder, which also limits the amount
+of metadata that accumulates over time. The backups that critical points
+mandate, however, cannot be dropped without risking the loss of funds or data
+and therefore remain observable. Where such behavioral patterns are
+unavoidable, the user must trust the service not to misuse them -- an
+assumption already made in the :ref:`threat-model`.
+
Definition of done
==================
@@ -2866,6 +2924,8 @@ Definition of done
Alternatives
============
+.. _sync-data-structures:
+
Synchronization data structures
-------------------------------
@@ -2941,14 +3001,6 @@ a full backup.
Discussion / Q&A
================
-* **How to preserve plausible deniability in case of a dishonest sync server
- that retains deleted blocks and old versions of updated blocks?**
-
- * One option would be to derive a key for each block based on its contents,
- and delete the keys of deleted blocks from all synced wallets, but the
- problem with this approach is the number of keys that would need to be
- stored and backed up.
-
* How to manage (add/rm) linked devices? Do they ever expire? Is there a
*master* device with permissions to manage linked devices?
