personaldb_protocol/authenticated_state/
mod.rs1use std::collections::{BTreeMap, BTreeSet};
8
9use serde::{Deserialize, Serialize};
10
11use crate::Sha256Digest;
12
13pub 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#[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#[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#[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#[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 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
165pub struct TableMerkleNodeV2 {
166 pub hash: Sha256Digest,
167 pub row_count: u64,
168}
169
170#[derive(Debug, Clone, PartialEq, Eq)]
172pub struct TableStateRootV2 {
173 pub table_name: String,
174 pub root: Sha256Digest,
175 pub row_count: u64,
176}
177
178pub fn canonical_primary_key_json_v1(
180 values: &[CanonicalStateValueV1],
181) -> Result<String, AuthenticatedStateError> {
182 Ok(CanonicalPrimaryKeyV1::from_values(values)?.into_string())
183}
184
185pub 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
198pub 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
214pub const fn merkle_leaf_bucket_v2(row_key_hash: Sha256Digest) -> u64 {
216 row_key_hash.as_bytes()[0] as u64
217}
218
219pub 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
251pub 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
296pub 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
306pub 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
370pub 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;