12.6. Design Doc 005: Wallet Backup and Sync

Warning

This is an unfinished draft.

12.6.1. Summary

This document discusses considerations for backup and synchronization of wallets.

12.6.2. Requirements

  • Backup and sync must not require any synchronous communication between the wallets
  • Wallets operating (payments/withdrawals/…) for longer periods of time without synchronizing should be handled well
  • Conflicts should be resolved automatically in pretty much all cases
  • One wallet can be enrolled with multiple sync servers, and a wallet can join
  • Other wallets connected to the sync server are trusted.

12.6.3. Proposed Solution

The blob stored on the backup/sync server is a compressed and encrypted JSON file.

The various entity types managed by the wallet are modeled LWW-Sets (Last Write Wins Set CRDT). Timestamps for inserts/deletes are are Lamport timestamps. Concurrent, conflicting insert/delete operations are resolved in favor of “delete”.

The managed entities are:

  • set of exchanges with the data from /keys, /wire
  • set of directly trusted exchange public keys
  • set of trusted auditors for currencies
  • set of reserves together with reserve history
  • set of accepted bank withdrawal operations
  • set of coins together with coin history and blinding secret (both for normal withdrawal and refresh) and coin source info (refresh operation, tip, reserve)
  • set of purchases (contract terms, applied refunds, …)
  • assignment of coins to their “primary wallet”

(Some of these might be further split up to allow more efficient updates.)

Entities that are not synchronized are:

  • purchases before the corresponding order has been claimed
  • withdrawal operations before they have been accepted by the user

Entities that could be synchronized (to be decided):

  • private keys of other sync accounts
  • coin planchets
  • tips before the corresponding coins have been withdrawn
  • refresh sessions (not only the “meta data” about the operation, but everything)

Garbage collection

There are two types of garbage collection involved:

  1. CRDT tombstones / other administrative data in the sync blob. These can be deleted after we’re sure all wallets enrolled in the sync server have a Lamport timestamp larger than the timestamp of the tombstone. Wallets include their own Lamport timestamp in the sync blob:

    {
      clocks: {
        my_desktop_wallet: 5,
        my_phone_wallet: 3
      },
      ...
    }
    

    All tombstones / overwritten set elements with a timestamp smaller than the smallest clock value can be deleted.

  2. Normal wallet GC. The deletion operations resulting from the wallet garbage collection (i.g. deleting legally expired denomination keys, coins, exchange signing keys, …) are propagated to the respective CRDT set in the sync blob.

Ghost Entities

Sometimes a wallet can learn about an operation that happened in another synced wallet before a sync over the sync server happens. An example of this is a deposit operation. When two synced wallets spend the same coin on something, one of them will receive an error from the exchange that proves the coin has been spent on something else. The wallet will add a “ghost entry” for such an event, in order to be able to show a consistent history (i.e. all numbers adding up) to the user.

When the two wallets sync later, the ghost entry is replaced by the actual purchase entity from the wallet that initiated the spending.

Ghost entities are not added to the sync state.

Multiple sync servers

When a wallet is connected to multiple sync servers, it automatically propagates changes it received from one sync server to the others. Local changes made by the wallet are propagated to all sync servers. The goal of this is to make the state of the sync servers converge.

The different sync servers one wallet is enrolled with do not necessarily have the same set of other wallet enrolled. Each sync server has a separate Lamport clock and contains a separate CRDT.

12.6.4. Backup user flow

digraph G { nodesep=0.5; withdrawal [ label = "First\nWithdrawal"; shape = oval; ]; has_backup [ label = "Has backup\nconfigured?"; shape = diamond; ]; app_settings [ label = "App\nSettings"; shape = rect; ]; backup_onboarding [ label = "Backup\nOnboarding"; shape = rect; ]; backup_settings [ label = "Backup Settings\n\n* time of last backup\n* current service"; shape = rect; ]; choose_backup_service [ label = "Choose\nBackup Service"; shape = rect; ]; tos_accepted [ label = "Current ToS\naccepted?"; shape = diamond; ]; tos [ label = "ToS"; shape = rect; ]; payment_required [ label = "Payment\nrequired?"; shape = diamond; ]; payment_confirmation [ label = "Payment\nConfirmation"; shape = rect; ]; backup_secret [ label = "Backup Secret\n\nStore or write down!"; shape = rect; ]; withdrawal -> has_backup; has_backup -> backup_onboarding [label="No"]; backup_onboarding -> backup_settings; app_settings -> backup_settings; backup_settings -> backup_settings [label="Disable Backup"]; backup_settings:w -> backup_settings:w [label="Sync now"]; backup_settings -> choose_backup_service; choose_backup_service -> tos_accepted [label="Select Service"]; tos_accepted -> tos [label="No"]; tos_accepted -> payment_required [label="Yes"]; choose_backup_service:w -> choose_backup_service [label="Remove current service"]; choose_backup_service:n -> choose_backup_service:n [headlabel="Add new service", labeldistance=3.5]; tos -> payment_required [label="Accept"]; payment_required -> payment_confirmation [label="Yes"]; payment_confirmation -> backup_secret [label="Paid"]; backup_secret -> backup_settings [dir=both, label="Stored"]; payment_required:s -> backup_secret:w [label="No"]; { rank=same; has_backup; backup_onboarding; } { rank=same; withdrawal; app_settings; } { rank=same; tos_accepted; tos; } { rank=same; payment_required; payment_confirmation; } }

Backup Settings Screen

  • Backup my wallet [on/off]
  • Backup services No service active (shows time of last backup per service)
  • Show backup secret You need this secret to restore from backup
  • option to sync/backup now (hidden in action bar overflow menu)

Choose Backup Service Screen

This screen can be reached by pressing the Backup services setting in the Backup Settings Screen. It lists the currently active service and other services that can be used. The user has the option to add new services to the list.

A backup service has

  • a name
  • a base URL
  • a fee per year in an explicit currency

Clicking an active service shows the above service information as well as:

  • the service secret that is required to restore from backup
  • last payment date and next scheduled payment date
  • option to deactivate the backup service

Clicking an inactive service allows the user to use the backup service (after accepting ToS and making the payment).

Terms of Service Screen

This screen always appears when a backup provider is selected and the user did not yet accept the current version of its terms of service.

It shows the terms of service text and an accept checkbox, as well as the usual back button.

Payment Confirmation Screen

This is the same screen that the user sees when doing other purchases. The only difference is that after successful payment, the user will be shown the service secret instead of the transaction list.

Backup Secret Screen

After setting up a backup service, the user needs to securely store the secret needed to restore from backup. The secret will be shown as a Taler URI in plain text. This has the form: taler://sync/$SYNC-DOMAIN/$SYNC-PATH#$PRIVATE-KEY Additionally, the URI will be encoded as a QRcode. Depending on the platform, there should be an option to print or export (PDF) the secret.

Backup Onboarding

If no backup service was selected when the user makes the first withdrawal, an onboarding screen will be shown that takes the user to the backup configuration screen.

Don’t loose your money, use a backup service!

Your wallet comes with a list of backup services that can store an encrypted copy of your wallet. Use one to keep your money safe!

[Set backup up now]

12.6.5. References

  • Shapiro, M., Preguiça, N., Baquero, C., & Zawirski, M. (2011). A comprehensive study of convergent and commutative replicated data types. [PDF]

12.6.6. Discussion / Q&A

  • Why is backup/sync not split into two services / use-cases?
    • For privacy reasons, we can’t use some interactive sync service. Thus we use the backup blob as a CRDT that also synchronization for us.
  • Do we need to handle backup/sync state becoming very large e.g. by many transactions and embedded product images potentially exceeding service quota?
  • Do we synchronize the list of other backup enrollments? How do we handle distributing the different private keys for them?
    • If we automatically sync the sync enrollments and the old sync account is compromised, the new sync account would automatically be compromised as well!
    • If every wallet had its own sync key pair, we could select which existing wallets to roll over as well.
  • How do we handle a synced wallet that becomes malicious deleting all coins or purchased products?
    • This needs to balance the genuine need to permanently delete data.
    • Should the sync server allow to fetch previous versions of the sync blob? (If not, how to provide backup functionality?)
    • Should the individual wallets keep tombstones (i.e. entities just marked as deleted) around for some time, or should they delete and “sanitize” (delete data not needed for the CRDT) tombstones as soon as possible?
  • How do we make it easy to remove compromised devices from the sync group and prevent them from getting access to future funds and transactions?
    • We need to remove all sync connections on all connected devices and then individually (and manually) add all devices to the new backup account.
    • If we encrypted the key with each wallet’s private sync key, we could choose which wallets we want to migrate to the new sync account.
    • Can we then roll-over wallets to the new account automatically or does it have to be manually on each device to prevent an attacker to roll us over?
  • How are wallets identified for backup/sync?
    • UUID / EdDSA pub and nick name? When nickname clashes, some number is added based on lexical sort of the random id (“phone#1”, “phone#2”).
  • How do we explain users that it can take days for wallet state to synchronize to all devices?
  • How are people supposed to securely store their backup account key(s)?
    • There can be an option to print/export the QR code
    • They can manually write down the taler:// Uri containing the key.
    • Maybe encode the key in a different format such as BIP39?
  • Do we have a passphrase for our backup account key(s)?
    • ???