092-incremental-backup-sync.rst (38865B)
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 reservePub: EddsaPublicKey; 612 timestampStart: TalerPreciseTimestamp; 613 restrictAge?: number; 614 instructedAmount: AmountString; 615 } 616 617 .. TODO: store reserves in backup? 618 (in wallet-core DB, exchangeBaseUrl is contained there) 619 620 * **Primary key:** ``[withdrawalGroupId]`` 621 * **Deletion groups:** ``[withdrawals]`` 622 623 Merge strategy 624 ++++++++++++++ 625 626 No merge is required, all withdrawals are independent from each other. 627 628 Abort a withdrawal 629 ~~~~~~~~~~~~~~~~~~ 630 631 User aborts a withdrawal. 632 633 .. ts:def:: WithdrawalAbortInc 634 635 interface WithdrawalAbortInc { 636 type: "withdrawal-abort"; 637 withdrawalGroupId: string; 638 abortReason?: TalerErrorDetail; 639 } 640 641 * **Primary key:** ``[withdrawalGroupId]`` 642 * **Deletion groups:** ``[withdrawals]`` 643 644 Merge strategy 645 ++++++++++++++ 646 647 Store all ``abortReason`` in the database. 648 649 Withdrawal done 650 ~~~~~~~~~~~~~~~ 651 652 A withdrawal started by the user completes successfully. 653 654 .. ts:def:: WithdrawalDoneInc 655 656 interface WithdrawalDoneInc { 657 type: "withdrawal-done"; 658 withdrawalGroupId: string; 659 timestampFinish: TalerPreciseTimestamp; 660 rawWithdrawalAmount: AmountString; 661 effectiveWithdrawalAmount: AmountString; 662 } 663 664 * **Primary key:** ``[withdrawalGroupId]`` 665 * **Deletion groups:** ``[withdrawals]`` 666 667 Merge strategy 668 ++++++++++++++ 669 670 No merge is required, a withdrawal can only succeed once. 671 672 Withdrawal failed 673 ~~~~~~~~~~~~~~~~~ 674 675 A withdrawal started by the user fails. 676 677 .. ts:def:: WithdrawalFailInc 678 679 interface WithdrawalFailInc { 680 type: "withdrawal-fail"; 681 withdrawalGroupId: string; 682 failReason: TalerErrorDetail; 683 } 684 685 * **Primary key:** ``[withdrawalGroupId]`` 686 * **Deletion groups:** ``[withdrawals]`` 687 688 Merge strategy 689 ++++++++++++++ 690 691 Store all ``failReason`` in the database. 692 693 .. TODO: withdrawal (soft) deletion as increment? 694 (can't be easily deleted because of coin references) 695 696 Start a deposit 697 ~~~~~~~~~~~~~~~ 698 699 .. ts:def:: DepositStartInc 700 701 interface DepositStartInc { 702 type: "deposit-start"; 703 depositGroupId: string; 704 currency: string; 705 amount: AmountString; 706 wireTransferDeadline: TalerProtocolTimestamp; 707 merchantPub: EddsaPublicKey; 708 merchantPriv: EddsaPrivateKey; 709 noncePub: EddsaPublicKey; 710 noncePriv: EddsaPrivateKey; 711 wire: {payto_uri: string, salt: string}; 712 contractTermsHash: HashCode; // blob 713 totalPayCost: AmountString; 714 timestampCreated: TalerPreciseTimestamp; 715 infoPerExchange: {[exchangeBaseUrl: string]: DepositInfoPerExchange}; 716 } 717 718 * **Primary key:** ``[depositGroupId]`` 719 * **Deletion groups:** ``[deposits]`` 720 721 Merge strategy 722 ++++++++++++++ 723 724 No merge is required, all deposits are independent from each other. 725 726 Abort a deposit 727 ~~~~~~~~~~~~~~~ 728 729 User aborts a deposit. 730 731 .. ts:def:: DepositAbortInc 732 733 interface DepositAbortInc { 734 type: "deposit-abort"; 735 depositGroupId: string; 736 abortReason?: TalerErrorDetail; 737 } 738 739 * **Primary key:** ``[depositGroupId]`` 740 * **Deletion groups:** ``[deposits]`` 741 742 Merge strategy 743 ++++++++++++++ 744 745 Store all ``abortReason`` in the database. 746 747 Deposit done 748 ~~~~~~~~~~~~ 749 750 A deposit started by the user completes successfully. 751 752 .. ts:def:: DepositDoneInc 753 754 interface DepositDoneInc { 755 type: "deposit-done"; 756 depositGroupId: string; 757 timestampFinished: TalerPreciseTimestamp; 758 } 759 760 * **Primary key:** ``[depositGroupId]`` 761 * **Deletion groups:** ``[deposits]`` 762 763 Merge strategy 764 ++++++++++++++ 765 766 No merge required, a deposit can only succeed once. 767 768 Deposit fail 769 ~~~~~~~~~~~~ 770 771 A deposit started by the user fails. 772 773 .. ts:def:: DepositFailInc 774 775 interface DepositFailInc { 776 type: "deposit-fail"; 777 depositGroupId: string; 778 failReason: TalerErrorDetail; 779 } 780 781 * **Primary key:** ``[depositGroupId]`` 782 * **Deletion groups:** ``[deposits]`` 783 784 Merge strategy 785 ++++++++++++++ 786 787 Store all ``failReason`` in the database. 788 789 Start a merchant payment 790 ~~~~~~~~~~~~~~~~~~~~~~~~ 791 792 User initiates a payment to a merchant. 793 794 .. ts:def:: PaymentStartInc 795 796 interface PaymentStartInc { 797 type: "payment-start"; 798 proposalId: string; 799 claimToken?: string; 800 downloadSessionId?: string; 801 repurchaseProposalId?: string; 802 noncePub: EddsaPublicKey; 803 noncePriv: EddsaPrivateKey; 804 secretSeed: string; 805 exchanges?: string[]; 806 contractTermsHash: string; // blob 807 timestamp: TalerPreciseTimestamp; 808 809 // Donau 810 donauOutputIndex?: number; 811 donauBaseUrl?: string; 812 donauAmount?: AmountString; 813 donauTaxIdHash?: string; 814 donauTaxIdSalt?: string; 815 donauTaxId?: string; 816 donauYear?: string; 817 } 818 819 * **Primary key:** ``[proposalId]`` 820 * **Deletion groups:** ``[payments]`` 821 822 Merge strategy 823 ++++++++++++++ 824 825 No merge is required, all payments are independent from each other. 826 827 Confirm a merchant payment 828 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 829 830 User confirms a payment to a merchant. 831 832 .. ts:def:: PaymentConfirmInc 833 834 interface PaymentConfirmInc { 835 type: "payment-confirm"; 836 proposalId: string; 837 choiceIndex?: number; 838 timestampAccept: TalerPreciseTimestamp; 839 } 840 841 * **Primary key:** ``[proposalId]`` 842 * **Deletion groups:** ``[payments]`` 843 844 Merge strategy 845 ++++++++++++++ 846 847 No merge is required, a payment can only succeed once. 848 849 Abort a merchant payment 850 ~~~~~~~~~~~~~~~~~~~~~~~~ 851 852 User aborts a payment to a merchant. 853 854 .. ts:def:: PaymentAbortInc 855 856 interface PaymentAbortInc { 857 type: "payment-abort"; 858 proposalId: string; 859 abortReason?: TalerErrorDetail; 860 } 861 862 * **Primary key:** ``[proposalId]`` 863 * **Deletion groups:** ``[payments]`` 864 865 Merge strategy 866 ++++++++++++++ 867 868 Store all ``abortReason`` in the database. 869 870 Merchant purchase done 871 ~~~~~~~~~~~~~~~~~~~~~~ 872 873 A payment started by the user completes successfully. 874 875 .. ts:def:: PaymentDoneInc 876 877 interface PaymentDoneInc { 878 type: "payment-done"; 879 proposalId: string; 880 } 881 882 * **Primary key:** ``[proposalId]`` 883 * **Deletion groups:** ``[payments]`` 884 885 Merchant purchase fail 886 ~~~~~~~~~~~~~~~~~~~~~~ 887 888 A payment started by the user fails. 889 890 .. ts:def:: PaymentFailInc 891 892 interface PaymentFailInc { 893 type: "payment-fail"; 894 proposalId: string; 895 failReason: TalerErrorDetail; 896 } 897 898 * **Primary key:** ``[proposalId]`` 899 * **Deletion groups:** ``[payments]`` 900 901 Merge strategy 902 ++++++++++++++ 903 904 Store all ``failReason`` in the database. 905 906 Start peer-push-credit 907 ~~~~~~~~~~~~~~~~~~~~~~ 908 909 User receives an incoming push payment. 910 911 .. ts:def:: PeerPushCreditStartInc 912 913 interface PeerPushCreditStartInc { 914 type: "peer-push-credit-start"; 915 peerPushCreditId: string; 916 exchangeBaseUrl: string; 917 pursePub: EddsaPublicKey; 918 mergePriv: EddsaPrivateKey; 919 contractPriv: EddsaPrivateKey; 920 timestamp: TalerPreciseTimestamp; 921 estimatedAmountEffective: AmountString; 922 contractTermsHash: HashCode; // blob 923 currency: string; 924 } 925 926 * **Primary key:** ``[peerPushCreditId]`` 927 * **Deletion groups:** ``[peer-push-credit]`` 928 929 Merge strategy 930 ++++++++++++++ 931 932 Last write wins, since the parameters of a peer-push-credit transaction are 933 expected to always remain constant. However, ``peerPushCreditId`` must be 934 derived from the ``exchangeBaseUrl`` and ``pursePub``. 935 936 Abort peer-push-credit 937 ~~~~~~~~~~~~~~~~~~~~~~ 938 939 User aborts an incoming push payment. 940 941 .. ts:def:: PeerPushCreditAbortInc 942 943 interface PeerPushCreditAbortInc { 944 type: "peer-push-credit-abort"; 945 peerPushCreditId: string; 946 abortReason?: TalerErrorDetail; 947 } 948 949 * **Primary key:** ``[peerPushCreditId]`` 950 * **Deletion groups:** ``[peer-push-credit]`` 951 952 Merge strategy 953 ++++++++++++++ 954 955 Store all ``abortReason`` in the database. 956 957 Peer-push-credit done 958 ~~~~~~~~~~~~~~~~~~~~~ 959 960 An incoming push payment received by the user completes successfully. 961 962 .. ts:def:: PeerPushCreditDoneInc 963 964 interface PeerPushCreditDoneInc { 965 type: "peer-push-credit-done"; 966 peerPushCreditId: string; 967 } 968 969 * **Primary key:** ``[peerPushCreditId]`` 970 * **Deletion groups:** ``[peer-push-credit]`` 971 972 Merge strategy 973 ++++++++++++++ 974 975 No merge is required, a peer-push-credit payment can only succeed once. 976 977 Peer-push-credit fail 978 ~~~~~~~~~~~~~~~~~~~~~ 979 980 An incoming push payment received by the user fails. 981 982 .. ts:def:: PeerPushCreditFailInc 983 984 interface PeerPushCreditFailInc { 985 type: "peer-push-credit-fail"; 986 peerPushCreditId: string; 987 failReason: TalerErrorDetail; 988 } 989 990 * **Primary key:** ``[peerPushCreditId]`` 991 * **Deletion groups:** ``[peer-push-credit]`` 992 993 Merge strategy 994 ++++++++++++++ 995 996 Store all ``failReason`` in the database. 997 998 Start peer-push-debit 999 ~~~~~~~~~~~~~~~~~~~~~ 1000 1001 User initiates an outgoing push payment. 1002 1003 .. ts:def:: PeerPushDebitStartInc 1004 1005 interface PeerPushDebitStartInc { 1006 type: "peer-push-debit-start"; 1007 exchangeBaseUrl: string; 1008 instructedAmount: AmountString; 1009 effectiveAmount: AmountString; 1010 contractTermsHash: HashCode; // blob 1011 pursePub: EddsaPublicKey; 1012 pursePriv: EddsaPrivateKey; 1013 mergePub: EddsaPublicKey; 1014 mergePriv: EddsaPrivateKey; 1015 contractPub: EddsaPublicKey; 1016 contractPriv: EddsaPrivateKey; 1017 contractEncNonce: string; 1018 purseExpiration: TalerProtocolTimestamp; 1019 timestampCreated: TalerPreciseTimestamp; 1020 } 1021 1022 * **Primary key:** ``[pursePub]`` 1023 * **Deletion groups:** ``[peer-push-debit]`` 1024 1025 Merge strategy 1026 ++++++++++++++ 1027 1028 No merge is required, all peer-push-debit payments are independent from each 1029 other. 1030 1031 Abort peer-push-debit 1032 ~~~~~~~~~~~~~~~~~~~~~ 1033 1034 User aborts an outgoing push payment. 1035 1036 .. ts:def:: PeerPushDebitAbortInc 1037 1038 interface PeerPushDebitAbortInc { 1039 type: "peer-push-debit-abort"; 1040 pursePub: EddsaPublicKey; 1041 abortReason?: TalerErrorDetail; 1042 } 1043 1044 * **Primary key:** ``[pursePub]`` 1045 * **Deletion groups:** ``[peer-push-debit]`` 1046 1047 Merge strategy 1048 ++++++++++++++ 1049 1050 Store all ``abortReason`` in the database. 1051 1052 Peer-push-debit done 1053 ~~~~~~~~~~~~~~~~~~~~ 1054 1055 An outgoing push payment initiated by the user completes successfully. 1056 1057 .. ts:def:: PeerPushDebitDoneInc 1058 1059 interface PeerPushDebitDoneInc { 1060 type: "peer-push-debit-done"; 1061 pursePub: EddsaPublicKey; 1062 } 1063 1064 * **Primary key:** ``[pursePub]`` 1065 * **Deletion groups:** ``[peer-push-debit]`` 1066 1067 Merge strategy 1068 ++++++++++++++ 1069 1070 No merge is required, a peer-push-debit payment can only succeed once. 1071 1072 Peer-push-debit fail 1073 ~~~~~~~~~~~~~~~~~~~~ 1074 1075 An outgoing push payment initiated by the user fails. 1076 1077 .. ts:def:: PeerPushDebitFailInc 1078 1079 interface PeerPushDebitFailInc { 1080 type: "peer-push-debit-fail"; 1081 pursePub: EddsaPublicKey; 1082 failReason: TalerErrorDetail; 1083 } 1084 1085 * **Primary key:** ``[pursePub]`` 1086 * **Deletion groups:** ``[peer-push-debit]`` 1087 1088 Merge strategy 1089 ++++++++++++++ 1090 1091 Store all ``failReason`` in the database. 1092 1093 Start peer-pull-debit 1094 ~~~~~~~~~~~~~~~~~~~~~ 1095 1096 User confirms a payment request from another wallet. 1097 1098 .. ts:def:: PeerPullDebitDoneInc 1099 1100 interface PeerPullDebitDoneInc { 1101 type: "peer-pull-debit-start"; 1102 peerPullDebitId: string; 1103 pursePub: EddsaPublicKey; 1104 exchangeBaseUrl: string; 1105 amount: AmountString; 1106 contractTermsHash: HashCode; // blob 1107 timestampCreated: TalerPreciseTimestamp; 1108 contractPriv: EddsaPrivateKey; 1109 totalCostEstimated: AmountString; 1110 } 1111 1112 * **Primary key:** ``[peerPullDebitId]`` 1113 * **Deletion groups:** ``[peer-pull-debit]`` 1114 1115 Merge strategy 1116 ++++++++++++++ 1117 1118 Last write wins, since the parameters of a peer-pull-debit transaction are 1119 expected to always remain constant. However, ``peerPullDebitId`` must be 1120 derived from the ``exchangeBaseUrl`` and ``pursePub``. 1121 1122 Abort peer-pull-debit 1123 ~~~~~~~~~~~~~~~~~~~~~ 1124 1125 User aborts a payment to another wallet. 1126 1127 .. ts:def:: PeerPullDebitAbortInc 1128 1129 interface PeerPullDebitAbortInc { 1130 type: "peer-pull-debit-abort"; 1131 peerPullDebitId: string; 1132 abortReason?: TalerErrorDetail; 1133 } 1134 1135 * **Primary key:** ``[peerPullDebitId]`` 1136 * **Deletion groups:** ``[peer-pull-debit]`` 1137 1138 Merge strategy 1139 ++++++++++++++ 1140 1141 Store all ``abortReason`` in the database. 1142 1143 Peer-pull-debit done 1144 ~~~~~~~~~~~~~~~~~~~~ 1145 1146 A payment to another wallet completes successfully. 1147 1148 .. ts:def:: PeerPullDebitDoneInc 1149 1150 interface PeerPullDebitDoneInc { 1151 type: "peer-pull-debit-done"; 1152 peerPullDebitId: string; 1153 } 1154 1155 * **Primary key:** ``[peerPullDebitId]`` 1156 * **Deletion groups:** ``[peer-pull-debit]`` 1157 1158 Merge strategy 1159 ++++++++++++++ 1160 1161 No merge is required, a peer-pull-debit payment can only succeed once. 1162 1163 Peer-pull-debit fail 1164 ~~~~~~~~~~~~~~~~~~~~ 1165 1166 A payment to another wallet fails. 1167 1168 .. ts:def:: PeerPullDebitFailInc 1169 1170 interface PeerPullDebitFailInc { 1171 type: "peer-pull-debit-fail"; 1172 peerPullDebitId: string; 1173 failReason: TalerErrorDetail; 1174 } 1175 1176 * **Primary key:** ``[peerPullDebitId]`` 1177 * **Deletion groups:** ``[peer-pull-debit]`` 1178 1179 Merge strategy 1180 ++++++++++++++ 1181 1182 Store all ``failReason`` in the database. 1183 1184 Start peer-pull-credit 1185 ~~~~~~~~~~~~~~~~~~~~~~ 1186 1187 User requests money to another wallet. 1188 1189 .. ts:def:: PeerPullCreditStartInc 1190 1191 interface PeerPullCreditStartInc { 1192 type: "peer-pull-credit-start"; 1193 exchangeBaseUrl: string; 1194 amount: AmountString; 1195 estimatedAmountEffective: AmountString; 1196 pursePub: EddsaPublicKey; 1197 pursePriv: EddsaPrivateKey; 1198 contractTermsHash: HashCode; // blob 1199 mergePub: EddsaPublicKey; 1200 mergePriv: EddsaPrivateKey; 1201 contractPub: EddsaPublicKey; 1202 contractPriv: EddsaPrivateKey; 1203 contractEncNonce: string; 1204 mergeTimestamp: TalerPreciseTimestamp; 1205 mergeReserveRowId: number; 1206 withdrawalGroupId?: string; 1207 } 1208 1209 * **Primary key:** ``[pursePub]`` 1210 * **Deletion groups:** ``[peer-pull-credit]`` 1211 1212 Merge strategy 1213 ++++++++++++++ 1214 1215 No merge is required, all peer-pull-credit payments are independent from each 1216 other. 1217 1218 Abort peer-pull-credit 1219 ~~~~~~~~~~~~~~~~~~~~~~ 1220 1221 User aborts request to another wallet. 1222 1223 .. ts:def:: PeerPullCreditAbortInc 1224 1225 interface PeerPullCreditAbortInc { 1226 type: "peer-pull-credit-abort"; 1227 pursePub: EddsaPublicKey; 1228 abortReason?: TalerErrorInfo; 1229 } 1230 1231 * **Primary key:** ``[pursePub]`` 1232 * **Deletion groups:** ``[peer-pull-credit]`` 1233 1234 Merge strategy 1235 ++++++++++++++ 1236 1237 Store all ``failReason`` in the database. 1238 1239 Peer-pull-credit done 1240 ~~~~~~~~~~~~~~~~~~~~~ 1241 1242 A request to another wallet completes successfully (i.e. money is received). 1243 1244 .. ts:def:: PeerPullCreditDoneInc 1245 1246 interface PeerPullCreditDoneInc { 1247 type: "peer-pull-credit-done"; 1248 pursePub: EddsaPublicKey; 1249 } 1250 1251 * **Primary key:** ``[pursePub]`` 1252 * **Deletion groups:** ``[peer-pull-credit]`` 1253 1254 Merge strategy 1255 ++++++++++++++ 1256 1257 No merge is required, a peer-pull-credit payment can only succeed once. 1258 1259 Peer-pull-credit fail 1260 ~~~~~~~~~~~~~~~~~~~~~ 1261 1262 A request to another wallet fails. 1263 1264 .. ts:def:: PeerPullCreditFailInc 1265 1266 interface PeerPullCreditFailInc { 1267 type: "peer-pull-credit-fail"; 1268 pursePub: EddsaPublicKey; 1269 failReason: TalerErrorInfo; 1270 } 1271 1272 * **Primary key:** ``[pursePub]`` 1273 * **Deletion groups:** ``[peer-pull-credit]`` 1274 1275 Merge strategy 1276 ++++++++++++++ 1277 1278 Store all ``failReason`` in the database. 1279 1280 Item deletion 1281 ------------- 1282 1283 Due to privacy considerations within our use case, rather than using classical 1284 CRDT-style tombstones to encode deletion operations into blocks, a novel 1285 approach was conceived, whereby each item (e.g. an exchange) in the local 1286 wallet database to be included in the backup keeps a list of UUIDs of the 1287 "origin" blocks that have inserted or updated it. 1288 1289 .. code-block:: typescript 1290 1291 originBlocks: Set<BlockUuid>; 1292 1293 Using this approach, a deletion of an item would simply consist of locating 1294 the origin blocks referenced in its UUID list, and deleting the corresponding 1295 insertion/update operations from all of them. 1296 1297 In order to prevent wallets from mistakenly reinserting an item into the 1298 backup that was previously deleted by another wallet, an item is deemed 1299 deleted iff it no longer appears in any of its origin blocks, allowing it to 1300 be safely removed from the local database as well. 1301 1302 Deletion groups 1303 ~~~~~~~~~~~~~~~ 1304 1305 A resource within its deletion group is identified by its primary key. When 1306 the resource in question is deleted, all references to this resource within 1307 the resource group must also be deleted from the blocks listed in the 1308 ``originBlocks`` field of its database record. 1309 1310 For example, when deleting a denomination, all the coin insertions of that 1311 denomination must also be deleted from the backup, since they are in the 1312 ``denominations`` deletion group and thus contain a reference to a 1313 denomination. In turn, all the sign and spend operations of the deleted coins 1314 must also be deleted, since they are in the ``coins`` deletion group and thus 1315 contain a reference to a coin. 1316 1317 .. TODO: 1318 Backup process 1319 -------------- 1320 1321 .. TODO: 1322 Backup schedule 1323 --------------- 1324 1325 .. TODO: 1326 Restore process 1327 --------------- 1328 1329 .. TODO: 1330 Restore schedule 1331 ---------------- 1332 1333 Definition of done 1334 ================== 1335 1336 * [x] Design backup schema. 1337 * [ ] Design incremental sync. 1338 * [ ] Design backup/restore schedules. 1339 * [ ] Design wallet-core API. 1340 * [ ] Wallet-core implementation. 1341 * [ ] Design sync API (+ auth). 1342 * [ ] Server-side implementation. 1343 * [ ] UI/UX for backup and sync. 1344 1345 Alternatives 1346 ============ 1347 1348 Synchronization data structures 1349 ------------------------------- 1350 1351 In order to perform incremental restores (i.e. synchronization) and converge 1352 towards the global state (a.k.a. reconciliation), wallets need to keep track 1353 (in real time) of all the changes in the backup that occurred after the last 1354 incremental restore, resolve any resulting conflicts, and apply the changes to 1355 the local database, all while preserving the requirements of incrementality 1356 and plausible deniability. 1357 1358 So far, two strategies to achieve this have been discussed: 1359 1360 * Invertible bloom filter. 1361 * Event-driven message queue. 1362 1363 Invertible bloom filter 1364 ~~~~~~~~~~~~~~~~~~~~~~~ 1365 1366 In this approach, a invertible bloom filter of dynamic size is calculated by 1367 the wallet and server across all known blocks, and used by the wallets to 1368 compare their local contents with the ones in the server and only fetch the 1369 inserted and updated blocks, deleting the ones missing from the server. 1370 1371 Wallets would use additional information stored in the server, such as total 1372 number of blocks, to decide based on the number of the number of differences 1373 with the server up to a specified threshold, whether to perform an incremental 1374 backup using the bloom filter or simply perform a full backup. 1375 1376 In order to reduce the rate of false positives, the bloom filter would be 1377 doubled in size and recalculated as the total number of blocks increases. In 1378 the rare event of a false positive, both the wallets and the server would 1379 recalculate the bloom filter by adding a special prefix to the blocks before 1380 hashing, rate-limited by the theoretical probability of false positives to 1381 prevent denial-of-service attacks. 1382 1383 Each bucket in the bloom filter (format below) would be 32 bits in size (for 1384 optimal byte alignment) and have the following structure: 1385 1386 .. code-block:: text 1387 1388 +-----------------------+ 1389 | Bloom filter (10 bit) | 1390 +-----------------------+ 1391 | Counter (4 bit) | 1392 +-----------------------+ 1393 | Hash (12-16 bit) | 1394 +-----------------------+ 1395 | Checksum (4-8 bit) | 1396 +-----------------------+ 1397 1398 Event-driven message queue 1399 ~~~~~~~~~~~~~~~~~~~~~~~~~~ 1400 1401 Another proposed solution is to use a message queue used mainly to stream 1402 blocks operations (INSERT, DELETE, UPDATE) to other wallets in the 1403 synchronization group. 1404 1405 In order to provide "eventual" plausible deniability, events in the message 1406 queue would be permanently deleted as soon as all the active wallets in the 1407 synchronization group have consumed them, meaning that the server would need 1408 to keep track of all the "subscribed" wallets. 1409 1410 Inactive wallets would be automatically "unsubscribed" from the message queue 1411 after a predefined period of time (e.g. 2 weeks), or after being manually 1412 deleted by the user (similarly to e.g. Signal). Upon coming back online or 1413 being added back to the synchronization group, a wallet would need to perform 1414 a full backup. 1415 1416 .. TODO: 1417 Drawbacks 1418 ========= 1419 1420 Discussion / Q&A 1421 ================ 1422 1423 * **How to preserve plausible deniability in case of a dishonest sync server 1424 that retains deleted blocks and old versions of updated blocks?** 1425 1426 * One option would be to derive a key for each block based on its contents, 1427 and delete the keys of deleted blocks from all synced wallets, but the 1428 problem with this approach is the number of keys that would need to be 1429 stored and backed up. 1430 1431 * How to manage (add/rm) linked devices? Do they ever expire? Is there a 1432 *master* device with permissions to manage linked devices? 1433 1434 * How to safely delete a withdrawal operation? Instead of storing the keypair 1435 for each coin, we derive coins from a secret seed and the coin index within 1436 a withdrawal group. Coins in the backup thus contain a reference to the 1437 originating withdrawal operation, which in the event of being deleted will 1438 prevent coins from being restored from backup.