taler-docs

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

---

 ===========================================
  DD 92: Incremental Wallet Backup and Sync
 ===========================================
 
 :Design status: Accepted
 :Implementation status: Prototype
 :DD shepherd: TBD
 :Historical contributors: Iván Ávalos, Christian Grothoff
 :First published: 2026-03-26
 :Last substantive change: 2026-08-18
 :Implementation evidence: ``taler-typescript-core`` (2026-08-12); ``taler-android`` (2026-08-07; 2026-08-09); not merged into the reviewed HEADs
 :Normative references: ``core/api-sync.rst`` (vBACKUP is upcoming; the current v2 API says no component uses 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 24-byte fresh encryption IV,
 an 8-byte serial, and a gzip-compressed JSON object with its length. The block
 is 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 24 bytes are what `secretbox`_ takes as its nonce, but they are a *fresh
 IV* drawn on every write, not the block identity: the identity that keys the
 URL and the block key is a separate random nonce, so an in-place rewrite (the
 redaction path) re-encrypts a different plaintext under a different
 encryption nonce.  Encrypting under the stable identity instead would make
 the old and new ciphertexts of a rewritten block a two-time pad over exactly
 the data deletion exists to destroy -- an adversary holding the old
 ciphertext recovers ``P_old XOR P_new`` verbatim -- and would reuse the
 Poly1305 one-time authenticator key as well.  The IV is prepended to the
 ciphertext in the clear (on-wire size ``1024n + 40``), so the decryptor can
 read it before decrypting; the block identity continues to travel in the URL
 and is what the key derives from.
 
 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 *identity 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.  The encryption nonce is the fresh
 IV, which travels in the clear with the ciphertext; the identity nonce travels
 in the URL.
 
 The block format starts at version 7, and only version 7 is ever read: the
 earlier pre-release framing (encrypted under its identity nonce, on-wire size
 ``1024n + 16``) is not supported and never shipped, so there is nothing to
 keep.
 
 .. note::
 
    The key is derived from the *identity 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)           |
    +-----------------------------------+
    | IV (24 byte)                      |  <- fresh per write, also the
    +-----------------------------------+     secretbox nonce
    | serial (8 byte)                   |
    +-----------------------------------+
    | JSON length n (4 byte)            |
    +-----------------------------------+
    | gzipped JSON (n byte)             |
    +-----------------------------------+
    | padding (to next full KB)         |
    +-----------------------------------+
    +-----------------------------------+
    | IV (24 byte)                      |  <- prepended in the clear
    +-----------------------------------+
    | secretbox(plaintext, IV, key)     |  <- ciphertext, 16-byte tag included
    +-----------------------------------+
 
 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.
 
    .. code-block:: typescript
 
       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.
 
    .. code-block:: typescript
 
       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.
 
    .. code-block:: typescript
 
       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.
 
 .. _sync-data-structures:
 
 Block reconciliation
 ~~~~~~~~~~~~~~~~~~~~
 
 A cycle does not have to walk the whole linked list in order to find what
 it is missing.  It can instead reconcile its local view of the list with
 the server's through an *invertible bloom filter* (IBF), built over every
 block's identity: the filter is constructed so that the difference between
 the wallet's filter and the server's filter enumerates exactly the blocks
 that one side has and the other does not -- including in-place rewrites,
 which keep their identity but change their content hash.  The wallet then
 fetches only those blocks.
 
 .. http:get:: /backups/${ACCOUNT_KEY}/blocks/reconcile
 
    Compute an invertible bloom filter over the account's blocks -- one
    element per block, the block's identity as defined below -- and return
    it, so that the wallet can subtract its own filter and enumerate the
    blocks that differ.  Like the other read endpoints, the request needs
    no signature: the account public key is the capability.
 
    **Request**
 
    :query prefix:
      Optional.  Fresh mixing salt for the filter (4 bytes, base32, network
      byte order).  The server builds its filter with this prefix; absent,
      it uses an all-zero prefix.  Either way the prefix that was used is
      echoed in the response, since both sides must derive the same bucket
      positions.  A caller that suspects a stale or hostile filter can
      demand a differently mixed one; the wallet itself does not currently
      pass a prefix.
 
    **Response**
 
    :http:statuscode:`200 OK`:
      The body is a ``SyncReconcileResponse`` object.  An account without
      blocks answers with ``total_blocks`` 0 and a filter of all-zero
      buckets (built with the minimum bucket count).
    :http:statuscode:`400 Bad request`:
      The ``prefix`` parameter is malformed.
    :http:statuscode:`402 Payment required`:
      The account has expired and requires payment.
    :http:statuscode:`500 Internal server error`:
      A database error occurred.
 
    .. code-block:: typescript
 
       interface SyncReconcileResponse {
         // Filter format version (currently 2).
         version: number;
         // Number of buckets the filter was built with.
         bucket_count: number;
         // Number of bucket positions each element occupies.
         k: number;
         // Mixing prefix the filter was built with (4 bytes, base32).
         prefix: string;
         // Number of blocks in the account's linked list.
         total_blocks: number;
         // The serialized filter, base32-encoded
         // (bucket_count * 98 bytes).
         filter: string;
       }
 
    The server computes its filter over the same element set and with the
    same parameters the wallet uses, so the two filters are directly
    comparable.
 
 Filter format
 +++++++++++++
 
 The filter is an IBF in the style of GNUnet's SET service, parameterized
 for the block store:
 
 * **Element.** One element is the identity of a block: the 24-byte nonce
   followed by the 64-byte SHA-512 hash of the encrypted contents
   (88 bytes).  The hash is part of the element because an in-place
   rewrite changes the hash under the same nonce, so it must show up as a
   difference rather than as a block the wallet already has.  It is the
   same ``block_hash`` the listing returns and the same hash the server
   compares on ``If-None-Match``.
 * **Bucket.** Each bucket holds a signed 16-bit counter, an 88-byte key
   sum (the XOR of every element mapped into the bucket) and an 8-byte key
   hash sum (the XOR of the first 8 bytes of the SHA-512 hash of every
   mapped element) -- 98 bytes in total:
 
   .. code-block:: text
 
      +----------------------------+
      | counter (2 byte, int16)    |
      +----------------------------+
      | key sum (88 byte, XOR)     |
      +----------------------------+
      | key hash sum (8 byte, XOR) |
      +----------------------------+
 
   The counter increments for an insert and decrements for a remove; the
   XOR sums are symmetric, which is what lets the wallet *subtract* its
   filter from the server's.
 * **Bucket positions.** Each element occupies ``k = 3`` distinct
   positions.  The positions are successive 32-bit words of the SHA-512
   over element + mixing prefix, reduced modulo the bucket count; when the
   words run out, the hash itself is hashed again (as in GNUnet's bloom
   filters), and duplicate positions are skipped (as in GNUnet's IBF
   implementation).
 * **Sizing.** The bucket count is the next power of two at or above the
   number of blocks, bounded to the range of 64 to 4096 buckets (the
   serialized filter therefore stays below 4096 * 98 = 401 408 bytes).
   The server rounds ``total_blocks`` up this way; the wallet builds its
   own filter with the server's ``bucket_count``, ``k`` and ``prefix``, so
   the two always match.
 
 Decoding the difference
 +++++++++++++++++++++++
 
 The wallet builds its own filter over its local (nonce, hash) pairs with
 the server's ``bucket_count``, ``k`` and ``prefix``, and subtracts it
 bucket by bucket: the counters difference and the XOR differences.  The
 result is decoded by repeatedly peeling "pure" buckets -- buckets whose
 counter is ``+-1`` and whose key sum hashes to their key hash sum: the
 key sum is then a single element of the difference, and it is removed
 from every bucket it occupies.  Peeling either exhausts the filter (every
 bucket back to zero -- the difference set is fully enumerated) or gets
 stuck on a bucket that mixes several elements (there are more differences
 than the filter size can peel).  A stuck filter is not treated as a lie:
 the wallet falls back to walking the list.
 
 The peeled elements have a side: counter ``+1`` elements exist only on
 the server ("missing" locally), counter ``-1`` elements only in the
 wallet ("stale" locally).  A nonce that appears on both sides is an
 in-place rewrite -- same identity, new hash -- which the wallet fetches
 like a missing block.
 
 The wallet fetches exactly the nonces the difference names -- one at a
 time, through the listing endpoint with ``limit=1`` and the inclusive
 ``start_nonce`` (there is no dedicated per-block GET), each entry verified
 before it is used -- plus, for their relinks, the stored neighbours of
 deleted nonces and the stored tail when nonces were added, since links
 only change server-side when a block is deleted or appended.  The result
 is joined into one chain through the ``prev`` links and applied in order;
 a difference that deletes or rewrites anything re-applies the whole
 chain, so the sweep behind it drops the stale blocks and the records only
 they backed up.  Any failure -- an undecodable filter, a fetch that fails
 verification, an ordering that does not close -- aborts the selective
 pull and falls back to walking the list, bounded by the safety cap of
 10 000 blocks.
 
 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.
 
    .. code-block:: typescript
 
       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.
 
 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).
 
 .. code-block:: typescript
 
    interface IncrementSet {
      version: number;
      addExchangeIncs?: AddExchangeInc[];
      setGlobalExchangeTrustIncs?: SetGlobalExchangeTrustInc[];
      addBankAccountIncs?: AddBankAccountInc[];
      // ...
    }
 
 The ``version`` field is the schema version, which the wallet reads to upgrade
 an older set to the current schema (and refuses a newer one rather than
 re-uploading a truncated view of it).  The upgrade chain is empty: version 1
 is the first schema a released wallet writes.  The prototype-era re-keying
 step (schema version 0) was removed with the data it existed to repair, so a
 v0 set is refused as *older*; the chain machinery stays for the next real
 schema change.  ``isIncrementSetEmpty`` -- which decides
 whether a redacted block may be deleted from the linked list -- tests the
 set's *own* keys rather than the known sections, so a section this wallet does
 not know still counts as content.
 
 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.
 
 .. code-block:: typescript
 
    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.
 
 When the merge resolves against a record the wallet already holds (the local
 timestamp and etag are newer), the origin block is still recorded on the
 record: a full re-apply resets the origin-block lists and sweeps every record
 that comes out of it empty, and skipping the marking would delete an exchange
 record that a block merely confirms.
 
 Set exchange to global trust
 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 
 User sets an exchange to global trust.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    interface SetDonauInfoInc {
      type: "set-donau-info";
      donauBaseUrl: string;
      taxPayerId: string;
      donauSalt?: string;
    }
 
 * **Primary key:** ``[info]``
 * **Deletion groups:** ``[donau-info]``
 
 ``donauSalt`` is the salt the tax-ID hash is derived with.  It is randomly
 generated per wallet, so it must travel with the record: deriving a fresh one
 on restore would change the tax-ID hash and break the linkage of every
 donation receipt already issued.  It is absent on increments written before
 the field was added; a wallet restoring such an increment derives a fresh salt
 as ``handleSetDonau`` does.
 
 Merge strategy
 ++++++++++++++
 
 Last write wins.
 
 Add a denomination
 ~~~~~~~~~~~~~~~~~~
 
 A denomination is stored in the wallet.
 
 .. code-block:: typescript
 
    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:** ``[exchangeMasterPub, hash(denomPub)]`` -- the wallet
   database keys denominations by the exchange *master* public key and the
   hash of the denomination public key, so the increments do too.
 * **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.
 
 .. code-block:: typescript
 
    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;
    }
 
 .. code-block:: typescript
 
    type CoinSource =
      | WithdrawalCoinSource
      | RefreshCoinSource;
 
 .. code-block:: typescript
 
    interface WithdrawalCoinSource {
      type: "withdrawal";
      withdrawalGroupId: string;
      coinIndex: number;
      reservePub: string;
    }
 
 .. code-block:: typescript
 
    interface RefreshCoinSource {
      type: "refresh";
      refreshGroupId: string;
      oldCoinPub: string;
    }
 
 * **Primary key:** ``[coinPub]``
 * **Deletion groups:** ``[coins, denominations]`` -- a coin references the
   denomination it was withdrawn under (by ``[exchangeMasterPub,
   denomPubHash]``), so deleting that denomination takes its coins along, and
   the coins in turn drag their recoups along through the ``coins`` group.
 
 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.
 
 .. code-block:: typescript
 
    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, denominations]``
 
 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``:
 
 .. code-block:: typescript
 
    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;
    }
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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 reserve's public key and,
 for a seed-derived reserve, the exchange and the derivation index -- and, for
 the reserves that predate the seed, the private key.
 
 .. code-block:: typescript
 
    interface AddReserveInc {
      type: "add-reserve";
      reservePub: EddsaPublicKey;
      exchangeBaseUrl?: string;
      // Derivation index, for a reserve whose key pair comes from the seed.
      reserveIndex?: number;
      // Only for reserves created before the reserve seed existed, whose
      // keys are random and cannot be re-derived.
      reservePriv?: EddsaPrivateKey;
    }
 
 * **Primary key:** ``[reservePub]`` -- the reserve's public key, which is
   what every other increment references it by.  Keying on
   ``[exchangeBaseUrl, reserveIndex]`` instead would let two devices hand the
   same derivation slot to different reserves and silently lose a reserve
   key pair, and ``reservePriv``-carrying reserves have no index at all.
 * **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 is carried (and checked against the re-derived key material on
 restore, so that a reserve restored under the wrong key is refused rather than
 written).  The restored ``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``).
 
 A private-key carry still travels with its local ``reserveIndex`` when the
 record has one.  The index is what the allocation scan
 (``max(highest + 1, counter)``) on every device derives the next seed-derived
 reserve from, so a carry that dropped it would let two wallets of the group
 advance their counters differently and derive different keys for their next
 reserve.
 
 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
 ~~~~~~~~~~~~~~~
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
       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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    interface PaymentDoneInc {
      type: "payment-done";
      proposalId: string;
      payCost?: AmountString;
    }
 
 * **Primary key:** ``[proposalId]``
 * **Deletion groups:** ``[payments]``
 
 ``payCost`` is what the payment actually cost the user
 (``payInfo.totalPayCost``), captured when the merchant confirmed it.  The
 pay-info record itself is not in the backup -- only this total is -- so a
 restored purchase can at least show what was paid.  It is optional so old
 done increments still parse; the full collection pass re-emits them for
 completed purchases, which is how pre-existing ones backfill the total.
 
 Merchant purchase fail
 ~~~~~~~~~~~~~~~~~~~~~~
 
 A payment started by the user fails.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    interface PeerPullDebitStartInc {
      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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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;
      mergeReservePub: EddsaPublicKey;
    }
 
 * **Primary key:** ``[pursePub]``
 * **Deletion groups:** ``[peer-pull-credit]``
 
 ``mergeReservePub`` names the reserve the purse is merged into.  The row id
 the wallet database keeps for it (``mergeReserveRowId``) is an autoincrement
 local to one database and meaningless on another device, so it is the reserve's
 public key that travels instead; the apply path resolves it back to the row id
 through the restored reserve record.
 
 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.
 
 .. code-block:: typescript
 
    interface PeerPullCreditAbortInc {
      type: "peer-pull-credit-abort";
      pursePub: EddsaPublicKey;
      abortReason?: TalerErrorDetail;
    }
 
 * **Primary key:** ``[pursePub]``
 * **Deletion groups:** ``[peer-pull-credit]``
 
 Merge strategy
 ++++++++++++++
 
 Store all ``abortReason`` in the database.
 
 Peer-pull-credit done
 ~~~~~~~~~~~~~~~~~~~~~
 
 A request to another wallet completes successfully (i.e. money is received).
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    interface PeerPullCreditFailInc {
      type: "peer-pull-credit-fail";
      pursePub: EddsaPublicKey;
      failReason: TalerErrorDetail;
    }
 
 * **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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    interface RefreshDoneInc {
      type: "refresh-done";
      refreshGroupId: string;
      timestampFinished: TalerPreciseTimestamp;
    }
 
 * **Primary key:** ``[refreshGroupId]``
 * **Deletion groups:** ``[refreshes]``
 
 Refresh failed
 ~~~~~~~~~~~~~~
 
 The refresh could not be completed.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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;
    }
 
 .. code-block:: typescript
 
    // 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.
 
 .. code-block:: typescript
 
    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]
 
 .. code-block:: typescript
 
    interface DenomLossInc {
      type: "denom-loss";
      denomLossEventId: string;
      currency: string;
      exchangeBaseUrl: string;
      // The master key whose denominations caused the event, when the wallet
      // that recorded it knew it.  It is what lets the deletion cascade match
      // the event against the denominations it wrote off.
      exchangeMasterPub?: 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 identity nonce, with a fresh encryption IV), one that becomes empty
 is removed from the linked list (``DELETE``, relinking its neighbours).  A
 block rewritten in place keeps its identity 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.
 
 Each increment type declares the deletion groups it belongs to: the group it
 is a resource of, plus every group whose resources it *references*.  Deleting
 a resource in a group removes every increment that references it, and the
 removed increments drag in everything that references *them* (the transitive
 closure).  The references are the increment's fields, not its own primary key:
 
 - a ``refund`` references the payment it refunds, by ``[proposalId]``;
 - a ``recoup`` references each coin it recouped, by ``[coinPub]``;
 - a ``add-coin``/``spend-coin`` references the denomination it was withdrawn
   under, by ``[exchangeMasterPub, denomPubHash]``;
 - a ``denom-loss`` references each denomination it wrote off, by
   ``[exchangeMasterPub, denomPubHash]`` (only when the increment carries the
   master public key; increments from before the field was added cannot be
   matched).
 
 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 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 -- and so are the recoups of those coins.  Deleting a
 payment likewise takes the refunds of that payment with it.
 
 .. note::
 
    The delete cascade runs on the increments the backup currently holds.  A
    redaction therefore only reaches the *blocks this wallet has*, which is
    what the deletion queue's retry loop is for: a block the deleting wallet
    has not pulled is redacted by whichever wallet pulls it after the item's
    origin blocks were scrubbed here.
 
 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.
 
 The pull is bounded by a safety cap (10 000 blocks) against a runaway linked
 list.  A list longer than the cap is *truncated*, and a truncated pull is not
 treated as the whole list: the fetched prefix is applied, but the cap must
 not masquerade it as complete.  In particular the re-apply's sweep -- which
 drops every record whose origin blocks no longer exist -- must not run on a
 truncated view, or every block beyond the cap would read as "deleted" and
 every record it alone backed up would be swept away.  A truncated pull
 therefore leaves the stored blocks and records beyond the cap alone, does not
 advance the last-acknowledged-block pointer to the prefix's end (the true
 tail is unknown, so the next append would fail against it), and reports the
 cycle as failed with the account too large to sync, so that the user can
 prune it.
 
 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.
 
 A burst of wake-ups -- a withdrawal records an increment at every step -- must
 not be allowed to chain one cycle into the next: at least three seconds have
 to elapse between the end of one cycle and the start of the next, and a
 wake-up that arrives inside the gate is absorbed instead of scheduled (the
 cycle statistics count it as a ``skippedWakeUp``).  A cycle that acknowledged
 its block rests until the next hourly interval: the buffer is drained, so no
 follow-up cycle is owed.  A cycle that ends still owed work -- the pack split
 what was pending, the payment still needs confirming -- reports progress
 rather than backing off, since a backoff would turn a long history into a
 trickle.  The statistics record how many cycles ran back-to-back
 (``consecutiveRuns``), so the difference between the two behaviours is
 observable.
 
 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 also re-emits the ``payment-done`` increment of every completed
 purchase.  Increments normally happen once, at the transition that created
 them, so a purchase completed before its done increment carried the paid
 total (see ``payment-done``) would never report it again; the re-emission
 ships the total to the group's other wallets.  Applying it is idempotent:
 wallets that already have the total keep it.
 
 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 --
    incrementally, by reconciling its local view through an invertible bloom
    filter and fetching only the blocks that differ (see Block
    reconciliation), or by walking the whole list when reconciliation is not
    possible -- 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.  The reverse direction
   recounts too: a coin removed by a re-apply's sweep corrects the counts of
   its denomination, and the availability row is deleted when the last coin
   of a denomination and age restriction is gone.
 * An increment whose dependency has not arrived yet is deferred, not
   dropped: a ``set-global-exchange-trust`` for an exchange that is not
   known locally, a ``refresh-session`` without its group, a ``refund``
   without its payment, an ``add-reserve`` whose seed is missing.  A record
   the wallet already holds is still marked with the origin block on this
   deferred path, so a full re-apply -- which resets the origin-block lists
   and sweeps records that come out of it empty -- does not delete it while
   it waits for its dependency.
 * 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.
 * A completed purchase's paid amount comes from the ``payCost`` field of its
   ``payment-done`` increment; the UI falls back to the order total when even
   that is missing.
 
 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.
 
 .. code-block:: typescript
 
    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:
 
 .. code-block:: typescript
 
    interface AddBackupProviderResponse {
      status: "ok";
    }
 
 ``removeBackupProvider`` takes a ``RemoveBackupProviderRequest`` naming the
 provider by base URL and returns an empty object.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    interface BackupInfo {
      walletRootPub: string;
      providers: ProviderInfo[];
    }
 
 ``ProviderInfo`` describes one known provider and the state of the wallet's
 account on it:
 
 .. code-block:: typescript
 
    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;
    }
 
 .. code-block:: typescript
 
    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:
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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"``.
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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;
    }
 
 .. code-block:: typescript
 
    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.
 
 .. code-block:: typescript
 
    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
 ==================
 
 The checked implementation items below describe prototype feature branches,
 not the reviewed main branches.  The normative Sync API still labels backup
 support as upcoming.
 
 * [x] Design backup schema, incremental sync, backup/restore schedules and
   the wallet-core API; design the sync API (with authentication).
 * [x] Wallet-core implementation: 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, item deletion
   (retro-redaction plus the pull-side sweep), the account payment flow,
   the API handlers and ``backup-status`` notifications, the
   invertible-bloom-filter reconciliation pull with its list-walk
   fallback, and every increment family in this document -- on both
   database backends (native sqlite and IndexedDB, with migration).
 * [x] Server-side implementation: block GET/POST/PUT/DELETE, the object
   store with reference counting, /config, payments, and the
   invertible-bloom-filter reconciliation endpoint.
 * [x] UI/UX in the Android wallet: provider management, the account
   payment prompt, recovery as QR code / paper key with import, "back up
   now" with a force-full-backup control and diagnostics, and the progress
   display driven by ``backup-status``; the web extension shows the cycle
   in its wallet-activity view but has no provider management UI yet.
 
 Known gaps, none of which loses money: refund *items* are not carried
 (nothing outside the refund query reads them); the exchange entries and
 peer-pull-credit records do not restore their ``currentMergeReserveRowId``
 pointer (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.
 
 Alternatives
 ============
 
 To perform incremental restores (i.e. synchronization) and converge towards
 the global state (a.k.a. reconciliation), wallets need to keep track 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.  Rather than the event-driven message queue outlined below, this
 document specifies the invertible bloom filter (see Block reconciliation),
 which the wallet and server implement.
 
 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.
 
 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?