019-wallet-backup-merge.rst (10214B)
1 XX 19: Wallet Backup Merging 2 ############################ 3 4 :Design status: Superseded 5 :Implementation status: Prototype 6 :DD shepherd: TBD 7 :Historical contributors: Florian Dold, Christian Grothoff, Iván Ávalos 8 :First published: 2021-04-26 9 :Last substantive change: 2026-08-09 10 :Superseded by: :doc:`092-incremental-backup-sync` 11 12 .. warning:: 13 14 This design document is deprecated. The incremental backup and sync 15 protocol described in `DD 92`_ supersedes it. 16 17 The body below is retained for historical context and is non-normative. 18 19 .. _DD 92: https://docs.taler.net/design-documents/092-incremental-backup-sync.html 20 21 Summary 22 ======= 23 24 This design doc discusses considerations for merging wallet backups. 25 26 27 Motivation 28 ========== 29 30 The wallet backup functionality is meant to be used primarily with one device 31 per backup account. Multiple devices sharing one backup account is heavily 32 discouraged, as it can lead to unexpected and unwanted user experiences, such 33 as money suddenly vanishing when it has been spent by another device 34 that shares the same backup account. 35 36 However, there are some situations where more than one device 37 accesses the same backup account. This happens when: 38 39 1. A wallet backup is restored on a new device, but the 40 old device is still active. In this scenario, the devices 41 have different device IDs, but share the same wallet root 42 public key. 43 2. An old wallet backup is taken over by an existing wallet. 44 In this scenario, the devices have different devices IDs and 45 different wallet root public keys. 46 ### CG: This is not exactly more than one device accessing the same backup account! 47 ### CG: Maybe formulate intro differently, to talk about key scenarios that deserve consideration / need to be distinguished? 48 3. A wallet device is copied, for example by restoring the whole 49 device from a device-level backup (not a wallet backup!). 50 In this scenario, the devices have the same device ID 51 and the same wallet root public key. 52 53 54 Requirements 55 ============ 56 57 The backup merging must ensure that: 58 59 * No data that the user wants to keep is lost. 60 * No data resurfaces that the user has previously intentionally deleted. 61 * Conflicts should be resolved automatically wherever possible. 62 * The solution tolerates system clocks not being monotonic. 63 64 65 Proposed Solution 66 ================= 67 68 Stored Information 69 ------------------ 70 71 * Every wallet keeps track of the following data: 72 73 * The current version number (positive integer) 74 * The current wallet root public key (Ed25519 public key) 75 ### CG: public key? Not the private key? What is the private information the wallet usually keeps? 76 * The current device ID (human-readable string) 77 * The status of every backup service account (not defined further here) 78 * The last system time observed on the current device (by device ID). 79 80 * A backup blob stores the following information relevant for backup merging: 81 82 * The backup's version number, equal to the version number of 83 the wallet when the backup was uploaded. 84 * The wallet root public key of the wallet that **owns** the backup account 85 * The device ID of the wallet that **owns** the backup account. 86 87 * Every record and tombstone in the wallet's database and the backup blob keeps 88 track of: 89 90 * The version number at which the entry was created. 91 * A timestamp for the entry, based on enforced monotonic time (per device ID). 92 93 The version number is incremented with every operation that adds an record or 94 tombstone to the wallet's database. 95 ### CG: operation or transaction? I would prefer transaction here. 96 97 98 Resolving Conflicts 99 ------------------- 100 101 This section describes how conflicts are resolved when a wallet (with ``wallet_version``, ``wallet_device_id`` 102 and ``wallet_root_pub``) is merged with a backup (with ``backup_version``, ``backup_device_id``, and 103 ``backup_root_pub``). 104 ### CG: The term 'merged' is something I do not like. Is this during 'backup', 'restore', or 'sync'? 105 ### I suspect these cases need to be distinguished, because the user asking for a 'restore' is 106 ### not creating the same situation than a wallet 'sync'ing during an automated backup, and 107 ### that may again differ from an _initial_ backup (where I guess there are no conflicts, but 108 ### to improve understanding 109 110 * If ``wallet_root_pub != backup_root_pub``: The user is shown a warning "the backup 111 account was written to by another wallet and can't be read by this wallet", and offered a dialog to either: 112 113 a. "Take over" the backup account and migrate it to the existing wallet root public key. 114 A clear warning must be shown that this will kick out the other device currently connected 115 to this account **and** will cause all data from the backup account to be lost. 116 ### CG: Do we even want to allow this? How _can_ this happen exactly? What is the relationship between backup account and root key? 117 ### CG: The private account key is derived from the root public key; 118 ### I do not see us saying anywhere that we would even support 119 ### extracting/exchanging account keys. Hence, I think this basically 120 ### cannot happen: to access the backup, I already must know the root private key. 121 b. Remove the backup account from the list. 122 123 Note that when first adding the backup account via a recovery code, there is a third option: 124 Migrate wallet to the account's wallet root public key. This is **only** possible when 125 scanning the recovery code, as the wallet needs the wallet root secret key to migrate 126 to the account. 127 ### CG: I think this should be the only thing that can possibly happen, by UI/UX. 128 ### Of course _theroretically_ someone could extract ONLY an account-priv and 129 ### use that to download the backup, but then they should just not be able to 130 ### decrypt it. End of story. 131 132 * If ``wallet_root_pub == backup_root_pub`` and ``wallet_device_id != backup_device_id``: The 133 user is shown a warning "two wallet devices are using the same backup account", and given 134 the option of: 135 136 a. Taking over the backup account from the existing device. This will not cause data loss, 137 but the other device (if it still exists!) will stop syncing. 138 b. To "abandon" the current wallet. This (optional, but recommended) will sync the current wallet state 139 with a special marker in the backup blob (so the other wallet continues syncing without 140 having to ask the user), and then delete the database contends and create a new ``wallet_root_pub``. 141 ### CG: I do not think we can 'recommend' option b, because we do not know if the other 142 ### device still exists. So the UI should be neutral here between the two equally valid choices. 143 144 * If ``wallet_root_pub == backup_root_pub`` and ``wallet_device_id == backup_device_id``: 145 146 * If ``wallet_version > backup_version``, do a normal backup 147 cycle (merge backup blob into wallet and upload a new backup). 148 ### CG: We should note that the motivation for a merge arises 149 ### from the 3rd scenario under Motivation: full device backup&recovery. 150 151 * If ``wallet_version <= backup_version``, another wallet with the same 152 root public key must have "tampered" 153 with the wallet's state. Do a normal backup cycle, but consider displaying 154 a warning/notification to the user. 155 ### CG: I think there is no point in distinguishing these two cases; 156 ### in both cases, if the merge is non-trivial, something odd happened. 157 ### Still, I am not sure that a warning/notification is helpful, as 158 ### it is hardly actionable for the user. 159 160 161 Garbage-collecting Tombstones 162 ----------------------------- 163 164 Tombstones should be automatically garbage-collected when the following criteria 165 are both fulfilled: 166 167 * The versions of active backup accounts are all larger than 168 the tombstone's version, and 169 * the tombstone exceeded a threshold age (say, 3 days). 170 171 ### CG: I backup at providers A and B. Make transaction T. Then I remove 172 ### provider A from my provider list. I then delete T. Eventually, I backup 173 ### again at provider B without the expired tombstone. Finally, 174 ### I restore from provider A, and then merge with provider B. 175 ### Here, the 'merge' has to be somehow smart enough to drop 176 ### the deleted data from provider A's backup without the tombstone. 177 ### I think we can safely decide that this is the case because 178 ### backup from A says that it was---at the time---synced with provider B. 179 ### However, this means that we do need to additionally retain the 180 ### historic chain of backup providers and their last merge points/versions! 181 182 183 Q / A 184 ===== 185 186 * Q: Why are version numbers and tombstones necessary in backups? 187 188 * A: When syncing with a backup server that still has an old version 189 (but same device ID and wallet root pub), the tombstones ensure 190 that no old data is re-surfaced that has been deleted in later 191 versions. This can happen in practice even with only one device, 192 namely when a backup provider is unavailable for a long time, 193 but then becomes available again. 194 195 * Q: Why are tombstones only GCed after exceeding an age threshold? 196 197 * A: If we deleted them immediately, this might cause data to resurface 198 if a user temporarily removes and adds a backup account (say by accident) 199 that hasn't been synced in a while. 200 ### CG: See above: the timeout does IMO not help here. 201 ### I think we need to track removed backup accounts 202 ### and the last version that was synced there, 203 ### and then basically determine if a sync/merge-chain exists 204 ### from the (possibly resurfaced) transaction version to 205 ### the current wallet version! 206 207 * Q: Why doesn't the wallet root public key get rotated every time 208 that a wallet backup is restored on a new device? 209 210 * A: Because that would mean that old "paper backups" and Anastasis 211 backups stop working, because they are based on the wallet root key. 212 213 * Q: Why can't the wallet obtain some unique devices identifier to exclude 214 case 3 (same device ID, same wallet root pub)? 215 216 * A: Because we don't have a reliable API for this on many platforms. 217 Even if we had one, we shouldn't rely on it.