tf_types/
chain.rs

1//! Proof-event chain and merkle-tree helpers.
2//!
3//! Matches `tools/tf-types-ts/src/core/chain.ts` byte-for-byte via
4//! `conformance/chain-vectors.yaml`.
5//!
6//! - `event_hash(event)` → `sha256:<hex>` over the canonical JSON of the
7//!   event with its `signature` field removed. This is the bytes a signer
8//!   actually signs; putting the signature inside the event would make the
9//!   hash self-referential.
10//! - `verify_chain(events)` → asserts every `events[i].parent_hash` equals
11//!   `event_hash(events[i-1])` for i > 0 (the first event has no parent).
12//! - `merkle_root(events)` → sha256 over pair-wise concatenated hashes,
13//!   duplicating the last leaf at each odd level (Bitcoin convention).
14//! - `chain_hash(events)` → rolling sha256(prev || event_hash) seeded with
15//!   32 zero bytes.
16
17use std::fmt::Write;
18
19use serde::Serialize;
20use serde_json::Value;
21use sha2::{Digest, Sha256};
22
23use crate::canonical::{canonicalize, CanonicalJsonError};
24use crate::crypto::parse_hashref;
25use crate::generated::proof_event::ProofEvent;
26
27#[derive(Debug, thiserror::Error, PartialEq, Eq)]
28pub enum ChainError {
29    #[error("canonical JSON error: {0}")]
30    Canonical(String),
31    #[error("serialization error: {0}")]
32    Serialize(String),
33    #[error("invalid hash ref in chain: {0}")]
34    BadHashRef(String),
35    #[error("event {0} declares parent_hash {1:?} but previous event hashes to {2:?}")]
36    ParentMismatch(usize, String, String),
37    #[error("event {0} is not the first but has no parent_hash")]
38    MissingParentHash(usize),
39}
40
41impl From<CanonicalJsonError> for ChainError {
42    fn from(e: CanonicalJsonError) -> Self {
43        ChainError::Canonical(e.to_string())
44    }
45}
46
47/// Canonical JSON of an event with its signature stripped.
48pub fn event_signed_payload(event: &ProofEvent) -> Result<String, ChainError> {
49    let mut v = serde_json::to_value(event).map_err(|e| ChainError::Serialize(e.to_string()))?;
50    if let Value::Object(ref mut map) = v {
51        map.remove("signature");
52    }
53    Ok(canonicalize(&v)?)
54}
55
56/// The `sha256:<hex>` hash of an event's signed payload.
57pub fn event_hash(event: &ProofEvent) -> Result<String, ChainError> {
58    let payload = event_signed_payload(event)?;
59    Ok(sha256_hash_of(payload.as_bytes()))
60}
61
62fn sha256_hash_of(bytes: &[u8]) -> String {
63    let digest = Sha256::digest(bytes);
64    format!("sha256:{}", hex_lower(&digest))
65}
66
67pub(crate) fn hex_lower(bytes: &[u8]) -> String {
68    let mut s = String::with_capacity(bytes.len() * 2);
69    for b in bytes {
70        write!(s, "{:02x}", b).unwrap();
71    }
72    s
73}
74
75/// Verify a chain of events. `events[0]` may have no `parent_hash`; every
76/// subsequent event must declare `parent_hash == event_hash(events[i-1])`.
77pub fn verify_chain(events: &[ProofEvent]) -> Result<(), ChainError> {
78    for i in 1..events.len() {
79        let expected = event_hash(&events[i - 1])?;
80        let Some(parent) = &events[i].parent_hash else {
81            return Err(ChainError::MissingParentHash(i));
82        };
83        if parent != &expected {
84            return Err(ChainError::ParentMismatch(i, parent.clone(), expected));
85        }
86    }
87    Ok(())
88}
89
90/// Merkle root over the event hashes. Empty trees return a sentinel zero
91/// hash; single-event trees return that event's hash; otherwise pair-wise
92/// hash up, duplicating the last leaf when a level has an odd number of
93/// nodes.
94pub fn merkle_root(events: &[ProofEvent]) -> Result<String, ChainError> {
95    if events.is_empty() {
96        return Ok(format!("sha256:{}", hex_lower(&[0u8; 32])));
97    }
98    let mut level: Vec<Vec<u8>> = events
99        .iter()
100        .map(|e| {
101            let hash = event_hash(e)?;
102            parse_hashref(&hash)
103                .map(|(_, bytes)| bytes)
104                .map_err(|err| ChainError::BadHashRef(err.to_string()))
105        })
106        .collect::<Result<_, ChainError>>()?;
107    while level.len() > 1 {
108        if level.len() % 2 == 1 {
109            level.push(level.last().unwrap().clone());
110        }
111        let mut next: Vec<Vec<u8>> = Vec::with_capacity(level.len() / 2);
112        for pair in level.chunks_exact(2) {
113            let mut hasher = Sha256::new();
114            hasher.update(&pair[0]);
115            hasher.update(&pair[1]);
116            next.push(hasher.finalize().to_vec());
117        }
118        level = next;
119    }
120    Ok(format!("sha256:{}", hex_lower(&level[0])))
121}
122
123/// Rolling chain hash: seeded with 32 zero bytes, then for each event the
124/// hash is `sha256(prev || sha256_bytes_of_event)`.
125pub fn chain_hash(events: &[ProofEvent]) -> Result<String, ChainError> {
126    let mut state = vec![0u8; 32];
127    for e in events {
128        let (_, event_bytes) = parse_hashref(&event_hash(e)?)
129            .map_err(|err| ChainError::BadHashRef(err.to_string()))?;
130        let mut hasher = Sha256::new();
131        hasher.update(&state);
132        hasher.update(&event_bytes);
133        state = hasher.finalize().to_vec();
134    }
135    Ok(format!("sha256:{}", hex_lower(&state)))
136}
137
138/// Minimal serialization helper used by tests that need to serialize an
139/// arbitrary Serialize value to canonical JSON.
140pub fn canonical_of<S: Serialize>(v: &S) -> Result<String, ChainError> {
141    let json = serde_json::to_value(v).map_err(|e| ChainError::Serialize(e.to_string()))?;
142    Ok(canonicalize(&json)?)
143}
tf_types/chain.rs

tf_types/
chain.rs
