askrobots / dbbasic-object-server
Public
Runs live, versioned Python application objects on one VM, with a suite of apps: projects, notes, tasks, files and more.
danq9
signup: the person chooses the password and name on the confirm page
83c7aa6
2 weeks, 5 days ago
History
object_ledger_head.py · 11.7 KB · 280 lines
| 1 | """object_ledger_head -- one digest that stands for a whole ledger, and |
| 2 | the verdict on whether that ledger still reproduces it. |
| 3 | |
| 4 | Pure. No I/O, no clock, no data directory. |
| 5 | |
| 6 | ## The simplification this module is built on |
| 7 | |
| 8 | plan/tamper-evidence-spec.md described a hash chain written into the |
| 9 | storage layer: every row carrying the hash of the one before it, computed |
| 10 | under the append lock. That is real work and it is not what shipped here, |
| 11 | because of an observation that makes most of it unnecessary: |
| 12 | |
| 13 | **For an append-only log, a PREFIX DIGEST is a chain head.** A hash chain |
| 14 | is simply an incremental way of computing prefix digests cheaply as rows |
| 15 | arrive. If the digest is only wanted once a day, over a file that is being |
| 16 | read anyway, it can be computed directly in one pass -- no per-row column, |
| 17 | no storage-layer change, and no risk of two concurrent appends forking the |
| 18 | chain, which was the specific hazard that kept the package-layer version |
| 19 | off the table. |
| 20 | |
| 21 | `head()` below is literally the chain fold, run over the rows in order. So |
| 22 | the value it produces is the value an incremental in-storage chain would |
| 23 | produce, and moving the computation into the append path later would NOT |
| 24 | invalidate a single anchor already published. That is the property that |
| 25 | makes shipping the cheap version now safe rather than a detour. |
| 26 | |
| 27 | ## What is hashed, and the two decisions that matter |
| 28 | |
| 29 | **Logical rows, never file bytes.** Hashing the file would be simpler and |
| 30 | would break on the first compaction: compaction rewrites an append log -- |
| 31 | folding updates, dropping deleted rows, rewriting the header -- so a |
| 32 | byte-level digest would report tampering every time routine maintenance |
| 33 | ran, and an integrity check that cries wolf on schedule is one nobody |
| 34 | reads by the third week. What is hashed is the folded rows the rest of |
| 35 | this system sees. |
| 36 | |
| 37 | **The field list is part of the anchor, not read from today's schema.** |
| 38 | Anchoring records which fields were covered, and verification reads THOSE |
| 39 | fields out of today's rows. Without this, adding a field to a schema would |
| 40 | change every historical digest at once and look exactly like a break -- |
| 41 | turning an ordinary migration into an integrity alarm, which again teaches |
| 42 | an operator to ignore the alarm. With it, a new field simply is not |
| 43 | covered by old anchors, which is true and harmless. |
| 44 | |
| 45 | ## What an anchor proves, and the honest limit |
| 46 | |
| 47 | An anchor is `(row_count, digest)` at a moment. Verifying it says: the |
| 48 | first `row_count` rows of this ledger are still, byte for byte in their |
| 49 | canonical form, what they were when the anchor was taken. |
| 50 | |
| 51 | That is a strong statement and it has an exact boundary: **it is only |
| 52 | worth what the anchor's storage is worth.** An anchor row sitting in the |
| 53 | same data directory as the ledger is defeated by anybody who can edit |
| 54 | both, which is everybody who could edit the ledger in the first place. |
| 55 | The value appears when the digest is lodged somewhere else -- with an |
| 56 | independent notary (app-notary), on another machine, in a mailbox at a |
| 57 | different provider. `system_publish_head` does the lodging; this module |
| 58 | does the arithmetic, and the arithmetic is the easy half. |
| 59 | |
| 60 | ## Locating a break |
| 61 | |
| 62 | A single anchor says "something in the first N rows changed" and cannot |
| 63 | say which row -- naming the row needs a per-row hash, which is the |
| 64 | in-storage chain. But anchors accumulate: a daily pass leaves a ladder of |
| 65 | them at increasing row counts, and `locate()` walks that ladder to bracket |
| 66 | a break between the newest anchor that still verifies and the oldest that |
| 67 | does not. With daily anchoring that is a day-sized window on which rows |
| 68 | were touched, from a fold that stores one line a day. |
| 69 | """ |
| 70 | |
| 71 | import hashlib |
| 72 | |
| 73 | ALGORITHM = "sha256" |
| 74 | |
| 75 | # Versioned and mixed into the genesis, so a future change to the |
| 76 | # canonical form is a DIFFERENT digest rather than a silently |
| 77 | # incompatible one. An anchor that verifies under a scheme it was not |
| 78 | # computed with would be the worst possible bug in this file. |
| 79 | SCHEME = "dbbasic-ledger-head-v1" |
| 80 | |
| 81 | |
| 82 | def canonical_row(row, fields): |
| 83 | """One row as bytes, injectively. |
| 84 | |
| 85 | Length-prefixed rather than delimiter-joined, on purpose. A naive |
| 86 | "\\t".join(values) is only injective while no value can contain a tab |
| 87 | -- true of TSV storage today, and a coupling between the integrity |
| 88 | digest and the storage format that nobody would remember when the |
| 89 | coupling stopped holding. Two rows that differ must produce different |
| 90 | bytes under every possible content, or an attacker gets to move |
| 91 | characters across a field boundary without changing the digest. |
| 92 | |
| 93 | A field the row does not have reads as empty, which is what makes an |
| 94 | anchor survive a schema gaining a column. |
| 95 | """ |
| 96 | parts = [] |
| 97 | for field in fields: |
| 98 | value = row.get(field) |
| 99 | text = "" if value is None else str(value) |
| 100 | encoded = text.encode("utf-8") |
| 101 | parts.append(str(len(encoded)).encode("ascii")) |
| 102 | parts.append(b":") |
| 103 | parts.append(encoded) |
| 104 | parts.append(b"|") |
| 105 | return b"".join(parts) |
| 106 | |
| 107 | |
| 108 | def genesis(collection, fields): |
| 109 | """The starting value of the fold. |
| 110 | |
| 111 | Binds the digest to the collection name and the exact field list, so |
| 112 | an anchor taken over `wallet_entries` cannot be checked against |
| 113 | `payments` and come out clean, and so a field list that differs by one |
| 114 | column is a different chain rather than a coincidence. |
| 115 | """ |
| 116 | seed = "\n".join([SCHEME, str(collection), ",".join(fields)]) |
| 117 | return hashlib.sha256(seed.encode("utf-8")).hexdigest() |
| 118 | |
| 119 | |
| 120 | def link(previous, row, fields): |
| 121 | """One step of the chain: the new head after appending `row`. |
| 122 | |
| 123 | Exposed separately from `head()` because it is the function an |
| 124 | in-storage chain would call per append. Whatever computes it, the |
| 125 | value is the same -- which is what lets the expensive version replace |
| 126 | the cheap one later without orphaning anchors already published. |
| 127 | """ |
| 128 | digest = hashlib.sha256() |
| 129 | digest.update(str(previous).encode("ascii")) |
| 130 | digest.update(b"\n") |
| 131 | digest.update(canonical_row(row, fields)) |
| 132 | return digest.hexdigest() |
| 133 | |
| 134 | |
| 135 | def head(rows, fields, *, collection="", count=None): |
| 136 | """The head over the first `count` rows (all of them by default). |
| 137 | |
| 138 | Returns the count actually covered alongside the digest, because a |
| 139 | digest without its row count is unverifiable: the whole verification |
| 140 | is "recompute over the same prefix", and the prefix has to be named. |
| 141 | """ |
| 142 | fields = list(fields) |
| 143 | rows = list(rows) |
| 144 | if count is None: |
| 145 | count = len(rows) |
| 146 | count = max(0, min(int(count), len(rows))) |
| 147 | |
| 148 | value = genesis(collection, fields) |
| 149 | for row in rows[:count]: |
| 150 | value = link(value, row, fields) |
| 151 | return { |
| 152 | "collection": str(collection), |
| 153 | "algorithm": ALGORITHM, |
| 154 | "scheme": SCHEME, |
| 155 | "fields": list(fields), |
| 156 | "row_count": count, |
| 157 | "digest": value, |
| 158 | } |
| 159 | |
| 160 | |
| 161 | def verify(rows, anchor): |
| 162 | """Does this ledger still reproduce that anchor? |
| 163 | |
| 164 | Reads the field list and the row count OUT OF THE ANCHOR rather than |
| 165 | from today's schema, which is what stops an ordinary migration |
| 166 | presenting as tampering. |
| 167 | |
| 168 | Three outcomes, and the middle one is the interesting one: |
| 169 | |
| 170 | * `verified` -- the anchored prefix is unchanged. |
| 171 | * `truncated` -- the ledger now has FEWER rows than the anchor |
| 172 | covered. Rows have been removed, which in an append-only ledger is |
| 173 | not something ordinary operation does. Reported separately from a |
| 174 | content mismatch because the remedy is different: a mismatch means |
| 175 | find what changed, a truncation means find what is missing. |
| 176 | * `mismatch` -- the prefix is the right length and hashes differently. |
| 177 | Something inside it was edited. |
| 178 | |
| 179 | Retention deliberately produces `truncated`, and that is correct |
| 180 | rather than a false alarm: pruning a ledger really does destroy the |
| 181 | evidence an anchor was taken over. A collection that is both anchored |
| 182 | and pruned is a configuration mistake, and this is where it surfaces. |
| 183 | """ |
| 184 | fields = list(anchor.get("fields") or []) |
| 185 | collection = str(anchor.get("collection") or "") |
| 186 | expected = str(anchor.get("digest") or "") |
| 187 | try: |
| 188 | anchored_rows = int(anchor.get("row_count") or 0) |
| 189 | except (TypeError, ValueError): |
| 190 | anchored_rows = 0 |
| 191 | |
| 192 | rows = list(rows) |
| 193 | if not expected or not fields: |
| 194 | return {"status": "unusable", "verified": False, |
| 195 | "detail": "The anchor carries no digest or no field list, so " |
| 196 | "there is nothing to check it against."} |
| 197 | |
| 198 | if len(rows) < anchored_rows: |
| 199 | return { |
| 200 | "status": "truncated", |
| 201 | "verified": False, |
| 202 | "anchored_rows": anchored_rows, |
| 203 | "present_rows": len(rows), |
| 204 | "detail": (f"The anchor covered {anchored_rows:,} rows and the " |
| 205 | f"ledger now holds {len(rows):,}. Rows an anchor was " |
| 206 | f"taken over have been removed."), |
| 207 | } |
| 208 | |
| 209 | recomputed = head(rows, fields, collection=collection, count=anchored_rows) |
| 210 | if recomputed["digest"] == expected: |
| 211 | return { |
| 212 | "status": "verified", |
| 213 | "verified": True, |
| 214 | "anchored_rows": anchored_rows, |
| 215 | "present_rows": len(rows), |
| 216 | "detail": (f"The first {anchored_rows:,} rows are unchanged since " |
| 217 | f"this anchor was taken."), |
| 218 | } |
| 219 | return { |
| 220 | "status": "mismatch", |
| 221 | "verified": False, |
| 222 | "anchored_rows": anchored_rows, |
| 223 | "present_rows": len(rows), |
| 224 | "expected": expected, |
| 225 | "actual": recomputed["digest"], |
| 226 | "detail": (f"The first {anchored_rows:,} rows no longer hash to what " |
| 227 | f"was anchored. Something inside them was changed after " |
| 228 | f"the fact."), |
| 229 | } |
| 230 | |
| 231 | |
| 232 | def locate(rows, anchors): |
| 233 | """Bracket a break between the anchors that pass and the ones that fail. |
| 234 | |
| 235 | One anchor can only say "something in the first N rows changed". A |
| 236 | LADDER of anchors -- which is what a daily pass leaves behind -- says |
| 237 | more: the newest anchor that still verifies puts a floor under the |
| 238 | break, and the oldest that fails puts a ceiling on it. With daily |
| 239 | anchoring that brackets an edit to the rows added on one particular |
| 240 | day, which is usually enough to find it by hand. |
| 241 | |
| 242 | Naming the exact row needs a per-row hash, and that is the in-storage |
| 243 | chain this module deliberately did not build. Reporting the window is |
| 244 | the honest thing a prefix digest can do, and it costs one line a day. |
| 245 | """ |
| 246 | checked = [] |
| 247 | for anchor in anchors or (): |
| 248 | result = verify(rows, anchor) |
| 249 | checked.append({ |
| 250 | "anchor": anchor, |
| 251 | "row_count": result.get("anchored_rows", 0), |
| 252 | "status": result["status"], |
| 253 | "verified": result["verified"], |
| 254 | }) |
| 255 | checked.sort(key=lambda entry: entry["row_count"]) |
| 256 | |
| 257 | good = [entry for entry in checked if entry["verified"]] |
| 258 | bad = [entry for entry in checked if not entry["verified"]] |
| 259 | if not bad: |
| 260 | return {"broken": False, "checked": len(checked), |
| 261 | "detail": ("Every anchor verifies." if checked else |
| 262 | "No anchors have been taken, so there is nothing " |
| 263 | "to verify against.")} |
| 264 | |
| 265 | floor = max((entry["row_count"] for entry in good), default=0) |
| 266 | ceiling = min(entry["row_count"] for entry in bad) |
| 267 | return { |
| 268 | "broken": True, |
| 269 | "checked": len(checked), |
| 270 | "failed": len(bad), |
| 271 | "first_bad_row_count": ceiling, |
| 272 | "last_good_row_count": floor, |
| 273 | "detail": (f"A change lies between row {floor + 1:,} and row " |
| 274 | f"{ceiling:,}. The anchor at {floor:,} rows still " |
| 275 | f"verifies; the one at {ceiling:,} does not." |
| 276 | if good else |
| 277 | f"Every anchor fails, including the earliest at " |
| 278 | f"{ceiling:,} rows. Either the change is very old or the " |
| 279 | f"field list has moved under them."), |
| 280 | } |