Runs live, versioned Python application objects on one VM, with a suite of apps: projects, notes, tasks, files and more.

0 downloads

dbbasic-object-server/object_ledger_head.py
Download zip
Clone
Clone with git
git clone https://gitstable.com/git/askrobots/dbbasic-object-server.git
HTTPS
https://gitstable.com/git/askrobots/dbbasic-object-server.git
SSH
ssh://git@gitstable.com:2222/askrobots/dbbasic-object-server.git

Cloning needs no sign-in. Pushing over HTTPS asks for your username and an access token. SSH needs your key under SSH keys.

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
2the verdict on whether that ledger still reproduces it.
3
4Pure. No I/O, no clock, no data directory.
5
6## The simplification this module is built on
7
8plan/tamper-evidence-spec.md described a hash chain written into the
9storage layer: every row carrying the hash of the one before it, computed
10under the append lock. That is real work and it is not what shipped here,
11because 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
14is simply an incremental way of computing prefix digests cheaply as rows
15arrive. If the digest is only wanted once a day, over a file that is being
16read anyway, it can be computed directly in one pass -- no per-row column,
17no storage-layer change, and no risk of two concurrent appends forking the
18chain, which was the specific hazard that kept the package-layer version
19off the table.
20
21`head()` below is literally the chain fold, run over the rows in order. So
22the value it produces is the value an incremental in-storage chain would
23produce, and moving the computation into the append path later would NOT
24invalidate a single anchor already published. That is the property that
25makes 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
30would break on the first compaction: compaction rewrites an append log --
31folding updates, dropping deleted rows, rewriting the header -- so a
32byte-level digest would report tampering every time routine maintenance
33ran, and an integrity check that cries wolf on schedule is one nobody
34reads by the third week. What is hashed is the folded rows the rest of
35this system sees.
36
37**The field list is part of the anchor, not read from today's schema.**
38Anchoring records which fields were covered, and verification reads THOSE
39fields out of today's rows. Without this, adding a field to a schema would
40change every historical digest at once and look exactly like a break --
41turning an ordinary migration into an integrity alarm, which again teaches
42an operator to ignore the alarm. With it, a new field simply is not
43covered by old anchors, which is true and harmless.
44
45## What an anchor proves, and the honest limit
46
47An anchor is `(row_count, digest)` at a moment. Verifying it says: the
48first `row_count` rows of this ledger are still, byte for byte in their
49canonical form, what they were when the anchor was taken.
50
51That is a strong statement and it has an exact boundary: **it is only
52worth what the anchor's storage is worth.** An anchor row sitting in the
53same data directory as the ledger is defeated by anybody who can edit
54both, which is everybody who could edit the ledger in the first place.
55The value appears when the digest is lodged somewhere else -- with an
56independent notary (app-notary), on another machine, in a mailbox at a
57different provider. `system_publish_head` does the lodging; this module
58does the arithmetic, and the arithmetic is the easy half.
59
60## Locating a break
61
62A single anchor says "something in the first N rows changed" and cannot
63say which row -- naming the row needs a per-row hash, which is the
64in-storage chain. But anchors accumulate: a daily pass leaves a ladder of
65them at increasing row counts, and `locate()` walks that ladder to bracket
66a break between the newest anchor that still verifies and the oldest that
67does not. With daily anchoring that is a day-sized window on which rows
68were touched, from a fold that stores one line a day.
69"""
70
71import hashlib
72
73ALGORITHM = "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.
79SCHEME = "dbbasic-ledger-head-v1"
80
81
82def 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
108def 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
120def 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
135def 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
161def 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
232def 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 }