telltale_vm/
verification.rs

1//! Verification model primitives aligned with the Lean VM typeclass.
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
219/// Compatibility alias requested in discrepancy tracking.
220#[allow(non_snake_case)]
221#[must_use]
222pub fn signValue(payload: &Value, key: &SigningKey) -> Signature {
223    sign_value(payload, key)
224}
225
226/// Compatibility alias requested in discrepancy tracking.
227#[allow(non_snake_case)]
228#[must_use]
229pub fn verifySignedValue(payload: &Value, signature: &Signature, key: &VerifyingKey) -> bool {
230    verify_signed_value(payload, signature, key)
231}
232
233fn merge_hash_pair(left: Hash, right: Hash) -> Hash {
234    let mut bytes = left.0.to_vec();
235    bytes.extend_from_slice(&right.0);
236    hash_bytes_with_tag(HashTag::MerkleNode, &bytes)
237}
238
239/// Merkle authentication path.
240#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
241pub struct AuthProof {
242    /// Zero-based index of the leaf.
243    pub index: usize,
244    /// Sibling hashes from leaf level upward.
245    pub siblings: Vec<Hash>,
246    /// Whether each sibling hash is on the left side.
247    pub sibling_on_left: Vec<bool>,
248}
249
250/// Merkle authentication tree.
251#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
252pub struct AuthTree {
253    leaves: Vec<Hash>,
254    levels: Vec<Vec<Hash>>,
255}
256
257impl AuthTree {
258    /// Build an authentication tree from leaf payload hashes.
259    #[must_use]
260    pub fn new(leaves: Vec<Hash>) -> Self {
261        if leaves.is_empty() {
262            return Self {
263                leaves,
264                levels: vec![vec![hash_bytes_with_tag(HashTag::MerkleLeaf, &[])]],
265            };
266        }
267        let mut levels = vec![leaves.clone()];
268        let mut level = leaves.clone();
269        while level.len() > 1 {
270            let mut next = Vec::with_capacity(level.len().div_ceil(2));
271            for chunk in level.chunks(2) {
272                let left = chunk[0];
273                let right = if chunk.len() == 2 { chunk[1] } else { chunk[0] };
274                next.push(merge_hash_pair(left, right));
275            }
276            levels.push(next.clone());
277            level = next;
278        }
279        Self { leaves, levels }
280    }
281
282    /// Append one leaf and update levels incrementally.
283    pub fn append_leaf(&mut self, leaf: Hash) {
284        if self.leaves.is_empty() {
285            *self = Self::new(vec![leaf]);
286            return;
287        }
288        self.leaves.push(leaf);
289        self.levels[0].push(leaf);
290        let mut idx = self.levels[0].len() - 1;
291        let mut level_idx = 0;
292        loop {
293            // bounded: traverses log(n) tree levels upward
294            let level = &self.levels[level_idx];
295            let pair_start = idx & !1;
296            let left = level[pair_start];
297            let right = if pair_start + 1 < level.len() {
298                level[pair_start + 1]
299            } else {
300                left
301            };
302            let parent = merge_hash_pair(left, right);
303            let parent_idx = pair_start / 2;
304            if self.levels.len() == level_idx + 1 {
305                self.levels.push(Vec::new());
306            }
307            let next = &mut self.levels[level_idx + 1];
308            if parent_idx < next.len() {
309                next[parent_idx] = parent;
310            } else {
311                next.push(parent);
312            }
313            if parent_idx == 0 && next.len() == 1 {
314                break;
315            }
316            idx = parent_idx;
317            level_idx += 1;
318        }
319    }
320
321    /// Root hash of the tree.
322    #[must_use]
323    pub fn root(&self) -> Hash {
324        self.levels
325            .last()
326            .and_then(|level| level.first().copied())
327            .unwrap_or_else(|| hash_bytes_with_tag(HashTag::MerkleLeaf, &[]))
328    }
329
330    /// Generate an authentication proof for a leaf index.
331    #[must_use]
332    pub fn prove(&self, index: usize) -> Option<AuthProof> {
333        if index >= self.leaves.len() {
334            return None;
335        }
336        let mut idx = index;
337        let mut siblings = Vec::new();
338        let mut sibling_on_left = Vec::new();
339        for level in &self.levels {
340            if level.len() <= 1 {
341                break;
342            }
343            let pair_index = idx ^ 1;
344            let sibling = if pair_index < level.len() {
345                level[pair_index]
346            } else {
347                level[idx]
348            };
349            siblings.push(sibling);
350            sibling_on_left.push(pair_index < idx);
351            idx /= 2;
352        }
353        Some(AuthProof {
354            index,
355            siblings,
356            sibling_on_left,
357        })
358    }
359
360    /// Verify a proof against the expected root hash.
361    #[must_use]
362    pub fn verify(root: Hash, leaf: Hash, proof: &AuthProof) -> bool {
363        if proof.siblings.len() != proof.sibling_on_left.len() {
364            return false;
365        }
366        let mut current = leaf;
367        let mut index = proof.index;
368        for (sibling, on_left) in proof.siblings.iter().zip(proof.sibling_on_left.iter()) {
369            let expected_on_left = index % 2 == 1;
370            if *on_left != expected_on_left {
371                return false;
372            }
373            current = if *on_left {
374                merge_hash_pair(*sibling, current)
375            } else {
376                merge_hash_pair(current, *sibling)
377            };
378            index /= 2;
379        }
380        current == root
381    }
382}
383
384#[cfg(test)]
385mod tests {
386    use super::*;
387
388    #[test]
389    fn signature_roundtrip() {
390        let ep = Endpoint {
391            sid: 9,
392            role: "Alice".to_string(),
393        };
394        let sk = signing_key_for_endpoint(&ep);
395        let vk = verifying_key_for_endpoint(&ep);
396        let payload = Value::Nat(42);
397        let sig = sign_value(&payload, &sk);
398        assert!(verify_signed_value(&payload, &sig, &vk));
399        assert!(!verify_signed_value(&Value::Nat(7), &sig, &vk));
400    }
401
402    #[test]
403    fn auth_tree_proof_roundtrip() {
404        let leaves = vec![
405            hash_bytes_with_tag(HashTag::MerkleLeaf, b"a"),
406            hash_bytes_with_tag(HashTag::MerkleLeaf, b"b"),
407            hash_bytes_with_tag(HashTag::MerkleLeaf, b"c"),
408        ];
409        let tree = AuthTree::new(leaves.clone());
410        let proof = tree.prove(1).expect("proof for valid index");
411        assert!(AuthTree::verify(tree.root(), leaves[1], &proof));
412    }
413
414    #[test]
415    fn auth_tree_incremental_append_matches_rebuild() {
416        let leaves = vec![
417            hash_bytes_with_tag(HashTag::MerkleLeaf, b"a"),
418            hash_bytes_with_tag(HashTag::MerkleLeaf, b"b"),
419            hash_bytes_with_tag(HashTag::MerkleLeaf, b"c"),
420            hash_bytes_with_tag(HashTag::MerkleLeaf, b"d"),
421            hash_bytes_with_tag(HashTag::MerkleLeaf, b"e"),
422        ];
423        let mut incremental = AuthTree::new(vec![leaves[0]]);
424        for leaf in leaves.iter().skip(1) {
425            incremental.append_leaf(*leaf);
426        }
427        let rebuilt = AuthTree::new(leaves);
428        assert_eq!(incremental.root(), rebuilt.root());
429    }
430}
telltale_vm/verification.rs

telltale_vm/
verification.rs
