taler-docs

092-incremental-backup-sync.rst (110271B)

---

 ===========================================
  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. 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
   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.
 
 .. _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
 =================
 
 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 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.
 
 .. 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 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 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 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 (read :ref:`sync-data-structures`).
 
 Block format
 ~~~~~~~~~~~~
 
 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.
 
 The serial is only ever seen by the wallets: it sits inside the encrypted
 payload, so the sync server knows nothing about it.  Wallets assign it on
 every content write (append or in-place update) as the account's maximum
 known serial plus one; relinking a block never changes its data and therefore
 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 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::
 
    The key is derived from the *nonce* rather than from the hash of the
    plaintext block: the nonce travels with the block, whereas the plaintext
    hash is only known to whoever can already decrypt it, so deriving from it
    would make the block undecryptable.
 
 .. code-block:: text
 
    +----------------------------+
    | version number (2 byte)    |
    +----------------------------+
    | nonce (24 byte)            |
    +----------------------------+
    | serial (8 byte)            |
    +----------------------------+
    | JSON length n (4 byte)     |
    +----------------------------+
    | gzipped JSON (n byte)      |
    +----------------------------+
    | padding (to next full KB)  |
    +----------------------------+
 
 Block store API
 ~~~~~~~~~~~~~~~
 
 The account key is the base32-encoded Crockford representation of an EdDSA
 public key that identifies the backup account.  All upload requests must be
 signed by the corresponding private key; the signature is transmitted in the
 request body.
 
 Binary values in URLs, headers and JSON bodies (nonces, UIDs, hashes,
 signatures and the encrypted payloads themselves) are all base32-encoded in
 Crockford representation, as is usual for Taler.
 
 Signatures use EdDSA with the account private key.  Each signature payload
 follows the common Taler signing structure with a ``purpose`` field (see
 :ref:`Signatures` in the API common conventions for the general format).  The
 specific payloads are:
 
 .. sourcecode:: c
 
    /**
     * Purpose: TALER_SIGNATURE_SYNC_BLOCK_UPLOAD (1452)
     * Authorizes the append or in-place update of a block.
     * For appends, old_hash is all-zeros.
     */
    struct SyncBlockUploadSignaturePS {
      struct GNUNET_CRYPTO_SignaturePurpose purpose;
      struct SYNC_BlockNonce prev_nonce;  ///< all-zeros if first block
      struct SYNC_BlockNonce next_nonce;  ///< all-zeros if last block
      struct SYNC_BlockNonce nonce;
      struct GNUNET_HashCode old_hash;    ///< all-zeros for appends
      struct GNUNET_HashCode new_hash;
      struct GNUNET_HashCode refs_hash;   ///< over object_refs, see below
    };
 
    /**
     * Purpose: TALER_SIGNATURE_SYNC_BLOCK_DELETE (1453)
     * Authorizes the deletion of a block.
     */
    struct SyncBlockDeleteSignaturePS {
      struct GNUNET_CRYPTO_SignaturePurpose purpose;
      struct SYNC_BlockNonce nonce;
      struct SYNC_BlockNonce prev_nonce;  ///< all-zeros if first block
      struct SYNC_BlockNonce next_nonce;  ///< all-zeros if last block
      struct GNUNET_HashCode hash;
      struct GNUNET_HashCode refs_hash;   ///< over object_refs, see below
    };
 
    /**
     * Purpose: TALER_SIGNATURE_SYNC_OBJECT_UPLOAD (1454)
     * Authorizes the upload of a blob object.
     */
    struct SyncObjectUploadSignaturePS {
      struct GNUNET_CRYPTO_SignaturePurpose purpose;
      struct SYNC_ObjectUID uid;
      struct GNUNET_HashCode hash;
    };
 
 Absent optional nonces (``prev_nonce`` / ``next_nonce``) are treated as
 all-zeros in the signed data.
 
 The ``refs_hash`` field covers the ``object_refs`` of the request, so that the
 reference-count adjustments cannot be altered in transit.  It is the SHA-512
 hash over a canonical *binary* encoding of the references — not over their
 JSON representation.
 
 Each reference is laid out as the 64 raw UID bytes followed by the adjustment
 as a signed 16-bit integer in network byte order, and the resulting 66-byte
 records are concatenated in ascending order of UID:
 
 .. code-block:: text
 
    +----------------------------+
    | uid (64 byte)              |
    +----------------------------+
    | adjustment (2 byte, int16) |
    +----------------------------+
 
 Sorting by UID is required because ``object_refs`` travels as a JSON object,
 whose member order is not preserved.  A request without any references hashes
 the empty byte string.
 
 A UID may appear at most once, since the wire format keys the references by
 UID and could not otherwise transmit them faithfully.
 
 The server stores the ``upload_sig`` with the block, together with the rest of
 the signed context (``old_hash`` and ``refs_hash``), and returns them in the
 block list.  A wallet therefore verifies every block's stored signature
 against the account key before applying it; a block whose signature does not
 verify must not be applied.
 
 Operations that rewrite the links of an existing block (an append relinks the
 previous tail, a delete relinks both of its neighbours) require that block's
 *new* signature to be uploaded along with the operation.  This is an ordinary
 ``TALER_SIGNATURE_SYNC_BLOCK_UPLOAD`` signature over the relinked block's new
 nonces, carried in the ``relink_prev`` / ``relink_next`` fields of the
 request.  The server verifies it against the current state of the relinked
 block and stores it in the block's row; relinking never changes the block's
 data, so the signature's ``old_hash`` and ``new_hash`` are both the block's
 stored hash.
 
 .. http:get:: /config
 
    Return the server's protocol version and terms.  Requires no account
    and no signature.
 
    **Response**
 
    :http:statuscode:`200 OK`:
      The body is a `SyncConfig` object.
 
    .. ts:def:: SyncConfig
 
       interface SyncConfig {
         name: "sync";
         implementation: string;
         storage_limit_in_megabytes: number;
         liability_limit: AmountString;
         annual_fee: AmountString;
         version: string;
       }
 
    ``storage_limit_in_megabytes`` is the per-upload limit enforced for both
    blocks and objects; exceeding it yields ``413``.  ``version`` follows the
    Taler ``current:revision:age`` convention.
 
 .. http:get:: /backups/${ACCOUNT_KEY}
 
    Report the state of the account: when it expires, and how much of the
    storage allowance its backup uses.  Requires no signature, like the other
    read endpoints -- the account public key is the capability, and the stored
    data is client-encrypted.
 
    This is the only endpoint that answers for an expired account rather than
    demanding payment: when the account expires is precisely what the caller is
    asking, so a ``402`` here would be useless.  Wallets use it to tell the
    user how long the backup is paid for without waiting for the next write to
    fail.
 
    **Response**
 
    :http:statuscode:`200 OK`:
      The body is a `SyncAccountStatus` object.  Returned even when
      ``expiration_date`` lies in the past.
    :http:statuscode:`404 Not found`:
      The server does not know this account at all.  It has never been
      paid for, so there is no expiry to report.
 
    .. ts:def:: SyncAccountStatus
 
       interface SyncAccountStatus {
         // When the account expires, or expired.  Every other endpoint
         // answers 402 past this point.
         expiration_date: Timestamp;
 
         // Total size of the account's stored blocks, in bytes.
         storage_used_bytes: number;
 
         // Number of blocks in the account's linked list.
         block_count: number;
       }
 
 .. http:get:: /backups/${ACCOUNT_KEY}/blocks
 
    List blocks from the account's linked list with pagination.
 
    **Request**
 
    :query limit:
      *Required.* Maximum number of blocks to return.  Must be a positive
      count (int16).
    :query start_nonce:
      Optional nonce of the block from which to start listing.  If omitted,
      listing starts from the first block.
 
    **Response**
 
    :http:statuscode:`200 OK`:
      The body is a JSON array of `BlockEntry` objects.  The array is
      empty if the account has no blocks.
    :http:statuscode:`400 Bad request`:
      The ``limit`` parameter is missing, malformed, given without a
      value, or not positive; or ``start_nonce`` is malformed or given
      without a value.
    :http:statuscode:`402 Payment required`:
      The account has expired and requires payment.
    :http:statuscode:`404 Not found`:
      The ``start_nonce`` block was not found in the linked list.
    :http:statuscode:`500 Internal server error`:
      A database error occurred.
 
    .. ts:def:: BlockEntry
 
       interface BlockEntry {
         nonce: BlockUuid;
         block_hash: HashCodeString;
         prev_nonce?: BlockUuid;
         next_nonce?: BlockUuid;
         data: string;
         upload_sig: EddsaSignatureString;
         old_hash: HashCodeString;
         refs_hash: HashCodeString;
       }
 
    ``data`` is the encrypted block payload as it was uploaded, and hashes to
    ``block_hash``.  ``prev_nonce`` and ``next_nonce`` are absent for the first
    and last block of the linked list respectively.  ``upload_sig`` is the
    signature stored with the block, and ``old_hash`` / ``refs_hash`` the
    remainder of the signed context; the wallet verifies the signature before
    applying the block.
 
 .. http:post:: /backups/${ACCOUNT_KEY}/blocks/${NONCE}
 
    Upload a new block and append it at the end of the account's linked list.
    If a block with the same nonce already exists, the content hash is
    compared: if it matches, a ``304 Not modified`` is returned; if it differs,
    the client should use ``PUT`` instead.
 
    The request must include an ``If-None-Match`` header containing the quoted
    base32-encoded SHA-512 hash of the encrypted block data.  This hash is used
    by the server to detect duplicates, and the server rejects the upload if
    the ``data`` in the body does not hash to it.
 
    **Request**
 
    :query fresh:
      Optional. Force the server to issue a fresh payment order even if a
      pending one already exists for this account.
    :query pay:
      Optional. Any non-empty value (e.g. ``y``) signals that the client
      wants to pay before uploading.
    :query paying:
      Optional. An existing order identifier.  The client is promising
      that it is already paying on a related order.  This will cause the
      server to delay processing until the respective payment has arrived
      (if the operation requires a payment).  Useful if the server
      previously returned a ``402 Payment required`` and the client wants
      to proceed as soon as the payment went through.
 
    The request body is a JSON object:
 
    .. code-block:: typescript
 
       interface UploadBlockRequest {
         upload_sig: EddsaSignatureString;
         prev_nonce?: BlockUuid;
         next_nonce?: BlockUuid;
         data: string;
         object_refs?: { [uid: BlobUid]: number };
         relink_prev?: { upload_sig: EddsaSignatureString };
       }
 
    ``upload_sig``
      EdDSA signature over the block nonce, ``prev_nonce``,
      ``next_nonce``, old data hash (for updates, all-zeros for appends),
      new data hash and the hash over ``object_refs``, signed with the
      account's private key
      (``TALER_SIGNATURE_SYNC_BLOCK_UPLOAD``).
 
    ``prev_nonce``
      Nonce of the preceding block in the DLL.
      Must be omitted for the first block.
 
    ``next_nonce``
      Must be omitted; inserts into the middle of the linked list are not
      supported, so an append never has a succeeding block.
 
    ``data``
      The encrypted block contents (binary, base32-encoded).
 
    ``object_refs``
      Optional object whose keys are blob UIDs and whose values are
      16-bit signed integer reference-count deltas.  Any objects
      referenced here must have been uploaded *beforehand* via
      ``POST /backups/${ACCOUNT_KEY}/objects/${UID}``, and each UID may
      appear at most once.  The adjustments are applied in the same
      transaction as the block operation: if any of them names an object
      the account does not have, or would take a reference count below
      zero, the entire request is rejected and nothing is modified.
 
    ``relink_prev``
      Required when ``prev_nonce`` is present.  The new signature of the
      block at ``prev_nonce`` (the previous tail), covering its new
      ``next`` link after this append.  The server verifies it against
      the tail's current state and stores it with the block.
 
    **Response**
 
    :http:statuscode:`204 No content`:
      The block was stored successfully.
    :http:statuscode:`304 Not modified`:
      A block with the same nonce and data hash already exists.
    :http:statuscode:`400 Bad request`:
      Malformed parameters, bad hash, or missing required headers.
    :http:statuscode:`402 Payment required`:
      The account has expired and requires payment.  The response includes
      a ``Taler`` header with a ``taler://pay/...`` URI.
    :http:statuscode:`403 Forbidden`:
      The signature is invalid or does not match the request.
    :http:statuscode:`409 Conflict`:
      The request does not fit the state the server holds, and retrying
      it unchanged will not help.  Either the write is outdated (the
      linked list has been modified by another device since the caller
      last fetched it), the nonce is already in use, or ``object_refs``
      names an object the account does not have or would take a
      reference count below zero.  Nothing was modified.
    :http:statuscode:`413 Request entity too large`:
      The upload exceeds the server's configured upload limit.
    :http:statuscode:`500 Internal server error`:
      A database error occurred.
 
 .. http:put:: /backups/${ACCOUNT_KEY}/blocks/${NONCE}
 
    Replace an existing block's content in-place.  Semantics are identical to
    ``POST`` on the same endpoint, with one addition: the ``If-Match`` header
    must contain the quoted base32-encoded SHA-512 hash of the old block data
    that is being replaced.  The server rejects the request with ``409
    Conflict`` if the old hash, ``prev_nonce`` or ``next_nonce`` do not match
    the stored block.
 
    The ``upload_sig`` must also cover the old data hash (from ``If-Match``) in
    addition to the new data hash (from ``If-None-Match``).
 
    .. note::
 
       ``PUT`` stands in for ``PATCH``, which the update operation would
       otherwise use, until the HTTP server library supports it.
 
    **Response**
 
    Same status codes as ``POST``, plus:
 
    :http:statuscode:`404 Not found`:
      The specified block does not exist (cannot update a missing block).
 
 .. http:delete:: /backups/${ACCOUNT_KEY}/blocks/${NONCE}
 
    Delete an existing block from the linked list.  The request must include an
    ``If-Match`` header containing the quoted base32-encoded SHA-512 hash of
    the block data to delete, which the server uses to detect concurrent
    modifications.
 
    **Request**
 
    The request body is a JSON object:
 
    .. code-block:: typescript
 
       interface DeleteBlockRequest {
         delete_sig: EddsaSignatureString;
         prev_nonce?: BlockUuid;
         next_nonce?: BlockUuid;
         object_refs?: { [uid: BlobUid]: number };
         relink_prev?: { upload_sig: EddsaSignatureString };
         relink_next?: { upload_sig: EddsaSignatureString };
       }
 
    ``delete_sig``
      EdDSA signature over the block nonce, ``prev_nonce``,
      ``next_nonce``, block hash (from ``If-Match``) and the hash over
      ``object_refs``, signed with the account's private key
      (``TALER_SIGNATURE_SYNC_BLOCK_DELETE``).
 
    ``prev_nonce``
      Nonce of the preceding block in the DLL.
      Must be omitted if the block being deleted is the first block.
 
    ``next_nonce``
      Nonce of the succeeding block in the DLL.
      Must be omitted if the block being deleted is the last block.
 
    ``object_refs``
      Optional object whose keys are blob UIDs and whose values are
      16-bit signed integer reference-count deltas (typically negative,
      to decrement the refcount of objects that were referenced by the
      deleted block).  The same rules as for block uploads apply: each
      UID may appear at most once, and the whole request is rejected if
      an adjustment names an unknown object or would take a reference
      count below zero.
 
    ``relink_prev``
      Required when ``prev_nonce`` is present.  The new signature of the
      block at ``prev_nonce``, covering its new ``next`` link.
 
    ``relink_next``
      Required when ``next_nonce`` is present.  The new signature of the
      block at ``next_nonce``, covering its new ``prev`` link.
 
    **Response**
 
    :http:statuscode:`204 No content`:
      The block was deleted successfully.
    :http:statuscode:`400 Bad request`:
      Malformed parameters or missing ``If-Match`` header.
    :http:statuscode:`402 Payment required`:
      The account has expired and requires payment.
    :http:statuscode:`403 Forbidden`:
      The signature is invalid or does not match the request.
    :http:statuscode:`404 Not found`:
      The specified block does not exist (or was already deleted).
    :http:statuscode:`409 Conflict`:
      The ``If-Match`` hash, ``prev_nonce`` or ``next_nonce`` do not
      match the stored block (concurrent modification detected), or
      ``object_refs`` names an object the account does not have or would
      take a reference count below zero.  Nothing was modified.
    :http:statuscode:`500 Internal server error`:
      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 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.
 
 Uploads are keyed by UID and are idempotent: re-uploading a UID that the
 account already holds is accepted and changes nothing, so a wallet that 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 consists of 2-byte version number, the 4-byte
 data length, the gzipped data, and a padding to the next whole kilobyte. The
 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
 
    key = KDF(32, backup_key, "taler-sync-blob-secret-salt", H(plaintext))
    uid = H(key)
 
 Every blob therefore has its own key. The 64-byte ``uid``, which is the
 SHA-512 hash of that key, is what indexes the object in the store and is the
 only one of the two the sync server ever learns; the key itself is stored
 *inside the blocks* that reference the blob, where it doubles as the reference
 to the object that has to be fetched.
 
 The key is thus all a wallet needs to both locate and decrypt a blob, which is
 the only thing a block carries. The `secretbox`_ nonce is consequently derived
 from the key as well, as the first 24 bytes of ``H(key)``. Nonce reuse cannot
 occur, because distinct plaintexts derive distinct keys.
 
 Because the key is derived from the plaintext, blobs are content-addressed:
 identical contents yield the same key, UID and ciphertext, so an unchanged
 blob is only ever uploaded once.
 
 .. code-block:: text
 
    +----------------------------+
    | version number (2 byte)    |
    +----------------------------+
    | data length n (4 byte)     |
    +----------------------------+
    | gzipped data (n byte)      |
    +----------------------------+
    | padding (to next full KB)  |
    +----------------------------+
 
 Object store API
 ~~~~~~~~~~~~~~~~
 
 Objects are scoped to the account: a UID is only ever visible to the account
 that uploaded it.
 
 .. http:get:: /backups/${ACCOUNT_KEY}/objects/${UID}
 
    Retrieve an existing blob by its UID.
 
    **Response**
 
    :http:statuscode:`200 OK`:
      The body is an `ObjectEntry` object.
    :http:statuscode:`400 Bad request`:
      The ``$UID`` is malformed.
    :http:statuscode:`404 Not found`:
      The account has no object under that UID.  This is also the answer
      for an account that does not exist.
    :http:statuscode:`500 Internal server error`:
      A database error occurred.
 
    .. ts:def:: ObjectEntry
 
       interface ObjectEntry {
         uid: BlobUid;
         data: string;
       }
 
 .. http:post:: /backups/${ACCOUNT_KEY}/objects/${UID}
 
    Upload an encrypted blob and store it in the hash-indexed object store.
    The ``$UID`` is the object's unique identifier.
 
    The object is stored with a reference count of zero; it only becomes
    referenced once a block naming it in ``object_refs`` is uploaded.  Until
    then it is subject to expiry, so blobs should be uploaded shortly before
    the block that references them.
 
    **Request**
 
    The request body is a JSON object:
 
    .. code-block:: typescript
 
       interface UploadObjectRequest {
         object_sig: EddsaSignatureString;
         data: string;
       }
 
    ``object_sig``
      EdDSA signature over the ``$UID`` and the hash of ``data``, signed
      with the account's private key
      (``TALER_SIGNATURE_SYNC_OBJECT_UPLOAD``).
 
    ``data``
      The encrypted blob contents (binary, base32-encoded).
 
    **Response**
 
    :http:statuscode:`204 No content`:
      The object was stored.  This is also the answer when the account
      already holds an object under that UID, in which case the stored
      contents are left as they are.
    :http:statuscode:`400 Bad request`:
      The ``$UID`` or the request body is malformed.
    :http:statuscode:`402 Payment required`:
      The account has expired and requires payment.
    :http:statuscode:`403 Forbidden`:
      The signature is invalid or does not match the request.
    :http:statuscode:`413 Request entity too large`:
      The upload exceeds the server's configured upload limit.
    :http:statuscode:`500 Internal server error`:
      A database error occurred.
 
 .. 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 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
 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.
 
 One rule cuts across all of the transaction families: **a transaction only
 ever moves towards its end.** The wallets of a group work on the same
 transactions at the same time, so an increment that would take a record back
 to a state it has already moved past is describing an older view of it, and
 only its origin block is recorded.  The terminal states are ranked rather than
 simply frozen, so that two wallets which reached *different* ones both settle
 on the same one:
 
 .. code-block:: text
 
    done  >  failed  >  aborted  >  expired  >  (not terminal)
 
 Preferring ``done`` is deterministic, which is what convergence needs, and it
 is also the truthful answer: a transaction that finished actually moved the
 money.  Without the rule, a wallet that completed a withdrawal would pull in
 the abort another device had issued against the copy it restored, and end up
 showing an abandoned transaction while holding the coins it produced.
 
 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 comes into the wallet (withdrawn or refreshed) and is signed by the
 exchange.
 
 The wallet database stores per-coin key material, so the increment carries the
 coin **as it stands** -- key, blinding key, signature and status -- rather
 than deriving it from a seed as earlier designs did.  The wallet records an
 ``add-coin`` when the coin is created and a ``spend-coin`` when it is spent;
 the full collection pass emits the ``add-coin`` form for any coin the backup
 has never seen, whatever state it is in.  The ``spend-coin`` section is
 applied after the ``add-coin`` section, so a coin that was spent before a
 cycle ran restores in its spent state.
 
 Restoring the coin also recomputes the wallet's *coin availability* rows (the
 counts the balance reads) from the restored coins, so a restored wallet shows
 the same balance as the wallet that made the backup.  The counts are always
 derived and never carried, which is what makes the restore idempotent; only a
 coin that is spendable (status ``fresh``) counts, matching what the wallet's
 own bookkeeping does with a suspended one.
 
 For the two balances to agree, *every* change to whether a coin counts has to
 reach the other wallets, not only spending: a coin melted into a refresh,
 recouped from a revoked denomination, written off with its denomination, or
 suspended by the user is reported with a ``spend-coin`` increment carrying its
 new status.  The section is the coin's terminal update, whatever brought it
 about.  A change that is not reported is the one way the two devices can end
 up disagreeing about how much money the user has, since a coin that is already
 backed up is never offered again by the full collection pass.
 
 The reserves (and with them the ability to recoup a restored coin) are backed
 up by the ``add-reserve`` family, and the withdrawal family
 (``withdrawal-start`` / ``withdrawal-abort`` / ``withdrawal-done`` /
 ``withdrawal-fail``, referencing the reserve by ``[exchangeBaseUrl,
 reservePub]``, and carrying the ``wgInfo`` with the ``taler://withdraw`` URI
 that identifies the bank's operation) restores the withdrawal transactions
 themselves and lets a restored wallet continue a pending one -- the bank's
 operation is keyed by that URI, and the reserve key pair and the coin seed are
 in the backup too; only an expired bank operation cannot be resumed.  A
 refreshed coin's melt is backed up by the refresh family below, so a restored
 coin can be recouped-refreshed as well as recouped (see the recoup discussion
 under "Add a reserve").
 
 ``exchangeWithdrawValues`` carries the blinding values the exchange
 contributed to the withdraw, which a recoup has to replay.  For an RSA coin
 they are the constant ``{"cipher": "RSA"}``; for a Clause-Schnorr coin they
 are the R-values, which nothing can re-derive, so they have to travel in the
 increment.  The field is optional because it was added after the increment was
 first released: a coin from a wallet that predates it is treated as RSA.
 
 .. ts:def:: AddCoinInc
 
    interface AddCoinInc {
      type: "add-coin";
      coinSource: CoinSource;
      sourceTransactionId?: string;
      coinPub: string;
      coinPriv: string;
      denomPubHash: string;
      denomSig: UnblindedDenominationSignature;
      exchangeBaseUrl: string;
      exchangeMasterPub: string;
      blindingKey: string;
      coinEvHash: string;
      status: CoinStatus;
      visible?: number;
      maxAge: number;
      ageCommitmentProof?: AgeCommitmentProof;
      exchangeWithdrawValues?: ExchangeWithdrawValue;
    }
 
 .. ts:def:: CoinSource
 
    type CoinSource =
      | WithdrawalCoinSource
      | RefreshCoinSource;
 
 .. ts:def:: WithdrawalCoinSource
 
    interface WithdrawalCoinSource {
      type: "withdrawal";
      withdrawalGroupId: string;
      coinNumber: number;
      reservePub: string;
    }
 
 .. ts:def:: RefreshCoinSource
 
    interface RefreshCoinSource {
      type: "refresh";
      refreshGroupId: string;
      oldCoinPub: string;
    }
 
 * **Primary key:** ``[coinPub]``
 * **Deletion groups:** ``[coins]``
 
 Merge strategy
 ++++++++++++++
 
 Last write wins: a coin is unique and its parameters never change, so the
 latest copy wins.
 
 Spend a coin
 ~~~~~~~~~~~~
 
 A signed coin is spent by the user.
 
 .. ts:def:: SpendCoinInc
 
    interface SpendCoinInc {
      type: "spend-coin";
      coinSource: CoinSource;
      sourceTransactionId?: string;
      coinPub: string;
      coinPriv: string;
      denomPubHash: string;
      denomSig: UnblindedDenominationSignature;
      exchangeBaseUrl: string;
      exchangeMasterPub: string;
      blindingKey: string;
      coinEvHash: string;
      status: CoinStatus;
      visible?: number;
      maxAge: number;
      ageCommitmentProof?: AgeCommitmentProof;
      exchangeWithdrawValues?: ExchangeWithdrawValue;
    }
 
 * **Primary key:** ``[coinPub]``
 * **Deletion groups:** ``[coins]``
 
 Add a token
 ~~~~~~~~~~~
 
 A token is generated by the wallet but not yet signed by the merchant (the
 wallet database calls this a *slate*).
 
 Like coins, tokens were originally designed as seed-derived: the increment
 carried ``[secretSeed, choiceIndex, outputIndex]`` and the wallet re-derived
 the key pair from it.  The wallet database stores per-token key material
 instead, so the increments carry the token as it stands, and the token's *use*
 public key is the primary key of the family.  The three increments share one
 body, ``TokenIncBase``:
 
 .. ts:def:: TokenIncBase
 
    interface TokenIncBase {
      // Purchase the token belongs to, and the position within its
      // contract that produced it.
      purchaseId: string;
      transactionId?: string;
      choiceIndex?: number;
      outputIndex?: number;
      repeatIndex?: number;
 
      merchantBaseUrl: string;
      kind: MerchantContractTokenKind;
      slug: string;
      name: string;
      description: string;
      descriptionI18n?: InternationalizedString;
      extraData: MerchantContractTokenDetails;
 
      tokenIssuePub: TokenIssuePublicKey;
      tokenIssuePubHash: string;
      tokenFamilyHash?: string;
      validAfter: TalerProtocolTimestamp;
      validBefore: TalerProtocolTimestamp;
 
      // The key material the wallet holds for this token.  Nothing can
      // reconstruct it, so it travels in the increment.
      tokenUsePub: string;
      tokenUsePriv: string;
      tokenUseSig?: TokenUseSig;
      tokenEv: TokenEnvelope;
      tokenEvHash: string;
      blindingKey: string;
    }
 
 .. ts:def:: AddTokenInc
 
    interface AddTokenInc extends TokenIncBase {
      type: "add-token";
    }
 
 * **Primary key:** ``[tokenUsePub]``
 * **Deletion groups:** ``[tokens]``
 
 Merge strategy
 ++++++++++++++
 
 No merge is required, new tokens are unique.
 
 Sign a token
 ~~~~~~~~~~~~
 
 A token is signed by the merchant.  Applying this increment also removes the
 slate the token was issued from, the same way the wallet's own issuance flow
 does.
 
 .. ts:def:: SignTokenInc
 
    interface SignTokenInc extends TokenIncBase {
      type: "sign-token";
      tokenIssueSig: UnblindedDenominationSignature;
    }
 
 * **Primary key:** ``[tokenUsePub]``
 * **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.  Only the fields the spend changes
 travel; the increment updates a token that is already there and is skipped
 when it is not.
 
 .. ts:def:: SpendTokenInc
 
    interface SpendTokenInc {
      type: "spend-token";
      tokenUsePub: string;
      transactionId?: string;
      tokenUseSig?: TokenUseSig;
    }
 
 * **Primary key:** ``[tokenUsePub]``
 * **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.
 
 The increment references the reserve by ``[exchangeBaseUrl, reservePub]`` (see
 the "Add a reserve" section): the restored wallet takes the reserve's key pair
 from the reserve record.  It also carries the ``wgInfo`` -- for a
 bank-integrated withdrawal, the ``taler://withdraw`` URI that identifies the
 bank's withdrawal operation.  That URI, the reserve key pair and the coin seed
 (all in the backup) are everything a restored wallet needs to continue a
 withdrawal that was still pending on the other device; the only thing that
 cannot be resumed is a bank operation the bank has already expired or deleted.
 
 .. ts:def:: WithdrawalStartInc
 
    interface WithdrawalStartInc {
      type: "withdrawal-start";
      withdrawalGroupId: string;
      exchangeBaseUrl: string;
      reservePub: EddsaPublicKey;
      secretSeed: string;
      timestampStart: TalerPreciseTimestamp;
      restrictAge?: number;
      instructedAmount?: AmountString;
      wgInfo: WgInfo;
    }
 
 * **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)
 
 Set the reserve seed
 ~~~~~~~~~~~~~~~~~~~~
 
 The wallet derives every reserve key pair from a single wallet-level seed (32
 random bytes), so that the backup carries no per-reserve key material: the
 private key of reserve ``i`` is re-derived as
 
 .. code-block:: text
 
    reservePriv_i = KDF(32, reserveSeed, "taler-reserve-key-salt", i)
 
 and the public key from the private one (``eddsa_get_public``).  The seed
 itself is wallet state and travels in the backup like the wallet root key;
 this increment is what the backup carries it as.  It is created lazily at the
 first reserve created after this feature ships, so wallets that predate it do
 not grow a seed until they create their next reserve.  Reserves created before
 the seed existed keep their random key pairs and are backed up with the
 ``reservePriv`` fallback of ``add-reserve`` below.
 
 .. ts:def:: SetReserveSeedInc
 
    interface SetReserveSeedInc {
      type: "set-reserve-seed";
      seed: string;
    }
 
 * **Primary key:** ``[]`` (a singleton, like ``set-donau-info``)
 * **Deletion groups:** ``[reserve-seed]``
 
 Merge strategy
 ++++++++++++++
 
 Last write wins.
 
 The ``set-reserve-seed`` section of an increment set is applied before the
 ``add-reserve`` section, so that a wallet deriving a reserve key pair on
 restore already has the seed.
 
 Add a reserve
 ~~~~~~~~~~~~~
 
 A reserve is created by the wallet for every withdrawal and for the merge
 capability of P2P payments, and its key pair lives in the wallet's
 ``reserves`` object store (see the ``WalletReserve`` record in ``db.ts``).
 The increment carries the record's identity -- the exchange and the reserve's
 derivation index -- and, for the reserves that predate the seed, the private
 key.
 
 .. ts:def:: AddReserveInc
 
    interface AddReserveInc {
      type: "add-reserve";
      exchangeBaseUrl: string;
      reserveIndex: number;
      // Only for reserves created before the reserve seed existed, whose
      // keys are random and cannot be re-derived.
      reservePriv?: EddsaPrivateKey;
    }
 
 * **Primary key:** ``[exchangeBaseUrl, reserveIndex]``
 * **Deletion groups:** ``[reserves]``
 
 Merge strategy
 ++++++++++++++
 
 Last write wins: the identity of a reserve never changes, and a re-recorded
 increment (e.g. by the full collection pass) carries the same index and the
 same key material.
 
 The public key of the reserve is *not* carried: it is derived from the private
 key on restore (``eddsa_get_public``), whether the private key was re-derived
 from the seed or restored from ``reservePriv``.  The restored record therefore
 has the same ``reservePub`` as the wallet that created the reserve, which is
 what the other increments reference it by (see below).  The ``WalletReserve``
 record gains ``exchangeBaseUrl``, ``reserveIndex`` and the
 ``reserveSeedDerived`` marker (which decides whether the full collection pass
 emits the index-only form or the index-plus-private-key form); the exchange
 base URL is required by the increment and was missing from the record (see the
 ``FIXME: Should reference exchange.`` comment in ``db.ts`` and the redundant
 ``exchangeBaseUrl`` of ``WithdrawalGroupRecord``).
 
 The remaining fields of ``WalletReserve`` (``status``, the KYC thresholds,
 ``kycAccessToken``, ``amlReview``) are all derivable by querying the exchange
 and are deliberately not backed up, so that a restored wallet re-derives them
 instead of trusting stale state.
 
 Recoup
 ++++++
 
 The reserve increment is what keeps recoup working on a restored wallet.  The
 recoup request itself is signed by the *coin*: the coin record (``add-coin``)
 carries the coin private key, the blinding key and the denomination signature
 the request needs, and the request names the reserve only by its public key,
 which the coin source carries.  After the exchange confirms the recoup, the
 wallet queries the reserve's balance and withdraws it back into coins; that
 re-withdrawal needs the reserve *private* key, which is exactly what
 ``add-reserve`` restores.  The recoup of a refreshed coin (``recoup-refresh``)
 likewise needs only the coin records -- the refreshed coin plus the old coin
 the refresh source names -- so no refresh-group data is involved.
 
 The upcoming batch recoup protocol (``vRECOUP``, see ``api-exchange.rst``)
 adds, per coin, the Clause-Schnorr blinding data (``cs_session_nonce`` and the
 ``cs_r_pubs`` of the exchange's ``/blinding-prepare``) for post-quantum
 denominations.  The wallet does not store that data anywhere yet; when it
 does, the ``add-coin`` increment must carry it (as optional fields).  That is
 a coin-family extension; the reserve side of a post-quantum recoup stays as
 described above.
 
 Why the schema matters to the other increment types
 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 
 The ``reserves`` store is referenced, directly or through its row id, by the
 withdrawal groups (``reservePub``/``reservePriv``), the coin sources
 (``WithdrawCoinSource.reservePub``, used for recouping), the exchange entries
 (``currentMergeReserveRowId``) and the peer-pull-credit records
 (``mergeReserveRowId``):
 
 * ``withdrawal-start`` is the most obvious case: the wallet's
   ``WithdrawalGroupRecord`` embeds the reserve key pair and the exchange base
   URL.  With ``add-reserve``, a ``withdrawal-start`` increment can reference
   the reserve by ``[exchangeBaseUrl, reservePub]`` instead of carrying the key
   pair, avoiding duplication.
 * ``add-coin`` / ``spend-coin`` reference the reserve through the withdrawal
   coin source's ``reservePub``; the restored reserve record is what makes the
   restored coin recoupable (see above).
 * The exchange entries and the peer-pull-credit records reference the merge
   reserve by a *row id* into the ``reserves`` store, which is not portable
   across wallets.  The ``add-exchange`` increment does not carry the
   ``currentMergeReserveRowId`` pointer, so a restored exchange entry starts
   without one; the merge reserve remains findable by its public key, and
   re-linking the pointer on restore is a follow-up.
 
 Every increment family in this document is implemented; see the "Definition of
 done" section for what remains.
 
 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;
         // Not in the original design, but needed to reconstruct the
         // `taler://pay/...' URI and re-download the proposal on restore:
         merchantBaseUrl: string;
         orderId: string;
         claimToken?: string;
         downloadSessionId?: string;
         repurchaseProposalId?: string;
         noncePub: EddsaPublicKey;
         noncePriv: EddsaPrivateKey;
         secretSeed: string;
         exchanges?: string[];
         // Hash of the contract terms (a blob).  Unknown until the
         // proposal has been downloaded.
         contractTermsHash?: string;
         timestamp: TalerPreciseTimestamp;
 
         // Donau
         donauOutputIndex?: number;
         donauBaseUrl?: string;
         donauAmount?: AmountString;
         donauTaxIdHash?: string;
         donauTaxIdSalt?: string;
         donauTaxId?: string;
         donauYear?: number;
       }
 
 * **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.
 
 Start a refresh
 ~~~~~~~~~~~~~~~
 
 The wallet melts the remainder of one or more coins into fresh ones -- as
 change after a payment, or to renew a coin whose denomination is about to
 expire.
 
 The group carries the plan; how far it has got lives in the per-coin sessions
 below.  A restored group is what lets a wallet that melted a coin and then
 lost the device still collect the change: the exchange holds the first melt
 commitment, and a wallet that re-melted with a fresh seed could not reveal
 against it.
 
 .. ts:def:: RefreshStartInc
 
    interface RefreshStartInc {
      type: "refresh-start";
      refreshGroupId: string;
      currency: string;
      reason: string;
      originatingTransactionId?: string;
      oldCoinPubs: string[];
      inputPerCoin: AmountString[];
      expectedOutputPerCoin: AmountString[];
      timestampCreated: TalerPreciseTimestamp;
    }
 
 * **Primary key:** ``[refreshGroupId]``
 * **Deletion groups:** ``[refreshes]``
 
 Merge strategy
 ++++++++++++++
 
 Last write wins: the plan of a refresh group never changes.
 
 Refresh session
 ~~~~~~~~~~~~~~~
 
 The melt of one coin of a refresh group.
 
 Everything the reveal step needs -- the fresh coins' key material included --
 is derived from ``sessionPublicSeed`` together with the old coin and the
 chosen denominations, all of which travel here, so this is the part of a
 refresh that has to be backed up.
 
 .. ts:def:: RefreshSessionInc
 
    interface RefreshSessionInc {
      type: "refresh-session";
      refreshGroupId: string;
      coinIndex: number;
      sessionPublicSeed?: string;
      refreshProtocolVersion?: number;
      amountRefreshOutput: AmountString;
      newDenoms: { denomPubHash: string; count: number }[];
      norevealIndex?: number;
    }
 
 * **Primary key:** ``[refreshGroupId, coinIndex]``
 * **Deletion groups:** ``[refreshes]``
 
 Merge strategy
 ++++++++++++++
 
 Last write wins: the session is written once, when the coin is melted.
 
 Refresh done
 ~~~~~~~~~~~~
 
 Every coin of the group has been melted and the fresh coins collected.
 
 .. ts:def:: RefreshDoneInc
 
    interface RefreshDoneInc {
      type: "refresh-done";
      refreshGroupId: string;
      timestampFinished: TalerPreciseTimestamp;
    }
 
 * **Primary key:** ``[refreshGroupId]``
 * **Deletion groups:** ``[refreshes]``
 
 Refresh failed
 ~~~~~~~~~~~~~~
 
 The refresh could not be completed.
 
 .. ts:def:: RefreshFailInc
 
    interface RefreshFailInc {
      type: "refresh-fail";
      refreshGroupId: string;
      failReason: TalerErrorDetail;
    }
 
 * **Primary key:** ``[refreshGroupId]``
 * **Deletion groups:** ``[refreshes]``
 
 Derived operations: refunds, recoups and denomination losses
 ------------------------------------------------------------
 
 The three families below differ from every other one in this document: the
 wallet does not start them, it *learns* about them.  A refund is the
 merchant's answer to a refund query, a recoup is forced by an exchange
 revoking a denomination, and a denomination loss is what the wallet has to
 write off when a denomination expires or is withdrawn from circulation.
 
 Any wallet holding the coins can ask the same question and get the same
 answer, which is what decides how they are backed up: **only a finished one
 travels, and it restores as finished.** Backing up a pending one would hand
 the second device work on an operation it cannot see the whole of -- it would
 go and query a merchant about a refund that is already settled on the first
 device -- and would leave the user looking at an operation that is long over
 elsewhere but "pending" here.  A pending one is simply not collected, and
 keeps no origin block, so a later pass offers it up once it has finished.
 
 Refund
 ~~~~~~
 
 A refund the merchant granted, as it finally stood.
 
 The refund *items* (one per coin) are deliberately not carried: nothing
 outside the refund query itself reads them, the transaction is rendered
 entirely from the group, and their identity is the merchant's
 (``coin_pub``/``rtransaction_id``), so a wallet that does query gets the same
 ones back.
 
 .. ts:def:: RefundInc
 
    interface RefundInc {
      type: "refund";
      refundGroupId: string;
      // The purchase this refunds; restored as the transaction it points
      // at, and not applied at all when that purchase is not there.
      proposalId: string;
      outcome: DerivedOutcome;
      amountRaw: AmountString;
      amountEffective: AmountString;
      timestampCreated: TalerPreciseTimestamp;
    }
 
 .. ts:def:: DerivedOutcome
 
    // How one of the derived operations ended.  A wire string rather than
    // the wallet's numeric status enum, which is a database detail.
    type DerivedOutcome = "done" | "failed" | "aborted" | "expired";
 
 * **Primary key:** ``[refundGroupId]``
 * **Deletion groups:** ``[refunds, payments]``
 
 Merge strategy
 ++++++++++++++
 
 Last write wins: the increment describes one finished operation, and there is
 nothing to reconcile field by field.
 
 Recoup
 ~~~~~~
 
 Coins reclaimed from an exchange that revoked their denomination.
 
 What the recoup *did* to the coins reaches the other wallets as coin
 increments; this is what makes the operation itself appear.  Its per-coin
 progress is not carried -- it describes a run the other wallet did not make --
 and a restored recoup is marked finished for every coin, so that the second
 device does not go and re-submit somebody else's recoup.
 
 .. ts:def:: RecoupInc
 
    interface RecoupInc {
      type: "recoup";
      recoupGroupId: string;
      exchangeBaseUrl: string;
      outcome: DerivedOutcome;
      // The coins that were recouped, in the order the group listed them.
      coinPubs: string[];
      timestampStarted: TalerPreciseTimestamp;
      timestampFinished?: TalerPreciseTimestamp;
    }
 
 * **Primary key:** ``[recoupGroupId]``
 * **Deletion groups:** ``[recoups, coins]``
 
 Merge strategy
 ++++++++++++++
 
 Last write wins.
 
 Denomination loss
 ~~~~~~~~~~~~~~~~~
 
 A denomination the wallet had to write off, with the coins it cost.
 
 Unlike the two above this one is not merely history: until the other wallets
 learn of it they keep the affected coins in their balance, and the two devices
 disagree about how much money the user has.  The coins themselves carry the
 same news -- their status becomes ``denom-loss`` -- and this is what makes the
 transaction appear.
 
 ``denomLossEventId`` is **derived from the loss** rather than drawn at random.
 Both wallets notice the same expiry on their own, each updating the exchange
 and seeing the same denominations go; with random identifiers the user would
 end up with the same loss listed twice.
 
 .. code-block:: text
 
    denom_loss_event_id = SHA512(exchange_base_url || 0 || event_type || 0 ||
                                 sorted(denom_pub_hashes) each || 0)[0:32]
 
 .. ts:def:: DenomLossInc
 
    interface DenomLossInc {
      type: "denom-loss";
      denomLossEventId: string;
      currency: string;
      exchangeBaseUrl: string;
      denomPubHashes: string[];
      // "denom-expired", "denom-vanished", "denom-revoked",
      // "denom-unoffered".
      eventType: string;
      // "aborted" when the loss turned out to be reversible.
      outcome: "done" | "aborted";
      amount: AmountString;
      timestampCreated: TalerPreciseTimestamp;
    }
 
 * **Primary key:** ``[denomLossEventId]``
 * **Deletion groups:** ``[denom-losses, denominations]``
 
 Merge strategy
 ++++++++++++++
 
 Last write wins.
 
 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.
 
 Mechanically, a wallet deletes an item by scrubbing its increments out of the
 pending buffer and rewriting every origin block that still carries them: a
 block that keeps other content is replaced in place (``PUT``, under its
 original nonce), one that becomes empty is removed from the linked list
 (``DELETE``, relinking its neighbours).  A block rewritten in place keeps its
 nonce, so the other wallets detect the change only by noticing that the
 block's hash no longer matches their local copy; a deleted block shows up as a
 gap in the linked list.  On either signal a wallet re-applies the whole linked
 list and drops every item that no longer appears in any origin block, which is
 what makes deletions propagate across the sync group.
 
 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.
 
 Backup process
 --------------
 
 Collecting increments
 ~~~~~~~~~~~~~~~~~~~~~
 
 Recording runs inside the very transaction that performs the withdrawal, the
 payment or the deposit, which is what makes wallet state and backup state
 commit together -- and also means that anything the recording throws takes
 that operation down with it.  It must therefore be impossible for the backup
 to fail an operation: the eager recording is an *optimisation*, not the
 guarantee.  A record whose increment never made it keeps its ``originBlocks``
 unset, which is exactly what the full collection pass looks for, so a failure
 costs a delay and nothing else.  Recording, waking the cycle and queueing a
 deletion all log and swallow; the critical-point hold fails open.
 
 The same applies to key material the wallet *derives* for an operation.  A
 reserve key pair comes from the reserve seed, so a seed the wallet cannot
 decode would otherwise block every withdrawal, permanently, since the seed is
 stored.  An unusable seed instead falls back to a random reserve key pair,
 which the backup carries as ``reservePriv`` the way it does for reserves that
 predate the seed, and the seed itself is left untouched -- reserves already
 derived from it are named by their index, so replacing it would make them
 underivable elsewhere.
 
 Stored key material is checked before it is decoded, because the two Crockford
 base32 decoders a wallet may run on do not agree: the JavaScript one ignores
 trailing padding bits that are not zero, while the native (qtart) one rejects
 the string outright.  A value decoded unchecked therefore works in a browser
 extension and throws on a phone.  Re-encoding the decoded bytes and comparing
 settles it on either runtime, and is what the restore path uses to refuse a
 malformed seed rather than store one.
 
 Wallet transactions record what they changed by appending increments to a
 pending buffer, held in the wallet's backup configuration record. The
 recording happens **within the same database transaction that performs the
 change**, so that the change and the increment describing it commit together.
 A wallet can therefore never end up in a state that its backup does not know
 about, however abruptly it is shut down.
 
 A wallet that has not set up backup yet has no encryption key to protect the
 increments with, so recording is a no-op rather than an error.
 
 An increment that another record depends on must not reach the group later
 than the record itself.  The denomination of a coin is the case that
 matters: a restored coin only counts towards the balance once the
 denomination it names is in the database, since that is where the
 availability row takes its currency and value from.  Denominations are not
 written by a transaction of their own, so recording a coin records its
 denomination with it -- once per denomination, however many coins of it a
 withdrawal makes -- and the two travel in the same block, where the
 denomination section is applied before the coin section.  Leaving the
 denomination to the full collection pass instead would let a coin reach
 the other wallets of the group up to a day ahead of it.
 
 The backup cycle
 ~~~~~~~~~~~~~~~~
 
 One cycle takes whatever increments have accumulated, packs them into a block,
 and appends that block to the account's linked list:
 
 1. In a single database transaction, move the pending increments out of the
    buffer and into an *in-flight block*, storing its nonce, hash, contents and
    the nonce of the block it is to be appended after.
 2. Upload any blobs the block references, then the block itself.
 3. Once the provider has acknowledged the block, discard the in-flight block
    and advance the pointer to the last acknowledged block.
 
 The hand-over in step 1 is what makes the cycle resilient: the increments are
 never absent from both the buffer and a block. A wallet that dies at any point
 either finds increments still pending, or finds an in-flight block and retries
 it — under its **original nonce**, which the server answers with ``304 Not
 modified`` if the upload did in fact land. Increments are thus neither lost
 nor backed up twice, and a cycle that has packed a block always retries it
 before packing new increments, so the linked list stays ordered.
 
 A cycle packs at most one block, and bounds its size.  The server refuses
 an upload beyond its ``storage_limit_in_megabytes`` with ``413``, and a
 block over that limit is not a transient failure: the wallet would re-upload
 the very same block on every cycle and never get past it.  The pack
 therefore stops well below any plausible server limit and leaves whatever
 does not fit in the pending buffer, which the next cycle takes -- a wallet
 handing over a long history (the full collection pass on a well-used
 device) sends it as a run of blocks rather than as one oversized one, and
 reports progress rather than backing off between them.  A ``413`` that
 happens anyway is answered by putting the block's increments back and
 packing the next one smaller, since retrying it unchanged can never
 succeed.
 
 A cycle also pulls the account's linked list before packing new increments,
 applying any blocks it has not seen before (see "Restore process" below), so
 that new blocks are appended after the current end of the list.
 
 An account that has not been paid for yet answers every request with ``402
 Payment required``, and only the upload endpoints carry the ``Taler:`` header
 with a ``taler://pay/...`` URI.  A cycle that is answered this way while
 pulling therefore pushes whatever it has pending, so the payment is settled —
 automatically when the annual fee is zero — and subsequent writes are
 accepted.
 
 Backup schedule
 ---------------
 
 A backup runs at *critical points* of wallet operations, and on a schedule
 otherwise.
 
 A critical point is one past which losing the device loses money or user data
 that cannot be reconstructed. The canonical example is a withdrawal: coin
 secrets are derived from the withdrawal group's seed, so a backup is triggered
 once every planchet has been generated and persisted but **before** the
 exchange is asked to sign them. Past that point the exchange considers the
 coins withdrawn while a wallet restored from an older backup could no longer
 reconstruct them.
 
 A cycle is triggered after the recording transaction commits; if the wallet
 stops before it runs, the increments simply stay pending until the next cycle.
 Independently, a periodic task runs a cycle every hour, covering increments
 whose trigger never fired, e.g. because the wallet was offline or the
 operation has no critical point.  A cycle that could not reach the provider is
 retried after five minutes, and one that is waiting for the account payment to
 be prepared after thirty seconds -- the payment is what unlocks every upload,
 so it is worth retrying as soon as the provider's merchant backend recovers.
 
 Waking the cycle is not always enough. Past a critical point the wallet has
 already revealed key material to somebody else -- the exchange has signed the
 planchets, the purse exists and can be paid into -- and the cycle runs
 concurrently, so the operation would go ahead regardless.  Those points
 therefore *hold*: the task returns to the scheduler and is retried, and only
 proceeds once the pending buffer has reached the provider.  The hold is
 skipped when the account is unpaid, since no cycle can drain the buffer until
 the user pays and freezing every such transaction would be the worse failure.
 
 Each request for a cycle names how much is at stake, and the most urgent
 reason asked for since the last cycle that reached the provider is what
 decides how hard a *failing* cycle retries:
 
 * ``irrecoverable-secret`` -- key material a lost device would turn into lost
   money.  Retried after fifteen seconds: the transaction that produced it is
   held until the buffer drains, so a longer wait is also how long that
   transaction sits still.
 * ``transaction-milestone`` -- a state the user would notice losing, but one
   that can be reconstructed.
 * ``account-payment`` -- the sync account's own payment moved; nothing of the
   user's is at stake.
 
 The last two fall back to the ordinary five-minute retry.  The urgency is not
 persisted: after a restart the pending increments are still there and the
 critical points ask again on their next retry, so it re-establishes itself
 rather than having to be reconstructed.
 
 Full collection pass
 ~~~~~~~~~~~~~~~~~~~~
 
 Eager recording covers every transaction family, but a record can still exist
 that no transaction ever reported: one that predates the backup, or one of a
 kind whose creation path bypasses the record handle.  A periodic *full
 collection pass* is the safety net: it walks every record kind the backup
 manages (the ``backupSources`` of ``sources.ts``) and turns the records that
 have never been backed up into "start" increments.
 
 The pass is expensive -- it reads every denomination, exchange, bank account
 and transaction the wallet holds -- so it does not run on every cycle.  It
 runs when a watermark, ``lastFullCollection`` in the wallet's backup
 configuration record, is older than 24 hours (or absent, i.e. never run).  A
 cycle that woke from a critical point therefore stays cheap while still
 backing up whatever the transactions themselves reported.
 
 A forced cycle (see ``runBackupCycle`` in the wallet-core API below) bypasses
 the watermark and runs the pass regardless.  This is the tool for developer
 diagnostics: everything the pass would collect is reported by
 ``getBackupDiagnostics`` before the cycle runs, so the two requests together
 show exactly what is waiting to be backed up and what a forced cycle would
 add.
 
 Restore process
 ---------------
 
 Restoring a wallet on a (fresh) device is the pull half of the backup cycle,
 driven by a recovery document from ``getBackupRecovery``:
 
 1. ``loadBackupRecovery`` installs the recovery's root key and providers, and
    drops the wallet's own block pointers, so the device starts from nothing.
 2. Once the user activates a recovered provider (``addBackupProvider`` with
    ``activate``), the backup cycle downloads the account's linked list,
    decodes each block it has not seen before, CRDT-applies its increments to
    the local database -- recording the block's nonce in the ``originBlocks``
    of every record it touched -- and stores the blocks locally.
 
 Because the same root key derives the same per-provider account keys, a
 recovering wallet sees exactly the blocks any other wallet in the group
 uploaded and applies them with the same merge rules, so all devices converge
 on the same state.
 
 Two things a restored record cannot simply carry are worked out again on
 the restoring device:
 
 * A coin that arrives before the denomination it names cannot be counted,
   because the availability row cannot be written without it.  Applying a
   denomination therefore recounts the coins of that denomination that are
   already in the database, so a coin whose denomination travels in a later
   block -- or in a block written by another wallet -- still reaches the
   balance instead of being dropped from it for good.
 * A pending withdrawal's transfer instructions -- the exchange's credit
   accounts, and the transfer options the user actually pays with -- are
   derived from the exchange, the instructed amount and the reserve key
   pair, and an option registered with a prepared-transfer service carries
   an expiry.  A restoring wallet derives them again whenever the ones it
   restored are absent or expired, and does so *before* it queries the
   reserve: until the transfer has been made the reserve does not exist at
   the exchange yet, so a wallet that waited for the reserve status would
   never get as far as showing the user something to pay with.
 
 Restore schedule
 ----------------
 
 Restoring happens on demand: it starts when a recovery document is loaded and
 the recovered provider is activated.  Afterwards the restored wallet is kept
 up to date by the same periodic backup task as every other wallet -- the pull
 half runs on every cycle, so changes made by other devices are picked up at
 the cycle interval.
 
 Wallet-core API
 ---------------
 
 Backup providers and the wallet's backup key are managed through the
 wallet-core API. All requests below are available on every platform.  The
 request handlers described here are implemented; the collection and scheduling
 mechanisms described above drive them.
 
 .. ts:def:: AddBackupProviderRequest
 
    interface AddBackupProviderRequest {
      backupProviderBaseUrl: string;
 
      name: string;
 
      // Activate the provider.  Should only be done after
      // the user has reviewed the provider.
      activate?: boolean;
    }
 
 The cycle never *waits* for the account payment.  Downloading the provider's
 proposal and paying it are the purchase's own task, so the cycle only ever
 looks at where that purchase has got to -- confirming it when it is waiting
 for a decision, and otherwise leaving it alone -- and comes back when the
 purchase transitions, or on its retry interval.  Every step is therefore
 idempotent and survives a wallet that stops in the middle.
 
 ``addBackupProvider`` registers a sync server: it stores a provider record and
 -- when ``activate`` is set -- makes it the active sync target and wakes the
 backup cycle.  The request itself does not talk to the provider and returns as
 soon as the record is written; an unreachable provider, or one that is not a
 sync server, therefore shows up as a failing (and retrying) cycle rather than
 as an error from this request.
 
 The first cycle is what learns the provider's terms (it fetches ``/config``
 and reports the result with the ``terms-fetched`` phase of the
 ``backup-status`` notification) and what settles the account payment: a sync
 account only exists once it has been paid for, and the server rejects every
 upload (even at a zero annual fee) until then.  A zero-fee account is paid
 automatically; any other account produces a payment transaction that the user
 confirms from the wallet, and the ``payment-required`` phase of the
 notification carries its ``taler://pay/...`` URI.  Clients follow all of this
 through the notifications, not through this request's response:
 
 .. ts:def:: AddBackupProviderResponse
 
    interface AddBackupProviderResponse {
      status: "ok";
    }
 
 ``removeBackupProvider`` takes a `RemoveBackupProviderRequest` naming the
 provider by base URL and returns an empty object.
 
 .. ts:def:: RemoveBackupProviderRequest
 
    interface RemoveBackupProviderRequest {
      backupProviderBaseUrl: string;
    }
 
 ``getBackupInfo`` reports the wallet's backup identity and the state of each
 known provider, including its terms, payment status and the outcome of the
 last backup attempt.
 
 .. ts:def:: BackupInfo
 
    interface BackupInfo {
      walletRootPub: string;
      providers: ProviderInfo[];
    }
 
 ``ProviderInfo`` describes one known provider and the state of the wallet's
 account on it:
 
 .. ts:def:: ProviderInfo
 
    interface ProviderInfo {
      active: boolean;
      backupProviderBaseUrl: string;
      name: string;
      terms?: BackupProviderTerms;
 
      // Why the last cycle failed, when it did.  Only for the active
      // provider: the cycle statistics describe the wallet's last cycle,
      // and that ran against the provider it syncs to.
      lastError?: TalerErrorDetail;
      lastSuccessfulBackupTimestamp?: TalerPreciseTimestamp;
      lastAttemptedBackupTimestamp?: TalerPreciseTimestamp;
 
      // Payment transactions opened for this account, most recent last.
      paymentTransactionIds: string[];
      // Deprecated alias of paymentTransactionIds, with the same contents,
      // for user interfaces built against an older wallet-core.
      paymentProposalIds: string[];
      paymentStatus: ProviderPaymentStatus;
 
      // What the provider reports it holds for the account, from the
      // account status lookup.  Absent until a cycle has managed to ask,
      // and for providers older than sync protocol v4.
      storageUsedBytes?: number;
      blockCount?: number;
    }
 
 .. ts:def:: BackupProviderTerms
 
    interface BackupProviderTerms {
      supportedProtocolVersion: string;
      annualFee: AmountString;
      storageLimitInMegabytes: number;
    }
 
 The provider's ``paymentStatus`` reflects how far the account payment has
 gotten, based on the payment transaction the wallet opened for it:
 
 .. ts:def:: ProviderPaymentStatus
 
    type ProviderPaymentStatus =
      | { type: "unpaid" }
      | { type: "pending"; talerUri?: string }
      | { type: "insufficient-balance"; amount: AmountString }
      | { type: "paid"; paidUntil: AbsoluteTime }
      | { type: "terms-changed";
          paidUntil: AbsoluteTime;
          oldTerms: BackupProviderTerms;
          newTerms: BackupProviderTerms };
 
 ``getBackupRecovery`` returns the secret needed to restore the wallet on
 another device, along with the providers to fetch the blocks from. It is what
 the user backs up out of band, and what a restoring wallet is fed.
 
 .. ts:def:: BackupRecovery
 
    interface BackupRecovery {
      walletRootPriv: string;
      providers: {
        name: string;
        url: string;
      }[];
 
      // The same data as a self-contained plain text, for writing down by
      // hand or saving to a file.  Produced here and *not* consumed by
      // loadBackupRecovery, which reads the structured fields above.
      paperKey?: string;
    }
 
 The paper key is line-oriented, so that a line is the unit to copy, parse and
 transpose:
 
 .. code-block:: text
 
    TALER-PAPERKEY:1
    KEY: GXDG VQKT ...            (the root key, grouped in fours)
    CHECK: a1b2c3d4               (first 8 hex digits of SHA-512(root key))
    PROVIDER: https://sync.example.com/
    URI: taler://restore/...      (the machine-readable form, LSD0006 5.7)
 
 The ``URI`` line is the canonical machine form: a device restoring from a scan
 or a file needs nothing but that line.  The ``KEY`` / ``PROVIDER`` lines are
 the human form, and the checksum catches a transcription error before it
 silently restores a different -- empty -- sync group.
 
 ``loadBackupRecovery`` feeds such a recovery document into a wallet, which is
 how a second (or replacing) device joins the sync group.  The wallet adopts
 the recovery's root key -- the key every per-provider account key is derived
 from, so adopting it *is* what joining the group means -- and adds the
 recovery's providers.  There is no "keep my own key" variant: a wallet that
 kept its own key would derive different account keys and so would not be in
 the group at all.
 
 Adopting another root key also detaches the wallet from the group it was in:
 the blocks it stored are encrypted under a key it no longer has, and the
 ``originBlocks`` lists that reference them are meaningless.  Both are cleared.
 That deliberately leaves the wallet's own records looking "never backed up",
 which is what they are with respect to the group being joined: the full
 collection pass then offers them up, instead of the pull's "deleted iff absent
 from all origin blocks" sweep removing them for not appearing in the new
 group's linked list.
 
 The providers are registered but not activated; the client activates one with
 ``addBackupProvider`` (``activate: true``), and that is what starts the cycle
 which pulls the backup.
 
 .. ts:def:: RecoveryLoadRequest
 
    interface RecoveryLoadRequest {
      recovery: BackupRecovery;
    }
 
 ``runBackupCycle`` runs a backup cycle now, instead of waiting for the
 periodic task.  This is the dedicated "back up now" request; earlier
 implementations triggered a cycle by re-adding the active provider.
 
 The request only *wakes* the cycle and returns an empty object immediately:
 the cycle runs asynchronously (and is serialized against any other cycle),
 reports its progress and outcome through the ``backup-status`` notifications,
 and persists its statistics for ``getBackupDiagnostics``.  Clients track the
 cycle through those, not through this request's response.
 
 .. ts:def:: RunBackupCycleRequest
 
    interface RunBackupCycleRequest {
      // Run the full-collection pass even when its periodic watermark
      // (24h since the last pass) has not elapsed.  Harmless -- the pass
      // only reads the wallet database -- and user interfaces are
      // expected to only expose it in developer mode.
      force?: boolean;
    }
 
 The statistics are persisted by the wallet after every cycle, whatever
 triggered it, and are reported by ``getBackupDiagnostics`` as the "last cycle"
 outcome.  The ``outcome`` field says how the cycle ended: ``"ok"`` (including
 idle cycles with nothing to push), ``"payment-required"`` (the account is
 unpaid) or ``"error"``.
 
 .. ts:def:: BackupCycleStats
 
    interface BackupCycleStats {
      timestamp: TalerPreciseTimestamp;
      // How the cycle ended: "ok", "payment-required" or "error".
      outcome: "ok" | "payment-required" | "error";
      // Why it failed, when the outcome is "error"; the same detail the
      // notification carried, kept for a client that was not listening.
      lastError?: TalerErrorDetail;
 
      // What the cycle pushed to the provider.
      pushed: {
        // Whether the full-collection pass ran in this cycle.
        fullCollectionRan: boolean;
        // Nonce of the block uploaded, if there was anything to upload.
        blockNonce?: string;
        incrementCount: number;
        // Number of increments per increment type, keyed by the
        // increment type's wire string (e.g. "payment-start").
        incrementsByType: { [type: string]: number };
        blobRefCount: number;
      };
 
      // What the cycle's pull applied from the provider.
      pulled: {
        blocksApplied: number;
        blocksSkipped: number;
        incrementCount: number;
        incrementsByType: { [type: string]: number };
        blobRestoreCount: number;
      };
    }
 
 ``getBackupDiagnostics`` reports aggregated statistics about what the backup
 holds: what a cycle would back up right now, and what the last cycle restored.
 It is intended for developer tooling; user interfaces are expected to only
 expose it in developer mode, but the request itself is harmless and available
 on every platform.
 
 .. ts:def:: BackupDiagnostics
 
    interface BackupDiagnostics {
      // The increments waiting in the eager pending buffer: what a normal
      // (unforced) cycle would push right now.
      pending: IncrementStatSummary;
 
      // The records the backup has never seen, which only the periodic
      // full-collection pass picks up: what a forced cycle would add.
      fullCollectionCandidates: IncrementStatSummary;
 
      // Outcome of the last backup cycle, when at least one has run.
      lastCycle?: BackupCycleStats;
    }
 
 .. ts:def:: IncrementStatSummary
 
    interface IncrementStatSummary {
      incrementCount: number;
      // Number of increments per increment type, keyed by the increment
      // type's wire string.
      incrementsByType: { [type: string]: number };
      // Number of distinct blob references the increments carry.
      blobRefCount: number;
    }
 
 Account keys are not part of any of these payloads: they are derived from the
 wallet root key and the provider's base URL, so each provider sees an
 unlinkable account public key and only the root key has to be preserved.
 
 .. code-block:: text
 
    account_priv = KDF(32, wallet_root_priv,
                       "taler-sync-account-key-salt", provider_base_url)
 
 Backup notifications
 --------------------
 
 The wallet pushes a ``backup-status`` notification to its clients
 (``NotificationType.BackupStatus``) as a backup cycle runs, through the
 regular wallet notification listener.  Clients should use it instead of
 polling ``getBackupInfo`` to track a cycle: it reports the phase the cycle is
 in and, on the terminal phases, the outcome and the relevant counters.
 
 .. ts:def:: BackupStatusNotification
 
    interface BackupStatusNotification {
      type: "backup-status";
      providerBaseUrl: string;
      // "started", "pulling", "pushing" and "terms-fetched" are progress
      // phases; the cycle ends in exactly one of "completed", "error" and
      // "payment-required".
      phase: "started" | "pulling" | "pushing" | "terms-fetched" |
             "completed" | "error" | "payment-required";
      // Number of increments packed into the block being pushed
      // (at "pushing").
      pendingIncrementCount?: number;
      // Number of blocks the pull applied (at "completed").
      pulledBlocks?: number;
      // Nonce of the block pushed (at "completed").
      pushedBlockNonce?: string;
      // Reason of the failure (at "error").
      error?: TalerErrorDetail;
      // taler://pay/... URI of the prepared account payment (at
      // "payment-required"); absent when the provider answered a bare
      // 402 without a pay URI.
      talerUri?: string;
      timestamp: TalerPreciseTimestamp;
    }
 
 The wallet emits ``started`` when a cycle begins, ``pulling`` before the
 linked list is fetched, ``pushing`` with the increment count before the packed
 block (and its blobs) is uploaded, ``terms-fetched`` when it has read the
 provider's ``/config`` (which is where a newly added provider's terms come
 from, so a client showing them refreshes on it), and a terminal phase when the
 cycle ends:
 
 * ``completed`` -- the cycle ran without error and without requiring payment
   (``pulledBlocks`` / ``pushedBlockNonce`` carry the counters);
 * ``payment-required`` -- the account is unpaid; a payment transaction may
   already have been prepared, and the UI should take the user to it;
 * ``error`` -- the cycle failed (with ``error`` as the reason); the wallet
   retries on its own schedule, so the notification is only for the user
   interface.  The reason is also persisted, and reported by ``getBackupInfo``
   as the active provider's ``lastError``, so a client that was not listening
   at the time still sees it.
 
 A cycle whose pull applied anything additionally emits a ``balance-change``
 notification.  The apply path writes coins and transactions straight into the
 database, so none of the transaction state machines report them; the
 ``backup-status`` notification says a cycle finished, not that the wallet's
 contents changed, and a client that refreshed on it alone would show a
 restoring wallet as empty until something else happened.
 
 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
 ==================
 
 * [x] Design backup schema.
 * [ ] Design incremental sync.
 * [x] Design backup/restore schedules.
 * [x] Design wallet-core API.
 * [x] Wallet-core implementation.  The machinery -- block and blob encoding,
   CRDT merge, the sync protocol client and its signatures, increment
   collection, the scheduled backup cycle with its pull/merge/apply half, the
   API request handlers, the account payment flow, and item deletion
   (retro-redaction of the ``originBlocks`` plus the pull-side "deleted iff
   absent from all origin blocks" sweep) -- is done, and so is **every
   increment family in this document**: the exchange, global-trust,
   bank-account, donau and denomination entities; the reserve family
   (``set-reserve-seed`` / ``add-reserve``, with the seed-derived key pairs and
   the ``reservePriv`` fallback for reserves that predate the seed), which is
   what makes a restored coin recoupable; the withdrawal, deposit,
   merchant-payment, peer-push-credit, peer-push-debit, peer-pull-debit and
   peer-pull-credit transaction families; the refresh family, whose per-coin
   session seed lets a restored wallet finish a melt instead of losing the
   change; and the coin and token families, which carry the per-record key
   material the wallet database stores (the seed-derived modelling of earlier
   drafts is gone from both).
 
   Contract terms travel as blobs -- uploaded ahead of the blocks that
   reference them, with their reference counts adjusted, and fetched and stored
   back into the contract-terms store on the pull side; a transaction whose
   terms are not available is shown in a reduced form instead of failing the
   transaction listing.  Restoring a coin recomputes the coin-availability
   rows, so a restored wallet shows the same balance as the wallet that made
   the backup, and a restored wallet can continue a pending withdrawal (only an
   expired bank operation cannot be resumed).  ``runBackupCycle`` and
   ``getBackupDiagnostics``, the per-cycle statistics, the forced
   full-collection pass and the ``backup-status`` notifications are all in
   place, on both database backends: the native (sqlite) schema stores the
   backup providers and blocks and the ``originBlocks`` of every backup-managed
   record, and a wallet migrating from the IndexedDB backend carries all three
   across.
 
   The three *derived* families -- refund, recoup and denomination loss -- are
   implemented as finished facts, and every change to whether a coin counts
   towards the balance (spend, refresh, recoup, denomination loss, suspend) is
   reported as a coin increment, so two wallets converge on the same balance
   rather than only on the same coins.  A transaction can no longer be taken
   back out of a terminal state by an increment describing an older view of it.
 
   Known gaps, none of which loses money: refund *items* are not carried
   (nothing outside the refund query reads them, and the merchant hands back
   the same ones); the exchange entries and peer-pull-credit records do not
   restore their ``currentMergeReserveRowId`` pointer, since it is a row id
   local to one database; recoup transactions are backed up and restored but
   the wallet does not yet render them as transactions; and a wallet cannot
   join a sync group written by a *newer* wallet -- it refuses the blocks
   rather than re-uploading a truncated view of them.
 * [x] Design sync API (+ auth).
 * [ ] Server-side implementation (partial: block GET/POST/PUT/DELETE, object
   store GET/POST with reference counting, /config and payments done;
   reconciliation mechanism still missing).
 * [x] UI/UX for backup and sync, in the Android wallet: adding and removing a
   provider, the account payment prompt, the recovery as a QR code and as a
   paper key (written down or saved to a file) with its import counterpart,
   "back up now" through ``runBackupCycle`` with a force-full-backup control
   and a diagnostics card in developer mode, and a progress display driven by
   the ``backup-status`` notifications.  The web extension shows the cycle in
   its wallet-activity view, but has no provider management user interface yet.
 
 Alternatives
 ============
 
 .. _sync-data-structures:
 
 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 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.
 
 * Should the wallets always keep a full copy of the linked list?