commit 97a691ca5c427513abfa7af3b48c9b4f752e4029
parent c04119f0ae3428bed3a76c99622f746419c3e939
Author: Iván Ávalos <avalos@disroot.org>
Date: Thu, 1 Oct 2026 11:35:41 +0200
dd92: update to match latest code (invertible bloom filter)
Diffstat:
1 file changed, 405 insertions(+), 188 deletions(-)
diff --git a/design-documents/092-incremental-backup-sync.rst b/design-documents/092-incremental-backup-sync.rst
@@ -172,13 +172,23 @@ reconciliation mechanism (read :ref:`sync-data-structures`).
Block format
~~~~~~~~~~~~
-Each block consists of a 2-byte version number, a random 24-byte nonce, an
-8-byte serial, and a gzip-compressed JSON object with its length. The block is
-be padded up to the next whole kilobyte for privacy reasons. A block whose
+Each block consists of a 2-byte version number, a 24-byte fresh encryption IV,
+an 8-byte serial, and a gzip-compressed JSON object with its length. The block
+is padded up to the next whole kilobyte for privacy reasons. A block whose
length is already a multiple of a kilobyte is not padded further.
-The nonce is 24 bytes because that is exactly what `secretbox`_ takes, which
-lets a block be encrypted under its own nonce.
+The 24 bytes are what `secretbox`_ takes as its nonce, but they are a *fresh
+IV* drawn on every write, not the block identity: the identity that keys the
+URL and the block key is a separate random nonce, so an in-place rewrite (the
+redaction path) re-encrypts a different plaintext under a different
+encryption nonce. Encrypting under the stable identity instead would make
+the old and new ciphertexts of a rewritten block a two-time pad over exactly
+the data deletion exists to destroy -- an adversary holding the old
+ciphertext recovers ``P_old XOR P_new`` verbatim -- and would reuse the
+Poly1305 one-time authenticator key as well. The IV is prepended to the
+ciphertext in the clear (on-wire size ``1024n + 40``), so the decryptor can
+read it before decrypting; the block identity continues to travel in the URL
+and is what the key derives from.
The serial is only ever seen by the wallets: it sits inside the encrypted
payload, so the sync server knows nothing about it. Wallets assign it on
@@ -190,32 +200,44 @@ that block, which makes a rolled-back (replayed) block detectable.
Encryption is performed on the block using symmetric authenticated encryption
via libsodium's `secretbox`_ function, with a 32-byte key derived from the
-wallet's backup encryption key and the nonce of the block, which in the final
-implementation should be shareable between any wallets that the user wishes to
-add to the synchronization group.
+wallet's backup encryption key and the *identity nonce* of the block, which in
+the final implementation should be shareable between any wallets that the user
+wishes to add to the synchronization group. The encryption nonce is the fresh
+IV, which travels in the clear with the ciphertext; the identity nonce travels
+in the URL.
+
+The block format starts at version 7, and only version 7 is ever read: the
+earlier pre-release framing (encrypted under its identity nonce, on-wire size
+``1024n + 16``) is not supported and never shipped, so there is nothing to
+keep.
.. note::
- The key is derived from the *nonce* rather than from the hash of the
- plaintext block: the nonce travels with the block, whereas the plaintext
- hash is only known to whoever can already decrypt it, so deriving from it
- would make the block undecryptable.
+ The key is derived from the *identity nonce* rather than from the hash of
+ the plaintext block: the nonce travels with the block, whereas the
+ plaintext hash is only known to whoever can already decrypt it, so deriving
+ from it would make the block undecryptable.
.. code-block:: text
- +----------------------------+
- | version number (2 byte) |
- +----------------------------+
- | nonce (24 byte) |
- +----------------------------+
- | serial (8 byte) |
- +----------------------------+
- | JSON length n (4 byte) |
- +----------------------------+
- | gzipped JSON (n byte) |
- +----------------------------+
- | padding (to next full KB) |
- +----------------------------+
+ +-----------------------------------+
+ | version number (2 byte) |
+ +-----------------------------------+
+ | IV (24 byte) | <- fresh per write, also the
+ +-----------------------------------+ secretbox nonce
+ | serial (8 byte) |
+ +-----------------------------------+
+ | JSON length n (4 byte) |
+ +-----------------------------------+
+ | gzipped JSON (n byte) |
+ +-----------------------------------+
+ | padding (to next full KB) |
+ +-----------------------------------+
+ +-----------------------------------+
+ | IV (24 byte) | <- prepended in the clear
+ +-----------------------------------+
+ | secretbox(plaintext, IV, key) | <- ciphertext, 16-byte tag included
+ +-----------------------------------+
Block store API
~~~~~~~~~~~~~~~
@@ -624,6 +646,153 @@ stored hash.
:http:statuscode:`500 Internal server error`:
A database error occurred.
+.. _sync-data-structures:
+
+Block reconciliation
+~~~~~~~~~~~~~~~~~~~~
+
+A cycle does not have to walk the whole linked list in order to find what
+it is missing. It can instead reconcile its local view of the list with
+the server's through an *invertible bloom filter* (IBF), built over every
+block's identity: the filter is constructed so that the difference between
+the wallet's filter and the server's filter enumerates exactly the blocks
+that one side has and the other does not -- including in-place rewrites,
+which keep their identity but change their content hash. The wallet then
+fetches only those blocks.
+
+.. http:get:: /backups/${ACCOUNT_KEY}/blocks/reconcile
+
+ Compute an invertible bloom filter over the account's blocks -- one
+ element per block, the block's identity as defined below -- and return
+ it, so that the wallet can subtract its own filter and enumerate the
+ blocks that differ. Like the other read endpoints, the request needs
+ no signature: the account public key is the capability.
+
+ **Request**
+
+ :query prefix:
+ Optional. Fresh mixing salt for the filter (4 bytes, base32, network
+ byte order). The server builds its filter with this prefix; absent,
+ it uses an all-zero prefix. Either way the prefix that was used is
+ echoed in the response, since both sides must derive the same bucket
+ positions. A caller that suspects a stale or hostile filter can
+ demand a differently mixed one; the wallet itself does not currently
+ pass a prefix.
+
+ **Response**
+
+ :http:statuscode:`200 OK`:
+ The body is a ``SyncReconcileResponse`` object. An account without
+ blocks answers with ``total_blocks`` 0 and a filter of all-zero
+ buckets (built with the minimum bucket count).
+ :http:statuscode:`400 Bad request`:
+ The ``prefix`` parameter is malformed.
+ :http:statuscode:`402 Payment required`:
+ The account has expired and requires payment.
+ :http:statuscode:`500 Internal server error`:
+ A database error occurred.
+
+ .. code-block:: typescript
+
+ interface SyncReconcileResponse {
+ // Filter format version (currently 2).
+ version: number;
+ // Number of buckets the filter was built with.
+ bucket_count: number;
+ // Number of bucket positions each element occupies.
+ k: number;
+ // Mixing prefix the filter was built with (4 bytes, base32).
+ prefix: string;
+ // Number of blocks in the account's linked list.
+ total_blocks: number;
+ // The serialized filter, base32-encoded
+ // (bucket_count * 98 bytes).
+ filter: string;
+ }
+
+ The server computes its filter over the same element set and with the
+ same parameters the wallet uses, so the two filters are directly
+ comparable.
+
+Filter format
++++++++++++++
+
+The filter is an IBF in the style of GNUnet's SET service, parameterized
+for the block store:
+
+* **Element.** One element is the identity of a block: the 24-byte nonce
+ followed by the 64-byte SHA-512 hash of the encrypted contents
+ (88 bytes). The hash is part of the element because an in-place
+ rewrite changes the hash under the same nonce, so it must show up as a
+ difference rather than as a block the wallet already has. It is the
+ same ``block_hash`` the listing returns and the same hash the server
+ compares on ``If-None-Match``.
+* **Bucket.** Each bucket holds a signed 16-bit counter, an 88-byte key
+ sum (the XOR of every element mapped into the bucket) and an 8-byte key
+ hash sum (the XOR of the first 8 bytes of the SHA-512 hash of every
+ mapped element) -- 98 bytes in total:
+
+ .. code-block:: text
+
+ +----------------------------+
+ | counter (2 byte, int16) |
+ +----------------------------+
+ | key sum (88 byte, XOR) |
+ +----------------------------+
+ | key hash sum (8 byte, XOR) |
+ +----------------------------+
+
+ The counter increments for an insert and decrements for a remove; the
+ XOR sums are symmetric, which is what lets the wallet *subtract* its
+ filter from the server's.
+* **Bucket positions.** Each element occupies ``k = 3`` distinct
+ positions. The positions are successive 32-bit words of the SHA-512
+ over element + mixing prefix, reduced modulo the bucket count; when the
+ words run out, the hash itself is hashed again (as in GNUnet's bloom
+ filters), and duplicate positions are skipped (as in GNUnet's IBF
+ implementation).
+* **Sizing.** The bucket count is the next power of two at or above the
+ number of blocks, bounded to the range of 64 to 4096 buckets (the
+ serialized filter therefore stays below 4096 * 98 = 401 408 bytes).
+ The server rounds ``total_blocks`` up this way; the wallet builds its
+ own filter with the server's ``bucket_count``, ``k`` and ``prefix``, so
+ the two always match.
+
+Decoding the difference
++++++++++++++++++++++++
+
+The wallet builds its own filter over its local (nonce, hash) pairs with
+the server's ``bucket_count``, ``k`` and ``prefix``, and subtracts it
+bucket by bucket: the counters difference and the XOR differences. The
+result is decoded by repeatedly peeling "pure" buckets -- buckets whose
+counter is ``+-1`` and whose key sum hashes to their key hash sum: the
+key sum is then a single element of the difference, and it is removed
+from every bucket it occupies. Peeling either exhausts the filter (every
+bucket back to zero -- the difference set is fully enumerated) or gets
+stuck on a bucket that mixes several elements (there are more differences
+than the filter size can peel). A stuck filter is not treated as a lie:
+the wallet falls back to walking the list.
+
+The peeled elements have a side: counter ``+1`` elements exist only on
+the server ("missing" locally), counter ``-1`` elements only in the
+wallet ("stale" locally). A nonce that appears on both sides is an
+in-place rewrite -- same identity, new hash -- which the wallet fetches
+like a missing block.
+
+The wallet fetches exactly the nonces the difference names -- one at a
+time, through the listing endpoint with ``limit=1`` and the inclusive
+``start_nonce`` (there is no dedicated per-block GET), each entry verified
+before it is used -- plus, for their relinks, the stored neighbours of
+deleted nonces and the stored tail when nonces were added, since links
+only change server-side when a block is deleted or appended. The result
+is joined into one chain through the ``prev`` links and applied in order;
+a difference that deletes or rewrites anything re-applies the whole
+chain, so the sweep behind it drops the stale blocks and the records only
+they backed up. Any failure -- an undecodable filter, a fetch that fails
+verification, an ordering that does not close -- aborts the selective
+pull and falls back to walking the list, bounded by the safety cap of
+10 000 blocks.
+
Hash-indexed object store
-------------------------
@@ -756,8 +925,6 @@ that uploaded it.
:http:statuscode:`500 Internal server error`:
A database error occurred.
-.. TODO: synchronization primitive
-
Backup schema
-------------
@@ -769,12 +936,24 @@ insertion operations (“increments”) for a particular database entity
.. code-block:: typescript
interface IncrementSet {
+ version: number;
addExchangeIncs?: AddExchangeInc[];
setGlobalExchangeTrustIncs?: SetGlobalExchangeTrustInc[];
addBankAccountIncs?: AddBankAccountInc[];
// ...
}
+The ``version`` field is the schema version, which the wallet reads to upgrade
+an older set to the current schema (and refuses a newer one rather than
+re-uploading a truncated view of it). The upgrade chain is empty: version 1
+is the first schema a released wallet writes. The prototype-era re-keying
+step (schema version 0) was removed with the data it existed to repair, so a
+v0 set is refused as *older*; the chain machinery stays for the next real
+schema change. ``isIncrementSetEmpty`` -- which decides
+whether a redacted block may be deleted from the linked list -- tests the
+set's *own* keys rather than the known sections, so a section this wallet does
+not know still counts as content.
+
When a backup operation is triggered, this buffer is processed into a block
and subsequently emptied. The resulting block gets assigned a random UUID,
appended to the local linked-list, and uploaded to the backup service.
@@ -828,6 +1007,12 @@ Favor the operation with the largest ``tosAcceptedEtagTimestamp``. If two
timestamps are equal, favor the operation with the largest ``tosAcceptedEtag``
in lexicographical order.
+When the merge resolves against a record the wallet already holds (the local
+timestamp and etag are newer), the origin block is still recorded on the
+record: a full re-apply resets the origin-block lists and sweeps every record
+that comes out of it empty, and skipping the marking would delete an exchange
+record that a block merely confirms.
+
Set exchange to global trust
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
@@ -882,11 +1067,19 @@ User sets info for tax-deductible donations.
type: "set-donau-info";
donauBaseUrl: string;
taxPayerId: string;
+ donauSalt?: string;
}
* **Primary key:** ``[info]``
* **Deletion groups:** ``[donau-info]``
+``donauSalt`` is the salt the tax-ID hash is derived with. It is randomly
+generated per wallet, so it must travel with the record: deriving a fresh one
+on restore would change the tax-ID hash and break the linkage of every
+donation receipt already issued. It is absent on increments written before
+the field was added; a wallet restoring such an increment derives a fresh salt
+as ``handleSetDonau`` does.
+
Merge strategy
++++++++++++++
@@ -913,7 +1106,9 @@ A denomination is stored in the wallet.
exchangeMasterPub: EddsaPublicKey;
}
-* **Primary key:** ``[exchangeBaseUrl, denomPub]``
+* **Primary key:** ``[exchangeMasterPub, hash(denomPub)]`` -- the wallet
+ database keys denominations by the exchange *master* public key and the
+ hash of the denomination public key, so the increments do too.
* **Deletion groups:** ``[denominations]``
Merge strategy
@@ -1005,7 +1200,7 @@ first released: a coin from a wallet that predates it is treated as RSA.
interface WithdrawalCoinSource {
type: "withdrawal";
withdrawalGroupId: string;
- coinNumber: number;
+ coinIndex: number;
reservePub: string;
}
@@ -1018,7 +1213,10 @@ first released: a coin from a wallet that predates it is treated as RSA.
}
* **Primary key:** ``[coinPub]``
-* **Deletion groups:** ``[coins]``
+* **Deletion groups:** ``[coins, denominations]`` -- a coin references the
+ denomination it was withdrawn under (by ``[exchangeMasterPub,
+ denomPubHash]``), so deleting that denomination takes its coins along, and
+ the coins in turn drag their recoups along through the ``coins`` group.
Merge strategy
++++++++++++++
@@ -1053,7 +1251,7 @@ A signed coin is spent by the user.
}
* **Primary key:** ``[coinPub]``
-* **Deletion groups:** ``[coins]``
+* **Deletion groups:** ``[coins, denominations]``
Add a token
~~~~~~~~~~~
@@ -1313,22 +1511,28 @@ Add a reserve
A reserve is created by the wallet for every withdrawal and for the merge
capability of P2P payments, and its key pair lives in the wallet's
``reserves`` object store (see the ``WalletReserve`` record in ``db.ts``).
-The increment carries the record's identity -- the exchange and the reserve's
-derivation index -- and, for the reserves that predate the seed, the private
-key.
+The increment carries the record's identity -- the reserve's public key and,
+for a seed-derived reserve, the exchange and the derivation index -- and, for
+the reserves that predate the seed, the private key.
.. code-block:: typescript
interface AddReserveInc {
type: "add-reserve";
- exchangeBaseUrl: string;
- reserveIndex: number;
+ reservePub: EddsaPublicKey;
+ exchangeBaseUrl?: string;
+ // Derivation index, for a reserve whose key pair comes from the seed.
+ reserveIndex?: number;
// Only for reserves created before the reserve seed existed, whose
// keys are random and cannot be re-derived.
reservePriv?: EddsaPrivateKey;
}
-* **Primary key:** ``[exchangeBaseUrl, reserveIndex]``
+* **Primary key:** ``[reservePub]`` -- the reserve's public key, which is
+ what every other increment references it by. Keying on
+ ``[exchangeBaseUrl, reserveIndex]`` instead would let two devices hand the
+ same derivation slot to different reserves and silently lose a reserve
+ key pair, and ``reservePriv``-carrying reserves have no index at all.
* **Deletion groups:** ``[reserves]``
Merge strategy
@@ -1338,17 +1542,21 @@ Last write wins: the identity of a reserve never changes, and a re-recorded
increment (e.g. by the full collection pass) carries the same index and the
same key material.
-The public key of the reserve is *not* carried: it is derived from the private
-key on restore (``eddsa_get_public``), whether the private key was re-derived
-from the seed or restored from ``reservePriv``. The restored record therefore
-has the same ``reservePub`` as the wallet that created the reserve, which is
-what the other increments reference it by (see below). The ``WalletReserve``
-record gains ``exchangeBaseUrl``, ``reserveIndex`` and the
-``reserveSeedDerived`` marker (which decides whether the full collection pass
-emits the index-only form or the index-plus-private-key form); the exchange
-base URL is required by the increment and was missing from the record (see the
-``FIXME: Should reference exchange.`` comment in ``db.ts`` and the redundant
-``exchangeBaseUrl`` of ``WithdrawalGroupRecord``).
+The public key is carried (and checked against the re-derived key material on
+restore, so that a reserve restored under the wrong key is refused rather than
+written). The restored ``WalletReserve`` record gains ``exchangeBaseUrl``,
+``reserveIndex`` and the ``reserveSeedDerived`` marker (which decides whether
+the full collection pass emits the index-only form or the index-plus-private-key
+form); the exchange base URL is required by the increment and was missing from
+the record (see the ``FIXME: Should reference exchange.`` comment in ``db.ts``
+and the redundant ``exchangeBaseUrl`` of ``WithdrawalGroupRecord``).
+
+A private-key carry still travels with its local ``reserveIndex`` when the
+record has one. The index is what the allocation scan
+(``max(highest + 1, counter)``) on every device derives the next seed-derived
+reserve from, so a carry that dropped it would let two wallets of the group
+advance their counters differently and derive different keys for their next
+reserve.
The remaining fields of ``WalletReserve`` (``status``, the KYC thresholds,
``kycAccessToken``, ``amlReview``) are all derivable by querying the exchange
@@ -1594,11 +1802,19 @@ A payment started by the user completes successfully.
interface PaymentDoneInc {
type: "payment-done";
proposalId: string;
+ payCost?: AmountString;
}
* **Primary key:** ``[proposalId]``
* **Deletion groups:** ``[payments]``
+``payCost`` is what the payment actually cost the user
+(``payInfo.totalPayCost``), captured when the merchant confirmed it. The
+pay-info record itself is not in the backup -- only this total is -- so a
+restored purchase can at least show what was paid. It is optional so old
+done increments still parse; the full collection pass re-emits them for
+completed purchases, which is how pre-existing ones backfill the total.
+
Merchant purchase fail
~~~~~~~~~~~~~~~~~~~~~~
@@ -1814,7 +2030,7 @@ User confirms a payment request from another wallet.
.. code-block:: typescript
- interface PeerPullDebitDoneInc {
+ interface PeerPullDebitStartInc {
type: "peer-pull-debit-start";
peerPullDebitId: string;
pursePub: EddsaPublicKey;
@@ -1919,13 +2135,18 @@ User requests money to another wallet.
contractPriv: EddsaPrivateKey;
contractEncNonce: string;
mergeTimestamp: TalerPreciseTimestamp;
- mergeReserveRowId: number;
- withdrawalGroupId?: string;
+ mergeReservePub: EddsaPublicKey;
}
* **Primary key:** ``[pursePub]``
* **Deletion groups:** ``[peer-pull-credit]``
+``mergeReservePub`` names the reserve the purse is merged into. The row id
+the wallet database keeps for it (``mergeReserveRowId``) is an autoincrement
+local to one database and meaningless on another device, so it is the reserve's
+public key that travels instead; the apply path resolves it back to the row id
+through the restored reserve record.
+
Merge strategy
++++++++++++++
@@ -1942,7 +2163,7 @@ User aborts request to another wallet.
interface PeerPullCreditAbortInc {
type: "peer-pull-credit-abort";
pursePub: EddsaPublicKey;
- abortReason?: TalerErrorInfo;
+ abortReason?: TalerErrorDetail;
}
* **Primary key:** ``[pursePub]``
@@ -1951,7 +2172,7 @@ User aborts request to another wallet.
Merge strategy
++++++++++++++
-Store all ``failReason`` in the database.
+Store all ``abortReason`` in the database.
Peer-pull-credit done
~~~~~~~~~~~~~~~~~~~~~
@@ -1983,7 +2204,7 @@ A request to another wallet fails.
interface PeerPullCreditFailInc {
type: "peer-pull-credit-fail";
pursePub: EddsaPublicKey;
- failReason: TalerErrorInfo;
+ failReason: TalerErrorDetail;
}
* **Primary key:** ``[pursePub]``
@@ -2210,6 +2431,10 @@ end up with the same loss listed twice.
denomLossEventId: string;
currency: string;
exchangeBaseUrl: string;
+ // The master key whose denominations caused the event, when the wallet
+ // that recorded it knew it. It is what lets the deletion cascade match
+ // the event against the denominations it wrote off.
+ exchangeMasterPub?: string;
denomPubHashes: string[];
// "denom-expired", "denom-vanished", "denom-revoked",
// "denom-unoffered".
@@ -2253,13 +2478,14 @@ be safely removed from the local database as well.
Mechanically, a wallet deletes an item by scrubbing its increments out of the
pending buffer and rewriting every origin block that still carries them: a
block that keeps other content is replaced in place (``PUT``, under its
-original nonce), one that becomes empty is removed from the linked list
-(``DELETE``, relinking its neighbours). A block rewritten in place keeps its
-nonce, so the other wallets detect the change only by noticing that the
-block's hash no longer matches their local copy; a deleted block shows up as a
-gap in the linked list. On either signal a wallet re-applies the whole linked
-list and drops every item that no longer appears in any origin block, which is
-what makes deletions propagate across the sync group.
+original identity nonce, with a fresh encryption IV), one that becomes empty
+is removed from the linked list (``DELETE``, relinking its neighbours). A
+block rewritten in place keeps its identity nonce, so the other wallets detect
+the change only by noticing that the block's hash no longer matches their
+local copy; a deleted block shows up as a gap in the linked list. On either
+signal a wallet re-applies the whole linked list and drops every item that no
+longer appears in any origin block, which is what makes deletions propagate
+across the sync group.
Deletion groups
~~~~~~~~~~~~~~~
@@ -2269,12 +2495,36 @@ 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.
+Each increment type declares the deletion groups it belongs to: the group it
+is a resource of, plus every group whose resources it *references*. Deleting
+a resource in a group removes every increment that references it, and the
+removed increments drag in everything that references *them* (the transitive
+closure). The references are the increment's fields, not its own primary key:
+
+- a ``refund`` references the payment it refunds, by ``[proposalId]``;
+- a ``recoup`` references each coin it recouped, by ``[coinPub]``;
+- a ``add-coin``/``spend-coin`` references the denomination it was withdrawn
+ under, by ``[exchangeMasterPub, denomPubHash]``;
+- a ``denom-loss`` references each denomination it wrote off, by
+ ``[exchangeMasterPub, denomPubHash]`` (only when the increment carries the
+ master public key; increments from before the field was added cannot be
+ matched).
+
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.
+denomination. In turn, all the 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 -- and so are the recoups of those coins. Deleting a
+payment likewise takes the refunds of that payment with it.
+
+.. note::
+
+ The delete cascade runs on the increments the backup currently holds. A
+ redaction therefore only reaches the *blocks this wallet has*, which is
+ what the deletion queue's retry loop is for: a block the deleting wallet
+ has not pulled is redacted by whichever wallet pulls it after the item's
+ origin blocks were scrubbed here.
Backup process
--------------
@@ -2369,6 +2619,19 @@ A cycle also pulls the account's linked list before packing new increments,
applying any blocks it has not seen before (see "Restore process" below), so
that new blocks are appended after the current end of the list.
+The pull is bounded by a safety cap (10 000 blocks) against a runaway linked
+list. A list longer than the cap is *truncated*, and a truncated pull is not
+treated as the whole list: the fetched prefix is applied, but the cap must
+not masquerade it as complete. In particular the re-apply's sweep -- which
+drops every record whose origin blocks no longer exist -- must not run on a
+truncated view, or every block beyond the cap would read as "deleted" and
+every record it alone backed up would be swept away. A truncated pull
+therefore leaves the stored blocks and records beyond the cap alone, does not
+advance the last-acknowledged-block pointer to the prefix's end (the true
+tail is unknown, so the next append would fail against it), and reports the
+cycle as failed with the account too large to sync, so that the user can
+prune it.
+
An account that has not been paid for yet answers every request with ``402
Payment required``, and only the upload endpoints carry the ``Taler:`` header
with a ``taler://pay/...`` URI. A cycle that is answered this way while
@@ -2399,6 +2662,19 @@ retried after five minutes, and one that is waiting for the account payment to
be prepared after thirty seconds -- the payment is what unlocks every upload,
so it is worth retrying as soon as the provider's merchant backend recovers.
+A burst of wake-ups -- a withdrawal records an increment at every step -- must
+not be allowed to chain one cycle into the next: at least three seconds have
+to elapse between the end of one cycle and the start of the next, and a
+wake-up that arrives inside the gate is absorbed instead of scheduled (the
+cycle statistics count it as a ``skippedWakeUp``). A cycle that acknowledged
+its block rests until the next hourly interval: the buffer is drained, so no
+follow-up cycle is owed. A cycle that ends still owed work -- the pack split
+what was pending, the payment still needs confirming -- reports progress
+rather than backing off, since a backoff would turn a long history into a
+trickle. The statistics record how many cycles ran back-to-back
+(``consecutiveRuns``), so the difference between the two behaviours is
+observable.
+
Waking the cycle is not always enough. Past a critical point the wallet has
already revealed key material to somebody else -- the exchange has signed the
planchets, the purse exists and can be paid into -- and the cycle runs
@@ -2436,6 +2712,13 @@ collection pass* is the safety net: it walks every record kind the backup
manages (the ``backupSources`` of ``sources.ts``) and turns the records that
have never been backed up into "start" increments.
+The pass also re-emits the ``payment-done`` increment of every completed
+purchase. Increments normally happen once, at the transition that created
+them, so a purchase completed before its done increment carried the paid
+total (see ``payment-done``) would never report it again; the re-emission
+ships the total to the group's other wallets. Applying it is idempotent:
+wallets that already have the total keep it.
+
The pass is expensive -- it reads every denomination, exchange, bank account
and transaction the wallet holds -- so it does not run on every cycle. It
runs when a watermark, ``lastFullCollection`` in the wallet's backup
@@ -2459,10 +2742,14 @@ driven by a recovery document from ``getBackupRecovery``:
1. ``loadBackupRecovery`` installs the recovery's root key and providers, and
drops the wallet's own block pointers, so the device starts from nothing.
2. Once the user activates a recovered provider (``addBackupProvider`` with
- ``activate``), the backup cycle downloads the account's linked list,
- decodes each block it has not seen before, CRDT-applies its increments to
- the local database -- recording the block's nonce in the ``originBlocks``
- of every record it touched -- and stores the blocks locally.
+ ``activate``), the backup cycle downloads the account's linked list --
+ incrementally, by reconciling its local view through an invertible bloom
+ filter and fetching only the blocks that differ (see Block
+ reconciliation), or by walking the whole list when reconciliation is not
+ possible -- decodes each block it has not seen before, CRDT-applies its
+ increments to the local database -- recording the block's nonce in the
+ ``originBlocks`` of every record it touched -- and stores the blocks
+ locally.
Because the same root key derives the same per-provider account keys, a
recovering wallet sees exactly the blocks any other wallet in the group
@@ -2477,7 +2764,18 @@ the restoring device:
denomination therefore recounts the coins of that denomination that are
already in the database, so a coin whose denomination travels in a later
block -- or in a block written by another wallet -- still reaches the
- balance instead of being dropped from it for good.
+ balance instead of being dropped from it for good. The reverse direction
+ recounts too: a coin removed by a re-apply's sweep corrects the counts of
+ its denomination, and the availability row is deleted when the last coin
+ of a denomination and age restriction is gone.
+* An increment whose dependency has not arrived yet is deferred, not
+ dropped: a ``set-global-exchange-trust`` for an exchange that is not
+ known locally, a ``refresh-session`` without its group, a ``refund``
+ without its payment, an ``add-reserve`` whose seed is missing. A record
+ the wallet already holds is still marked with the origin block on this
+ deferred path, so a full re-apply -- which resets the origin-block lists
+ and sweeps records that come out of it empty -- does not delete it while
+ it waits for its dependency.
* A pending withdrawal's transfer instructions -- the exchange's credit
accounts, and the transfer options the user actually pays with -- are
derived from the exchange, the instructed amount and the reserve key
@@ -2487,6 +2785,9 @@ the restoring device:
reserve: until the transfer has been made the reserve does not exist at
the exchange yet, so a wallet that waited for the reserve status would
never get as far as showing the user something to pay with.
+* A completed purchase's paid amount comes from the ``payCost`` field of its
+ ``payment-done`` increment; the UI falls back to the order total when even
+ that is missing.
Restore schedule
----------------
@@ -2883,127 +3184,47 @@ The checked implementation items below describe prototype feature branches,
not the reviewed main branches. The normative Sync API still labels backup
support as upcoming.
-* [x] Design backup schema.
-* [ ] Design incremental sync.
-* [x] Design backup/restore schedules.
-* [x] Design wallet-core API.
-* [x] Wallet-core implementation. The machinery -- block and blob encoding,
- CRDT merge, the sync protocol client and its signatures, increment
- collection, the scheduled backup cycle with its pull/merge/apply half, the
- API request handlers, the account payment flow, and item deletion
- (retro-redaction of the ``originBlocks`` plus the pull-side "deleted iff
- absent from all origin blocks" sweep) -- is done, and so is **every
- increment family in this document**: the exchange, global-trust,
- bank-account, donau and denomination entities; the reserve family
- (``set-reserve-seed`` / ``add-reserve``, with the seed-derived key pairs and
- the ``reservePriv`` fallback for reserves that predate the seed), which is
- what makes a restored coin recoupable; the withdrawal, deposit,
- merchant-payment, peer-push-credit, peer-push-debit, peer-pull-debit and
- peer-pull-credit transaction families; the refresh family, whose per-coin
- session seed lets a restored wallet finish a melt instead of losing the
- change; and the coin and token families, which carry the per-record key
- material the wallet database stores (the seed-derived modelling of earlier
- drafts is gone from both).
-
- Contract terms travel as blobs -- uploaded ahead of the blocks that
- reference them, with their reference counts adjusted, and fetched and stored
- back into the contract-terms store on the pull side; a transaction whose
- terms are not available is shown in a reduced form instead of failing the
- transaction listing. Restoring a coin recomputes the coin-availability
- rows, so a restored wallet shows the same balance as the wallet that made
- the backup, and a restored wallet can continue a pending withdrawal (only an
- expired bank operation cannot be resumed). ``runBackupCycle`` and
- ``getBackupDiagnostics``, the per-cycle statistics, the forced
- full-collection pass and the ``backup-status`` notifications are all in
- place, on both database backends: the native (sqlite) schema stores the
- backup providers and blocks and the ``originBlocks`` of every backup-managed
- record, and a wallet migrating from the IndexedDB backend carries all three
- across.
-
- The three *derived* families -- refund, recoup and denomination loss -- are
- implemented as finished facts, and every change to whether a coin counts
- towards the balance (spend, refresh, recoup, denomination loss, suspend) is
- reported as a coin increment, so two wallets converge on the same balance
- rather than only on the same coins. A transaction can no longer be taken
- back out of a terminal state by an increment describing an older view of it.
-
- Known gaps, none of which loses money: refund *items* are not carried
- (nothing outside the refund query reads them, and the merchant hands back
- the same ones); the exchange entries and peer-pull-credit records do not
- restore their ``currentMergeReserveRowId`` pointer, since it is a row id
- local to one database; recoup transactions are backed up and restored but
- the wallet does not yet render them as transactions; and a wallet cannot
- join a sync group written by a *newer* wallet -- it refuses the blocks
- rather than re-uploading a truncated view of them.
-* [x] Design sync API (+ auth).
-* [ ] Server-side implementation (partial: block GET/POST/PUT/DELETE, object
- store GET/POST with reference counting, /config and payments done;
- reconciliation mechanism still missing).
-* [x] UI/UX for backup and sync, in the Android wallet: adding and removing a
- provider, the account payment prompt, the recovery as a QR code and as a
- paper key (written down or saved to a file) with its import counterpart,
- "back up now" through ``runBackupCycle`` with a force-full-backup control
- and a diagnostics card in developer mode, and a progress display driven by
- the ``backup-status`` notifications. The web extension shows the cycle in
- its wallet-activity view, but has no provider management user interface yet.
+* [x] Design backup schema, incremental sync, backup/restore schedules and
+ the wallet-core API; design the sync API (with authentication).
+* [x] Wallet-core implementation: block and blob encoding, CRDT merge, the
+ sync protocol client and its signatures, increment collection, the
+ scheduled backup cycle with its pull/merge/apply half, item deletion
+ (retro-redaction plus the pull-side sweep), the account payment flow,
+ the API handlers and ``backup-status`` notifications, the
+ invertible-bloom-filter reconciliation pull with its list-walk
+ fallback, and every increment family in this document -- on both
+ database backends (native sqlite and IndexedDB, with migration).
+* [x] Server-side implementation: block GET/POST/PUT/DELETE, the object
+ store with reference counting, /config, payments, and the
+ invertible-bloom-filter reconciliation endpoint.
+* [x] UI/UX in the Android wallet: provider management, the account
+ payment prompt, recovery as QR code / paper key with import, "back up
+ now" with a force-full-backup control and diagnostics, and the progress
+ display driven by ``backup-status``; the web extension shows the cycle
+ in its wallet-activity view but has no provider management UI yet.
+
+Known gaps, none of which loses money: refund *items* are not carried
+(nothing outside the refund query reads them); the exchange entries and
+peer-pull-credit records do not restore their ``currentMergeReserveRowId``
+pointer (a row id local to one database); recoup transactions are backed
+up and restored but the wallet does not yet render them as transactions;
+and a wallet cannot join a sync group written by a *newer* wallet -- it
+refuses the blocks rather than re-uploading a truncated view of them.
Alternatives
============
-.. _sync-data-structures:
-
-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.
-
-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:
-
-.. code-block:: text
-
- +-----------------------+
- | Bloom filter (10 bit) |
- +-----------------------+
- | Counter (4 bit) |
- +-----------------------+
- | Hash (12-16 bit) |
- +-----------------------+
- | Checksum (4-8 bit) |
- +-----------------------+
+To perform incremental restores (i.e. synchronization) and converge towards
+the global state (a.k.a. reconciliation), wallets need to keep track 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. Rather than the event-driven message queue outlined below, this
+document specifies the invertible bloom filter (see Block reconciliation),
+which the wallet and server implement.
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
@@ -3020,10 +3241,6 @@ 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.
-.. TODO:
- Drawbacks
- =========
-
Discussion / Q&A
================
