storage/
verified_prefix.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at https://mozilla.org/MPL/2.0/.
4// Copyright (c) 2026 2youg1 and the sprawling contributors
5
6//! What a strict walk of the chain proved, one record per segment, so the
7//! next proof reads and hashes those bytes instead of checking them line
8//! by line again (`crates/storage/spec/ChainAudit.lean` §8-30).
9//!
10//! A projection: a record that is missing, damaged, of another rule
11//! version, or out of step with the chain state entering its segment is
12//! not used, and that segment is checked line by line. That reusing a
13//! record gives the strict verdict is `cachedVerifyIsStrict` in
14//! `crates/storage/spec/Snapshot.lean`.
15
16use std::io;
17use std::path::{Path, PathBuf};
18
19use kernel::{B3Hash, Seq};
20
21use crate::chain_audit::ProofCount;
22use crate::error::StorageError;
23use crate::jsonl::{JsonlLedger, LineCheck};
24use crate::real_fs::RealFs;
25use crate::vfs::Vfs;
26
27/// Changed whenever the per-line check changes what it accepts within one
28/// version of this binary; a new version discards every record anyway,
29/// because [`line_check_version`] hashes the version in with this. The
30/// suffix is the digest of a fixed fixture's verdicts, which
31/// `chain_audit::tests` holds, so the rule cannot move alone.
32pub(crate) const LINE_CHECK_RULES: &str = "line-check-40e703f48b222ca7";
33
34const MAGIC: &[u8; 8] = b"SPRPRF01";
35const SUFFIX: &str = ".proof";
36const STAGED: &str = ".staged";
37
38/// The rule version a record is written and accepted under.
39pub fn line_check_version() -> u32 {
40    let rules = [env!("CARGO_PKG_VERSION"), LINE_CHECK_RULES].join("\n");
41    let [a, b, c, d, ..] = *B3Hash::digest(rules.as_bytes()).as_bytes();
42    u32::from_le_bytes([a, b, c, d])
43}
44
45/// Where a city's records live, and whether this holder may write them.
46#[derive(Debug, Clone)]
47pub struct ProofRecords {
48    dir: PathBuf,
49    may: May,
50}
51
52/// Only a handle that holds the writer lock writes records, so a
53/// read-only command never touches the disk (`crates/storage/spec/ChainAudit.lean` §8-30).
54#[derive(Debug, Clone, Copy, PartialEq, Eq)]
55enum May {
56    Read,
57    ReadAndWrite,
58}
59
60impl ProofRecords {
61    /// Records read, never written: `ask`, `replay`, and any holder that
62    /// does not hold the writer lock.
63    pub fn read_only(dir: &Path) -> ProofRecords {
64        ProofRecords {
65            dir: dir.to_path_buf(),
66            may: May::Read,
67        }
68    }
69
70    /// The record of the segment named `segment`, when there is one this
71    /// build can read. Absent, unreadable and damaged all answer `None`:
72    /// the segment is then checked line by line, which is the answer this
73    /// projection gives to every doubt.
74    pub(crate) fn read(&self, segment: &str) -> Option<SegmentRecord> {
75        let path = self.path_of(segment);
76        match RealFs::new().read(&path) {
77            Ok(bytes) => SegmentRecord::decode(&bytes),
78            Err(_unreadable) => None,
79        }
80    }
81
82    /// Writes `record` for `segment`, replacing the one there; nothing
83    /// for a read-only holder.
84    ///
85    /// # Errors
86    /// `StorageError::Snapshot` naming the step that failed.
87    pub(crate) fn keep(&self, segment: &str, record: &SegmentRecord) -> Result<(), StorageError> {
88        match self.may {
89            May::Read => Ok(()),
90            May::ReadAndWrite => self.write(segment, record),
91        }
92    }
93
94    fn write(&self, segment: &str, record: &SegmentRecord) -> Result<(), StorageError> {
95        let mut vfs = RealFs::new();
96        let file = self.path_of(segment);
97        let staged = self.dir.join(format!("{segment}{SUFFIX}{STAGED}"));
98        vfs.create_dir_all(&self.dir)
99            .map_err(refused("create the proof records dir", &self.dir))?;
100        if vfs.exists(&staged) {
101            vfs.remove_file(&staged)
102                .map_err(refused("remove a staged proof record", &staged))?;
103        }
104        vfs.append(&staged, &record.encode())
105            .map_err(refused("write a staged proof record", &staged))?;
106        vfs.sync_data(&staged)
107            .map_err(refused("sync a staged proof record", &staged))?;
108        vfs.rename(&staged, &file)
109            .map_err(refused("rename a staged proof record", &file))?;
110        vfs.sync_dir(&self.dir)
111            .map_err(refused("sync the proof records dir", &self.dir))
112    }
113
114    fn path_of(&self, segment: &str) -> PathBuf {
115        self.dir.join(format!("{segment}{SUFFIX}"))
116    }
117}
118
119/// Where checking a ledger's last segment begins when the ledger is
120/// opened: the byte, the lines before it, the chain state there, and what
121/// was read and hashed to get there (`crates/storage/spec/Jsonl.lean` §8-34).
122pub(crate) struct TailStart {
123    pub(crate) from: usize,
124    pub(crate) lines: u64,
125    pub(crate) check: LineCheck,
126    pub(crate) counted: ProofCount,
127}
128
129impl TailStart {
130    /// From the first byte of `bytes`, the whole segment read, at `entry`.
131    pub(crate) fn strict(bytes: &[u8], entry: LineCheck) -> TailStart {
132        TailStart {
133            from: 0,
134            lines: 0,
135            check: entry,
136            counted: ProofCount {
137                bytes_read: u64::try_from(bytes.len()).unwrap_or(u64::MAX),
138                ..ProofCount::default()
139            },
140        }
141    }
142}
143
144impl ProofRecords {
145    /// Where checking `bytes`, the last segment `segment` entered at
146    /// `entry`, begins: after the prefix its record proves when the record
147    /// stands for it (`SegmentRecord::prefix`, `SegmentRecord::stands`),
148    /// and at the first byte otherwise. The bytes hashed are the bytes
149    /// then checked: one read.
150    pub(crate) fn tail_start(&self, segment: &str, bytes: &[u8], entry: LineCheck) -> TailStart {
151        let strict = TailStart::strict(bytes, entry);
152        let Some(record) = self.read(segment) else {
153            return strict;
154        };
155        let Some(prefix) = record.prefix(bytes, line_check_version()) else {
156            return strict;
157        };
158        let mut hasher = blake3::Hasher::new();
159        hasher.update(prefix);
160        let hashed = u64::try_from(prefix.len()).unwrap_or(u64::MAX);
161        match record.stands(entry, &hasher) {
162            None => TailStart {
163                counted: ProofCount {
164                    bytes_hashed: hashed,
165                    ..strict.counted
166                },
167                ..strict
168            },
169            Some((lines, exit)) => TailStart {
170                from: prefix.len(),
171                lines,
172                check: exit,
173                counted: ProofCount {
174                    segments_by_digest: 1,
175                    bytes_hashed: hashed,
176                    ..strict.counted
177                },
178            },
179        }
180    }
181}
182
183impl JsonlLedger {
184    /// The records of this ledger's proofs, kept in `dir`: writable when
185    /// this handle holds the ledger's writer lock, read-only otherwise.
186    pub fn proof_records(&self, dir: &Path) -> ProofRecords {
187        ProofRecords {
188            dir: dir.to_path_buf(),
189            may: match self.lock {
190                Some(_) => May::ReadAndWrite,
191                None => May::Read,
192            },
193        }
194    }
195}
196
197/// What a strict walk proved about the first `len` bytes of one segment.
198#[derive(Debug, Clone, PartialEq, Eq)]
199pub(crate) struct SegmentRecord {
200    pub(crate) version: u32,
201    /// The length of the proved prefix: always the end of a complete line.
202    pub(crate) len: u64,
203    pub(crate) lines: u64,
204    pub(crate) entry: LineCheck,
205    pub(crate) exit: LineCheck,
206    pub(crate) digest: B3Hash,
207}
208
209impl SegmentRecord {
210    /// `MAGIC | version u32 | len u64 | lines u64 | entry | exit | digest |
211    /// blake3 of everything before it`, a chain state being its `prev`
212    /// hash and the seq it expects, little-endian.
213    fn encode(&self) -> Vec<u8> {
214        let body = [
215            MAGIC.as_slice(),
216            &self.version.to_le_bytes(),
217            &self.len.to_le_bytes(),
218            &self.lines.to_le_bytes(),
219            self.entry.prev().as_bytes(),
220            &self.entry.expected().value().to_le_bytes(),
221            self.exit.prev().as_bytes(),
222            &self.exit.expected().value().to_le_bytes(),
223            self.digest.as_bytes(),
224        ]
225        .concat();
226        let seal = B3Hash::digest(&body);
227        [body.as_slice(), seal.as_bytes()].concat()
228    }
229
230    /// The record `encode` wrote; `None` for bytes that are not one.
231    fn decode(bytes: &[u8]) -> Option<SegmentRecord> {
232        let (body, seal) = bytes.split_last_chunk::<32>()?;
233        if B3Hash::digest(body).as_bytes() != seal {
234            return None;
235        }
236        let (magic, rest) = body.split_first_chunk::<8>()?;
237        if magic != MAGIC {
238            return None;
239        }
240        let (version, rest) = rest.split_first_chunk::<4>()?;
241        let (len, rest) = rest.split_first_chunk::<8>()?;
242        let (lines, rest) = rest.split_first_chunk::<8>()?;
243        let (entry, rest) = chain_state(rest)?;
244        let (exit, rest) = chain_state(rest)?;
245        let digest = <[u8; 32]>::try_from(rest).ok()?;
246        Some(SegmentRecord {
247            version: u32::from_le_bytes(*version),
248            len: u64::from_le_bytes(*len),
249            lines: u64::from_le_bytes(*lines),
250            entry,
251            exit,
252            digest: B3Hash::from_bytes(digest),
253        })
254    }
255}
256
257/// The judgement of one record, in two halves a proof can take apart:
258/// what the segment's own bytes decide, which a wave hashes before the
259/// walk reaches the segment, and what the chain entering it decides
260/// (`crates/storage/Spec.lean` §8-30, §8-34, §8-37). Together they are `reuses` in
261/// `crates/storage/spec/Snapshot.lean`, whose `cachedVerifyIsStrict`
262/// says a record that stands gives the strict verdict.
263impl SegmentRecord {
264    /// The first `len` bytes of `bytes` this record names, when it was
265    /// written under rule version `version` and the segment still holds
266    /// that much; `None` otherwise, and nothing is to be hashed.
267    pub(crate) fn prefix<'a>(&self, bytes: &'a [u8], version: u32) -> Option<&'a [u8]> {
268        if self.version != version {
269            return None;
270        }
271        usize::try_from(self.len)
272            .ok()
273            .and_then(|len| bytes.get(..len))
274    }
275
276    /// Whether this record stands in for the prefix `hashed` has hashed,
277    /// entered at `entry`: its entry and its digest must both match. The
278    /// answer is the lines the prefix held and the chain state after them.
279    pub(crate) fn stands(
280        &self,
281        entry: LineCheck,
282        hashed: &blake3::Hasher,
283    ) -> Option<(u64, LineCheck)> {
284        (self.entry == entry && B3Hash::from_bytes(*hashed.finalize().as_bytes()) == self.digest)
285            .then_some((self.lines, self.exit))
286    }
287}
288
289fn chain_state(bytes: &[u8]) -> Option<(LineCheck, &[u8])> {
290    let (prev, rest) = bytes.split_first_chunk::<32>()?;
291    let (expected, rest) = rest.split_first_chunk::<8>()?;
292    Some((
293        LineCheck::after(
294            B3Hash::from_bytes(*prev),
295            Seq::new(u64::from_le_bytes(*expected)),
296        ),
297        rest,
298    ))
299}
300
301/// The constructor of a record's I/O failure. A record is a projection
302/// like a snapshot, so it shares the snapshot's advice.
303fn refused(op: &'static str, path: &Path) -> impl FnOnce(io::Error) -> StorageError {
304    let path = path.to_path_buf();
305    move |source| StorageError::Snapshot { op, path, source }
306}
storage/verified_prefix.rs

storage/
verified_prefix.rs
