Skip to main content

personaldb_protocol/authenticated_state/
mod.rs

1//! Storage-independent construction of PersonalDB authenticated state roots.
2//!
3//! These primitives implement the exact algorithm used by PersonalDB commit
4//! `276515e624e91d3d0ac9f438d7d3a940ddf2ddb4`. They do not read a database or
5//! prescribe how rows, accumulators, or Merkle nodes are stored.
6
7use std::collections::{BTreeMap, BTreeSet};
8
9use serde::{Deserialize, Serialize};
10
11use crate::Sha256Digest;
12
13/// The fixed table tree has one leaf for each possible first byte of a row-key hash.
14pub const TABLE_MERKLE_DEPTH_V2: u32 = 8;
15
16pub const ROW_KEY_DOMAIN_V1: &str = "personaldb-row-key";
17pub const ROW_STATE_DOMAIN_V1: &str = "personaldb-row-state";
18pub const MERKLE_LEAF_DOMAIN_V2: &str = "personaldb-merkle-leaf-v2";
19pub const MERKLE_NODE_DOMAIN_V2: &str = "personaldb-merkle-node-v2";
20pub const DATABASE_ROOT_DOMAIN_V1: &str = "personaldb-database-root";
21pub const EMPTY_TABLE_DOMAIN_V1: &str = "personaldb-empty-table";
22
23/// Storage-neutral values in the exact externally-tagged JSON representation
24/// used by PersonalDB's authenticated row algorithm.
25///
26/// Values in a row must appear in managed-schema column order. Primary-key
27/// values must appear in declared primary-key order.
28#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
29pub enum CanonicalStateValueV1 {
30    Null,
31    Integer(i64),
32    Real(f64),
33    Text(String),
34    Blob(Vec<u8>),
35    Bool(bool),
36}
37
38impl CanonicalStateValueV1 {
39    fn validate(&self) -> Result<(), AuthenticatedStateError> {
40        if let Self::Real(value) = self
41            && !value.is_finite()
42        {
43            return Err(AuthenticatedStateError::NonFiniteReal);
44        }
45        Ok(())
46    }
47}
48
49/// Canonical JSON text for a row's ordered primary-key values.
50#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
51pub struct CanonicalPrimaryKeyV1(String);
52
53impl CanonicalPrimaryKeyV1 {
54    pub fn from_values(values: &[CanonicalStateValueV1]) -> Result<Self, AuthenticatedStateError> {
55        if values.is_empty() {
56            return Err(AuthenticatedStateError::EmptyPrimaryKey);
57        }
58        validate_values(values)?;
59        Ok(Self(serde_json::to_string(values)?))
60    }
61
62    pub fn as_str(&self) -> &str {
63        &self.0
64    }
65
66    pub fn into_string(self) -> String {
67        self.0
68    }
69}
70
71/// One committed managed row, independent of any storage engine.
72#[derive(Debug, Clone, PartialEq)]
73pub struct AuthenticatedRowV1 {
74    pub primary_key: Vec<CanonicalStateValueV1>,
75    pub stored_values: Vec<CanonicalStateValueV1>,
76}
77
78impl AuthenticatedRowV1 {
79    pub fn new(
80        primary_key: Vec<CanonicalStateValueV1>,
81        stored_values: Vec<CanonicalStateValueV1>,
82    ) -> Self {
83        Self {
84            primary_key,
85            stored_values,
86        }
87    }
88}
89
90/// XOR accumulator and row count for one of the 256 sparse table leaves.
91#[derive(Debug, Clone, Copy, PartialEq, Eq)]
92pub struct MerkleLeafAccumulatorV2 {
93    accumulator_xor: [u8; 32],
94    row_count: u64,
95}
96
97impl Default for MerkleLeafAccumulatorV2 {
98    fn default() -> Self {
99        Self::EMPTY
100    }
101}
102
103impl MerkleLeafAccumulatorV2 {
104    pub const EMPTY: Self = Self {
105        accumulator_xor: [0; 32],
106        row_count: 0,
107    };
108
109    pub fn from_parts(
110        accumulator_xor: [u8; 32],
111        row_count: u64,
112    ) -> Result<Self, AuthenticatedStateError> {
113        if row_count == 0 && accumulator_xor != [0; 32] {
114            return Err(AuthenticatedStateError::NonZeroEmptyAccumulator);
115        }
116        Ok(Self {
117            accumulator_xor,
118            row_count,
119        })
120    }
121
122    pub const fn accumulator_xor(&self) -> &[u8; 32] {
123        &self.accumulator_xor
124    }
125
126    pub const fn row_count(&self) -> u64 {
127        self.row_count
128    }
129
130    pub const fn is_empty(&self) -> bool {
131        self.row_count == 0
132    }
133
134    pub fn add(&mut self, row_hash: Sha256Digest) -> Result<(), AuthenticatedStateError> {
135        self.row_count = self
136            .row_count
137            .checked_add(1)
138            .ok_or(AuthenticatedStateError::RowCountOverflow)?;
139        xor_digest(&mut self.accumulator_xor, row_hash);
140        Ok(())
141    }
142
143    /// Removes a hash known by the caller to be present in this leaf.
144    ///
145    /// XOR accumulators cannot prove membership; storage implementations must
146    /// authenticate the old row hash before calling this method.
147    pub fn remove(&mut self, row_hash: Sha256Digest) -> Result<(), AuthenticatedStateError> {
148        if self.row_count == 0 {
149            return Err(AuthenticatedStateError::RemoveFromEmptyAccumulator);
150        }
151        let next_count = self.row_count - 1;
152        let mut next_accumulator = self.accumulator_xor;
153        xor_digest(&mut next_accumulator, row_hash);
154        if next_count == 0 && next_accumulator != [0; 32] {
155            return Err(AuthenticatedStateError::NonZeroEmptyAccumulator);
156        }
157        self.row_count = next_count;
158        self.accumulator_xor = next_accumulator;
159        Ok(())
160    }
161}
162
163/// A materialized sparse-Merkle node and the number of rows below it.
164#[derive(Debug, Clone, Copy, PartialEq, Eq)]
165pub struct TableMerkleNodeV2 {
166    pub hash: Sha256Digest,
167    pub row_count: u64,
168}
169
170/// Final authenticated state for one writable managed table.
171#[derive(Debug, Clone, PartialEq, Eq)]
172pub struct TableStateRootV2 {
173    pub table_name: String,
174    pub root: Sha256Digest,
175    pub row_count: u64,
176}
177
178/// Returns the exact compact JSON text committed as a primary-key string.
179pub fn canonical_primary_key_json_v1(
180    values: &[CanonicalStateValueV1],
181) -> Result<String, AuthenticatedStateError> {
182    Ok(CanonicalPrimaryKeyV1::from_values(values)?.into_string())
183}
184
185/// Hashes a table name and canonical primary-key JSON into the row-key digest.
186pub fn row_key_hash_v1(
187    table_name: &str,
188    primary_key: &CanonicalPrimaryKeyV1,
189) -> Result<Sha256Digest, AuthenticatedStateError> {
190    validate_table_name(table_name)?;
191    hash_json(&serde_json::json!([
192        ROW_KEY_DOMAIN_V1,
193        table_name,
194        primary_key.as_str()
195    ]))
196}
197
198/// Hashes the exact committed stored values for one managed row.
199pub fn row_state_hash_v1(
200    table_name: &str,
201    primary_key: &CanonicalPrimaryKeyV1,
202    stored_values: &[CanonicalStateValueV1],
203) -> Result<Sha256Digest, AuthenticatedStateError> {
204    validate_table_name(table_name)?;
205    validate_values(stored_values)?;
206    hash_json(&serde_json::json!([
207        ROW_STATE_DOMAIN_V1,
208        table_name,
209        primary_key.as_str(),
210        stored_values
211    ]))
212}
213
214/// Selects one of 256 leaves from the first byte of the row-key SHA-256 digest.
215pub const fn merkle_leaf_bucket_v2(row_key_hash: Sha256Digest) -> u64 {
216    row_key_hash.as_bytes()[0] as u64
217}
218
219/// Materializes a non-empty sparse-Merkle leaf.
220pub fn merkle_leaf_node_v2(
221    table_name: &str,
222    leaf_bucket: u64,
223    accumulator: &MerkleLeafAccumulatorV2,
224) -> Result<Option<TableMerkleNodeV2>, AuthenticatedStateError> {
225    validate_table_name(table_name)?;
226    if leaf_bucket >= (1_u64 << TABLE_MERKLE_DEPTH_V2) {
227        return Err(AuthenticatedStateError::InvalidMerklePosition {
228            level: 0,
229            bucket: leaf_bucket,
230        });
231    }
232    if accumulator.is_empty() {
233        if accumulator.accumulator_xor != [0; 32] {
234            return Err(AuthenticatedStateError::NonZeroEmptyAccumulator);
235        }
236        return Ok(None);
237    }
238    let hash = hash_json(&serde_json::json!([
239        MERKLE_LEAF_DOMAIN_V2,
240        table_name,
241        leaf_bucket,
242        accumulator.row_count,
243        hex::encode(accumulator.accumulator_xor)
244    ]))?;
245    Ok(Some(TableMerkleNodeV2 {
246        hash,
247        row_count: accumulator.row_count,
248    }))
249}
250
251/// Materializes one internal sparse-Merkle node.
252///
253/// Missing children are committed as empty strings, matching PersonalDB's
254/// sparse representation. If both children are absent, the parent is absent.
255pub fn merkle_parent_node_v2(
256    table_name: &str,
257    level: u32,
258    parent_bucket: u64,
259    left: Option<&TableMerkleNodeV2>,
260    right: Option<&TableMerkleNodeV2>,
261) -> Result<Option<TableMerkleNodeV2>, AuthenticatedStateError> {
262    validate_table_name(table_name)?;
263    if !(1..=TABLE_MERKLE_DEPTH_V2).contains(&level)
264        || parent_bucket >= (1_u64 << (TABLE_MERKLE_DEPTH_V2 - level))
265    {
266        return Err(AuthenticatedStateError::InvalidMerklePosition {
267            level,
268            bucket: parent_bucket,
269        });
270    }
271    if left.is_none() && right.is_none() {
272        return Ok(None);
273    }
274    let left_hash = left
275        .map(|node| node.hash.to_prefixed_hex())
276        .unwrap_or_default();
277    let right_hash = right
278        .map(|node| node.hash.to_prefixed_hex())
279        .unwrap_or_default();
280    let row_count = left
281        .map(|node| node.row_count)
282        .unwrap_or(0)
283        .checked_add(right.map(|node| node.row_count).unwrap_or(0))
284        .ok_or(AuthenticatedStateError::RowCountOverflow)?;
285    let hash = hash_json(&serde_json::json!([
286        MERKLE_NODE_DOMAIN_V2,
287        table_name,
288        level,
289        parent_bucket,
290        left_hash,
291        right_hash
292    ]))?;
293    Ok(Some(TableMerkleNodeV2 { hash, row_count }))
294}
295
296/// Root used for a writable managed table with no committed rows.
297pub fn empty_table_state_root_v1(
298    table_name: &str,
299) -> Result<Sha256Digest, AuthenticatedStateError> {
300    validate_table_name(table_name)?;
301    Ok(Sha256Digest::hash(
302        format!("{EMPTY_TABLE_DOMAIN_V1}:{table_name}").as_bytes(),
303    ))
304}
305
306/// Recomputes a table root from storage-neutral committed rows.
307///
308/// Input order does not affect the result. Duplicate primary keys are rejected.
309pub fn table_state_root_v2(
310    table_name: &str,
311    rows: impl IntoIterator<Item = AuthenticatedRowV1>,
312) -> Result<TableStateRootV2, AuthenticatedStateError> {
313    validate_table_name(table_name)?;
314    let mut primary_keys = BTreeSet::new();
315    let mut leaves = BTreeMap::<u64, MerkleLeafAccumulatorV2>::new();
316    for row in rows {
317        let primary_key = CanonicalPrimaryKeyV1::from_values(&row.primary_key)?;
318        if !primary_keys.insert(primary_key.clone()) {
319            return Err(AuthenticatedStateError::DuplicatePrimaryKey);
320        }
321        let key_hash = row_key_hash_v1(table_name, &primary_key)?;
322        let row_hash = row_state_hash_v1(table_name, &primary_key, &row.stored_values)?;
323        leaves
324            .entry(merkle_leaf_bucket_v2(key_hash))
325            .or_default()
326            .add(row_hash)?;
327    }
328
329    let row_count = leaves.values().try_fold(0_u64, |count, leaf| {
330        count
331            .checked_add(leaf.row_count())
332            .ok_or(AuthenticatedStateError::RowCountOverflow)
333    })?;
334    let mut nodes = leaves
335        .into_iter()
336        .map(|(bucket, accumulator)| {
337            let node = merkle_leaf_node_v2(table_name, bucket, &accumulator)?
338                .ok_or(AuthenticatedStateError::UnexpectedEmptyMerkleNode)?;
339            Ok((bucket, node))
340        })
341        .collect::<Result<BTreeMap<_, _>, AuthenticatedStateError>>()?;
342
343    for level in 1..=TABLE_MERKLE_DEPTH_V2 {
344        let parents = nodes
345            .keys()
346            .map(|bucket| bucket >> 1)
347            .collect::<BTreeSet<_>>();
348        let mut next = BTreeMap::new();
349        for parent in parents {
350            let left = nodes.get(&(parent << 1));
351            let right = nodes.get(&((parent << 1) + 1));
352            let node = merkle_parent_node_v2(table_name, level, parent, left, right)?
353                .ok_or(AuthenticatedStateError::UnexpectedEmptyMerkleNode)?;
354            next.insert(parent, node);
355        }
356        nodes = next;
357    }
358
359    let root = nodes
360        .get(&0)
361        .map(|node| node.hash)
362        .unwrap_or(empty_table_state_root_v1(table_name)?);
363    Ok(TableStateRootV2 {
364        table_name: table_name.to_string(),
365        root,
366        row_count,
367    })
368}
369
370/// Computes the database root over all writable managed table roots.
371///
372/// Tables are sorted by name before hashing, matching PersonalDB's `BTreeMap`
373/// traversal. Duplicate table names are rejected.
374pub fn database_state_root_v1(
375    table_roots: impl IntoIterator<Item = TableStateRootV2>,
376) -> Result<Sha256Digest, AuthenticatedStateError> {
377    let mut ordered = BTreeMap::new();
378    for table in table_roots {
379        validate_table_name(&table.table_name)?;
380        if ordered
381            .insert(table.table_name, table.root.to_prefixed_hex())
382            .is_some()
383        {
384            return Err(AuthenticatedStateError::DuplicateTableName);
385        }
386    }
387    let table_roots = ordered.into_iter().collect::<Vec<_>>();
388    hash_json(&serde_json::json!([DATABASE_ROOT_DOMAIN_V1, table_roots]))
389}
390
391fn validate_values(values: &[CanonicalStateValueV1]) -> Result<(), AuthenticatedStateError> {
392    for value in values {
393        value.validate()?;
394    }
395    Ok(())
396}
397
398fn validate_table_name(table_name: &str) -> Result<(), AuthenticatedStateError> {
399    if table_name.is_empty() {
400        return Err(AuthenticatedStateError::EmptyTableName);
401    }
402    Ok(())
403}
404
405fn hash_json(value: &serde_json::Value) -> Result<Sha256Digest, AuthenticatedStateError> {
406    Ok(Sha256Digest::hash(&serde_json::to_vec(value)?))
407}
408
409fn xor_digest(accumulator: &mut [u8; 32], digest: Sha256Digest) {
410    for (target, source) in accumulator.iter_mut().zip(digest.into_bytes()) {
411        *target ^= source;
412    }
413}
414
415#[derive(Debug, thiserror::Error)]
416pub enum AuthenticatedStateError {
417    #[error("primary key must contain at least one value")]
418    EmptyPrimaryKey,
419    #[error("table name must not be empty")]
420    EmptyTableName,
421    #[error("real values must be finite")]
422    NonFiniteReal,
423    #[error("duplicate primary key")]
424    DuplicatePrimaryKey,
425    #[error("duplicate table name")]
426    DuplicateTableName,
427    #[error("row count overflow")]
428    RowCountOverflow,
429    #[error("cannot remove a row hash from an empty leaf accumulator")]
430    RemoveFromEmptyAccumulator,
431    #[error("an empty leaf accumulator must contain an all-zero XOR digest")]
432    NonZeroEmptyAccumulator,
433    #[error("invalid sparse-Merkle position at level {level}, bucket {bucket}")]
434    InvalidMerklePosition { level: u32, bucket: u64 },
435    #[error("sparse-Merkle construction produced an unexpected empty node")]
436    UnexpectedEmptyMerkleNode,
437    #[error("canonical JSON serialization failed: {0}")]
438    Json(#[from] serde_json::Error),
439}
440
441#[cfg(test)]
442mod tests;