| 1 | # 🤖 Sealed search index — plan for message search at business scale |
| 2 | |
| 3 | **Status: designed 2026-07-14, not built.** This documents the agreed upgrade |
| 4 | path for client-side message search before large (Business-tier, ~1 TB |
| 5 | allowance) spaces make today's design hurt. Nothing here is urgent yet — the |
| 6 | triggers below say when to build it. Companion decisions this plan leans on: |
| 7 | the storage/durability ladder (`tier-economics.md § Durability per tier`) and |
| 8 | the R2 attachment offload (#550), which keeps media out of the search path |
| 9 | entirely. |
| 10 | |
| 11 | ## Where search stands today |
| 12 | |
| 13 | Search is **local on every platform** — the query never leaves the device, |
| 14 | and the server never gains a search surface. That's a consequence of the E2EE |
| 15 | rule, not a feature toggle, and this plan does not bend it. |
| 16 | |
| 17 | - **Web** (#586 + the #228 "time machine"): the local store (`store.js`) |
| 18 | holds raw **ciphertext** rows in IndexedDB; `search.js`'s `SearchIndex` |
| 19 | decrypts each thread **once per session into an in-memory index** (never |
| 20 | persisted), and queries are substring scans over it. "Search earlier |
| 21 | messages" walks incomplete threads' history into the store (`runBackfill`) |
| 22 | and streams new hits in. The design's own comments accept the limits and |
| 23 | say "revisit if a real space ever makes this hurt". |
| 24 | - **iOS / Mac**: the App-Group `MessageStore` keeps **decrypted payloads** in |
| 25 | SQLite with an **FTS5** twin table (`messages_fts`); `MessageStore.search` |
| 26 | is a `MATCH` join, newest-first, limit 50. At-rest protection is the OS's |
| 27 | (file-level Data Protection), which is the platform-normal posture — |
| 28 | Signal and WhatsApp do the same. |
| 29 | |
| 30 | Two honest asymmetries fall out of that, worth naming because this plan |
| 31 | resolves one and keeps the other: |
| 32 | |
| 33 | 1. **Semantics differ**: web matches *substrings* (`matchText` uses |
| 34 | `includes`), native matches FTS5 *word/prefix terms*. Searching "ana" |
| 35 | finds "banana" on web and not on iOS. This plan aligns both on |
| 36 | word-prefix (below). |
| 37 | 2. **At-rest posture differs**: native stores plaintext under OS file |
| 38 | encryption; web deliberately stores only ciphertext. This plan **keeps** |
| 39 | web's stricter posture — that's what "sealed" means. |
| 40 | |
| 41 | ## Why web search will hurt, and when |
| 42 | |
| 43 | The in-memory index costs one full-store decrypt per tab session plus RAM |
| 44 | proportional to the whole corpus's text. Media never enters the path (the |
| 45 | store caches message rows only; attachment bytes fetch on demand), so the |
| 46 | problem scales with **history length, not storage bytes**: |
| 47 | |
| 48 | | Space | Rows on device | First search (est.) | Index RAM (est.) | |
| 49 | |---|---|---|---| |
| 50 | | Family, years | ~50k | ~1–2 s | ~10 MB | |
| 51 | | Community, years | ~300k | ~10 s | ~50 MB | |
| 52 | | Business, a decade | ~2M | minutes | 300+ MB | |
| 53 | |
| 54 | A phone browser will evict or kill the tab well before the last row. The |
| 55 | scan is fine to roughly **100–200k rows per device**; beyond that every |
| 56 | session pays the full decrypt again. |
| 57 | |
| 58 | **Triggers to build this** (client-side heuristics, no analytics — measure |
| 59 | locally and log to console): a device's store crosses ~150k rows, or a |
| 60 | measured first-search ensure pass exceeds ~3 s. Either observed in a real |
| 61 | space = schedule the work. |
| 62 | |
| 63 | ## Design: a sealed, disposable index beside the ciphertext store |
| 64 | |
| 65 | One sentence: **persist the derived index the session index already builds, |
| 66 | encrypted at rest under a device-local key, and query it via postings so a |
| 67 | search decrypts a few shards and a handful of candidate rows instead of the |
| 68 | whole store.** |
| 69 | |
| 70 | ### Invariants (the non-negotiables) |
| 71 | |
| 72 | - **Never plaintext at rest in web storage.** Index shards are AES-GCM |
| 73 | ciphertext in IndexedDB, sealed under a **device-local, non-extractable |
| 74 | WebCrypto key** stored alongside (structured-clone of a `CryptoKey`). |
| 75 | `store.js`'s ciphertext-only rule survives intact. |
| 76 | - **The index is a cache, never truth.** It is derived from the ciphertext |
| 77 | store, deletable at any time, rebuilt lazily from the store. Schema-version |
| 78 | mismatch → drop and rebuild. Sign-out → delete with everything else. |
| 79 | - **Postings are hints.** Every hit re-decrypts its row from the store and |
| 80 | re-verifies the match before display — so stale postings from edits, |
| 81 | deletes, and tombstones fall out silently rather than needing synchronous |
| 82 | index maintenance. |
| 83 | - **Per-device coverage, honestly stated.** The index covers what this |
| 84 | device's store holds; the existing backfill narration ("searching back to |
| 85 | 2024…") already sets that expectation and stays. |
| 86 | - **No dependencies, no build step.** Tokenization via the built-in |
| 87 | `Intl.Segmenter`; everything else is plain ES modules. (Running the |
| 88 | indexer in a module Worker to keep the UI responsive is an implementation |
| 89 | freedom, not a requirement.) |
| 90 | |
| 91 | ### Shape |
| 92 | |
| 93 | - **Stores** (new object stores in the existing `lchat-store` DB): |
| 94 | `idx-shards` (sealed term-shard blobs), `idx-meta` (per-thread indexed |
| 95 | interval + schema version), `idx-key` (the CryptoKey). |
| 96 | - **Tokenization**: `Intl.Segmenter` word segmentation, lowercased; message |
| 97 | text plus sender name. **Query semantics become word-prefix AND** — each |
| 98 | query term must prefix-match an indexed term. This matches native FTS5, |
| 99 | fixing asymmetry #1, and is what every mainstream chat app does. (The |
| 100 | substring-parity alternative — a trigram index — was rejected: ~3× the |
| 101 | size for a semantics nobody expects.) |
| 102 | - **Shards**: terms bucketed by normalized prefix, target ~128–512 KB per |
| 103 | shard sealed; postings are `(threadId, messageId)` pairs, delta-encoded. |
| 104 | Sizing: ~2M messages × ~12 tokens ≈ 24M postings ≈ well under 100 MB |
| 105 | sealed — comfortable IndexedDB territory. |
| 106 | - **Write path — piggyback on decryption that already happens**: live |
| 107 | receive, thread render, `SearchIndex.ensureThread`, and `runBackfill`'s |
| 108 | `onPage` hook (whose docstring already reserves it "for incremental |
| 109 | indexing"). A buffered writer batches term→posting appends and |
| 110 | read-modify-writes sealed shards. Per-thread coverage is tracked as an |
| 111 | **interval** (`[minIndexed, maxIndexed]`) rather than the session index's |
| 112 | seen-`Set` — backfill extends it downward, live traffic upward. (Same |
| 113 | known gap-above caveat as the store's backfill watermark; same acceptance.) |
| 114 | - **Query path**: segment the query → decrypt the few shards its term |
| 115 | prefixes land in → intersect postings (AND) → decrypt candidate rows only, |
| 116 | newest-first, limit 50 → verify with the real matcher → render through the |
| 117 | existing `#msg-results` scaffold and jump. First search on a warm index: |
| 118 | milliseconds of shard decrypt plus tens of row decrypts. |
| 119 | - **Compaction**: lazy and occasional — rewrite shards dropping postings the |
| 120 | verify step has seen dead (deleted/edited/left threads). Nothing correct |
| 121 | depends on it; it only reclaims space, because hints are re-verified. |
| 122 | |
| 123 | ### What sealing buys, and what it doesn't |
| 124 | |
| 125 | Sealing keeps derived plaintext (a term list is readable content!) out of |
| 126 | casual reach: disk images, sync'd browser-profile backups, and forensic |
| 127 | strolls through IndexedDB see only ciphertext — the same at-rest level as |
| 128 | the message store beside it. It does **not** defend against an attacker who |
| 129 | controls the same origin at runtime (XSS) or who lifts the whole profile and |
| 130 | runs the browser — but neither does anything else in the client: the user's |
| 131 | private key and wrapped thread keys live in the same origin storage. The |
| 132 | sealed index adds **no new exposure class**; that's the bar it has to meet, |
| 133 | and the reason a plaintext web index (native-style) was rejected — browser |
| 134 | storage lacks the OS file-protection story App-Group SQLite gets. |
| 135 | |
| 136 | ## Phases |
| 137 | |
| 138 | 1. **P0 — semantics + measurement** (small, anytime): align web `matchText` |
| 139 | on word-prefix AND (shared test vectors web ↔ native so the tokenizer/ |
| 140 | match contract is pinned the way event vectors pin folds), and add the |
| 141 | local first-search timing log that arms the trigger. |
| 142 | 2. **P1 — the sealed index** (the feature): stores, writer, query path, |
| 143 | rebuild-on-version-mismatch. Scan remains the fallback for anything the |
| 144 | index doesn't cover yet. |
| 145 | 3. **P2 — compaction + polish**: lazy shard compaction, leave-thread |
| 146 | cleanup, coverage surfacing in the results footer. |
| 147 | 4. **P3 — richer queries** (optional, later): attachment-filename terms |
| 148 | (filenames ride inside encrypted payloads, so they index client-side like |
| 149 | any other text), `from:` / `in:` filters (the entry fields already |
| 150 | exist), quoted phrases (positional postings — only if wanted). |
| 151 | |
| 152 | ## Rejected |
| 153 | |
| 154 | - **Any server-side search**, including searchable-encryption schemes — |
| 155 | they leak query and access patterns to exactly the party the product |
| 156 | promises can see nothing. Off the table permanently. |
| 157 | - **Trigram/substring index** — 3× size for unfamiliar semantics. |
| 158 | - **Cross-device index sync** — each device derives its own from the store |
| 159 | it already syncs; shipping index blobs around adds a surface for zero |
| 160 | user-visible gain. |
| 161 | - **Plaintext index on web** — see the sealing analysis above. |
| 162 | |
amadan