telltale_machine/
verification.rs

1//! Verification model primitives for protocol-machine signatures and commitments.
2//!
3//! This module provides domain-separated hashing, signing/verification helpers,
4//! and a Merkle authentication tree for commitment proofs.
5
6use std::hash::{Hash as StdHash, Hasher};
7
8use serde::{Deserialize, Serialize};
9
10use crate::coroutine::Value;
11use crate::instr::Endpoint;
12
13/// Domain-separated 32-byte hash.
14#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
15pub struct Hash(pub [u8; 32]);
16
17/// Hash domain tags to avoid cross-domain collisions.
18#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
19pub enum HashTag {
20    /// Generic value hashing.
21    Value,
22    /// Signed value digest.
23    SignedValue,
24    /// Merkle tree leaf hash.
25    MerkleLeaf,
26    /// Merkle tree internal node hash.
27    MerkleNode,
28    /// Resource commitment hash.
29    Commitment,
30    /// Nullifier hash for consumption tracking.
31    Nullifier,
32    /// Signing key derivation hash.
33    SigningKey,
34}
35
36impl HashTag {
37    fn domain_byte(self) -> u8 {
38        match self {
39            Self::Value => 0x01,
40            Self::SignedValue => 0x02,
41            Self::MerkleLeaf => 0x03,
42            Self::MerkleNode => 0x04,
43            Self::Commitment => 0x05,
44            Self::Nullifier => 0x06,
45            Self::SigningKey => 0x07,
46        }
47    }
48}
49
50/// Signing key used to sign values.
51#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
52pub struct SigningKey(pub [u8; 32]);
53
54/// Verification key used to verify signatures.
55#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
56pub struct VerifyingKey(pub [u8; 32]);
57
58/// Signature attached to a value.
59#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
60pub struct Signature {
61    /// Signer identity.
62    pub signer: VerifyingKey,
63    /// Domain-separated payload digest.
64    pub digest: Hash,
65}
66
67/// Commitment for resource/state commitments.
68#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
69pub struct Commitment(pub Hash);
70
71/// Nullifier for one-time resource consumption.
72#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
73pub struct Nullifier(pub Hash);
74
75/// Verification model typeclass.
76pub trait VerificationModel {
77    /// Hash type.
78    type Hash;
79    /// Signing key type.
80    type SigningKey;
81    /// Verifying key type.
82    type VerifyingKey;
83    /// Signature type.
84    type Signature;
85    /// Commitment type.
86    type Commitment;
87    /// Nullifier type.
88    type Nullifier;
89
90    /// Domain-separated hash.
91    fn hash(tag: HashTag, bytes: &[u8]) -> Self::Hash;
92    /// Derive a verifying key from a signing key.
93    fn deriving(signing: &Self::SigningKey) -> Self::VerifyingKey;
94    /// Sign a value payload.
95    fn sign_value(payload: &Value, key: &Self::SigningKey) -> Self::Signature;
96    /// Verify a signed value payload.
97    fn verify_signed_value(
98        payload: &Value,
99        signature: &Self::Signature,
100        key: &Self::VerifyingKey,
101    ) -> bool;
102    /// Compute a commitment for a value.
103    fn commitment(payload: &Value) -> Self::Commitment;
104    /// Compute a nullifier for a value.
105    fn nullifier(payload: &Value) -> Self::Nullifier;
106}
107
108/// Default runtime verification model.
109#[derive(Debug, Clone, Copy, Default, Serialize, Deserialize)]
110pub struct DefaultVerificationModel;
111
112fn hash_bytes_with_tag(tag: HashTag, bytes: &[u8]) -> Hash {
113    // Portable deterministic pseudo-hash suitable for replay/consensus tests.
114    // Crypto-grade implementations can replace this model behind the trait.
115    let mut out = [0_u8; 32];
116    for block in 0_u64..4 {
117        let mut hasher = std::collections::hash_map::DefaultHasher::new();
118        tag.domain_byte().hash(&mut hasher);
119        block.hash(&mut hasher);
120        bytes.hash(&mut hasher);
121        let digest = hasher.finish().to_le_bytes();
122        let Ok(block_usize) = usize::try_from(block) else {
123            return Hash(out);
124        };
125        let start = block_usize * 8;
126        out[start..start + 8].copy_from_slice(&digest);
127    }
128    Hash(out)
129}
130
131fn encode_value(value: &Value) -> Vec<u8> {
132    serde_json::to_vec(value).unwrap_or_else(|_| format!("{value:?}").into_bytes())
133}
134
135impl VerificationModel for DefaultVerificationModel {
136    type Hash = Hash;
137    type SigningKey = SigningKey;
138    type VerifyingKey = VerifyingKey;
139    type Signature = Signature;
140    type Commitment = Commitment;
141    type Nullifier = Nullifier;
142
143    fn hash(tag: HashTag, bytes: &[u8]) -> Self::Hash {
144        hash_bytes_with_tag(tag, bytes)
145    }
146
147    fn deriving(signing: &Self::SigningKey) -> Self::VerifyingKey {
148        let digest = hash_bytes_with_tag(HashTag::SigningKey, &signing.0);
149        VerifyingKey(digest.0)
150    }
151
152    fn sign_value(payload: &Value, key: &Self::SigningKey) -> Self::Signature {
153        crate::verification::sign_value(payload, key)
154    }
155
156    fn verify_signed_value(
157        payload: &Value,
158        signature: &Self::Signature,
159        key: &Self::VerifyingKey,
160    ) -> bool {
161        verify_signed_value(payload, signature, key)
162    }
163
164    fn commitment(payload: &Value) -> Self::Commitment {
165        Commitment(hash_bytes_with_tag(
166            HashTag::Commitment,
167            &encode_value(payload),
168        ))
169    }
170
171    fn nullifier(payload: &Value) -> Self::Nullifier {
172        Nullifier(hash_bytes_with_tag(
173            HashTag::Nullifier,
174            &encode_value(payload),
175        ))
176    }
177}
178
179/// Deterministically derive a signing key for an endpoint.
180#[must_use]
181pub fn signing_key_for_endpoint(endpoint: &Endpoint) -> SigningKey {
182    let mut bytes = endpoint.sid.to_le_bytes().to_vec();
183    bytes.extend_from_slice(endpoint.role.as_bytes());
184    let digest = hash_bytes_with_tag(HashTag::SigningKey, &bytes);
185    SigningKey(digest.0)
186}
187
188/// Deterministically derive a verifying key for an endpoint.
189#[must_use]
190pub fn verifying_key_for_endpoint(endpoint: &Endpoint) -> VerifyingKey {
191    DefaultVerificationModel::deriving(&signing_key_for_endpoint(endpoint))
192}
193
194/// Sign one runtime value.
195#[must_use]
196pub fn sign_value(payload: &Value, key: &SigningKey) -> Signature {
197    let verifying = DefaultVerificationModel::deriving(key);
198    let mut bytes = verifying.0.to_vec();
199    bytes.extend_from_slice(&encode_value(payload));
200    let digest = hash_bytes_with_tag(HashTag::SignedValue, &bytes);
201    Signature {
202        signer: verifying,
203        digest,
204    }
205}
206
207/// Verify one signed runtime value.
208#[must_use]
209pub fn verify_signed_value(payload: &Value, signature: &Signature, key: &VerifyingKey) -> bool {
210    if signature.signer != *key {
211        return false;
212    }
213    let mut bytes = key.0.to_vec();
214    bytes.extend_from_slice(&encode_value(payload));
215    let expected = hash_bytes_with_tag(HashTag::SignedValue, &bytes);
216    expected == signature.digest
217}
218
219fn merge_hash_pair(left: Hash, right: Hash) -> Hash {
220    let mut bytes = left.0.to_vec();
221    bytes.extend_from_slice(&right.0);
222    hash_bytes_with_tag(HashTag::MerkleNode, &bytes)
223}
224
225/// Merkle authentication path.
226#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
227pub struct AuthProof {
228    /// Zero-based index of the leaf.
229    pub index: usize,
230    /// Sibling hashes from leaf level upward.
231    pub siblings: Vec<Hash>,
232    /// Whether each sibling hash is on the left side.
233    pub sibling_on_left: Vec<bool>,
234}
235
236/// Merkle authentication tree.
237#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
238pub struct AuthTree {
239    leaves: Vec<Hash>,
240    levels: Vec<Vec<Hash>>,
241}
242
243impl AuthTree {
244    /// Build an authentication tree from leaf payload hashes.
245    #[must_use]
246    pub fn new(leaves: Vec<Hash>) -> Self {
247        if leaves.is_empty() {
248            return Self {
249                leaves,
250                levels: vec![vec![hash_bytes_with_tag(HashTag::MerkleLeaf, &[])]],
251            };
252        }
253        let mut levels = vec![leaves.clone()];
254        let mut level = leaves.clone();
255        while level.len() > 1 {
256            let mut next = Vec::with_capacity(level.len().div_ceil(2));
257            for chunk in level.chunks(2) {
258                let left = chunk[0];
259                let right = if chunk.len() == 2 { chunk[1] } else { chunk[0] };
260                next.push(merge_hash_pair(left, right));
261            }
262            levels.push(next.clone());
263            level = next;
264        }
265        Self { leaves, levels }
266    }
267
268    /// Append one leaf and update levels incrementally.
269    pub fn append_leaf(&mut self, leaf: Hash) {
270        if self.leaves.is_empty() {
271            *self = Self::new(vec![leaf]);
272            return;
273        }
274        self.leaves.push(leaf);
275        self.levels[0].push(leaf);
276        let mut idx = self.levels[0].len() - 1;
277        let mut level_idx = 0;
278        loop {
279            // bounded: traverses log(n) tree levels upward
280            let level = &self.levels[level_idx];
281            let pair_start = idx & !1;
282            let left = level[pair_start];
283            let right = if pair_start + 1 < level.len() {
284                level[pair_start + 1]
285            } else {
286                left
287            };
288            let parent = merge_hash_pair(left, right);
289            let parent_idx = pair_start / 2;
290            if self.levels.len() == level_idx + 1 {
291                self.levels.push(Vec::new());
292            }
293            let next = &mut self.levels[level_idx + 1];
294            if parent_idx < next.len() {
295                next[parent_idx] = parent;
296            } else {
297                next.push(parent);
298            }
299            if parent_idx == 0 && next.len() == 1 {
300                break;
301            }
302            idx = parent_idx;
303            level_idx += 1;
304        }
305    }
306
307    /// Root hash of the tree.
308    #[must_use]
309    pub fn root(&self) -> Hash {
310        self.levels
311            .last()
312            .and_then(|level| level.first().copied())
313            .unwrap_or_else(|| hash_bytes_with_tag(HashTag::MerkleLeaf, &[]))
314    }
315
316    /// Generate an authentication proof for a leaf index.
317    #[must_use]
318    pub fn prove(&self, index: usize) -> Option<AuthProof> {
319        if index >= self.leaves.len() {
320            return None;
321        }
322        let mut idx = index;
323        let mut siblings = Vec::new();
324        let mut sibling_on_left = Vec::new();
325        for level in &self.levels {
326            if level.len() <= 1 {
327                break;
328            }
329            let pair_index = idx ^ 1;
330            let sibling = if pair_index < level.len() {
331                level[pair_index]
332            } else {
333                level[idx]
334            };
335            siblings.push(sibling);
336            sibling_on_left.push(pair_index < idx);
337            idx /= 2;
338        }
339        Some(AuthProof {
340            index,
341            siblings,
342            sibling_on_left,
343        })
344    }
345
346    /// Verify a proof against the expected root hash.
347    #[must_use]
348    pub fn verify(root: Hash, leaf: Hash, proof: &AuthProof) -> bool {
349        if proof.siblings.len() != proof.sibling_on_left.len() {
350            return false;
351        }
352        let mut current = leaf;
353        let mut index = proof.index;
354        for (sibling, on_left) in proof.siblings.iter().zip(proof.sibling_on_left.iter()) {
355            let expected_on_left = index % 2 == 1;
356            if *on_left != expected_on_left {
357                return false;
358            }
359            current = if *on_left {
360                merge_hash_pair(*sibling, current)
361            } else {
362                merge_hash_pair(current, *sibling)
363            };
364            index /= 2;
365        }
366        current == root
367    }
368}
369
370#[cfg(test)]
371mod tests {
372    use super::*;
373
374    #[test]
375    fn signature_roundtrip() {
376        let ep = Endpoint {
377            sid: 9,
378            role: "Alice".to_string(),
379        };
380        let sk = signing_key_for_endpoint(&ep);
381        let vk = verifying_key_for_endpoint(&ep);
382        let payload = Value::Nat(42);
383        let sig = sign_value(&payload, &sk);
384        assert!(verify_signed_value(&payload, &sig, &vk));
385        assert!(!verify_signed_value(&Value::Nat(7), &sig, &vk));
386    }
387
388    #[test]
389    fn auth_tree_proof_roundtrip() {
390        let leaves = vec![
391            hash_bytes_with_tag(HashTag::MerkleLeaf, b"a"),
392            hash_bytes_with_tag(HashTag::MerkleLeaf, b"b"),
393            hash_bytes_with_tag(HashTag::MerkleLeaf, b"c"),
394        ];
395        let tree = AuthTree::new(leaves.clone());
396        let proof = tree.prove(1).expect("proof for valid index");
397        assert!(AuthTree::verify(tree.root(), leaves[1], &proof));
398    }
399
400    #[test]
401    fn auth_tree_incremental_append_matches_rebuild() {
402        let leaves = vec![
403            hash_bytes_with_tag(HashTag::MerkleLeaf, b"a"),
404            hash_bytes_with_tag(HashTag::MerkleLeaf, b"b"),
405            hash_bytes_with_tag(HashTag::MerkleLeaf, b"c"),
406            hash_bytes_with_tag(HashTag::MerkleLeaf, b"d"),
407            hash_bytes_with_tag(HashTag::MerkleLeaf, b"e"),
408        ];
409        let mut incremental = AuthTree::new(vec![leaves[0]]);
410        for leaf in leaves.iter().skip(1) {
411            incremental.append_leaf(*leaf);
412        }
413        let rebuilt = AuthTree::new(leaves);
414        assert_eq!(incremental.root(), rebuilt.root());
415    }
416}
telltale_machine/verification.rs

telltale_machine/
verification.rs
