vote_commitment_tree/
path.rs

1//! Merkle authentication path for the vote commitment tree.
2
3use incrementalmerkletree::Hashable;
4use pasta_curves::Fp;
5
6use crate::anchor::Anchor;
7use crate::hash::{MerkleHashVote, TREE_DEPTH};
8
9/// Serialized size: 4 bytes (position u32 LE) + 32 * TREE_DEPTH bytes (auth path).
10pub const MERKLE_PATH_BYTES: usize = 4 + 32 * TREE_DEPTH;
11
12// ---------------------------------------------------------------------------
13// MerklePath
14// ---------------------------------------------------------------------------
15
16/// Merkle authentication path from a leaf to the tree root.
17///
18/// Used by ZKP #2 (VAN membership) and ZKP #3 (VC membership).
19#[derive(Clone, Debug, PartialEq, Eq)]
20pub struct MerklePath {
21    position: u32,
22    auth_path: [MerkleHashVote; TREE_DEPTH],
23}
24
25impl From<incrementalmerkletree::MerklePath<MerkleHashVote, { TREE_DEPTH as u8 }>> for MerklePath {
26    fn from(path: incrementalmerkletree::MerklePath<MerkleHashVote, { TREE_DEPTH as u8 }>) -> Self {
27        let position: u64 = path.position().into();
28        Self {
29            position: position as u32,
30            auth_path: path.path_elems().try_into().unwrap(),
31        }
32    }
33}
34
35impl MerklePath {
36    /// Construct from raw parts.
37    pub fn from_parts(position: u32, auth_path: [MerkleHashVote; TREE_DEPTH]) -> Self {
38        Self {
39            position,
40            auth_path,
41        }
42    }
43
44    /// Recompute the root from the given leaf and this authentication path.
45    pub fn root(&self, leaf: MerkleHashVote) -> Anchor {
46        self.auth_path
47            .iter()
48            .enumerate()
49            .fold(leaf, |node, (l, sibling)| {
50                let l = l as u8;
51                if self.position & (1 << l) == 0 {
52                    MerkleHashVote::combine(l.into(), &node, sibling)
53                } else {
54                    MerkleHashVote::combine(l.into(), sibling, &node)
55                }
56            })
57            .into()
58    }
59
60    /// Verify that this path produces the expected `root` when combined with `leaf`.
61    pub fn verify(&self, leaf: Fp, root: Fp) -> bool {
62        let computed = self.root(MerkleHashVote::from_fp(leaf));
63        computed.inner() == root
64    }
65
66    /// Leaf position in the tree.
67    pub fn position(&self) -> u32 {
68        self.position
69    }
70
71    /// The authentication path (sibling hashes from leaf to root).
72    pub fn auth_path(&self) -> &[MerkleHashVote; TREE_DEPTH] {
73        &self.auth_path
74    }
75
76    /// Serialize to bytes for FFI / network transport.
77    ///
78    /// Format (little-endian, [`MERKLE_PATH_BYTES`] bytes total):
79    /// - Bytes `[0..4)`: position (`u32` LE)
80    /// - Remaining bytes: auth path (`TREE_DEPTH` sibling hashes, 32 bytes each,
81    ///   in order from leaf level to root level)
82    pub fn to_bytes(&self) -> Vec<u8> {
83        let mut buf = Vec::with_capacity(MERKLE_PATH_BYTES);
84        buf.extend_from_slice(&self.position.to_le_bytes());
85        for hash in &self.auth_path {
86            buf.extend_from_slice(&hash.to_bytes());
87        }
88        buf
89    }
90
91    /// Deserialize from bytes produced by [`to_bytes`](Self::to_bytes).
92    ///
93    /// Returns `None` if the data is too short or contains non-canonical
94    /// field element encodings.
95    pub fn from_bytes(bytes: &[u8]) -> Option<Self> {
96        if bytes.len() < MERKLE_PATH_BYTES {
97            return None;
98        }
99
100        let position = u32::from_le_bytes(bytes[0..4].try_into().ok()?);
101
102        let mut auth_path = [MerkleHashVote::from_fp(Fp::zero()); TREE_DEPTH];
103        for (i, hash) in auth_path.iter_mut().enumerate() {
104            let start = 4 + i * 32;
105            let chunk: [u8; 32] = bytes[start..start + 32].try_into().ok()?;
106            *hash = MerkleHashVote::from_bytes(&chunk)?;
107        }
108
109        Some(Self {
110            position,
111            auth_path,
112        })
113    }
114}
vote_commitment_tree/path.rs

vote_commitment_tree/
path.rs
