# Authenticated Pages, Unanchored Counters: Positional Integrity Without Freshness in an Encrypted Single-File Database Daozhendong Yang, School of Intelligent Science and Engineering, Yunnan Technology and Business University, Kunming, China — Paper about **Nebula**, a local-first encrypted memory database written in Rust. A database is one file: page 0 holds a cleartext header prefix and a sealed payload, page 1 holds the sealed catalog, and pages 2 and up hold records, index snapshots and free pages. Every non-header page is sealed with ChaCha20-Poly1305 under associated data that binds the page number and the page role. The paper measures the real binary against three questions: what the per-page binding actually catches, what it cannot catch, and what the guarantees cost. ## arXiv classification - **Primary:** `cs.CR` — Cryptography and Security - **Cross-lists:** `cs.DB` — Databases The same classification is stated in the header comment of `main.tex`. ## Abstract (plain-text rendering) An encrypted single-file database protects its contents with a key derived from a password and seals every page with an authenticated cipher whose associated data binds the page to its number and to its role. That construction is good. We measured it: across 13 byte-level mutations of a real database, 7 were refused when the file was opened, 5 more were caught only when the database was read, and 1 mutation was never noticed at all. What the construction does not provide is freshness. The counter that records how far the database has advanced lives inside the encrypted catalog, so an attacker who keeps an old copy of the file can restore it and every page will still authenticate. We measured that too: after restoring a snapshot over a live database, 40 of 80 records were silently lost, the checkpoint counter rewound from 8 to 4, the file was byte-identical to the snapshot, and the engine reported no error of any kind. We then show that no purely local mechanism can detect this: whatever the database says about its own history is exactly what the attacker can rewrite. Freshness requires a witness the attacker cannot reach. We build one — a chained anchor kept outside the database — and measure its cost at 2.11 µs per verification against the 178.4 ms that opening the database already costs, a factor of 84,710. We also characterise the cost of the guarantees themselves: the per-page framing is 0.7324% of a 4 KiB page, but because each record occupies a page of its own the file grows 13.2x when the page size goes from 4 KiB to 64 KiB, and an open is dominated by Argon2id rather than by data (178.4 ms for an empty database, 297.5 ms at 8,000 records). Finally we measure the query path: index-evaluable predicates stay flat at 0.0301 ms while scan-only predicates grow linearly to 60.807 ms, a ratio of 9,968, and a scan that matches a single record costs within 17% of one that matches 1,600. The result is a three-way separation that the format literature usually leaves implicit: confidentiality and positional integrity are local and cheap, freshness is not local at all, and its price is not the crypto but the bookkeeping. ## Abstract for the arXiv form (1,920-character limit) The abstract printed in the paper is longer than the form accepts, so the submission form takes this shorter version. It keeps every measured number that the paper reports and drops only the prose that restates them. > An encrypted single-file database seals every page with an authenticated > cipher whose associated data binds the page to its number and role. We > measured that construction on a real database: across 13 byte-level > mutations, 7 were refused at open, 5 were caught only when the database was > read, and 1 was never noticed. What it does not provide is freshness: the > counter that records progress lives inside the encrypted catalog, so an > attacker who keeps an old copy can restore it and every page still > authenticates. After restoring a snapshot over a live database, 40 of 80 > records were silently lost, the checkpoint counter rewound from 8 to 4, and > the engine reported no error. No purely local mechanism can detect this, > because whatever the database says about its own history is what the > attacker can rewrite. We build a witness the attacker cannot reach — a > chained anchor kept outside the database — and measure it at 2.11 us per > verification against the 178.4 ms an open already costs, a factor of 84,710; > the anchor located the rolled-back state at position 0 of a chain of length > 2. We also characterise the cost of the guarantees: per-page framing is > 0.7324% of a 4 KiB page, but the file grows 13.2x when the page size goes > from 4 KiB to 64 KiB, and an open is dominated by Argon2id (178.4 ms empty, > 297.5 ms at 8,000 records). Index-evaluable predicates stay flat at 0.0301 ms > while scan-only predicates grow to 60.807 ms, a ratio of 9,968. The result is > a three-way separation: confidentiality and positional integrity are local > and cheap, freshness is not local at all, and its price is not the crypto > but the bookkeeping. ## What is measured Every experiment runs against the compiled `nebula.exe` binary, and every number is written into `scripts/results/nebula_measure.json`. The tables, the macros and the figures are generated from that file; nothing was typed by hand. | Experiment | What it does | What it answers | | --- | --- | --- | | `format` | creates databases at three page sizes | the plaintext prefix, the framing overhead, the page count | | `tamper` | 13 byte-level mutations plus two controls | where the per-page binding is checked, and where it is not | | `rollback` | keeps a copy of the file, grows the live one, restores the copy | whether freshness is available locally | | `anchor` | chains the catalog digest outside the database | the cost of an external freshness witness | | `query_cold` | six predicates at three corpus sizes, cache off | the cost of an index probe against the cost of a scan | | `query_default` | the same with the document cache on | whether the cache changes the picture | | `storage` | three page sizes at two corpus sizes | bytes per record, and the price of one record per page | | `open` | four corpus sizes | what an open costs, and how much of it is the key derivation | ### Headline results - **Tamper matrix (13 mutations):** 7 refused at open, 3 caught when the damaged record was fetched, 2 caught only on a full scan, 1 never noticed. Appending a page to the file is invisible: the engine derives the page count from the file length, so an appended page is simply unreferenced. - **Rollback:** 40 records written after a snapshot were silently lost; the checkpoint counter rewound from 8 to 4; the restored file was byte-identical to the snapshot (same SHA-256); all 40 record pages still authenticated; the engine reported no error. - **Anchor:** a chained HMAC witness outside the database, 2.09 µs per chain step and 2.11 µs per verification, i.e. 84,710x cheaper than the Argon2id derivation every open already pays. It located the rolled-back state at position 0 of a chain of length 2 and reported 4 checkpoints rolled back. - **Framing:** 30 bytes per page, which is 0.7324% of a 4 KiB page and 0.0458% of a 64 KiB page. - **Storage:** one record per page means the file grows 13.2x when the page size goes from 4 KiB (5,120 bytes per record) to 64 KiB (67,502 bytes per record). - **Open:** 178.4 ms for an empty file, 297.5 ms at 8,000 records. The extra 119.1 ms buys 40,370,176 bytes of data; the fixed latency is the Argon2id derivation (19 MiB, t=2, p=1). - **Queries:** at 8,000 records an index probe costs between 0.0015 ms and 0.0301 ms and does not grow with the corpus; a scan costs 60.807 ms and grows linearly. A shared-tag index lookup costs 0.1389 ms at 25 matches and 2.8239 ms at 400 matches, so an index query costs O(answer), not O(database). A scan that matches one record costs 17% less than a scan that matches 1,600, so the cost of a scan is the scan and not the size of its answer. ## Layout of the paper directory ``` main.tex the paper common.tex the shared preamble, identical to papers/_shared/common.tex numbers.tex generated macros, one per measured number refs.bib the bibliography tables/ generated tables, one float each figures/ generated figures scripts/ the harness and the generators scripts/results/ the measurement artifact ``` ## Reproducing the numbers ``` cargo build --release python scripts/measure.py --out scripts/results/nebula_measure.json python scripts/make_artifacts.py python scripts/make_figures.py ``` The first command builds the database; the second rewrites the measurement artifact; the third and the fourth regenerate the LaTeX numbers, the tables and the figures. A full measurement run takes several minutes, because every tamper case, every query batch and every open is timed in a fresh process. `scripts/derive_metrics.py` is a separate pass over the source tree: it counts the crates, the files, the lines, the statement kinds, the expression variants and the page roles, and it extracts the predicates the planner can answer from the inverted index. Its output is `scripts/out/metrics.json`, which is the second input of `scripts/make_artifacts.py`. ## Building the paper Requires a TeX distribution with `pdflatex`, `bibtex`, `natbib`, `booktabs`, `graphicx` and `microtype`, or `tectonic`, which fetches the packages on demand and runs `bibtex` itself: ```bash pdflatex main && bibtex main && pdflatex main && pdflatex main ``` or ```bash tectonic main.tex ``` `common.tex` must stay byte-identical to the shared copy: ```bash cmp common.tex ../_shared/common.tex && echo identical ``` ## Submission steps 1. Start a new arXiv submission at . 2. Choose **cs.CR** as the primary category; add **cs.DB** as a cross-list. 3. Paste the title and the abstract above; author `Daozhendong Yang` (or `yxpil`, but use one identity consistently across the paper, the arXiv account, and this README). 4. Upload `nebula-arxiv.tar.gz`. arXiv detects `main.tex` and runs `pdflatex` + `bibtex`. 5. Inspect the auto-built PDF: 5 figures, 7 tables, no overfull boxes that push text into the margin. 6. Select a license and submit. A first cs.CR submission may require an endorsement. ## Artifact provenance - Repository commit: `7e1273e6255b4244a2e67e1d3abdd72d37abf676` - Binary SHA-256: `864a9b6f1b9a52b13c2688cf2de3fc73771b55a4775f1bb593d03e77fb9aa150` - Binary size: 7,267,328 bytes (6.93 MiB) - Source: 10 crates, 43 Rust files, 14,504 lines, 153 tests - Compiler: rustc 1.98.1 (48a229cea 2026-09-01) - Profile: release - Host: Windows 11 (10.0.26300) - Artifact generated: 2026-10-25T03:45:56Z - Harness: Python 3.13, `perf_counter`, medians over repeated sessions The measurements are host-specific. The open cost is dominated by the Argon2id parameters and would be different on a machine with more memory bandwidth; the scan cost is dominated by the per-record page read and would be different on a faster disk. The JSON records the binary hash and the compiler version so that the same experiments can be repeated elsewhere. ## Limitations stated in the paper The tamper matrix is 13 mutations of one file, so it is a sample of the mutation space and not the space. The rollback is a single run. The paper does not attack the key schedule, does not test nonce reuse across processes or key reuse across databases, and does not cover the behaviour of the format under a partial write or a power loss. The anchor is a construction in the paper, not a component of the system: it was implemented in the harness rather than in the engine, and its security rests on an assumption about where the anchor file lives that was not tested.