18.92. DD 92: Incremental Wallet Backup and Sync#
18.92.1. Summary#
This design document describes an incremental, CRDT-based, encrypted wallet backup and sync protocol that addresses the limitations of previous solutions.
18.92.2. 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.
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.
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.
18.92.3. 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.
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.
18.92.4. Proposed solution#
18.92.4.1. 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 will trigger the incremental backup process, where this buffer will be 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.
18.92.4.1.1. Double-linked list block store#
The sync server will maintain a double-linked list in its database, as well as references to the global first and last block (useful for full restores), and is trusted to update the list. Via INSERT, DELETE and REPLACE operations, 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 the blocks 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.
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 expected to not retain any deleted blocks or 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 that will be discussed in further sections.
18.92.4.1.1.1. Block format#
Each block will consist of a 2-byte version number, a random 32-byte nonce, and a gzip-compressed JSON object with its length. The block will be padded up to the next whole kilobyte for privacy reasons.
Encryption will be performed on the block using symmetric authenticated encryption via libsodium’s secretbox function, with a 32-bit key derived from the wallet’s backup encryption key and the hash of the entire plaintext block, which in the final implementation should be shareable between any wallets that the user wishes to add to the synchronization group.
+----------------------------+
| version number (2 byte) |
+----------------------------+
| nonce (32 byte) |
+----------------------------+
| JSON length n (4 byte) |
+----------------------------+
| gzipped JSON (n byte) |
+----------------------------+
| padding (to next full KB) |
+----------------------------+
18.92.4.1.2. 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 will be stored in a hash-indexed object store with a reference count of zero, which will increase 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.
In order to prevent wallets from uploading duplicate blobs, the sync server will compare the hash of the encrypted blob provided by the wallet against the object store before allowing the upload to proceed, rejecting it in case the blob already exists.
18.92.4.1.2.1. Blob format#
Similar to blocks, each blob will consist of 2-byte version number, the 4-byte data length, the gzipped data, and a padding to the next whole kilobyte. The blob will be encrypted using a key derived from the wallet’s backup encryption key and the hash of the unencrypted file.
The hash used to index the object in the store will be computer from the encrypted blob using SHA-512 and truncated to 32 bytes.
+----------------------------+
| version number (2 byte) |
+----------------------------+
| data length n (4 byte) |
+----------------------------+
| gzipped data (n byte) |
+----------------------------+
| padding (to next full KB) |
+----------------------------+
18.92.4.2. 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).
interface IncrementSet {
addExchangeIncs?: AddExchangeInc[];
setGlobalExchangeTrustIncs?: SetGlobalExchangeTrustInc[];
addBankAccountIncs?: AddBankAccountInc[];
// ...
}
When a backup operation is triggered, this buffer will be processed into a block and emptied. The resulting block will be 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.
18.92.4.2.1. 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.
interface AddExchangeInc {
type: "add-exchange";
exchangeBaseUrl: string;
tosAcceptedEtag: string;
tosAcceptedEtagTimestamp: Timestamp;
}
Primary key:
[exchangeBaseUrl]Deletion groups:
[exchanges]
18.92.4.2.1.1. Merge strategy#
Favor the operation with the largest tosAcceptedEtagTimestamp. If two
timestamps are equal, favor the operation with the largest tosAcceptedEtag
in lexicographical order.
18.92.4.2.2. Set exchange to global trust#
User sets an exchange to global trust.
interface SetGlobalExchangeTrustInc {
type: "set-global-exchange-trust";
exchangeBaseUrl: string;
exchangeMasterPub: EddsaPublicKey;
}
Primary key:
[exchangeBaseUrl, exchangeMasterPub]Deletion groups:
[global-exchange-trust]
18.92.4.2.2.1. Merge strategy#
No merge is required.
18.92.4.2.3. Add or update a bank account#
User adds (or updates) a known bank account.
interface AddBankAccountInc {
type: "add-bank-account";
bankAccountId: string;
paytoUri: string;
label: string;
}
Primary key:
[bankAccountId]Deletion groups:
[bank-accounts]
18.92.4.2.3.1. Merge strategy#
Last write wins.
18.92.4.2.4. Set Donau info#
User sets info for tax-deductible donations.
interface SetDonauInfoInc {
type: "set-donau-info";
donauBaseUrl: string;
taxPayerId: string;
}
Primary key:
[info]Deletion groups:
[donau-info]
18.92.4.2.4.1. Merge strategy#
Last write wins.
18.92.4.2.5. Add a denomination#
A denomination is stored in the wallet.
interface AddDenominationInc {
type: "add-denomination";
denomPub: DenominationPubKey;
value: AmountString;
fees: DenomFees;
stampStart: TalerProtocolTimestamp;
stampExpireWithdraw: TalerProtocolTimestamp;
stampExpireLegal: TalerProtocolTimestamp;
stampExpireDeposit: TalerProtocolTimestamp;
masterSig: EddsaSignature;
exchangeBaseUrl: string;
exchangeMasterPub: EddsaPublicKey;
}
Primary key:
[exchangeBaseUrl, denomPub]Deletion groups:
[denominations]
18.92.4.2.5.1. 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.
18.92.4.2.6. Add a coin#
A coin is generated by the wallet but not yet signed by the exchange.
interface AddCoinInc {
type: "add-coin";
coinSource: CoinSource;
denominationId: string;
ageCommitmentProof?: AgeCommitmentProof;
}
type CoinSource =
| WithdrawalCoinSource
| RefreshCoinSource;
interface WithdrawalCoinSource {
type: "withdrawal";
withdrawalGroupId: string;
coinNumber: number;
}
Primary key:
[coinSource]Deletion groups:
[coins, denominations, withdrawals]
18.92.4.2.6.1. Merge strategy#
No merge is required, new coins are unique.
18.92.4.2.7. Sign a coin#
A coin is signed by the exchange.
interface SignCoinInc {
type: "sign-coin";
coinSource: CoinSource;
denomSig: UnblindedDenominationSignature;
}
Primary key:
[coinSource]Deletion groups:
[coins, withdrawals]
18.92.4.2.7.1. Merge strategy#
No merge is required, only one signature for a given coin can be issued by the exchange, further attempts to sign it will fail.
18.92.4.2.8. Spend a coin#
A signed coin is spent by the user.
interface SpendCoinInc {
type: "spend-coin";
coinSource: CoinSource;
}
Primary key:
[coinSource]Deletion groups:
[coins, withdrawals]
18.92.4.2.8.1. Merge strategy#
No merge is required, each coin can only be spent once, further attempts at spending the coin will fail.
18.92.4.2.9. Add a token#
A token is generated by the wallet but not yet signed by the merchant.
interface AddTokenInc {
type: "add-token";
secretSeed: string;
choiceIndex: number;
outputIndex: number;
contractTermsHash: HashCode; // blob
}
Primary key:
[secretSeed, choiceIndex, outputIndex]Deletion groups:
[tokens]
18.92.4.2.9.1. Merge strategy#
No merge is required, new tokens are unique.
18.92.4.2.10. Sign a token#
A token is signed by the merchant.
interface SignTokenInc {
type: "sign-token";
secretSeed: string;
choiceIndex: number;
outputIndex: number;
contractTermsHash: HashCode; // blob
tokenIssueSig: UnblindedDenominationSignature;
}
Primary key:
[secretSeed, choiceIndex, outputIndex]Deletion groups:
[tokens]
18.92.4.2.10.1. 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.
18.92.4.2.11. Spend a token#
A signed token is spent by the user.
interface SpendTokenInc {
type: "spend-token";
secretSeed: string;
choiceIndex: number;
outputIndex: number;
}
Primary key:
[secretSeed, choiceIndex, outputIndex]Deletion groups:
[tokens]
18.92.4.2.11.1. Merge strategy#
No merge is required, each token can only be spent once, further attempts at spending the token will fail.
18.92.4.2.12. Start a withdrawal#
User initiates a withdrawal.
interface WithdrawalStartInc {
type: "withdrawal-start";
withdrawalGroupId: string;
secretSeed: string;
reservePub: EddsaPublicKey;
timestampStart: TalerPreciseTimestamp;
restrictAge?: number;
instructedAmount: AmountString;
}
Primary key:
[withdrawalGroupId]Deletion groups:
[withdrawals]
18.92.4.2.12.1. Merge strategy#
No merge is required, all withdrawals are independent from each other.
18.92.4.2.13. Abort a withdrawal#
User aborts a withdrawal.
interface WithdrawalAbortInc {
type: "withdrawal-abort";
withdrawalGroupId: string;
abortReason?: TalerErrorDetail;
}
Primary key:
[withdrawalGroupId]Deletion groups:
[withdrawals]
18.92.4.2.13.1. Merge strategy#
Store all abortReason in the database.
18.92.4.2.14. Withdrawal done#
A withdrawal started by the user completes successfully.
interface WithdrawalDoneInc {
type: "withdrawal-done";
withdrawalGroupId: string;
timestampFinish: TalerPreciseTimestamp;
rawWithdrawalAmount: AmountString;
effectiveWithdrawalAmount: AmountString;
}
Primary key:
[withdrawalGroupId]Deletion groups:
[withdrawals]
18.92.4.2.14.1. Merge strategy#
No merge is required, a withdrawal can only succeed once.
18.92.4.2.15. Withdrawal failed#
A withdrawal started by the user fails.
interface WithdrawalFailInc {
type: "withdrawal-fail";
withdrawalGroupId: string;
failReason: TalerErrorDetail;
}
Primary key:
[withdrawalGroupId]Deletion groups:
[withdrawals]
18.92.4.2.15.1. Merge strategy#
Store all failReason in the database.
18.92.4.2.16. Start a deposit#
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]
18.92.4.2.16.1. Merge strategy#
No merge is required, all deposits are independent from each other.
18.92.4.2.17. Abort a deposit#
User aborts a deposit.
interface DepositAbortInc {
type: "deposit-abort";
depositGroupId: string;
abortReason?: TalerErrorDetail;
}
Primary key:
[depositGroupId]Deletion groups:
[deposits]
18.92.4.2.17.1. Merge strategy#
Store all abortReason in the database.
18.92.4.2.18. Deposit done#
A deposit started by the user completes successfully.
interface DepositDoneInc {
type: "deposit-done";
depositGroupId: string;
timestampFinished: TalerPreciseTimestamp;
}
Primary key:
[depositGroupId]Deletion groups:
[deposits]
18.92.4.2.18.1. Merge strategy#
No merge required, a deposit can only succeed once.
18.92.4.2.19. Deposit fail#
A deposit started by the user fails.
interface DepositFailInc {
type: "deposit-fail";
depositGroupId: string;
failReason: TalerErrorDetail;
}
Primary key:
[depositGroupId]Deletion groups:
[deposits]
18.92.4.2.19.1. Merge strategy#
Store all failReason in the database.
18.92.4.2.20. Start a merchant payment#
User initiates a payment to a merchant.
interface PaymentStartInc {
type: "payment-start";
proposalId: string;
claimToken?: string;
downloadSessionId?: string;
repurchaseProposalId?: string;
noncePub: EddsaPublicKey;
noncePriv: EddsaPrivateKey;
secretSeed: string;
exchanges?: string[];
contractTermsHash: string; // blob
timestamp: TalerPreciseTimestamp;
// Donau
donauOutputIndex?: number;
donauBaseUrl?: string;
donauAmount?: AmountString;
donauTaxIdHash?: string;
donauTaxIdSalt?: string;
donauTaxId?: string;
donauYear?: string;
}
Primary key:
[proposalId]Deletion groups:
[payments]
18.92.4.2.20.1. Merge strategy#
No merge is required, all payments are independent from each other.
18.92.4.2.21. Confirm a merchant payment#
User confirms a payment to a merchant.
interface PaymentConfirmInc {
type: "payment-confirm";
proposalId: string;
choiceIndex?: number;
timestampAccept: TalerPreciseTimestamp;
}
Primary key:
[proposalId]Deletion groups:
[payments]
18.92.4.2.21.1. Merge strategy#
No merge is required, a payment can only succeed once.
18.92.4.2.22. Abort a merchant payment#
User aborts a payment to a merchant.
interface PaymentAbortInc {
type: "payment-abort";
proposalId: string;
abortReason?: TalerErrorDetail;
}
Primary key:
[proposalId]Deletion groups:
[payments]
18.92.4.2.22.1. Merge strategy#
Store all abortReason in the database.
18.92.4.2.23. Merchant purchase done#
A payment started by the user completes successfully.
interface PaymentDoneInc {
type: "payment-done";
proposalId: string;
}
Primary key:
[proposalId]Deletion groups:
[payments]
18.92.4.2.24. Merchant purchase fail#
A payment started by the user fails.
interface PaymentFailInc {
type: "payment-fail";
proposalId: string;
failReason: TalerErrorDetail;
}
Primary key:
[proposalId]Deletion groups:
[payments]
18.92.4.2.24.1. Merge strategy#
Store all failReason in the database.
18.92.4.2.25. Start peer-push-credit#
User receives an incoming push payment.
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]
18.92.4.2.25.1. 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.
18.92.4.2.26. Abort peer-push-credit#
User aborts an incoming push payment.
interface PeerPushCreditAbortInc {
type: "peer-push-credit-abort";
peerPushCreditId: string;
abortReason?: TalerErrorDetail;
}
Primary key:
[peerPushCreditId]Deletion groups:
[peer-push-credit]
18.92.4.2.26.1. Merge strategy#
Store all abortReason in the database.
18.92.4.2.27. Peer-push-credit done#
An incoming push payment received by the user completes successfully.
interface PeerPushCreditDoneInc {
type: "peer-push-credit-done";
peerPushCreditId: string;
}
Primary key:
[peerPushCreditId]Deletion groups:
[peer-push-credit]
18.92.4.2.27.1. Merge strategy#
No merge is required, a peer-push-credit payment can only succeed once.
18.92.4.2.28. Peer-push-credit fail#
An incoming push payment received by the user fails.
interface PeerPushCreditFailInc {
type: "peer-push-credit-fail";
peerPushCreditId: string;
failReason: TalerErrorDetail;
}
Primary key:
[peerPushCreditId]Deletion groups:
[peer-push-credit]
18.92.4.2.28.1. Merge strategy#
Store all failReason in the database.
18.92.4.2.29. Start peer-push-debit#
User initiates an outgoing push payment.
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]
18.92.4.2.29.1. Merge strategy#
No merge is required, all peer-push-debit payments are independent from each other.
18.92.4.2.30. Abort peer-push-debit#
User aborts an outgoing push payment.
interface PeerPushDebitAbortInc {
type: "peer-push-debit-abort";
pursePub: EddsaPublicKey;
abortReason?: TalerErrorDetail;
}
Primary key:
[pursePub]Deletion groups:
[peer-push-debit]
18.92.4.2.30.1. Merge strategy#
Store all abortReason in the database.
18.92.4.2.31. Peer-push-debit done#
An outgoing push payment initiated by the user completes successfully.
interface PeerPushDebitDoneInc {
type: "peer-push-debit-done";
pursePub: EddsaPublicKey;
}
Primary key:
[pursePub]Deletion groups:
[peer-push-debit]
18.92.4.2.31.1. Merge strategy#
No merge is required, a peer-push-debit payment can only succeed once.
18.92.4.2.32. Peer-push-debit fail#
An outgoing push payment initiated by the user fails.
interface PeerPushDebitFailInc {
type: "peer-push-debit-fail";
pursePub: EddsaPublicKey;
failReason: TalerErrorDetail;
}
Primary key:
[pursePub]Deletion groups:
[peer-push-debit]
18.92.4.2.32.1. Merge strategy#
Store all failReason in the database.
18.92.4.2.33. Start peer-pull-debit#
User confirms a payment request from another wallet.
interface PeerPullDebitDoneInc {
type: "peer-pull-debit-start";
peerPullDebitId: string;
pursePub: EddsaPublicKey;
exchangeBaseUrl: string;
amount: AmountString;
contractTermsHash: HashCode; // blob
timestampCreated: TalerPreciseTimestamp;
contractPriv: EddsaPrivateKey;
totalCostEstimated: AmountString;
}
Primary key:
[peerPullDebitId]Deletion groups:
[peer-pull-debit]
18.92.4.2.33.1. 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.
18.92.4.2.34. Abort peer-pull-debit#
User aborts a payment to another wallet.
interface PeerPullDebitAbortInc {
type: "peer-pull-debit-abort";
peerPullDebitId: string;
abortReason?: TalerErrorDetail;
}
Primary key:
[peerPullDebitId]Deletion groups:
[peer-pull-debit]
18.92.4.2.34.1. Merge strategy#
Store all abortReason in the database.
18.92.4.2.35. Peer-pull-debit done#
A payment to another wallet completes successfully.
interface PeerPullDebitDoneInc {
type: "peer-pull-debit-done";
peerPullDebitId: string;
}
Primary key:
[peerPullDebitId]Deletion groups:
[peer-pull-debit]
18.92.4.2.35.1. Merge strategy#
No merge is required, a peer-pull-debit payment can only succeed once.
18.92.4.2.36. Peer-pull-debit fail#
A payment to another wallet fails.
interface PeerPullDebitFailInc {
type: "peer-pull-debit-fail";
peerPullDebitId: string;
failReason: TalerErrorDetail;
}
Primary key:
[peerPullDebitId]Deletion groups:
[peer-pull-debit]
18.92.4.2.36.1. Merge strategy#
Store all failReason in the database.
18.92.4.2.37. Start peer-pull-credit#
User requests money to another wallet.
interface PeerPullCreditStartInc {
type: "peer-pull-credit-start";
exchangeBaseUrl: string;
amount: AmountString;
estimatedAmountEffective: AmountString;
pursePub: EddsaPublicKey;
pursePriv: EddsaPrivateKey;
contractTermsHash: HashCode; // blob
mergePub: EddsaPublicKey;
mergePriv: EddsaPrivateKey;
contractPub: EddsaPublicKey;
contractPriv: EddsaPrivateKey;
contractEncNonce: string;
mergeTimestamp: TalerPreciseTimestamp;
mergeReserveRowId: number;
withdrawalGroupId?: string;
}
Primary key:
[pursePub]Deletion groups:
[peer-pull-credit]
18.92.4.2.37.1. Merge strategy#
No merge is required, all peer-pull-credit payments are independent from each other.
18.92.4.2.38. Abort peer-pull-credit#
User aborts request to another wallet.
interface PeerPullCreditAbortInc {
type: "peer-pull-credit-abort";
pursePub: EddsaPublicKey;
abortReason?: TalerErrorInfo;
}
Primary key:
[pursePub]Deletion groups:
[peer-pull-credit]
18.92.4.2.38.1. Merge strategy#
Store all failReason in the database.
18.92.4.2.39. Peer-pull-credit done#
A request to another wallet completes successfully (i.e. money is received).
interface PeerPullCreditDoneInc {
type: "peer-pull-credit-done";
pursePub: EddsaPublicKey;
}
Primary key:
[pursePub]Deletion groups:
[peer-pull-credit]
18.92.4.2.39.1. Merge strategy#
No merge is required, a peer-pull-credit payment can only succeed once.
18.92.4.2.40. Peer-pull-credit fail#
A request to another wallet fails.
interface PeerPullCreditFailInc {
type: "peer-pull-credit-fail";
pursePub: EddsaPublicKey;
failReason: TalerErrorInfo;
}
Primary key:
[pursePub]Deletion groups:
[peer-pull-credit]
18.92.4.2.40.1. Merge strategy#
Store all failReason in the database.
18.92.4.3. 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.
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.
18.92.4.3.1. Deletion groups#
A resource within its deletion group is identified by its primary key. When
the resource in question is deleted, all references to this resource within
the resource group must also be deleted from the blocks listed in the
originBlocks field of its database record.
For example, when deleting a denomination, all the coin insertions of that
denomination must also be deleted from the backup, since they are in the
denominations deletion group and thus contain a reference to a
denomination. In turn, all the sign and spend operations of the deleted coins
must also be deleted, since they are in the coins deletion group and thus
contain a reference to a coin.
18.92.5. Definition of done#
[x] Design backup schema.
[ ] Design incremental sync.
[ ] Design backup/restore schedules.
[ ] Design wallet-core API.
[ ] Wallet-core implementation.
[ ] Design sync API (+ auth).
[ ] Server-side implementation.
[ ] UI/UX for backup and sync.
18.92.6. Alternatives#
18.92.6.1. Synchronization data structures#
In order to perform incremental restores (i.e. synchronization) and converge towards the global state (a.k.a. reconciliation), wallets need to keep track (in real time) of all the changes in the backup that occurred after the last incremental restore, resolve any resulting conflicts, and apply the changes to the local database, all while preserving the requirements of incrementality and plausible deniability.
So far, two strategies to achieve this have been discussed:
Invertible bloom filter.
Event-driven message queue.
18.92.6.1.1. Invertible bloom filter#
In this approach, a invertible bloom filter of dynamic size is calculated by the wallet and server across all known blocks, and used by the wallets to compare their local contents with the ones in the server and only fetch the inserted and updated blocks, deleting the ones missing from the server.
Wallets would use additional information stored in the server, such as total number of blocks, to decide based on the number of the number of differences with the server up to a specified threshold, whether to perform an incremental backup using the bloom filter or simply perform a full backup.
In order to reduce the rate of false positives, the bloom filter would be doubled in size and recalculated as the total number of blocks increases. In the rare event of a false positive, both the wallets and the server would recalculate the bloom filter by adding a special prefix to the blocks before hashing, rate-limited by the theoretical probability of false positives to prevent denial-of-service attacks.
Each bucket in the bloom filter (format below) would be 32 bits in size (for optimal byte alignment) and have the following structure:
+-----------------------+
| Bloom filter (10 bit) |
+-----------------------+
| Counter (4 bit) |
+-----------------------+
| Hash (12-16 bit) |
+-----------------------+
| Checksum (4-8 bit) |
+-----------------------+
18.92.6.1.2. 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.
18.92.7. Discussion / Q&A#
How to preserve plausible deniability in case of a dishonest sync server that retains deleted blocks and old versions of updated blocks?
One option would be to derive a key for each block based on its contents, and delete the keys of deleted blocks from all synced wallets, but the problem with this approach is the number of keys that would need to be stored and backed up.
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.