Design Doc 019: Wallet Backup Merging
#####################################

Summary
=======

This design doc discusses considerations for merging wallet backups.


Motivation
==========

The wallet backup functionality is meant to be used primarily with one device
per backup account.  Multiple devices sharing one backup account is heavily
discouraged, as it can lead to unexpected and unwanted user experiences, such
as money suddenly vanishing when it has been spent by a device that shares the
backup account.

However, there are some situations where more than one device accesses the same
backup account.  This happens when:

1. A wallet backup is restored on a new device, but the
   old device is still active.  In this scenario, the devices
   have different device IDs, but the same wallet root public key.
2. An old wallet backup is taken over by an existing wallet.
   In this scenario, the devices have different devices IDs and
   different wallet root public keys.
3. A wallet device is copied, for example by restoring the whole
   device from a device-level backup (not a wallet backup!).
   In this scenario, the devices have the same device ID
   and the same wallet root public key.


Requirements
============

The backup merging must ensure that:

* No data that the user wants to keep is lost.
* No data that the user has intentionally deleted is re-surfaced.
* Conflicts should be resolved automatically wherever possible.


Proposed Solution
=================

Stored Information
------------------

* Every wallet keeps track of the following data:

  * The current version number (positive integer)
  * The current wallet root public key (Ed25519 public key)
  * The current device ID (human-readable string)
  * The status of every backup service account (not defined further here)

* A backup blob stores the following information relevant for backup merging:

  * The backup's version number, equal to the version number of
    the wallet when the backup was uploaded.
  * The wallet root public key of the wallet that owns the backup account
  * The device ID of the wallet that owns the backup account.

* Every object and tombstone in the wallet's database and the backup blob keeps
  track of:

  * The version number at which the entry was created.
  * A timestamp for the entry.

The version number is incremented with every operation that adds an object or
tombstone to the wallet's database.


Resolving Conflicts
-------------------

This section describes how conflicts are resolved when a wallet (with ``wallet_version``, ``wallet_device_id``
and ``wallet_root_pub``) is merged with a backup (with ``backup_version``, ``backup_device_id``, and
``backup_root_pub``).

* If ``wallet_root_pub != backup_root_pub``:  The user is shown a warning "the backup
  account was written to by another wallet and can't be read by this wallet", and offered a dialog to either:

  a. "Take over" the backup account and migrate it to the existing wallet root public key.
     A clear warning must be shown that this will kick out the other device currently connected
     to this account **and** will cause all data from the backup account to be lost.
  b. Remove the backup account from the list.

  Note that when first adding the backup account via a recovery code, there is a third option:
  Migrate wallet to the account's wallet root public key.  This is **only** possible when
  scanning the recovery code, as the wallet needs the wallet root secret key to migrate
  to the account.

* If ``wallet_root_pub == backup_root_pub`` and ``wallet_device_id != backup_device_id``:  The
  user is shown a warning "two wallet devices are using the same backup account", and given
  the option of:

  a. Taking over the account from the existing device.  This will not cause data loss,
     but the other device (if it still exists!) will stop syncing.
  b. To "abandon" the current wallet.  This (optional, but recommended) will sync the current wallet state
     with a special marker in the backup blob (so the other wallet continues syncing without
     having to ask the user), and then delete the database contends and create a new ``wallet_root_pub``. 

* If ``wallet_root_pub == backup_root_pub`` and ``wallet_device_id == backup_device_id``:

  * If ``wallet_version > backup_version``, do a normal backup
    cycle (merge backup blob into wallet and upload a new backup).

  * If ``wallet_version <= backup_version``, another wallet with the same
    root public key must have "tampered"
    with the wallet's state.  Do a normal backup cycle, but consider displaying
    a warning/notification to the user.


Garbage-collecting Tombstones
-----------------------------

Tombstones should be automatically garbage-collected when the following criterea
are both fulfilled:

* The versions of active backup accounts are all larger than
  the tombstone's version, and
* the tombstone exceeded a threshold age (say, 3 days).


Q / A
=====

* Q: Why are version numbers and tombstones necessary in backups?

  * A: When syncing with a backup server that still has an old version
    (but same device ID and wallet root pub), the tombstones ensure
    that no old data is re-surfaced that has been deleted in later
    versions.

* Q: Why are tombstones only GCed after exceeding an age threshold?

  * A:  If we deleted them immediately, this might cause data to be re-surface
    if a user temporarily removes and adds a backup account (say by accident)
    that hasn't been synced in a while.

* Q: Why doesn't the wallet root public key get rotated every time
  that a wallet backup is restored on a new device?

  * A: Because that would mean that old "paper backups" and Anastasis
    backups stop working, because they are based on the wallet root key.

* Q: Why can't the wallet obtain some unique devices identifier to exclude
  case 3 (same device ID, same wallet root pub)?

  * A: Because we don't have a reliable API for this on many platforms.
    Even if we had one, we shouldn't rely on it.