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 start = usize::try_from(block).expect("u64 block index fits in usize") * 8;
123        out[start..start + 8].copy_from_slice(&digest);
124    }
125    Hash(out)
126}
127
128fn encode_value(value: &Value) -> Vec<u8> {
129    serde_json::to_vec(value).unwrap_or_else(|_| format!("{value:?}").into_bytes())
130}
131
132impl VerificationModel for DefaultVerificationModel {
133    type Hash = Hash;
134    type SigningKey = SigningKey;
135    type VerifyingKey = VerifyingKey;
136    type Signature = Signature;
137    type Commitment = Commitment;
138    type Nullifier = Nullifier;
139
140    fn hash(tag: HashTag, bytes: &[u8]) -> Self::Hash {
141        hash_bytes_with_tag(tag, bytes)
142    }
143
144    fn deriving(signing: &Self::SigningKey) -> Self::VerifyingKey {
145        let digest = hash_bytes_with_tag(HashTag::SigningKey, &signing.0);
146        VerifyingKey(digest.0)
147    }
148
149    fn sign_value(payload: &Value, key: &Self::SigningKey) -> Self::Signature {
150        crate::verification::sign_value(payload, key)
151    }
152
153    fn verify_signed_value(
154        payload: &Value,
155        signature: &Self::Signature,
156        key: &Self::VerifyingKey,
157    ) -> bool {
158        verify_signed_value(payload, signature, key)
159    }
160
161    fn commitment(payload: &Value) -> Self::Commitment {
162        Commitment(hash_bytes_with_tag(
163            HashTag::Commitment,
164            &encode_value(payload),
165        ))
166    }
167
168    fn nullifier(payload: &Value) -> Self::Nullifier {
169        Nullifier(hash_bytes_with_tag(
170            HashTag::Nullifier,
171            &encode_value(payload),
172        ))
173    }
174}
175
176/// Deterministically derive a signing key for an endpoint.
177#[must_use]
178pub fn signing_key_for_endpoint(endpoint: &Endpoint) -> SigningKey {
179    let mut bytes = endpoint.sid.to_le_bytes().to_vec();
180    bytes.extend_from_slice(endpoint.role.as_bytes());
181    let digest = hash_bytes_with_tag(HashTag::SigningKey, &bytes);
182    SigningKey(digest.0)
183}
184
185/// Deterministically derive a verifying key for an endpoint.
186#[must_use]
187pub fn verifying_key_for_endpoint(endpoint: &Endpoint) -> VerifyingKey {
188    DefaultVerificationModel::deriving(&signing_key_for_endpoint(endpoint))
189}
190
191/// Sign one runtime value.
192#[must_use]
193pub fn sign_value(payload: &Value, key: &SigningKey) -> Signature {
194    let verifying = DefaultVerificationModel::deriving(key);
195    let mut bytes = verifying.0.to_vec();
196    bytes.extend_from_slice(&encode_value(payload));
197    let digest = hash_bytes_with_tag(HashTag::SignedValue, &bytes);
198    Signature {
199        signer: verifying,
200        digest,
201    }
202}
203
204/// Verify one signed runtime value.
205#[must_use]
206pub fn verify_signed_value(payload: &Value, signature: &Signature, key: &VerifyingKey) -> bool {
207    if signature.signer != *key {
208        return false;
209    }
210    let mut bytes = key.0.to_vec();
211    bytes.extend_from_slice(&encode_value(payload));
212    let expected = hash_bytes_with_tag(HashTag::SignedValue, &bytes);
213    expected == signature.digest
214}
215
216/// Compatibility alias requested in discrepancy tracking.
217#[allow(non_snake_case)]
218#[must_use]
219pub fn signValue(payload: &Value, key: &SigningKey) -> Signature {
220    sign_value(payload, key)
221}
222
223/// Compatibility alias requested in discrepancy tracking.
224#[allow(non_snake_case)]
225#[must_use]
226pub fn verifySignedValue(payload: &Value, signature: &Signature, key: &VerifyingKey) -> bool {
227    verify_signed_value(payload, signature, key)
228}
229
230fn merge_hash_pair(left: Hash, right: Hash) -> Hash {
231    let mut bytes = left.0.to_vec();
232    bytes.extend_from_slice(&right.0);
233    hash_bytes_with_tag(HashTag::MerkleNode, &bytes)
234}
235
236/// Merkle authentication path.
237#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
238pub struct AuthProof {
239    /// Zero-based index of the leaf.
240    pub index: usize,
241    /// Sibling hashes from leaf level upward.
242    pub siblings: Vec<Hash>,
243    /// Whether each sibling hash is on the left side.
244    pub sibling_on_left: Vec<bool>,
245}
246
247/// Merkle authentication tree.
248#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
249pub struct AuthTree {
250    leaves: Vec<Hash>,
251    levels: Vec<Vec<Hash>>,
252}
253
254impl AuthTree {
255    /// Build an authentication tree from leaf payload hashes.
256    #[must_use]
257    pub fn new(leaves: Vec<Hash>) -> Self {
258        if leaves.is_empty() {
259            return Self {
260                leaves,
261                levels: vec![vec![hash_bytes_with_tag(HashTag::MerkleLeaf, &[])]],
262            };
263        }
264        let mut levels = vec![leaves.clone()];
265        let mut level = leaves.clone();
266        while level.len() > 1 {
267            let mut next = Vec::with_capacity(level.len().div_ceil(2));
268            for chunk in level.chunks(2) {
269                let left = chunk[0];
270                let right = if chunk.len() == 2 { chunk[1] } else { chunk[0] };
271                next.push(merge_hash_pair(left, right));
272            }
273            levels.push(next.clone());
274            level = next;
275        }
276        Self { leaves, levels }
277    }
278
279    /// Append one leaf and update levels incrementally.
280    pub fn append_leaf(&mut self, leaf: Hash) {
281        if self.leaves.is_empty() {
282            *self = Self::new(vec![leaf]);
283            return;
284        }
285        self.leaves.push(leaf);
286        self.levels[0].push(leaf);
287        let mut idx = self.levels[0].len() - 1;
288        let mut level_idx = 0;
289        loop {
290            let level = &self.levels[level_idx];
291            let pair_start = idx & !1;
292            let left = level[pair_start];
293            let right = if pair_start + 1 < level.len() {
294                level[pair_start + 1]
295            } else {
296                left
297            };
298            let parent = merge_hash_pair(left, right);
299            let parent_idx = pair_start / 2;
300            if self.levels.len() == level_idx + 1 {
301                self.levels.push(Vec::new());
302            }
303            let next = &mut self.levels[level_idx + 1];
304            if parent_idx < next.len() {
305                next[parent_idx] = parent;
306            } else {
307                next.push(parent);
308            }
309            if parent_idx == 0 && next.len() == 1 {
310                break;
311            }
312            idx = parent_idx;
313            level_idx += 1;
314        }
315    }
316
317    /// Root hash of the tree.
318    #[must_use]
319    pub fn root(&self) -> Hash {
320        self.levels
321            .last()
322            .and_then(|level| level.first().copied())
323            .unwrap_or_else(|| hash_bytes_with_tag(HashTag::MerkleLeaf, &[]))
324    }
325
326    /// Generate an authentication proof for a leaf index.
327    #[must_use]
328    pub fn prove(&self, index: usize) -> Option<AuthProof> {
329        if index >= self.leaves.len() {
330            return None;
331        }
332        let mut idx = index;
333        let mut siblings = Vec::new();
334        let mut sibling_on_left = Vec::new();
335        for level in &self.levels {
336            if level.len() <= 1 {
337                break;
338            }
339            let pair_index = idx ^ 1;
340            let sibling = if pair_index < level.len() {
341                level[pair_index]
342            } else {
343                level[idx]
344            };
345            siblings.push(sibling);
346            sibling_on_left.push(pair_index < idx);
347            idx /= 2;
348        }
349        Some(AuthProof {
350            index,
351            siblings,
352            sibling_on_left,
353        })
354    }
355
356    /// Verify a proof against the expected root hash.
357    #[must_use]
358    pub fn verify(root: Hash, leaf: Hash, proof: &AuthProof) -> bool {
359        if proof.siblings.len() != proof.sibling_on_left.len() {
360            return false;
361        }
362        let mut current = leaf;
363        let mut index = proof.index;
364        for (sibling, on_left) in proof.siblings.iter().zip(proof.sibling_on_left.iter()) {
365            let expected_on_left = index % 2 == 1;
366            if *on_left != expected_on_left {
367                return false;
368            }
369            current = if *on_left {
370                merge_hash_pair(*sibling, current)
371            } else {
372                merge_hash_pair(current, *sibling)
373            };
374            index /= 2;
375        }
376        current == root
377    }
378}
379
380#[cfg(test)]
381mod tests {
382    use super::*;
383
384    #[test]
385    fn signature_roundtrip() {
386        let ep = Endpoint {
387            sid: 9,
388            role: "Alice".to_string(),
389        };
390        let sk = signing_key_for_endpoint(&ep);
391        let vk = verifying_key_for_endpoint(&ep);
392        let payload = Value::Nat(42);
393        let sig = sign_value(&payload, &sk);
394        assert!(verify_signed_value(&payload, &sig, &vk));
395        assert!(!verify_signed_value(&Value::Nat(7), &sig, &vk));
396    }
397
398    #[test]
399    fn auth_tree_proof_roundtrip() {
400        let leaves = vec![
401            hash_bytes_with_tag(HashTag::MerkleLeaf, b"a"),
402            hash_bytes_with_tag(HashTag::MerkleLeaf, b"b"),
403            hash_bytes_with_tag(HashTag::MerkleLeaf, b"c"),
404        ];
405        let tree = AuthTree::new(leaves.clone());
406        let proof = tree.prove(1).expect("proof for valid index");
407        assert!(AuthTree::verify(tree.root(), leaves[1], &proof));
408    }
409
410    #[test]
411    fn auth_tree_incremental_append_matches_rebuild() {
412        let leaves = vec![
413            hash_bytes_with_tag(HashTag::MerkleLeaf, b"a"),
414            hash_bytes_with_tag(HashTag::MerkleLeaf, b"b"),
415            hash_bytes_with_tag(HashTag::MerkleLeaf, b"c"),
416            hash_bytes_with_tag(HashTag::MerkleLeaf, b"d"),
417            hash_bytes_with_tag(HashTag::MerkleLeaf, b"e"),
418        ];
419        let mut incremental = AuthTree::new(vec![leaves[0]]);
420        for leaf in leaves.iter().skip(1) {
421            incremental.append_leaf(*leaf);
422        }
423        let rebuilt = AuthTree::new(leaves);
424        assert_eq!(incremental.root(), rebuilt.root());
425    }
426}
telltale_vm/verification.rs

telltale_vm/
verification.rs
