commit 1767b32e0b5a56b26997f8a244c3b1022cbeb874
parent ac728de28a3f7d1a336121cbf8aa762c7af13539
Author: Iván Ávalos <avalos@disroot.org>
Date: Thu, 26 Mar 2026 21:54:07 +0100
add dd92: backup and sync
Diffstat:
1 file changed, 1438 insertions(+), 0 deletions(-)
diff --git a/design-documents/092-incremental-backup-sync.rst b/design-documents/092-incremental-backup-sync.rst
@@ -0,0 +1,1438 @@
+===========================================
+ DD 92: Incremental Wallet Backup and Sync
+===========================================
+
+Summary
+=======
+
+This design document describes an incremental, CRDT-based, encrypted wallet
+backup and sync protocol that addresses the limitations of previous solutions.
+
+Motivation
+==========
+
+An encrypted backup and sync protocol for wallets was the subject of three
+design documents (`DD05`_, `DD09`_ and `DD19`_), in which considerations for
+different aspects of backup and sync, as well as limitations of the proposed
+designs, were discussed and documented, ultimately resulting in a
+proof-of-concept server and wallet implementation.
+
+.. _DD05: https://docs.taler.net/design-documents/005-wallet-backup-sync.html
+.. _DD09: https://docs.taler.net/design-documents/009-backup.html
+.. _DD19: https://docs.taler.net/design-documents/019-wallet-backup-merge.html
+
+In the original design, an object containing a set of data entities managed by
+the wallet is serialized, gzip-compressed, kilobyte-padded and encrypted using
+libsodium's `secretbox`_ function using a symmetric key derived from the
+wallet's root key and a salt.
+
+.. _secretbox: https://libsodium.gitbook.io/doc/secret-key_cryptography/secretbox
+
+The resulting block is then uploaded to a sync server configured in the
+wallet, where it can be later recovered by another wallet and decrypted. It is
+at this point where conflicts with the existing database are resolved on a
+last-write-wins CRDT fashion, favoring deletion in concurrent, conflicting
+insert/delete operations.
+
+Since the data entities contained in the backup represent the state of the
+entire database at a given timestamp, the backup and restore operations
+described are not incremental and therefore not practical for synchronization
+between multiple devices, as the database can grow in size indefinitely,
+slowing down backup and restore operations over time.
+
+The revised solution proposed in this design document aims to address the
+limitations of the previous design by introducing an incremental, CRDT-based,
+end-to-end-encrypted wallet backup and sync protocol that is robust,
+efficient, reliable, and suitable for use between multiple devices.
+
+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.
+* **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
+ required.
+* **Plausible deniability:** The solution should ensure that no information
+ can be decrypted or retrieved from the backup after its deletion, including
+ the evidence that such information was deleted.
+
+Proposed solution
+=================
+
+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
+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.
+
+.. graphviz::
+
+ digraph G {
+ subgraph block {
+ {
+ rank = same
+ "Block 0" [shape=box]
+ "Block 1" [shape=box]
+ "Block 2" [shape=box]
+ }
+
+ "Block 0" -> "Block 1"
+ "Block 1" -> "Block 0"
+ "Block 1" -> "Block 2"
+ "Block 2" -> "Block 1"
+
+ {
+ rank = same
+ first [shape=plaintext]
+ last [shape=plaintext]
+ }
+
+ first -> "Block 0"
+ last -> "Block 2"
+ }
+
+ node [shape=record]
+ hash [label="{<f0> 197d605 | <f1> 409f945 | <f2> 8103756} | {<g0> 1 | <g1> 0 | <g2> 2} | {<h0> \<blob\> | <h1> \<blob\> | <h2> \<blob\>}"]
+
+ edge [style=dotted]
+ "Block 0" -> hash:f0 [constraint=false]
+ "Block 1" -> hash:f2 [constraint=false]
+ "Block 2" -> hash:f2 [constraint=false]
+ }
+
+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 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.
+
+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.
+
+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.
+
+Block format
+++++++++++++
+
+Each block will consist of a 2-byte version number, a random 32-byte nonce,
+and a gzip-compressed JSON object with its length. The block will be padded up
+to the next whole kilobyte for privacy reasons.
+
+Encryption will be performed on the block using symmetric authenticated
+encryption via libsodium's `secretbox`_ function, with a 32-bit key derived
+from the wallet's backup encryption key and the hash of the entire plaintext
+block, which in the final implementation should be shareable between any
+wallets that the user wishes to add to the synchronization group.
+
+.. code-block:: text
+
+ +----------------------------+
+ | version number (2 byte) |
+ +----------------------------+
+ | nonce (32 byte) |
+ +----------------------------+
+ | JSON length n (4 byte) |
+ +----------------------------+
+ | gzipped JSON (n byte) |
+ +----------------------------+
+ | padding (to next full KB) |
+ +----------------------------+
+
+.. TODO:
+ Block store API
+ +++++++++++++++
+
+ .. http:get:: /backups/${BACKUP_ID}
+
+ Get backup information.
+
+ **Response**
+
+ .. code-block:: typescript
+
+ interface GetBackupResponse {
+ /**
+ * Total number of blocks in the backup.
+ */
+ total_num_blocks: number;
+
+ /**
+ * First block in the backup (epoch).
+ */
+ first_block_nonce: string;
+
+ /**
+ * Current last block in the backup.
+ */
+ last_block_nonce: string;
+ }
+
+ .. http:post:: /backups/${BACKUP_ID}/block/${NONCE}
+
+ Upload an encrypted and binary encoded block.
+
+ **Request**
+
+ :query prev: Optional argument providing the nonce of the previous block in
+ the linked list. Shall not be provided if there is no previous block.
+
+ :query next: Optional argument providing the nonce of the next block in the
+ linked list. Shall not be provided if there is no previous block.
+
+ :query blob: Optional argument providing the hash of a referenced blob.
+ Can be repeated once for every referenced blob.
+
+ .. http:get:: /backups/${BACKUP_ID}/block
+
+ Get all blocks from a backup or specific blocks.
+
+ **Request**
+
+ :query nonce: Optional argument providing the nonce of the block to fetch.
+ Can be repeated once for every block to fetch.
+
+ .. http:put:: /backups/${BACKUP_ID}/block/${NONCE}
+
+ Replace an existing block with a new one in-place.
+
+ **Request**
+
+ :query old: Nonce of the old block to replace.
+
+ :query new: Nonce of the new block to insert.
+
+ :query blob: Optional argument providing the hash of a referenced blob.
+ Can be repeated once for every referenced blob.
+
+ .. http:delete:: /backups/${BACKUP_ID}/block/${NONCE}
+
+ Delete an existing block from the linked list.
+
+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
+block store. Any blobs with a reference count of zero will be deleted from the
+server after a preconfigured expiration period.
+
+In order to prevent wallets from uploading duplicate blobs, the sync server
+will compare the hash of the encrypted blob provided by the wallet against the
+object store before allowing the upload to proceed, rejecting it in case the
+blob already exists.
+
+Blob format
++++++++++++
+
+Similar to blocks, each blob will consist 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
+key and the hash of the unencrypted file.
+
+The hash used to index the object in the store will be computer from the
+encrypted blob using SHA-512 and truncated to 32 bytes.
+
+.. code-block:: text
+
+ +----------------------------+
+ | version number (2 byte) |
+ +----------------------------+
+ | data length n (4 byte) |
+ +----------------------------+
+ | gzipped data (n byte) |
+ +----------------------------+
+ | padding (to next full KB) |
+ +----------------------------+
+
+.. TODO:
+ Object store API
+ ++++++++++++++++
+
+ .. http:post:: /backups/${BACKUP_ID}/object
+
+ Upload an encrypted and binary encoded blob.
+
+ .. http:get:: /backups/${BACKUP_ID}/object
+
+ Fetch one or more existing blobs.
+
+ **Request**
+
+ :query hash: Hash of a blob to fetch.
+ Should be repeated once for every blob to fetch.
+
+ .. http:delete:: /backups/${BACKUP_ID}/object
+
+ Delete an existing blob.
+
+ **Request**
+
+ :query hash: Hash of a blob to delete.
+ Should be repeated once for every blob to delete.
+
+.. TODO: synchronization primitive
+
+Backup schema
+-------------
+
+Local operations on the wallet database are collected into a temporary buffer,
+called an “increment set”. Each top-level key in this set holds a list of
+insertion operations (“increments”) for a particular database entity
+(e.g. exchanges) or event (e.g. payments).
+
+.. ts:def:: IncrementSet
+
+ interface IncrementSet {
+ addExchangeIncs?: AddExchangeInc[];
+ setGlobalExchangeTrustIncs?: SetGlobalExchangeTrustInc[];
+ addBankAccountIncs?: AddBankAccountInc[];
+ // ...
+ }
+
+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,
+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
+backup with matching primary keys, a state-based CRDT “merge” strategy was
+carefuly devised for every top-level operation type in the block, so that
+wallets can deterministically agree on a consistent global state.
+
+Add or update an exchange
+~~~~~~~~~~~~~~~~~~~~~~~~~
+
+User accepts ToS for a new or existing exchange.
+
+Exchanges without an accepted ToS are not included in the backup.
+
+.. ts:def:: AddExchangeInc
+
+ interface AddExchangeInc {
+ type: "add-exchange";
+ exchangeBaseUrl: string;
+ tosAcceptedEtag: string;
+ tosAcceptedEtagTimestamp: Timestamp;
+ }
+
+* **Primary key:** ``[exchangeBaseUrl]``
+* **Deletion groups:** ``[exchanges]``
+
+Merge strategy
+++++++++++++++
+
+Favor the operation with the largest ``tosAcceptedEtagTimestamp``. If two
+timestamps are equal, favor the operation with the largest ``tosAcceptedEtag``
+in lexicographical order.
+
+Set exchange to global trust
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+User sets an exchange to global trust.
+
+.. ts:def:: SetGlobalExchangeTrustInc
+
+ interface SetGlobalExchangeTrustInc {
+ type: "set-global-exchange-trust";
+ exchangeBaseUrl: string;
+ exchangeMasterPub: EddsaPublicKey;
+ }
+
+* **Primary key:** ``[exchangeBaseUrl, exchangeMasterPub]``
+* **Deletion groups:** ``[global-exchange-trust]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required.
+
+Add or update a bank account
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+User adds (or updates) a known bank account.
+
+.. ts:def:: AddBankAccountInc
+
+ interface AddBankAccountInc {
+ type: "add-bank-account";
+ bankAccountId: string;
+ paytoUri: string;
+ label: string;
+ }
+
+* **Primary key:** ``[bankAccountId]``
+* **Deletion groups:** ``[bank-accounts]``
+
+Merge strategy
+++++++++++++++
+
+Last write wins.
+
+Set Donau info
+~~~~~~~~~~~~~~
+
+User sets info for tax-deductible donations.
+
+.. ts:def:: SetDonauInfoInc
+
+ interface SetDonauInfoInc {
+ type: "set-donau-info";
+ donauBaseUrl: string;
+ taxPayerId: string;
+ }
+
+* **Primary key:** ``[info]``
+* **Deletion groups:** ``[donau-info]``
+
+Merge strategy
+++++++++++++++
+
+Last write wins.
+
+Add a denomination
+~~~~~~~~~~~~~~~~~~
+
+A denomination is stored in the wallet.
+
+.. ts:def:: AddDenominationInc
+
+ interface AddDenominationInc {
+ type: "add-denomination";
+ denomPub: DenominationPubKey;
+ value: AmountString;
+ fees: DenomFees;
+ stampStart: TalerProtocolTimestamp;
+ stampExpireWithdraw: TalerProtocolTimestamp;
+ stampExpireLegal: TalerProtocolTimestamp;
+ stampExpireDeposit: TalerProtocolTimestamp;
+ masterSig: EddsaSignature;
+ exchangeBaseUrl: string;
+ exchangeMasterPub: EddsaPublicKey;
+ }
+
+* **Primary key:** ``[exchangeBaseUrl, denomPub]``
+* **Deletion groups:** ``[denominations]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, a denomination is expected to always remain constant, so
+later additions of the same denomination can be safely discarded.
+
+Add a coin
+~~~~~~~~~~
+
+A coin is generated by the wallet but not yet signed by the exchange.
+
+.. ts:def:: AddCoinInc
+
+ interface AddCoinInc {
+ type: "add-coin";
+ coinSource: CoinSource;
+ denominationId: string;
+ ageCommitmentProof?: AgeCommitmentProof;
+ }
+
+.. ts:def:: CoinSource
+
+ type CoinSource =
+ | WithdrawalCoinSource
+ | RefreshCoinSource;
+
+.. ts:def:: WithdrawalCoinSource
+
+ interface WithdrawalCoinSource {
+ type: "withdrawal";
+ withdrawalGroupId: string;
+ coinNumber: number;
+ }
+
+.. TODO: RefreshCoinSource (backup refresh groups?)
+
+* **Primary key:** ``[coinSource]``
+* **Deletion groups:** ``[coins, denominations, withdrawals]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, new coins are unique.
+
+Sign a coin
+~~~~~~~~~~~
+
+A coin is signed by the exchange.
+
+.. ts:def:: SignCoinInc
+
+ interface SignCoinInc {
+ type: "sign-coin";
+ coinSource: CoinSource;
+ denomSig: UnblindedDenominationSignature;
+ }
+
+* **Primary key:** ``[coinSource]``
+* **Deletion groups:** ``[coins, withdrawals]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, only one signature for a given coin can be issued by the
+exchange, further attempts to sign it will fail.
+
+Spend a coin
+~~~~~~~~~~~~
+
+A signed coin is spent by the user.
+
+.. ts:def:: SpendCoinInc
+
+ interface SpendCoinInc {
+ type: "spend-coin";
+ coinSource: CoinSource;
+ }
+
+* **Primary key:** ``[coinSource]``
+* **Deletion groups:** ``[coins, withdrawals]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, each coin can only be spent once, further attempts at
+spending the coin will fail.
+
+Add a token
+~~~~~~~~~~~
+
+A token is generated by the wallet but not yet signed by the merchant.
+
+.. ts:def:: AddTokenInc
+
+ interface AddTokenInc {
+ type: "add-token";
+ secretSeed: string;
+ choiceIndex: number;
+ outputIndex: number;
+ contractTermsHash: HashCode; // blob
+ }
+
+* **Primary key:** ``[secretSeed, choiceIndex, outputIndex]``
+* **Deletion groups:** ``[tokens]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, new tokens are unique.
+
+Sign a token
+~~~~~~~~~~~~
+
+A token is signed by the merchant.
+
+.. ts:def:: SignTokenInc
+
+ interface SignTokenInc {
+ type: "sign-token";
+ secretSeed: string;
+ choiceIndex: number;
+ outputIndex: number;
+ contractTermsHash: HashCode; // blob
+ tokenIssueSig: UnblindedDenominationSignature;
+ }
+
+* **Primary key:** ``[secretSeed, choiceIndex, outputIndex]``
+* **Deletion groups:** ``[tokens]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, only one signature for a given token can be issued by
+the merchant, further attempts to sign it will fail.
+
+Spend a token
+~~~~~~~~~~~~~
+
+A signed token is spent by the user.
+
+.. ts:def:: SpendTokenInc
+
+ interface SpendTokenInc {
+ type: "spend-token";
+ secretSeed: string;
+ choiceIndex: number;
+ outputIndex: number;
+ }
+
+* **Primary key:** ``[secretSeed, choiceIndex, outputIndex]``
+* **Deletion groups:** ``[tokens]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, each token can only be spent once, further attempts at
+spending the token will fail.
+
+Start a withdrawal
+~~~~~~~~~~~~~~~~~~
+
+User initiates a withdrawal.
+
+.. ts:def:: WithdrawalStartInc
+
+ interface WithdrawalStartInc {
+ type: "withdrawal-start";
+ withdrawalGroupId: string;
+ secretSeed: string;
+ reservePub: EddsaPublicKey;
+ timestampStart: TalerPreciseTimestamp;
+ restrictAge?: number;
+ instructedAmount: AmountString;
+ }
+
+.. TODO: store reserves in backup?
+ (in wallet-core DB, exchangeBaseUrl is contained there)
+
+* **Primary key:** ``[withdrawalGroupId]``
+* **Deletion groups:** ``[withdrawals]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, all withdrawals are independent from each other.
+
+Abort a withdrawal
+~~~~~~~~~~~~~~~~~~
+
+User aborts a withdrawal.
+
+.. ts:def:: WithdrawalAbortInc
+
+ interface WithdrawalAbortInc {
+ type: "withdrawal-abort";
+ withdrawalGroupId: string;
+ abortReason?: TalerErrorDetail;
+ }
+
+* **Primary key:** ``[withdrawalGroupId]``
+* **Deletion groups:** ``[withdrawals]``
+
+Merge strategy
+++++++++++++++
+
+Store all ``abortReason`` in the database.
+
+Withdrawal done
+~~~~~~~~~~~~~~~
+
+A withdrawal started by the user completes successfully.
+
+.. ts:def:: WithdrawalDoneInc
+
+ interface WithdrawalDoneInc {
+ type: "withdrawal-done";
+ withdrawalGroupId: string;
+ timestampFinish: TalerPreciseTimestamp;
+ rawWithdrawalAmount: AmountString;
+ effectiveWithdrawalAmount: AmountString;
+ }
+
+* **Primary key:** ``[withdrawalGroupId]``
+* **Deletion groups:** ``[withdrawals]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, a withdrawal can only succeed once.
+
+Withdrawal failed
+~~~~~~~~~~~~~~~~~
+
+A withdrawal started by the user fails.
+
+.. ts:def:: WithdrawalFailInc
+
+ interface WithdrawalFailInc {
+ type: "withdrawal-fail";
+ withdrawalGroupId: string;
+ failReason: TalerErrorDetail;
+ }
+
+* **Primary key:** ``[withdrawalGroupId]``
+* **Deletion groups:** ``[withdrawals]``
+
+Merge strategy
+++++++++++++++
+
+Store all ``failReason`` in the database.
+
+.. TODO: withdrawal (soft) deletion as increment?
+ (can't be easily deleted because of coin references)
+
+Start a deposit
+~~~~~~~~~~~~~~~
+
+.. ts:def:: DepositStartInc
+
+ interface DepositStartInc {
+ type: "deposit-start";
+ depositGroupId: string;
+ currency: string;
+ amount: AmountString;
+ wireTransferDeadline: TalerProtocolTimestamp;
+ merchantPub: EddsaPublicKey;
+ merchantPriv: EddsaPrivateKey;
+ noncePub: EddsaPublicKey;
+ noncePriv: EddsaPrivateKey;
+ wire: {payto_uri: string, salt: string};
+ contractTermsHash: HashCode; // blob
+ totalPayCost: AmountString;
+ timestampCreated: TalerPreciseTimestamp;
+ infoPerExchange: {[exchangeBaseUrl: string]: DepositInfoPerExchange};
+ }
+
+* **Primary key:** ``[depositGroupId]``
+* **Deletion groups:** ``[deposits]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, all deposits are independent from each other.
+
+Abort a deposit
+~~~~~~~~~~~~~~~
+
+User aborts a deposit.
+
+.. ts:def:: DepositAbortInc
+
+ interface DepositAbortInc {
+ type: "deposit-abort";
+ depositGroupId: string;
+ abortReason?: TalerErrorDetail;
+ }
+
+* **Primary key:** ``[depositGroupId]``
+* **Deletion groups:** ``[deposits]``
+
+Merge strategy
+++++++++++++++
+
+Store all ``abortReason`` in the database.
+
+Deposit done
+~~~~~~~~~~~~
+
+A deposit started by the user completes successfully.
+
+.. ts:def:: DepositDoneInc
+
+ interface DepositDoneInc {
+ type: "deposit-done";
+ depositGroupId: string;
+ timestampFinished: TalerPreciseTimestamp;
+ }
+
+* **Primary key:** ``[depositGroupId]``
+* **Deletion groups:** ``[deposits]``
+
+Merge strategy
+++++++++++++++
+
+No merge required, a deposit can only succeed once.
+
+Deposit fail
+~~~~~~~~~~~~
+
+A deposit started by the user fails.
+
+.. ts:def:: DepositFailInc
+
+ interface DepositFailInc {
+ type: "deposit-fail";
+ depositGroupId: string;
+ failReason: TalerErrorDetail;
+ }
+
+* **Primary key:** ``[depositGroupId]``
+* **Deletion groups:** ``[deposits]``
+
+Merge strategy
+++++++++++++++
+
+Store all ``failReason`` in the database.
+
+Start a merchant payment
+~~~~~~~~~~~~~~~~~~~~~~~~
+
+User initiates a payment to a merchant.
+
+.. ts:def:: PaymentStartInc
+
+ interface PaymentStartInc {
+ type: "payment-start";
+ proposalId: string;
+ claimToken?: string;
+ downloadSessionId?: string;
+ repurchaseProposalId?: string;
+ noncePub: EddsaPublicKey;
+ noncePriv: EddsaPrivateKey;
+ secretSeed: string;
+ exchanges?: string[];
+ contractTermsHash: string; // blob
+ timestamp: TalerPreciseTimestamp;
+
+ // Donau
+ donauOutputIndex?: number;
+ donauBaseUrl?: string;
+ donauAmount?: AmountString;
+ donauTaxIdHash?: string;
+ donauTaxIdSalt?: string;
+ donauTaxId?: string;
+ donauYear?: string;
+ }
+
+* **Primary key:** ``[proposalId]``
+* **Deletion groups:** ``[payments]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, all payments are independent from each other.
+
+Confirm a merchant payment
+~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+User confirms a payment to a merchant.
+
+.. ts:def:: PaymentConfirmInc
+
+ interface PaymentConfirmInc {
+ type: "payment-confirm";
+ proposalId: string;
+ choiceIndex?: number;
+ timestampAccept: TalerPreciseTimestamp;
+ }
+
+* **Primary key:** ``[proposalId]``
+* **Deletion groups:** ``[payments]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, a payment can only succeed once.
+
+Abort a merchant payment
+~~~~~~~~~~~~~~~~~~~~~~~~
+
+User aborts a payment to a merchant.
+
+.. ts:def:: PaymentAbortInc
+
+ interface PaymentAbortInc {
+ type: "payment-abort";
+ proposalId: string;
+ abortReason?: TalerErrorDetail;
+ }
+
+* **Primary key:** ``[proposalId]``
+* **Deletion groups:** ``[payments]``
+
+Merge strategy
+++++++++++++++
+
+Store all ``abortReason`` in the database.
+
+Merchant purchase done
+~~~~~~~~~~~~~~~~~~~~~~
+
+A payment started by the user completes successfully.
+
+.. ts:def:: PaymentDoneInc
+
+ interface PaymentDoneInc {
+ type: "payment-done";
+ proposalId: string;
+ }
+
+* **Primary key:** ``[proposalId]``
+* **Deletion groups:** ``[payments]``
+
+Merchant purchase fail
+~~~~~~~~~~~~~~~~~~~~~~
+
+A payment started by the user fails.
+
+.. ts:def:: PaymentFailInc
+
+ interface PaymentFailInc {
+ type: "payment-fail";
+ proposalId: string;
+ failReason: TalerErrorDetail;
+ }
+
+* **Primary key:** ``[proposalId]``
+* **Deletion groups:** ``[payments]``
+
+Merge strategy
+++++++++++++++
+
+Store all ``failReason`` in the database.
+
+Start peer-push-credit
+~~~~~~~~~~~~~~~~~~~~~~
+
+User receives an incoming push payment.
+
+.. ts:def:: PeerPushCreditStartInc
+
+ interface PeerPushCreditStartInc {
+ type: "peer-push-credit-start";
+ peerPushCreditId: string;
+ exchangeBaseUrl: string;
+ pursePub: EddsaPublicKey;
+ mergePriv: EddsaPrivateKey;
+ contractPriv: EddsaPrivateKey;
+ timestamp: TalerPreciseTimestamp;
+ estimatedAmountEffective: AmountString;
+ contractTermsHash: HashCode; // blob
+ currency: string;
+ }
+
+* **Primary key:** ``[peerPushCreditId]``
+* **Deletion groups:** ``[peer-push-credit]``
+
+Merge strategy
+++++++++++++++
+
+Last write wins, since the parameters of a peer-push-credit transaction are
+expected to always remain constant. However, ``peerPushCreditId`` must be
+derived from the ``exchangeBaseUrl`` and ``pursePub``.
+
+Abort peer-push-credit
+~~~~~~~~~~~~~~~~~~~~~~
+
+User aborts an incoming push payment.
+
+.. ts:def:: PeerPushCreditAbortInc
+
+ interface PeerPushCreditAbortInc {
+ type: "peer-push-credit-abort";
+ peerPushCreditId: string;
+ abortReason?: TalerErrorDetail;
+ }
+
+* **Primary key:** ``[peerPushCreditId]``
+* **Deletion groups:** ``[peer-push-credit]``
+
+Merge strategy
+++++++++++++++
+
+Store all ``abortReason`` in the database.
+
+Peer-push-credit done
+~~~~~~~~~~~~~~~~~~~~~
+
+An incoming push payment received by the user completes successfully.
+
+.. ts:def:: PeerPushCreditDoneInc
+
+ interface PeerPushCreditDoneInc {
+ type: "peer-push-credit-done";
+ peerPushCreditId: string;
+ }
+
+* **Primary key:** ``[peerPushCreditId]``
+* **Deletion groups:** ``[peer-push-credit]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, a peer-push-credit payment can only succeed once.
+
+Peer-push-credit fail
+~~~~~~~~~~~~~~~~~~~~~
+
+An incoming push payment received by the user fails.
+
+.. ts:def:: PeerPushCreditFailInc
+
+ interface PeerPushCreditFailInc {
+ type: "peer-push-credit-fail";
+ peerPushCreditId: string;
+ failReason: TalerErrorDetail;
+ }
+
+* **Primary key:** ``[peerPushCreditId]``
+* **Deletion groups:** ``[peer-push-credit]``
+
+Merge strategy
+++++++++++++++
+
+Store all ``failReason`` in the database.
+
+Start peer-push-debit
+~~~~~~~~~~~~~~~~~~~~~
+
+User initiates an outgoing push payment.
+
+.. ts:def:: PeerPushDebitStartInc
+
+ interface PeerPushDebitStartInc {
+ type: "peer-push-debit-start";
+ exchangeBaseUrl: string;
+ instructedAmount: AmountString;
+ effectiveAmount: AmountString;
+ contractTermsHash: HashCode; // blob
+ pursePub: EddsaPublicKey;
+ pursePriv: EddsaPrivateKey;
+ mergePub: EddsaPublicKey;
+ mergePriv: EddsaPrivateKey;
+ contractPub: EddsaPublicKey;
+ contractPriv: EddsaPrivateKey;
+ contractEncNonce: string;
+ purseExpiration: TalerProtocolTimestamp;
+ timestampCreated: TalerPreciseTimestamp;
+ }
+
+* **Primary key:** ``[pursePub]``
+* **Deletion groups:** ``[peer-push-debit]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, all peer-push-debit payments are independent from each
+other.
+
+Abort peer-push-debit
+~~~~~~~~~~~~~~~~~~~~~
+
+User aborts an outgoing push payment.
+
+.. ts:def:: PeerPushDebitAbortInc
+
+ interface PeerPushDebitAbortInc {
+ type: "peer-push-debit-abort";
+ pursePub: EddsaPublicKey;
+ abortReason?: TalerErrorDetail;
+ }
+
+* **Primary key:** ``[pursePub]``
+* **Deletion groups:** ``[peer-push-debit]``
+
+Merge strategy
+++++++++++++++
+
+Store all ``abortReason`` in the database.
+
+Peer-push-debit done
+~~~~~~~~~~~~~~~~~~~~
+
+An outgoing push payment initiated by the user completes successfully.
+
+.. ts:def:: PeerPushDebitDoneInc
+
+ interface PeerPushDebitDoneInc {
+ type: "peer-push-debit-done";
+ pursePub: EddsaPublicKey;
+ }
+
+* **Primary key:** ``[pursePub]``
+* **Deletion groups:** ``[peer-push-debit]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, a peer-push-debit payment can only succeed once.
+
+Peer-push-debit fail
+~~~~~~~~~~~~~~~~~~~~
+
+An outgoing push payment initiated by the user fails.
+
+.. ts:def:: PeerPushDebitFailInc
+
+ interface PeerPushDebitFailInc {
+ type: "peer-push-debit-fail";
+ pursePub: EddsaPublicKey;
+ failReason: TalerErrorDetail;
+ }
+
+* **Primary key:** ``[pursePub]``
+* **Deletion groups:** ``[peer-push-debit]``
+
+Merge strategy
+++++++++++++++
+
+Store all ``failReason`` in the database.
+
+Start peer-pull-debit
+~~~~~~~~~~~~~~~~~~~~~
+
+User confirms a payment request from another wallet.
+
+.. ts:def:: PeerPullDebitDoneInc
+
+ interface PeerPullDebitDoneInc {
+ type: "peer-pull-debit-start";
+ peerPullDebitId: string;
+ pursePub: EddsaPublicKey;
+ exchangeBaseUrl: string;
+ amount: AmountString;
+ contractTermsHash: HashCode; // blob
+ timestampCreated: TalerPreciseTimestamp;
+ contractPriv: EddsaPrivateKey;
+ totalCostEstimated: AmountString;
+ }
+
+* **Primary key:** ``[peerPullDebitId]``
+* **Deletion groups:** ``[peer-pull-debit]``
+
+Merge strategy
+++++++++++++++
+
+Last write wins, since the parameters of a peer-pull-debit transaction are
+expected to always remain constant. However, ``peerPullDebitId`` must be
+derived from the ``exchangeBaseUrl`` and ``pursePub``.
+
+Abort peer-pull-debit
+~~~~~~~~~~~~~~~~~~~~~
+
+User aborts a payment to another wallet.
+
+.. ts:def:: PeerPullDebitAbortInc
+
+ interface PeerPullDebitAbortInc {
+ type: "peer-pull-debit-abort";
+ peerPullDebitId: string;
+ abortReason?: TalerErrorDetail;
+ }
+
+* **Primary key:** ``[peerPullDebitId]``
+* **Deletion groups:** ``[peer-pull-debit]``
+
+Merge strategy
+++++++++++++++
+
+Store all ``abortReason`` in the database.
+
+Peer-pull-debit done
+~~~~~~~~~~~~~~~~~~~~
+
+A payment to another wallet completes successfully.
+
+.. ts:def:: PeerPullDebitDoneInc
+
+ interface PeerPullDebitDoneInc {
+ type: "peer-pull-debit-done";
+ peerPullDebitId: string;
+ }
+
+* **Primary key:** ``[peerPullDebitId]``
+* **Deletion groups:** ``[peer-pull-debit]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, a peer-pull-debit payment can only succeed once.
+
+Peer-pull-debit fail
+~~~~~~~~~~~~~~~~~~~~
+
+A payment to another wallet fails.
+
+.. ts:def:: PeerPullDebitFailInc
+
+ interface PeerPullDebitFailInc {
+ type: "peer-pull-debit-fail";
+ peerPullDebitId: string;
+ failReason: TalerErrorDetail;
+ }
+
+* **Primary key:** ``[peerPullDebitId]``
+* **Deletion groups:** ``[peer-pull-debit]``
+
+Merge strategy
+++++++++++++++
+
+Store all ``failReason`` in the database.
+
+Start peer-pull-credit
+~~~~~~~~~~~~~~~~~~~~~~
+
+User requests money to another wallet.
+
+.. ts:def:: PeerPullCreditStartInc
+
+ interface PeerPullCreditStartInc {
+ type: "peer-pull-credit-start";
+ exchangeBaseUrl: string;
+ amount: AmountString;
+ estimatedAmountEffective: AmountString;
+ pursePub: EddsaPublicKey;
+ pursePriv: EddsaPrivateKey;
+ contractTermsHash: HashCode; // blob
+ mergePub: EddsaPublicKey;
+ mergePriv: EddsaPrivateKey;
+ contractPub: EddsaPublicKey;
+ contractPriv: EddsaPrivateKey;
+ contractEncNonce: string;
+ mergeTimestamp: TalerPreciseTimestamp;
+ mergeReserveRowId: number;
+ withdrawalGroupId?: string;
+ }
+
+* **Primary key:** ``[pursePub]``
+* **Deletion groups:** ``[peer-pull-credit]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, all peer-pull-credit payments are independent from each
+other.
+
+Abort peer-pull-credit
+~~~~~~~~~~~~~~~~~~~~~~
+
+User aborts request to another wallet.
+
+.. ts:def:: PeerPullCreditAbortInc
+
+ interface PeerPullCreditAbortInc {
+ type: "peer-pull-credit-abort";
+ pursePub: EddsaPublicKey;
+ abortReason?: TalerErrorInfo;
+ }
+
+* **Primary key:** ``[pursePub]``
+* **Deletion groups:** ``[peer-pull-credit]``
+
+Merge strategy
+++++++++++++++
+
+Store all ``failReason`` in the database.
+
+Peer-pull-credit done
+~~~~~~~~~~~~~~~~~~~~~
+
+A request to another wallet completes successfully (i.e. money is received).
+
+.. ts:def:: PeerPullCreditDoneInc
+
+ interface PeerPullCreditDoneInc {
+ type: "peer-pull-credit-done";
+ pursePub: EddsaPublicKey;
+ }
+
+* **Primary key:** ``[pursePub]``
+* **Deletion groups:** ``[peer-pull-credit]``
+
+Merge strategy
+++++++++++++++
+
+No merge is required, a peer-pull-credit payment can only succeed once.
+
+Peer-pull-credit fail
+~~~~~~~~~~~~~~~~~~~~~
+
+A request to another wallet fails.
+
+.. ts:def:: PeerPullCreditFailInc
+
+ interface PeerPullCreditFailInc {
+ type: "peer-pull-credit-fail";
+ pursePub: EddsaPublicKey;
+ failReason: TalerErrorInfo;
+ }
+
+* **Primary key:** ``[pursePub]``
+* **Deletion groups:** ``[peer-pull-credit]``
+
+Merge strategy
+++++++++++++++
+
+Store all ``failReason`` in the database.
+
+Item deletion
+-------------
+
+Due to privacy considerations within our use case, rather than using classical
+CRDT-style tombstones to encode deletion operations into blocks, a novel
+approach was conceived, whereby each item (e.g. an exchange) in the local
+wallet database to be included in the backup keeps a list of UUIDs of the
+"origin" blocks that have inserted or updated it.
+
+.. code-block:: typescript
+
+ originBlocks: Set<BlockUuid>;
+
+Using this approach, a deletion of an item would simply consist of locating
+the origin blocks referenced in its UUID list, and deleting the corresponding
+insertion/update operations from all of them.
+
+In order to prevent wallets from mistakenly reinserting an item into the
+backup that was previously deleted by another wallet, an item is deemed
+deleted iff it no longer appears in any of its origin blocks, allowing it to
+be safely removed from the local database as well.
+
+Deletion groups
+~~~~~~~~~~~~~~~
+
+A resource within its deletion group is identified by its primary key. When
+the resource in question is deleted, all references to this resource within
+the resource group must also be deleted from the blocks listed in the
+``originBlocks`` field of its database record.
+
+For example, when deleting a denomination, all the coin insertions of that
+denomination must also be deleted from the backup, since they are in the
+``denominations`` deletion group and thus contain a reference to a
+denomination. In turn, all the sign and spend operations of the deleted coins
+must also be deleted, since they are in the ``coins`` deletion group and thus
+contain a reference to a coin.
+
+.. TODO:
+ Backup process
+ --------------
+
+.. TODO:
+ Backup schedule
+ ---------------
+
+.. TODO:
+ Restore process
+ ---------------
+
+.. TODO:
+ Restore schedule
+ ----------------
+
+Definition of done
+==================
+
+* [x] Design backup schema.
+* [ ] Design incremental sync.
+* [ ] Design backup/restore schedules.
+* [ ] Design wallet-core API.
+* [ ] Wallet-core implementation.
+* [ ] Design sync API (+ auth).
+* [ ] Server-side implementation.
+* [ ] UI/UX for backup and sync.
+
+Alternatives
+============
+
+Synchronization data structures
+-------------------------------
+
+In order to perform incremental restores (i.e. synchronization) and converge
+towards the global state (a.k.a. reconciliation), wallets need to keep track
+(in real time) of all the changes in the backup that occurred after the last
+incremental restore, resolve any resulting conflicts, and apply the changes to
+the local database, all while preserving the requirements of incrementality
+and plausible deniability.
+
+So far, two strategies to achieve this have been discussed:
+
+* Invertible bloom filter.
+* Event-driven message queue.
+
+Invertible bloom filter
+~~~~~~~~~~~~~~~~~~~~~~~
+
+In this approach, a invertible bloom filter of dynamic size is calculated by
+the wallet and server across all known blocks, and used by the wallets to
+compare their local contents with the ones in the server and only fetch the
+inserted and updated blocks, deleting the ones missing from the server.
+
+Wallets would use additional information stored in the server, such as total
+number of blocks, to decide based on the number of the number of differences
+with the server up to a specified threshold, whether to perform an incremental
+backup using the bloom filter or simply perform a full backup.
+
+In order to reduce the rate of false positives, the bloom filter would be
+doubled in size and recalculated as the total number of blocks increases. In
+the rare event of a false positive, both the wallets and the server would
+recalculate the bloom filter by adding a special prefix to the blocks before
+hashing, rate-limited by the theoretical probability of false positives to
+prevent denial-of-service attacks.
+
+Each bucket in the bloom filter (format below) would be 32 bits in size (for
+optimal byte alignment) and have the following structure:
+
+.. code-block:: text
+
+ +-----------------------+
+ | Bloom filter (10 bit) |
+ +-----------------------+
+ | Counter (4 bit) |
+ +-----------------------+
+ | Hash (12-16 bit) |
+ +-----------------------+
+ | Checksum (4-8 bit) |
+ +-----------------------+
+
+Event-driven message queue
+~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Another proposed solution is to use a message queue used mainly to stream
+blocks operations (INSERT, DELETE, UPDATE) to other wallets in the
+synchronization group.
+
+In order to provide "eventual" plausible deniability, events in the message
+queue would be permanently deleted as soon as all the active wallets in the
+synchronization group have consumed them, meaning that the server would need
+to keep track of all the "subscribed" wallets.
+
+Inactive wallets would be automatically "unsubscribed" from the message queue
+after a predefined period of time (e.g. 2 weeks), or after being manually
+deleted by the user (similarly to e.g. Signal). Upon coming back online or
+being added back to the synchronization group, a wallet would need to perform
+a full backup.
+
+.. TODO:
+ Drawbacks
+ =========
+
+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?
+
+* How to safely delete a withdrawal operation? Instead of storing the keypair
+ for each coin, we derive coins from a secret seed and the coin index within
+ a withdrawal group. Coins in the backup thus contain a reference to the
+ originating withdrawal operation, which in the event of being deleted will
+ prevent coins from being restored from backup.
