prikk_store/
state_root.rs

1//! Canonical format-2 clean-state Merkle authority.
2
3use std::collections::BTreeSet;
4
5use prikk_error::{PrikkError, Result};
6use prikk_hash::sha256;
7use prikk_object::{MerkleRoot, NodeId, NodeKind, ObjectId};
8
9use crate::node_lifecycle::{NodeContent, NodeLifecycleState};
10use crate::path::{RepoPath, validate_no_path_collisions};
11
12const LEAF_DOMAIN: &[u8] = b"PRIKK-STATE-LEAF-v2";
13const NODE_DOMAIN: &[u8] = b"PRIKK-STATE-NODE-v2";
14const ROOT_DOMAIN: &[u8] = b"PRIKK-STATE-ROOT-v2";
15const REGULAR_MODE: u32 = 0o100644;
16const EXECUTABLE_MODE: u32 = 0o100755;
17
18/// Content identity committed by one canonical clean-state entry.
19#[derive(Debug, Clone, PartialEq, Eq)]
20pub enum StateRootContent {
21    /// Schema-1 Blob object identity for a text or binary file.
22    Blob(ObjectId),
23    /// Exact opaque schema-1 UTF-8 symlink target.
24    Symlink(String),
25}
26
27/// One canonical format-2 clean-state entry.
28#[derive(Debug, Clone, PartialEq, Eq)]
29pub struct StateRootEntry {
30    /// Canonical repository path.
31    pub path: RepoPath,
32    /// Nonzero stable node identity.
33    pub node_id: NodeId,
34    /// Text, binary, or symlink node kind.
35    pub kind: NodeKind,
36    /// Normalized file mode; symlinks require zero.
37    pub mode: u32,
38    /// Blob identity or exact symlink target.
39    pub content: StateRootContent,
40}
41
42/// Construct the exact format-2 leaf preimage for one validated entry.
43pub fn state_leaf_preimage(entry: &StateRootEntry) -> Result<Vec<u8>> {
44    validate_entry(entry)?;
45    let path = entry.path.as_str().as_bytes();
46    let path_len = u32::try_from(path.len())
47        .map_err(|_| PrikkError::Integrity("state-root path length exceeds u32".to_string()))?;
48    let content = content_bytes(entry);
49    let content_len = u64::try_from(content.len())
50        .map_err(|_| PrikkError::Integrity("state-root content length exceeds u64".to_string()))?;
51    let mut preimage =
52        Vec::with_capacity(LEAF_DOMAIN.len() + 4 + path.len() + 32 + 2 + 4 + 8 + content.len());
53    preimage.extend_from_slice(LEAF_DOMAIN);
54    preimage.extend_from_slice(&path_len.to_be_bytes());
55    preimage.extend_from_slice(path);
56    preimage.extend_from_slice(entry.node_id.as_bytes());
57    preimage.extend_from_slice(&entry.kind.code().to_be_bytes());
58    preimage.extend_from_slice(&entry.mode.to_be_bytes());
59    preimage.extend_from_slice(&content_len.to_be_bytes());
60    preimage.extend_from_slice(content);
61    Ok(preimage)
62}
63
64/// Hash one validated canonical format-2 clean-state entry.
65pub fn state_leaf_hash(entry: &StateRootEntry) -> Result<[u8; 32]> {
66    Ok(sha256(&state_leaf_preimage(entry)?))
67}
68
69/// Compute the format-2 state root from entries in strict canonical path order.
70pub fn compute_state_root(entries: &[StateRootEntry]) -> Result<MerkleRoot> {
71    validate_entries(entries)?;
72    let count = u64::try_from(entries.len())
73        .map_err(|_| PrikkError::Integrity("state-root entry count exceeds u64".to_string()))?;
74    if entries.is_empty() {
75        let mut preimage = Vec::with_capacity(ROOT_DOMAIN.len() + 8);
76        preimage.extend_from_slice(ROOT_DOMAIN);
77        preimage.extend_from_slice(&count.to_be_bytes());
78        return Ok(MerkleRoot(sha256(&preimage)));
79    }
80    let mut level = entries
81        .iter()
82        .map(state_leaf_hash)
83        .collect::<Result<Vec<_>>>()?;
84    while level.len() > 1 {
85        let mut next = Vec::with_capacity(level.len().div_ceil(2));
86        for pair in level.chunks(2) {
87            match pair {
88                [left, right] => {
89                    let mut preimage = Vec::with_capacity(NODE_DOMAIN.len() + 64);
90                    preimage.extend_from_slice(NODE_DOMAIN);
91                    preimage.extend_from_slice(left);
92                    preimage.extend_from_slice(right);
93                    next.push(sha256(&preimage));
94                }
95                [single] => next.push(*single),
96                _ => {}
97            }
98        }
99        level = next;
100    }
101    let top = level.first().ok_or_else(|| {
102        PrikkError::Integrity("non-empty state-root reduction produced no hash".to_string())
103    })?;
104    let mut preimage = Vec::with_capacity(ROOT_DOMAIN.len() + 8 + 32);
105    preimage.extend_from_slice(ROOT_DOMAIN);
106    preimage.extend_from_slice(&count.to_be_bytes());
107    preimage.extend_from_slice(top);
108    Ok(MerkleRoot(sha256(&preimage)))
109}
110
111pub(crate) fn entries_from_state(state: &NodeLifecycleState) -> Result<Vec<StateRootEntry>> {
112    let mut entries = state
113        .live_nodes()
114        .map(|(node_id, node)| {
115            let (mode, content) = match &node.content {
116                NodeContent::File { blob_id, mode } => (*mode, StateRootContent::Blob(*blob_id)),
117                NodeContent::Symlink { target } => (0, StateRootContent::Symlink(target.clone())),
118            };
119            StateRootEntry {
120                path: node.path.clone(),
121                node_id: *node_id,
122                kind: node.kind,
123                mode,
124                content,
125            }
126        })
127        .collect::<Vec<_>>();
128    entries.sort_by(|left, right| {
129        left.path
130            .as_str()
131            .as_bytes()
132            .cmp(right.path.as_str().as_bytes())
133    });
134    validate_entries(&entries)?;
135    Ok(entries)
136}
137
138fn validate_entries(entries: &[StateRootEntry]) -> Result<()> {
139    let paths = entries
140        .iter()
141        .map(|entry| entry.path.clone())
142        .collect::<Vec<_>>();
143    validate_no_path_collisions(&paths)?;
144    if !entries.windows(2).all(
145        |pair| matches!(pair, [left, right] if left.path.as_str().as_bytes() < right.path.as_str().as_bytes()),
146    ) {
147        return Err(PrikkError::Integrity(
148            "state-root entries are not in strict canonical path order".to_string(),
149        ));
150    }
151    let mut node_ids = BTreeSet::new();
152    for entry in entries {
153        validate_entry(entry)?;
154        if !node_ids.insert(entry.node_id) {
155            return Err(PrikkError::Integrity(
156                "state-root entries contain a duplicate node_id".to_string(),
157            ));
158        }
159    }
160    Ok(())
161}
162
163fn validate_entry(entry: &StateRootEntry) -> Result<()> {
164    if entry.node_id.is_zero() {
165        return Err(PrikkError::Integrity(
166            "state-root entry node_id must be nonzero".to_string(),
167        ));
168    }
169    match (&entry.kind, &entry.content, entry.mode) {
170        (
171            NodeKind::TextFile | NodeKind::BinaryFile,
172            StateRootContent::Blob(_),
173            REGULAR_MODE | EXECUTABLE_MODE,
174        ) => Ok(()),
175        (NodeKind::Symlink, StateRootContent::Symlink(_), 0) => Ok(()),
176        _ => Err(PrikkError::Integrity(
177            "state-root entry kind, content, or normalized mode is invalid".to_string(),
178        )),
179    }
180}
181
182fn content_bytes(entry: &StateRootEntry) -> &[u8] {
183    match &entry.content {
184        StateRootContent::Blob(blob_id) => blob_id.as_bytes(),
185        StateRootContent::Symlink(target) => target.as_bytes(),
186    }
187}
188
189#[cfg(test)]
190mod tests;
prikk_store/state_root.rs

prikk_store/
state_root.rs
