092-incremental-backup-sync.rst (38898B)
1 =========================================== 2 DD 92: Incremental Wallet Backup and Sync 3 =========================================== 4 5 Summary 6 ======= 7 8 This design document describes an incremental, CRDT-based, encrypted wallet 9 backup and sync protocol that addresses the limitations of previous solutions. 10 11 Motivation 12 ========== 13 14 An encrypted backup and sync protocol for wallets was the subject of three 15 design documents (`DD05`_, `DD09`_ and `DD19`_), in which considerations for 16 different aspects of backup and sync, as well as limitations of the proposed 17 designs, were discussed and documented, ultimately resulting in a 18 proof-of-concept server and wallet implementation. 19 20 .. _DD05: https://docs.taler.net/design-documents/005-wallet-backup-sync.html 21 .. _DD09: https://docs.taler.net/design-documents/009-backup.html 22 .. _DD19: https://docs.taler.net/design-documents/019-wallet-backup-merge.html 23 24 In the original design, an object containing a set of data entities managed by 25 the wallet is serialized, gzip-compressed, kilobyte-padded and encrypted using 26 libsodium's `secretbox`_ function using a symmetric key derived from the 27 wallet's root key and a salt. 28 29 .. _secretbox: https://libsodium.gitbook.io/doc/secret-key_cryptography/secretbox 30 31 The resulting block is then uploaded to a sync server configured in the 32 wallet, where it can be later recovered by another wallet and decrypted. It is 33 at this point where conflicts with the existing database are resolved on a 34 last-write-wins CRDT fashion, favoring deletion in concurrent, conflicting 35 insert/delete operations. 36 37 Since the data entities contained in the backup represent the state of the 38 entire database at a given timestamp, the backup and restore operations 39 described are not incremental and therefore not practical for synchronization 40 between multiple devices, as the database can grow in size indefinitely, 41 slowing down backup and restore operations over time. 42 43 The revised solution proposed in this design document aims to address the 44 limitations of the previous design by introducing an incremental, CRDT-based, 45 end-to-end-encrypted wallet backup and sync protocol that is robust, 46 efficient, reliable, and suitable for use between multiple devices. 47 48 Requirements 49 ============ 50 51 * **Confidenciality/E2EE:** No information about the contents of the wallets 52 should be accessible or derivable by any third-party who lacks control over 53 the wallet, including the backup service. 54 * **Incrementality:** The solution should minimize network usage and bandwidth 55 by incrementally uploading and fetching updates to the global state when 56 possible, limiting the situations where a full backup or restore is 57 required. 58 * **Plausible deniability:** The solution should ensure that no information 59 can be decrypted or retrieved from the backup after its deletion, including 60 the evidence that such information was deleted. 61 62 Proposed solution 63 ================= 64 65 Backup and synchronization service 66 ---------------------------------- 67 68 Insertions and updates to objects in the wallet database are collected in a 69 temporary buffer. Certain events in schedules in the wallet will trigger the 70 incremental backup process, where this buffer will be serialized, encrypted 71 into a kilobyte-padded block, assigned a random UUID, and finally uploaded to 72 the backup service, along with the UUIDs of the previous and next block (when 73 applicable), and the hashes of all the large binary objects (blob) that are 74 referenced in the batch, which are expected to be encrypted and uploaded 75 beforehand to a separate hash-indexed object store. 76 77 .. graphviz:: 78 79 digraph G { 80 subgraph block { 81 { 82 rank = same 83 "Block 0" [shape=box] 84 "Block 1" [shape=box] 85 "Block 2" [shape=box] 86 } 87 88 "Block 0" -> "Block 1" 89 "Block 1" -> "Block 0" 90 "Block 1" -> "Block 2" 91 "Block 2" -> "Block 1" 92 93 { 94 rank = same 95 first [shape=plaintext] 96 last [shape=plaintext] 97 } 98 99 first -> "Block 0" 100 last -> "Block 2" 101 } 102 103 node [shape=record] 104 hash [label="{<f0> 197d605 | <f1> 409f945 | <f2> 8103756} | {<g0> 1 | <g1> 0 | <g2> 2} | {<h0> \<blob\> | <h1> \<blob\> | <h2> \<blob\>}"] 105 106 edge [style=dotted] 107 "Block 0" -> hash:f0 [constraint=false] 108 "Block 1" -> hash:f2 [constraint=false] 109 "Block 2" -> hash:f2 [constraint=false] 110 } 111 112 Double-linked list block store 113 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 114 115 The sync server will maintain a double-linked list in its database, as well as 116 references to the global first and last block (useful for full restores), and 117 is trusted to update the list. Via INSERT, DELETE and REPLACE operations, 118 wallets can upload blocks and manipulate the linked list in accordance with 119 their internal CRDT logic. 120 121 The sync server itself makes no decisions based on the content of the blocks, 122 since it can only see the blocks in their encrypted form. Wallets must 123 therefore maintain a local, unencrypted version of the block store by fetching 124 missing blocks from the server and assembling them in the correct order. 125 126 Furthermore, wallets are responsible of ensuring that all deletion operations 127 provide plausible deniability by retroactively redacting the deleted objects 128 from all the blocks where they appear or are referenced, and uploading the 129 changes to the sync server, which is in turn expected to not retain any 130 deleted blocks or previous versions of updated blocks. 131 132 During the synchronization process, wallets can either download the entirety 133 of the linked list (full sync), or fetch only the missing and updated blocks 134 by comparing their contents with the ones in the sync server by means of a 135 reconciliation mechanism that will be discussed in further sections. 136 137 Block format 138 ++++++++++++ 139 140 Each block will consist of a 2-byte version number, a random 32-byte nonce, 141 and a gzip-compressed JSON object with its length. The block will be padded up 142 to the next whole kilobyte for privacy reasons. 143 144 Encryption will be performed on the block using symmetric authenticated 145 encryption via libsodium's `secretbox`_ function, with a 32-bit key derived 146 from the wallet's backup encryption key and the hash of the entire plaintext 147 block, which in the final implementation should be shareable between any 148 wallets that the user wishes to add to the synchronization group. 149 150 .. code-block:: text 151 152 +----------------------------+ 153 | version number (2 byte) | 154 +----------------------------+ 155 | nonce (32 byte) | 156 +----------------------------+ 157 | JSON length n (4 byte) | 158 +----------------------------+ 159 | gzipped JSON (n byte) | 160 +----------------------------+ 161 | padding (to next full KB) | 162 +----------------------------+ 163 164 .. TODO: 165 Block store API 166 +++++++++++++++ 167 168 .. http:get:: /backups/${BACKUP_ID} 169 170 Get backup information. 171 172 **Response** 173 174 .. code-block:: typescript 175 176 interface GetBackupResponse { 177 /** 178 * Total number of blocks in the backup. 179 */ 180 total_num_blocks: number; 181 182 /** 183 * First block in the backup (epoch). 184 */ 185 first_block_nonce: string; 186 187 /** 188 * Current last block in the backup. 189 */ 190 last_block_nonce: string; 191 } 192 193 .. http:post:: /backups/${BACKUP_ID}/block/${NONCE} 194 195 Upload an encrypted and binary encoded block. 196 197 **Request** 198 199 :query prev: Optional argument providing the nonce of the previous block in 200 the linked list. Shall not be provided if there is no previous block. 201 202 :query next: Optional argument providing the nonce of the next block in the 203 linked list. Shall not be provided if there is no previous block. 204 205 :query blob: Optional argument providing the hash of a referenced blob. 206 Can be repeated once for every referenced blob. 207 208 .. http:get:: /backups/${BACKUP_ID}/block 209 210 Get all blocks from a backup or specific blocks. 211 212 **Request** 213 214 :query nonce: Optional argument providing the nonce of the block to fetch. 215 Can be repeated once for every block to fetch. 216 217 .. http:put:: /backups/${BACKUP_ID}/block/${NONCE} 218 219 Replace an existing block with a new one in-place. 220 221 **Request** 222 223 :query old: Nonce of the old block to replace. 224 225 :query new: Nonce of the new block to insert. 226 227 :query blob: Optional argument providing the hash of a referenced blob. 228 Can be repeated once for every referenced blob. 229 230 .. http:delete:: /backups/${BACKUP_ID}/block/${NONCE} 231 232 Delete an existing block from the linked list. 233 234 Hash-indexed object store 235 ~~~~~~~~~~~~~~~~~~~~~~~~~ 236 237 All static large binary objects (blobs) referenced in a new block generated by 238 the wallet are required to be uploaded separately to the sync server in 239 encrypted form before the actual referencing block is uploaded. 240 241 Blobs will be stored in a hash-indexed object store with a reference count of 242 zero, which will increase with every referencing block that is uploaded to the 243 block store. Any blobs with a reference count of zero will be deleted from the 244 server after a preconfigured expiration period. 245 246 In order to prevent wallets from uploading duplicate blobs, the sync server 247 will compare the hash of the encrypted blob provided by the wallet against the 248 object store before allowing the upload to proceed, rejecting it in case the 249 blob already exists. 250 251 Blob format 252 +++++++++++ 253 254 Similar to blocks, each blob will consist of 2-byte version number, the 4-byte 255 data length, the gzipped data, and a padding to the next whole kilobyte. The 256 blob will be encrypted using a key derived from the wallet's backup encryption 257 key and the hash of the unencrypted file. 258 259 The hash used to index the object in the store will be computer from the 260 encrypted blob using SHA-512 and truncated to 32 bytes. 261 262 .. code-block:: text 263 264 +----------------------------+ 265 | version number (2 byte) | 266 +----------------------------+ 267 | data length n (4 byte) | 268 +----------------------------+ 269 | gzipped data (n byte) | 270 +----------------------------+ 271 | padding (to next full KB) | 272 +----------------------------+ 273 274 .. TODO: 275 Object store API 276 ++++++++++++++++ 277 278 .. http:post:: /backups/${BACKUP_ID}/object 279 280 Upload an encrypted and binary encoded blob. 281 282 .. http:get:: /backups/${BACKUP_ID}/object 283 284 Fetch one or more existing blobs. 285 286 **Request** 287 288 :query hash: Hash of a blob to fetch. 289 Should be repeated once for every blob to fetch. 290 291 .. http:delete:: /backups/${BACKUP_ID}/object 292 293 Delete an existing blob. 294 295 **Request** 296 297 :query hash: Hash of a blob to delete. 298 Should be repeated once for every blob to delete. 299 300 .. TODO: synchronization primitive 301 302 Backup schema 303 ------------- 304 305 Local operations on the wallet database are collected into a temporary buffer, 306 called an “increment set”. Each top-level key in this set holds a list of 307 insertion operations (“increments”) for a particular database entity 308 (e.g. exchanges) or event (e.g. payments). 309 310 .. ts:def:: IncrementSet 311 312 interface IncrementSet { 313 addExchangeIncs?: AddExchangeInc[]; 314 setGlobalExchangeTrustIncs?: SetGlobalExchangeTrustInc[]; 315 addBankAccountIncs?: AddBankAccountInc[]; 316 // ... 317 } 318 319 When a backup operation is triggered, this buffer will be processed into a 320 block and emptied. The resulting block will be assigned a random UUID, 321 appended to the local linked-list, and uploaded to the backup service. 322 323 Since the operations in a given wallet may conflict with operations in the 324 backup with matching primary keys, a state-based CRDT “merge” strategy was 325 carefuly devised for every top-level operation type in the block, so that 326 wallets can deterministically agree on a consistent global state. 327 328 Add or update an exchange 329 ~~~~~~~~~~~~~~~~~~~~~~~~~ 330 331 User accepts ToS for a new or existing exchange. 332 333 Exchanges without an accepted ToS are not included in the backup. 334 335 .. ts:def:: AddExchangeInc 336 337 interface AddExchangeInc { 338 type: "add-exchange"; 339 exchangeBaseUrl: string; 340 tosAcceptedEtag: string; 341 tosAcceptedEtagTimestamp: Timestamp; 342 } 343 344 * **Primary key:** ``[exchangeBaseUrl]`` 345 * **Deletion groups:** ``[exchanges]`` 346 347 Merge strategy 348 ++++++++++++++ 349 350 Favor the operation with the largest ``tosAcceptedEtagTimestamp``. If two 351 timestamps are equal, favor the operation with the largest ``tosAcceptedEtag`` 352 in lexicographical order. 353 354 Set exchange to global trust 355 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 356 357 User sets an exchange to global trust. 358 359 .. ts:def:: SetGlobalExchangeTrustInc 360 361 interface SetGlobalExchangeTrustInc { 362 type: "set-global-exchange-trust"; 363 exchangeBaseUrl: string; 364 exchangeMasterPub: EddsaPublicKey; 365 } 366 367 * **Primary key:** ``[exchangeBaseUrl, exchangeMasterPub]`` 368 * **Deletion groups:** ``[global-exchange-trust]`` 369 370 Merge strategy 371 ++++++++++++++ 372 373 No merge is required. 374 375 Add or update a bank account 376 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 377 378 User adds (or updates) a known bank account. 379 380 .. ts:def:: AddBankAccountInc 381 382 interface AddBankAccountInc { 383 type: "add-bank-account"; 384 bankAccountId: string; 385 paytoUri: string; 386 label: string; 387 } 388 389 * **Primary key:** ``[bankAccountId]`` 390 * **Deletion groups:** ``[bank-accounts]`` 391 392 Merge strategy 393 ++++++++++++++ 394 395 Last write wins. 396 397 Set Donau info 398 ~~~~~~~~~~~~~~ 399 400 User sets info for tax-deductible donations. 401 402 .. ts:def:: SetDonauInfoInc 403 404 interface SetDonauInfoInc { 405 type: "set-donau-info"; 406 donauBaseUrl: string; 407 taxPayerId: string; 408 } 409 410 * **Primary key:** ``[info]`` 411 * **Deletion groups:** ``[donau-info]`` 412 413 Merge strategy 414 ++++++++++++++ 415 416 Last write wins. 417 418 Add a denomination 419 ~~~~~~~~~~~~~~~~~~ 420 421 A denomination is stored in the wallet. 422 423 .. ts:def:: AddDenominationInc 424 425 interface AddDenominationInc { 426 type: "add-denomination"; 427 denomPub: DenominationPubKey; 428 value: AmountString; 429 fees: DenomFees; 430 stampStart: TalerProtocolTimestamp; 431 stampExpireWithdraw: TalerProtocolTimestamp; 432 stampExpireLegal: TalerProtocolTimestamp; 433 stampExpireDeposit: TalerProtocolTimestamp; 434 masterSig: EddsaSignature; 435 exchangeBaseUrl: string; 436 exchangeMasterPub: EddsaPublicKey; 437 } 438 439 * **Primary key:** ``[exchangeBaseUrl, denomPub]`` 440 * **Deletion groups:** ``[denominations]`` 441 442 Merge strategy 443 ++++++++++++++ 444 445 No merge is required, a denomination is expected to always remain constant, so 446 later additions of the same denomination can be safely discarded. 447 448 Add a coin 449 ~~~~~~~~~~ 450 451 A coin is generated by the wallet but not yet signed by the exchange. 452 453 .. ts:def:: AddCoinInc 454 455 interface AddCoinInc { 456 type: "add-coin"; 457 coinSource: CoinSource; 458 denominationId: string; 459 ageCommitmentProof?: AgeCommitmentProof; 460 } 461 462 .. ts:def:: CoinSource 463 464 type CoinSource = 465 | WithdrawalCoinSource 466 | RefreshCoinSource; 467 468 .. ts:def:: WithdrawalCoinSource 469 470 interface WithdrawalCoinSource { 471 type: "withdrawal"; 472 withdrawalGroupId: string; 473 coinNumber: number; 474 } 475 476 .. TODO: RefreshCoinSource (backup refresh groups?) 477 478 * **Primary key:** ``[coinSource]`` 479 * **Deletion groups:** ``[coins, denominations, withdrawals]`` 480 481 Merge strategy 482 ++++++++++++++ 483 484 No merge is required, new coins are unique. 485 486 Sign a coin 487 ~~~~~~~~~~~ 488 489 A coin is signed by the exchange. 490 491 .. ts:def:: SignCoinInc 492 493 interface SignCoinInc { 494 type: "sign-coin"; 495 coinSource: CoinSource; 496 denomSig: UnblindedDenominationSignature; 497 } 498 499 * **Primary key:** ``[coinSource]`` 500 * **Deletion groups:** ``[coins, withdrawals]`` 501 502 Merge strategy 503 ++++++++++++++ 504 505 No merge is required, only one signature for a given coin can be issued by the 506 exchange, further attempts to sign it will fail. 507 508 Spend a coin 509 ~~~~~~~~~~~~ 510 511 A signed coin is spent by the user. 512 513 .. ts:def:: SpendCoinInc 514 515 interface SpendCoinInc { 516 type: "spend-coin"; 517 coinSource: CoinSource; 518 } 519 520 * **Primary key:** ``[coinSource]`` 521 * **Deletion groups:** ``[coins, withdrawals]`` 522 523 Merge strategy 524 ++++++++++++++ 525 526 No merge is required, each coin can only be spent once, further attempts at 527 spending the coin will fail. 528 529 Add a token 530 ~~~~~~~~~~~ 531 532 A token is generated by the wallet but not yet signed by the merchant. 533 534 .. ts:def:: AddTokenInc 535 536 interface AddTokenInc { 537 type: "add-token"; 538 secretSeed: string; 539 choiceIndex: number; 540 outputIndex: number; 541 contractTermsHash: HashCode; // blob 542 } 543 544 * **Primary key:** ``[secretSeed, choiceIndex, outputIndex]`` 545 * **Deletion groups:** ``[tokens]`` 546 547 Merge strategy 548 ++++++++++++++ 549 550 No merge is required, new tokens are unique. 551 552 Sign a token 553 ~~~~~~~~~~~~ 554 555 A token is signed by the merchant. 556 557 .. ts:def:: SignTokenInc 558 559 interface SignTokenInc { 560 type: "sign-token"; 561 secretSeed: string; 562 choiceIndex: number; 563 outputIndex: number; 564 contractTermsHash: HashCode; // blob 565 tokenIssueSig: UnblindedDenominationSignature; 566 } 567 568 * **Primary key:** ``[secretSeed, choiceIndex, outputIndex]`` 569 * **Deletion groups:** ``[tokens]`` 570 571 Merge strategy 572 ++++++++++++++ 573 574 No merge is required, only one signature for a given token can be issued by 575 the merchant, further attempts to sign it will fail. 576 577 Spend a token 578 ~~~~~~~~~~~~~ 579 580 A signed token is spent by the user. 581 582 .. ts:def:: SpendTokenInc 583 584 interface SpendTokenInc { 585 type: "spend-token"; 586 secretSeed: string; 587 choiceIndex: number; 588 outputIndex: number; 589 } 590 591 * **Primary key:** ``[secretSeed, choiceIndex, outputIndex]`` 592 * **Deletion groups:** ``[tokens]`` 593 594 Merge strategy 595 ++++++++++++++ 596 597 No merge is required, each token can only be spent once, further attempts at 598 spending the token will fail. 599 600 Start a withdrawal 601 ~~~~~~~~~~~~~~~~~~ 602 603 User initiates a withdrawal. 604 605 .. ts:def:: WithdrawalStartInc 606 607 interface WithdrawalStartInc { 608 type: "withdrawal-start"; 609 withdrawalGroupId: string; 610 secretSeed: string; 611 timestampStart: TalerPreciseTimestamp; 612 restrictAge?: number; 613 instructedAmount: AmountString; 614 } 615 616 .. TODO: store reserves in backup? 617 (in wallet-core DB, exchangeBaseUrl is contained there) 618 619 * **Primary key:** ``[withdrawalGroupId]`` 620 * **Deletion groups:** ``[withdrawals]`` 621 622 Merge strategy 623 ++++++++++++++ 624 625 No merge is required, all withdrawals are independent from each other. 626 627 Abort a withdrawal 628 ~~~~~~~~~~~~~~~~~~ 629 630 User aborts a withdrawal. 631 632 .. ts:def:: WithdrawalAbortInc 633 634 interface WithdrawalAbortInc { 635 type: "withdrawal-abort"; 636 withdrawalGroupId: string; 637 abortReason?: TalerErrorDetail; 638 } 639 640 * **Primary key:** ``[withdrawalGroupId]`` 641 * **Deletion groups:** ``[withdrawals]`` 642 643 Merge strategy 644 ++++++++++++++ 645 646 Store all ``abortReason`` in the database. 647 648 Withdrawal done 649 ~~~~~~~~~~~~~~~ 650 651 A withdrawal started by the user completes successfully. 652 653 .. ts:def:: WithdrawalDoneInc 654 655 interface WithdrawalDoneInc { 656 type: "withdrawal-done"; 657 withdrawalGroupId: string; 658 timestampFinish: TalerPreciseTimestamp; 659 rawWithdrawalAmount: AmountString; 660 effectiveWithdrawalAmount: AmountString; 661 } 662 663 * **Primary key:** ``[withdrawalGroupId]`` 664 * **Deletion groups:** ``[withdrawals]`` 665 666 Merge strategy 667 ++++++++++++++ 668 669 No merge is required, a withdrawal can only succeed once. 670 671 Withdrawal failed 672 ~~~~~~~~~~~~~~~~~ 673 674 A withdrawal started by the user fails. 675 676 .. ts:def:: WithdrawalFailInc 677 678 interface WithdrawalFailInc { 679 type: "withdrawal-fail"; 680 withdrawalGroupId: string; 681 failReason: TalerErrorDetail; 682 } 683 684 * **Primary key:** ``[withdrawalGroupId]`` 685 * **Deletion groups:** ``[withdrawals]`` 686 687 Merge strategy 688 ++++++++++++++ 689 690 Store all ``failReason`` in the database. 691 692 .. TODO: withdrawal (soft) deletion as increment? 693 (can't be easily deleted because of coin references) 694 695 Start a deposit 696 ~~~~~~~~~~~~~~~ 697 698 .. ts:def:: DepositStartInc 699 700 interface DepositStartInc { 701 type: "deposit-start"; 702 depositGroupId: string; 703 currency: string; 704 amount: AmountString; 705 wireTransferDeadline: TalerProtocolTimestamp; 706 merchantPub: EddsaPublicKey; 707 merchantPriv: EddsaPrivateKey; 708 noncePub: EddsaPublicKey; 709 noncePriv: EddsaPrivateKey; 710 wire: {payto_uri: string, salt: string}; 711 contractTermsHash: HashCode; // blob 712 totalPayCost: AmountString; 713 timestampCreated: TalerPreciseTimestamp; 714 infoPerExchange: {[exchangeBaseUrl: string]: DepositInfoPerExchange}; 715 } 716 717 * **Primary key:** ``[depositGroupId]`` 718 * **Deletion groups:** ``[deposits]`` 719 720 Merge strategy 721 ++++++++++++++ 722 723 No merge is required, all deposits are independent from each other. 724 725 Abort a deposit 726 ~~~~~~~~~~~~~~~ 727 728 User aborts a deposit. 729 730 .. ts:def:: DepositAbortInc 731 732 interface DepositAbortInc { 733 type: "deposit-abort"; 734 depositGroupId: string; 735 abortReason?: TalerErrorDetail; 736 } 737 738 * **Primary key:** ``[depositGroupId]`` 739 * **Deletion groups:** ``[deposits]`` 740 741 Merge strategy 742 ++++++++++++++ 743 744 Store all ``abortReason`` in the database. 745 746 Deposit done 747 ~~~~~~~~~~~~ 748 749 A deposit started by the user completes successfully. 750 751 .. ts:def:: DepositDoneInc 752 753 interface DepositDoneInc { 754 type: "deposit-done"; 755 depositGroupId: string; 756 timestampFinished: TalerPreciseTimestamp; 757 } 758 759 * **Primary key:** ``[depositGroupId]`` 760 * **Deletion groups:** ``[deposits]`` 761 762 Merge strategy 763 ++++++++++++++ 764 765 No merge required, a deposit can only succeed once. 766 767 Deposit fail 768 ~~~~~~~~~~~~ 769 770 A deposit started by the user fails. 771 772 .. ts:def:: DepositFailInc 773 774 interface DepositFailInc { 775 type: "deposit-fail"; 776 depositGroupId: string; 777 failReason: TalerErrorDetail; 778 } 779 780 * **Primary key:** ``[depositGroupId]`` 781 * **Deletion groups:** ``[deposits]`` 782 783 Merge strategy 784 ++++++++++++++ 785 786 Store all ``failReason`` in the database. 787 788 Start a merchant payment 789 ~~~~~~~~~~~~~~~~~~~~~~~~ 790 791 User initiates a payment to a merchant. 792 793 .. ts:def:: PaymentStartInc 794 795 interface PaymentStartInc { 796 type: "payment-start"; 797 proposalId: string; 798 claimToken?: string; 799 downloadSessionId?: string; 800 repurchaseProposalId?: string; 801 noncePub: EddsaPublicKey; 802 noncePriv: EddsaPrivateKey; 803 secretSeed: string; 804 exchanges?: string[]; 805 contractTermsHash: string; // blob 806 timestamp: TalerPreciseTimestamp; 807 808 // Donau 809 donauOutputIndex?: number; 810 donauBaseUrl?: string; 811 donauAmount?: AmountString; 812 donauTaxIdHash?: string; 813 donauTaxIdSalt?: string; 814 donauTaxId?: string; 815 donauYear?: string; 816 } 817 818 * **Primary key:** ``[proposalId]`` 819 * **Deletion groups:** ``[payments]`` 820 821 Merge strategy 822 ++++++++++++++ 823 824 No merge is required, all payments are independent from each other. 825 826 Confirm a merchant payment 827 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 828 829 User confirms a payment to a merchant. 830 831 .. ts:def:: PaymentConfirmInc 832 833 interface PaymentConfirmInc { 834 type: "payment-confirm"; 835 proposalId: string; 836 choiceIndex?: number; 837 timestampAccept: TalerPreciseTimestamp; 838 } 839 840 * **Primary key:** ``[proposalId]`` 841 * **Deletion groups:** ``[payments]`` 842 843 Merge strategy 844 ++++++++++++++ 845 846 No merge is required, a payment can only succeed once. 847 848 Abort a merchant payment 849 ~~~~~~~~~~~~~~~~~~~~~~~~ 850 851 User aborts a payment to a merchant. 852 853 .. ts:def:: PaymentAbortInc 854 855 interface PaymentAbortInc { 856 type: "payment-abort"; 857 proposalId: string; 858 abortReason?: TalerErrorDetail; 859 } 860 861 * **Primary key:** ``[proposalId]`` 862 * **Deletion groups:** ``[payments]`` 863 864 Merge strategy 865 ++++++++++++++ 866 867 Store all ``abortReason`` in the database. 868 869 Merchant purchase done 870 ~~~~~~~~~~~~~~~~~~~~~~ 871 872 A payment started by the user completes successfully. 873 874 .. ts:def:: PaymentDoneInc 875 876 interface PaymentDoneInc { 877 type: "payment-done"; 878 proposalId: string; 879 } 880 881 * **Primary key:** ``[proposalId]`` 882 * **Deletion groups:** ``[payments]`` 883 884 Merchant purchase fail 885 ~~~~~~~~~~~~~~~~~~~~~~ 886 887 A payment started by the user fails. 888 889 .. ts:def:: PaymentFailInc 890 891 interface PaymentFailInc { 892 type: "payment-fail"; 893 proposalId: string; 894 failReason: TalerErrorDetail; 895 } 896 897 * **Primary key:** ``[proposalId]`` 898 * **Deletion groups:** ``[payments]`` 899 900 Merge strategy 901 ++++++++++++++ 902 903 Store all ``failReason`` in the database. 904 905 Start peer-push-credit 906 ~~~~~~~~~~~~~~~~~~~~~~ 907 908 User receives an incoming push payment. 909 910 .. ts:def:: PeerPushCreditStartInc 911 912 interface PeerPushCreditStartInc { 913 type: "peer-push-credit-start"; 914 peerPushCreditId: string; 915 exchangeBaseUrl: string; 916 pursePub: EddsaPublicKey; 917 mergePriv: EddsaPrivateKey; 918 contractPriv: EddsaPrivateKey; 919 timestamp: TalerPreciseTimestamp; 920 estimatedAmountEffective: AmountString; 921 contractTermsHash: HashCode; // blob 922 currency: string; 923 } 924 925 * **Primary key:** ``[peerPushCreditId]`` 926 * **Deletion groups:** ``[peer-push-credit]`` 927 928 Merge strategy 929 ++++++++++++++ 930 931 Last write wins, since the parameters of a peer-push-credit transaction are 932 expected to always remain constant. However, ``peerPushCreditId`` must be 933 derived from the ``exchangeBaseUrl`` and ``pursePub``. 934 935 Abort peer-push-credit 936 ~~~~~~~~~~~~~~~~~~~~~~ 937 938 User aborts an incoming push payment. 939 940 .. ts:def:: PeerPushCreditAbortInc 941 942 interface PeerPushCreditAbortInc { 943 type: "peer-push-credit-abort"; 944 peerPushCreditId: string; 945 abortReason?: TalerErrorDetail; 946 } 947 948 * **Primary key:** ``[peerPushCreditId]`` 949 * **Deletion groups:** ``[peer-push-credit]`` 950 951 Merge strategy 952 ++++++++++++++ 953 954 Store all ``abortReason`` in the database. 955 956 Peer-push-credit done 957 ~~~~~~~~~~~~~~~~~~~~~ 958 959 An incoming push payment received by the user completes successfully. 960 961 .. ts:def:: PeerPushCreditDoneInc 962 963 interface PeerPushCreditDoneInc { 964 type: "peer-push-credit-done"; 965 peerPushCreditId: string; 966 } 967 968 * **Primary key:** ``[peerPushCreditId]`` 969 * **Deletion groups:** ``[peer-push-credit]`` 970 971 Merge strategy 972 ++++++++++++++ 973 974 No merge is required, a peer-push-credit payment can only succeed once. 975 976 Peer-push-credit fail 977 ~~~~~~~~~~~~~~~~~~~~~ 978 979 An incoming push payment received by the user fails. 980 981 .. ts:def:: PeerPushCreditFailInc 982 983 interface PeerPushCreditFailInc { 984 type: "peer-push-credit-fail"; 985 peerPushCreditId: string; 986 failReason: TalerErrorDetail; 987 } 988 989 * **Primary key:** ``[peerPushCreditId]`` 990 * **Deletion groups:** ``[peer-push-credit]`` 991 992 Merge strategy 993 ++++++++++++++ 994 995 Store all ``failReason`` in the database. 996 997 Start peer-push-debit 998 ~~~~~~~~~~~~~~~~~~~~~ 999 1000 User initiates an outgoing push payment. 1001 1002 .. ts:def:: PeerPushDebitStartInc 1003 1004 interface PeerPushDebitStartInc { 1005 type: "peer-push-debit-start"; 1006 exchangeBaseUrl: string; 1007 instructedAmount: AmountString; 1008 effectiveAmount: AmountString; 1009 contractTermsHash: HashCode; // blob 1010 pursePub: EddsaPublicKey; 1011 pursePriv: EddsaPrivateKey; 1012 mergePub: EddsaPublicKey; 1013 mergePriv: EddsaPrivateKey; 1014 contractPub: EddsaPublicKey; 1015 contractPriv: EddsaPrivateKey; 1016 contractEncNonce: string; 1017 purseExpiration: TalerProtocolTimestamp; 1018 timestampCreated: TalerPreciseTimestamp; 1019 } 1020 1021 * **Primary key:** ``[pursePub]`` 1022 * **Deletion groups:** ``[peer-push-debit]`` 1023 1024 Merge strategy 1025 ++++++++++++++ 1026 1027 No merge is required, all peer-push-debit payments are independent from each 1028 other. 1029 1030 Abort peer-push-debit 1031 ~~~~~~~~~~~~~~~~~~~~~ 1032 1033 User aborts an outgoing push payment. 1034 1035 .. ts:def:: PeerPushDebitAbortInc 1036 1037 interface PeerPushDebitAbortInc { 1038 type: "peer-push-debit-abort"; 1039 pursePub: EddsaPublicKey; 1040 abortReason?: TalerErrorDetail; 1041 } 1042 1043 * **Primary key:** ``[pursePub]`` 1044 * **Deletion groups:** ``[peer-push-debit]`` 1045 1046 Merge strategy 1047 ++++++++++++++ 1048 1049 Store all ``abortReason`` in the database. 1050 1051 Peer-push-debit done 1052 ~~~~~~~~~~~~~~~~~~~~ 1053 1054 An outgoing push payment initiated by the user completes successfully. 1055 1056 .. ts:def:: PeerPushDebitDoneInc 1057 1058 interface PeerPushDebitDoneInc { 1059 type: "peer-push-debit-done"; 1060 pursePub: EddsaPublicKey; 1061 } 1062 1063 * **Primary key:** ``[pursePub]`` 1064 * **Deletion groups:** ``[peer-push-debit]`` 1065 1066 Merge strategy 1067 ++++++++++++++ 1068 1069 No merge is required, a peer-push-debit payment can only succeed once. 1070 1071 Peer-push-debit fail 1072 ~~~~~~~~~~~~~~~~~~~~ 1073 1074 An outgoing push payment initiated by the user fails. 1075 1076 .. ts:def:: PeerPushDebitFailInc 1077 1078 interface PeerPushDebitFailInc { 1079 type: "peer-push-debit-fail"; 1080 pursePub: EddsaPublicKey; 1081 failReason: TalerErrorDetail; 1082 } 1083 1084 * **Primary key:** ``[pursePub]`` 1085 * **Deletion groups:** ``[peer-push-debit]`` 1086 1087 Merge strategy 1088 ++++++++++++++ 1089 1090 Store all ``failReason`` in the database. 1091 1092 Start peer-pull-debit 1093 ~~~~~~~~~~~~~~~~~~~~~ 1094 1095 User confirms a payment request from another wallet. 1096 1097 .. ts:def:: PeerPullDebitDoneInc 1098 1099 interface PeerPullDebitDoneInc { 1100 type: "peer-pull-debit-start"; 1101 peerPullDebitId: string; 1102 pursePub: EddsaPublicKey; 1103 exchangeBaseUrl: string; 1104 amount: AmountString; 1105 contractTermsHash: HashCode; // blob 1106 timestampCreated: TalerPreciseTimestamp; 1107 contractPriv: EddsaPrivateKey; 1108 totalCostEstimated: AmountString; 1109 } 1110 1111 * **Primary key:** ``[peerPullDebitId]`` 1112 * **Deletion groups:** ``[peer-pull-debit]`` 1113 1114 Merge strategy 1115 ++++++++++++++ 1116 1117 Last write wins, since the parameters of a peer-pull-debit transaction are 1118 expected to always remain constant. However, ``peerPullDebitId`` must be 1119 derived from the ``exchangeBaseUrl`` and ``pursePub``. 1120 1121 Abort peer-pull-debit 1122 ~~~~~~~~~~~~~~~~~~~~~ 1123 1124 User aborts a payment to another wallet. 1125 1126 .. ts:def:: PeerPullDebitAbortInc 1127 1128 interface PeerPullDebitAbortInc { 1129 type: "peer-pull-debit-abort"; 1130 peerPullDebitId: string; 1131 abortReason?: TalerErrorDetail; 1132 } 1133 1134 * **Primary key:** ``[peerPullDebitId]`` 1135 * **Deletion groups:** ``[peer-pull-debit]`` 1136 1137 Merge strategy 1138 ++++++++++++++ 1139 1140 Store all ``abortReason`` in the database. 1141 1142 Peer-pull-debit done 1143 ~~~~~~~~~~~~~~~~~~~~ 1144 1145 A payment to another wallet completes successfully. 1146 1147 .. ts:def:: PeerPullDebitDoneInc 1148 1149 interface PeerPullDebitDoneInc { 1150 type: "peer-pull-debit-done"; 1151 peerPullDebitId: string; 1152 } 1153 1154 * **Primary key:** ``[peerPullDebitId]`` 1155 * **Deletion groups:** ``[peer-pull-debit]`` 1156 1157 Merge strategy 1158 ++++++++++++++ 1159 1160 No merge is required, a peer-pull-debit payment can only succeed once. 1161 1162 Peer-pull-debit fail 1163 ~~~~~~~~~~~~~~~~~~~~ 1164 1165 A payment to another wallet fails. 1166 1167 .. ts:def:: PeerPullDebitFailInc 1168 1169 interface PeerPullDebitFailInc { 1170 type: "peer-pull-debit-fail"; 1171 peerPullDebitId: string; 1172 failReason: TalerErrorDetail; 1173 } 1174 1175 * **Primary key:** ``[peerPullDebitId]`` 1176 * **Deletion groups:** ``[peer-pull-debit]`` 1177 1178 Merge strategy 1179 ++++++++++++++ 1180 1181 Store all ``failReason`` in the database. 1182 1183 Start peer-pull-credit 1184 ~~~~~~~~~~~~~~~~~~~~~~ 1185 1186 User requests money to another wallet. 1187 1188 .. ts:def:: PeerPullCreditStartInc 1189 1190 interface PeerPullCreditStartInc { 1191 type: "peer-pull-credit-start"; 1192 exchangeBaseUrl: string; 1193 amount: AmountString; 1194 estimatedAmountEffective: AmountString; 1195 pursePub: EddsaPublicKey; 1196 pursePriv: EddsaPrivateKey; 1197 contractTermsHash: HashCode; // blob 1198 mergePub: EddsaPublicKey; 1199 mergePriv: EddsaPrivateKey; 1200 contractPub: EddsaPublicKey; 1201 contractPriv: EddsaPrivateKey; 1202 contractEncNonce: string; 1203 mergeTimestamp: TalerPreciseTimestamp; 1204 mergeReserveRowId: number; 1205 withdrawalGroupId?: string; 1206 } 1207 1208 * **Primary key:** ``[pursePub]`` 1209 * **Deletion groups:** ``[peer-pull-credit]`` 1210 1211 Merge strategy 1212 ++++++++++++++ 1213 1214 No merge is required, all peer-pull-credit payments are independent from each 1215 other. 1216 1217 Abort peer-pull-credit 1218 ~~~~~~~~~~~~~~~~~~~~~~ 1219 1220 User aborts request to another wallet. 1221 1222 .. ts:def:: PeerPullCreditAbortInc 1223 1224 interface PeerPullCreditAbortInc { 1225 type: "peer-pull-credit-abort"; 1226 pursePub: EddsaPublicKey; 1227 abortReason?: TalerErrorInfo; 1228 } 1229 1230 * **Primary key:** ``[pursePub]`` 1231 * **Deletion groups:** ``[peer-pull-credit]`` 1232 1233 Merge strategy 1234 ++++++++++++++ 1235 1236 Store all ``failReason`` in the database. 1237 1238 Peer-pull-credit done 1239 ~~~~~~~~~~~~~~~~~~~~~ 1240 1241 A request to another wallet completes successfully (i.e. money is received). 1242 1243 .. ts:def:: PeerPullCreditDoneInc 1244 1245 interface PeerPullCreditDoneInc { 1246 type: "peer-pull-credit-done"; 1247 pursePub: EddsaPublicKey; 1248 } 1249 1250 * **Primary key:** ``[pursePub]`` 1251 * **Deletion groups:** ``[peer-pull-credit]`` 1252 1253 Merge strategy 1254 ++++++++++++++ 1255 1256 No merge is required, a peer-pull-credit payment can only succeed once. 1257 1258 Peer-pull-credit fail 1259 ~~~~~~~~~~~~~~~~~~~~~ 1260 1261 A request to another wallet fails. 1262 1263 .. ts:def:: PeerPullCreditFailInc 1264 1265 interface PeerPullCreditFailInc { 1266 type: "peer-pull-credit-fail"; 1267 pursePub: EddsaPublicKey; 1268 failReason: TalerErrorInfo; 1269 } 1270 1271 * **Primary key:** ``[pursePub]`` 1272 * **Deletion groups:** ``[peer-pull-credit]`` 1273 1274 Merge strategy 1275 ++++++++++++++ 1276 1277 Store all ``failReason`` in the database. 1278 1279 Item deletion 1280 ------------- 1281 1282 Due to privacy considerations within our use case, rather than using classical 1283 CRDT-style tombstones to encode deletion operations into blocks, a novel 1284 approach was conceived, whereby each item (e.g. an exchange) in the local 1285 wallet database to be included in the backup keeps a list of UUIDs of the 1286 "origin" blocks that have inserted or updated it. 1287 1288 .. code-block:: typescript 1289 1290 originBlocks: Set<BlockUuid>; 1291 1292 Using this approach, a deletion of an item would simply consist of locating 1293 the origin blocks referenced in its UUID list, and deleting the corresponding 1294 insertion/update operations from all of them. 1295 1296 In order to prevent wallets from mistakenly reinserting an item into the 1297 backup that was previously deleted by another wallet, an item is deemed 1298 deleted iff it no longer appears in any of its origin blocks, allowing it to 1299 be safely removed from the local database as well. 1300 1301 Deletion groups 1302 ~~~~~~~~~~~~~~~ 1303 1304 A resource within its deletion group is identified by its primary key. When 1305 the resource in question is deleted, all references to this resource within 1306 the resource group must also be deleted from the blocks listed in the 1307 ``originBlocks`` field of its database record. 1308 1309 For example, when deleting a denomination, all the coin insertions of that 1310 denomination must also be deleted from the backup, since they are in the 1311 ``denominations`` deletion group and thus contain a reference to a 1312 denomination. In turn, all the sign and spend operations of the deleted coins 1313 must also be deleted, since they are in the ``coins`` deletion group and thus 1314 contain a reference to a coin. 1315 1316 .. TODO: 1317 Backup process 1318 -------------- 1319 1320 .. TODO: 1321 Backup schedule 1322 --------------- 1323 1324 .. TODO: 1325 Restore process 1326 --------------- 1327 1328 .. TODO: 1329 Restore schedule 1330 ---------------- 1331 1332 Definition of done 1333 ================== 1334 1335 * [x] Design backup schema. 1336 * [ ] Design incremental sync. 1337 * [ ] Design backup/restore schedules. 1338 * [ ] Design wallet-core API. 1339 * [ ] Wallet-core implementation. 1340 * [ ] Design sync API (+ auth). 1341 * [ ] Server-side implementation. 1342 * [ ] UI/UX for backup and sync. 1343 1344 Alternatives 1345 ============ 1346 1347 Synchronization data structures 1348 ------------------------------- 1349 1350 In order to perform incremental restores (i.e. synchronization) and converge 1351 towards the global state (a.k.a. reconciliation), wallets need to keep track 1352 (in real time) of all the changes in the backup that occurred after the last 1353 incremental restore, resolve any resulting conflicts, and apply the changes to 1354 the local database, all while preserving the requirements of incrementality 1355 and plausible deniability. 1356 1357 So far, two strategies to achieve this have been discussed: 1358 1359 * Invertible bloom filter. 1360 * Event-driven message queue. 1361 1362 Invertible bloom filter 1363 ~~~~~~~~~~~~~~~~~~~~~~~ 1364 1365 In this approach, a invertible bloom filter of dynamic size is calculated by 1366 the wallet and server across all known blocks, and used by the wallets to 1367 compare their local contents with the ones in the server and only fetch the 1368 inserted and updated blocks, deleting the ones missing from the server. 1369 1370 Wallets would use additional information stored in the server, such as total 1371 number of blocks, to decide based on the number of the number of differences 1372 with the server up to a specified threshold, whether to perform an incremental 1373 backup using the bloom filter or simply perform a full backup. 1374 1375 In order to reduce the rate of false positives, the bloom filter would be 1376 doubled in size and recalculated as the total number of blocks increases. In 1377 the rare event of a false positive, both the wallets and the server would 1378 recalculate the bloom filter by adding a special prefix to the blocks before 1379 hashing, rate-limited by the theoretical probability of false positives to 1380 prevent denial-of-service attacks. 1381 1382 Each bucket in the bloom filter (format below) would be 32 bits in size (for 1383 optimal byte alignment) and have the following structure: 1384 1385 .. code-block:: text 1386 1387 +-----------------------+ 1388 | Bloom filter (10 bit) | 1389 +-----------------------+ 1390 | Counter (4 bit) | 1391 +-----------------------+ 1392 | Hash (12-16 bit) | 1393 +-----------------------+ 1394 | Checksum (4-8 bit) | 1395 +-----------------------+ 1396 1397 Event-driven message queue 1398 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 1399 1400 Another proposed solution is to use a message queue used mainly to stream 1401 blocks operations (INSERT, DELETE, UPDATE) to other wallets in the 1402 synchronization group. 1403 1404 In order to provide "eventual" plausible deniability, events in the message 1405 queue would be permanently deleted as soon as all the active wallets in the 1406 synchronization group have consumed them, meaning that the server would need 1407 to keep track of all the "subscribed" wallets. 1408 1409 Inactive wallets would be automatically "unsubscribed" from the message queue 1410 after a predefined period of time (e.g. 2 weeks), or after being manually 1411 deleted by the user (similarly to e.g. Signal). Upon coming back online or 1412 being added back to the synchronization group, a wallet would need to perform 1413 a full backup. 1414 1415 .. TODO: 1416 Drawbacks 1417 ========= 1418 1419 Discussion / Q&A 1420 ================ 1421 1422 * **How to preserve plausible deniability in case of a dishonest sync server 1423 that retains deleted blocks and old versions of updated blocks?** 1424 1425 * One option would be to derive a key for each block based on its contents, 1426 and delete the keys of deleted blocks from all synced wallets, but the 1427 problem with this approach is the number of keys that would need to be 1428 stored and backed up. 1429 1430 * How to manage (add/rm) linked devices? Do they ever expire? Is there a 1431 *master* device with permissions to manage linked devices? 1432 1433 * How to safely delete a withdrawal operation? Instead of storing the keypair 1434 for each coin, we derive coins from a secret seed and the coin index within 1435 a withdrawal group. Coins in the backup thus contain a reference to the 1436 originating withdrawal operation, which in the event of being deleted will 1437 prevent coins from being restored from backup. 1438 1439 * Should the wallets always keep a full copy of the linked list?