penumbra_sdk_tct/internal/
path.rs

1//! Authentication paths into the tree, generically for trees of any height.
2//!
3//! An authentication path of a tree is a sequence of triples of hashes equal in length to the
4//! height of the tree.
5//!
6//! The interpretation of an authentication path is dependent on an _index_ into the tree, stored
7//! separately, which indicates the position of the leaf witnessed by the authentication path.
8//!
9//! These are wrapped in more specific domain types by the exposed crate API to make it more
10//! comprehensible.
11
12use crate::prelude::*;
13
14/// An authentication path into a `Tree`.
15///
16/// This is statically guaranteed to have the same length as the height of the tree.
17pub type AuthPath<Tree> = <<Tree as Height>::Height as Path>::Path;
18
19/// Identifies the unique type representing an authentication path for the given height.
20pub trait Path: IsHeight + Sized {
21    /// The authentication path for this height.
22    type Path;
23
24    /// Calculate the root hash for a path leading to a leaf with the given index and hash.
25    fn root(path: &Self::Path, index: u64, leaf: Hash) -> Hash;
26}
27
28/// The empty authentication path, for the zero-height tree.
29#[derive(Debug, Clone, Copy, Eq, PartialEq, Default)]
30pub struct Leaf;
31
32impl Path for Zero {
33    type Path = Leaf;
34
35    #[inline]
36    fn root(Leaf: &Leaf, _index: u64, leaf: Hash) -> Hash {
37        leaf
38    }
39}
40
41/// The authentication path for a node, whose height is always at least 1.
42#[derive(Debug, Clone, Copy, Eq, PartialEq)]
43pub struct Node<Child> {
44    /// The sibling hashes of the child.
45    ///
46    /// Note that this does not record which child is witnessed; that information lies in the index
47    /// of the leaf.
48    pub siblings: [Hash; 3],
49
50    /// The authentication path for the witnessed child.
51    pub child: Child,
52}
53
54impl<Child, N: Path<Path = Child>> Path for Succ<N> {
55    type Path = Node<Child>;
56
57    #[inline]
58    fn root(Node { siblings, child }: &Node<Child>, index: u64, leaf: Hash) -> Hash {
59        // Based on the index, place the root hash of the child in the correct position among its
60        // sibling hashes, so that we can hash this node
61        let which_way = WhichWay::at(Self::HEIGHT, index).0;
62        let [leftmost, left, right, rightmost] =
63            which_way.insert(N::root(child, index, leaf), *siblings);
64
65        // Get the hash of this node at its correct height
66        Hash::node(Self::HEIGHT, leftmost, left, right, rightmost)
67    }
68}
69
70/// An enumeration of the different ways a path can go down a quadtree.
71#[derive(Debug, Clone, Copy, Eq, PartialEq)]
72pub enum WhichWay {
73    /// The leftmost (0th) child.
74    Leftmost,
75    /// The left (1st) child.
76    Left,
77    /// The right (2nd) child.
78    Right,
79    /// The rightmost (3rd) child.
80    Rightmost,
81}
82
83impl WhichWay {
84    /// Given a height and an index of a leaf, determine which direction the path down to that leaf
85    /// should branch at the node at that height.
86    #[inline]
87    pub fn at(height: u8, index: u64) -> (WhichWay, u64) {
88        // Shift the index right by (2 * (height - 1)) so that the last 2 bits are our direction, then
89        // mask off just those bits and branch on them to generate the output
90        let which_way = match (index >> (2 * (height - 1))) & 0b11 {
91            0 => WhichWay::Leftmost,
92            1 => WhichWay::Left,
93            2 => WhichWay::Right,
94            3 => WhichWay::Rightmost,
95            _ => unreachable!(),
96        };
97
98        // The index into the child: mask off the bits we just used to determine the direction
99        let index = index & !(0b11 << ((height - 1) * 2));
100
101        (which_way, index)
102    }
103
104    /// Given a 3-element array, insert an item into the array in the place indicated by the [`WhichWay`].
105    ///
106    /// This is the inverse of [`WhichWay::pick`].
107    #[inline]
108    pub fn insert<T>(&self, item: T, siblings: [T; 3]) -> [T; 4] {
109        use WhichWay::*;
110
111        let (
112            (Leftmost,  leftmost,  [/* leftmost, */ left,    right,    rightmost   ]) |
113            (Left,      left,      [   leftmost, /* left, */ right,    rightmost   ]) |
114            (Right,     right,     [   leftmost,    left, /* right, */ rightmost   ]) |
115            (Rightmost, rightmost, [   leftmost,    left,    right, /* rightmost */])
116        ) = (self, item, siblings);
117
118        [leftmost, left, right, rightmost]
119    }
120
121    /// Given a 4-element array, pick out the item in the array indicated by the [`WhichWay`], and
122    /// pair it with all the others, in the order they occurred.
123    ///
124    /// This is the inverse of [`WhichWay::insert`].
125    #[inline]
126    pub fn pick<T>(&self, siblings: [T; 4]) -> (T, [T; 3]) {
127        use WhichWay::*;
128
129        let ((Leftmost, [picked, a, b, c])
130        | (Left, [a, picked, b, c])
131        | (Right, [a, b, picked, c])
132        | (Rightmost, [a, b, c, picked])) = (self, siblings);
133
134        (picked, [a, b, c])
135    }
136}
137
138impl<T> Index<WhichWay> for [T; 4] {
139    type Output = T;
140
141    fn index(&self, index: WhichWay) -> &T {
142        match index {
143            WhichWay::Leftmost => &self[0],
144            WhichWay::Left => &self[1],
145            WhichWay::Right => &self[2],
146            WhichWay::Rightmost => &self[3],
147        }
148    }
149}
150
151impl<T> IndexMut<WhichWay> for [T; 4] {
152    fn index_mut(&mut self, index: WhichWay) -> &mut T {
153        match index {
154            WhichWay::Leftmost => &mut self[0],
155            WhichWay::Left => &mut self[1],
156            WhichWay::Right => &mut self[2],
157            WhichWay::Rightmost => &mut self[3],
158        }
159    }
160}
161
162#[cfg(test)]
163mod test {
164    use super::*;
165    use proptest::prelude::*;
166
167    /// Get directions from the root (at the given height)
168    fn directions_of_index(height: u8, index: u64) -> Vec<WhichWay> {
169        (1..=height)
170            .rev() // iterate from the root to the leaf (height down to 1)
171            .map(|height| WhichWay::at(height, index).0)
172            .collect()
173    }
174
175    /// Get a sequence of indices representing the index of the originally specified leaf from the
176    /// starting height down to zero.
177    fn directions_via_indices(height: u8, index: u64) -> Vec<WhichWay> {
178        (1..=height)
179            .rev() // iterate from the leaf to the root (height down to 1)
180            .scan(index, |index, height| {
181                let (which_way, next_index) = WhichWay::at(height, *index);
182                *index = next_index;
183                Some(which_way)
184            })
185            .collect()
186    }
187
188    #[test]
189    fn directions_of_index_check() {
190        assert_eq!(directions_of_index(1, 0), &[WhichWay::Leftmost]);
191        assert_eq!(directions_of_index(1, 1), &[WhichWay::Left]);
192        assert_eq!(directions_of_index(1, 2), &[WhichWay::Right]);
193        assert_eq!(directions_of_index(1, 3), &[WhichWay::Rightmost]);
194    }
195
196    /// Get the index which represents the given sequence of directions.
197    fn index_of_directions(directions: &[WhichWay]) -> u64 {
198        directions
199            .iter()
200            .rev() // Iterating rom the leaf to the root...
201            .zip(1..) // Keeping track of the height (starting at 1 for the leafmost node)...
202            .fold(0, |index, (&direction, height)| {
203                index | // Set the bits in the index...
204                (direction as u64) << (2 * (height - 1)) // ...which correspond to the direction at the height - 1.
205            })
206    }
207
208    proptest! {
209        #[test]
210        fn which_way_indices_correct(
211            (height, index) in (
212                // This is a dependent generator: we ensure that the index is in-bounds for the height
213                (0u8..(3 * 8)), 0u64..u64::MAX).prop_map(|(height, index)| (height, (index % (4u64.pow(height as u32))))
214            )
215        ) {
216            assert_eq!(directions_of_index(height, index), directions_via_indices(height, index));
217        }
218
219        #[test]
220        fn which_way_direction_correct(
221            (height, index) in (
222                // This is a dependent generator: we ensure that the index is in-bounds for the height
223                (0u8..(3 * 8)), 0u64..u64::MAX).prop_map(|(height, index)| (height, (index % (4u64.pow(height as u32)))))
224        ) {
225            assert_eq!(index, index_of_directions(&directions_of_index(height, index)));
226        }
227    }
228}
229
230// All the below is just for serialization to/from protobufs:
231
232/// When deserializing an authentication path, it was malformed.
233#[derive(Debug, Clone, Copy, Eq, PartialEq, Error)]
234#[error("could not decode authentication path")]
235pub struct PathDecodeError;
236
237use decaf377::Fq;
238use penumbra_sdk_proto::penumbra::crypto::tct::v1 as pb;
239use std::{
240    collections::VecDeque,
241    ops::{Index, IndexMut},
242};
243
244impl From<Leaf> for VecDeque<pb::MerklePathChunk> {
245    fn from(Leaf: Leaf) -> VecDeque<pb::MerklePathChunk> {
246        VecDeque::new()
247    }
248}
249
250impl From<Leaf> for Vec<pb::MerklePathChunk> {
251    fn from(Leaf: Leaf) -> Vec<pb::MerklePathChunk> {
252        Vec::new()
253    }
254}
255
256impl TryFrom<VecDeque<pb::MerklePathChunk>> for Leaf {
257    type Error = PathDecodeError;
258
259    fn try_from(queue: VecDeque<pb::MerklePathChunk>) -> Result<Leaf, Self::Error> {
260        if queue.is_empty() {
261            Ok(Leaf)
262        } else {
263            Err(PathDecodeError)
264        }
265    }
266}
267
268impl TryFrom<Vec<pb::MerklePathChunk>> for Leaf {
269    type Error = PathDecodeError;
270
271    fn try_from(vec: Vec<pb::MerklePathChunk>) -> Result<Leaf, Self::Error> {
272        if vec.is_empty() {
273            Ok(Leaf)
274        } else {
275            Err(PathDecodeError)
276        }
277    }
278}
279
280// To create `Vec<pb::MerklePathChunk>`, we have a recursive impl for `VecDeque` which we delegate
281// to, then finally turn into a `Vec` at the end.
282impl<Child> From<Node<Child>> for VecDeque<pb::MerklePathChunk>
283where
284    VecDeque<pb::MerklePathChunk>: From<Child>,
285{
286    fn from(node: Node<Child>) -> VecDeque<pb::MerklePathChunk> {
287        let [sibling_1, sibling_2, sibling_3] =
288            node.siblings.map(|hash| Fq::from(hash).to_bytes().to_vec());
289        let mut path: VecDeque<pb::MerklePathChunk> = node.child.into();
290        path.push_front(pb::MerklePathChunk {
291            sibling_1,
292            sibling_2,
293            sibling_3,
294        });
295        path
296    }
297}
298
299impl<Child> From<Node<Child>> for Vec<pb::MerklePathChunk>
300where
301    VecDeque<pb::MerklePathChunk>: From<Child>,
302{
303    fn from(node: Node<Child>) -> Vec<pb::MerklePathChunk> {
304        let [sibling_1, sibling_2, sibling_3] =
305            node.siblings.map(|hash| Fq::from(hash).to_bytes().to_vec());
306        let mut path = VecDeque::from(node.child);
307        path.push_front(pb::MerklePathChunk {
308            sibling_1,
309            sibling_2,
310            sibling_3,
311        });
312        path.into()
313    }
314}
315
316// To create `Node<Child>`, we have a recursive impl for `VecDeque` which we delegate to, then
317// finally turn into a `Vec` at the end.
318impl<Child> TryFrom<VecDeque<pb::MerklePathChunk>> for Node<Child>
319where
320    Child: TryFrom<VecDeque<pb::MerklePathChunk>, Error = PathDecodeError>,
321{
322    type Error = PathDecodeError;
323
324    fn try_from(mut queue: VecDeque<pb::MerklePathChunk>) -> Result<Node<Child>, Self::Error> {
325        if let Some(pb::MerklePathChunk {
326            sibling_1,
327            sibling_2,
328            sibling_3,
329        }) = queue.pop_front()
330        {
331            let child = Child::try_from(queue)?;
332            Ok(Node {
333                siblings: [
334                    Hash::new(
335                        Fq::from_bytes_checked(&sibling_1.try_into().map_err(|_| PathDecodeError)?)
336                            .map_err(|_| PathDecodeError)?,
337                    ),
338                    Hash::new(
339                        Fq::from_bytes_checked(&sibling_2.try_into().map_err(|_| PathDecodeError)?)
340                            .map_err(|_| PathDecodeError)?,
341                    ),
342                    Hash::new(
343                        Fq::from_bytes_checked(&sibling_3.try_into().map_err(|_| PathDecodeError)?)
344                            .map_err(|_| PathDecodeError)?,
345                    ),
346                ],
347                child,
348            })
349        } else {
350            Err(PathDecodeError)
351        }
352    }
353}
354
355impl<Child> TryFrom<Vec<pb::MerklePathChunk>> for Node<Child>
356where
357    Node<Child>: TryFrom<VecDeque<pb::MerklePathChunk>>,
358{
359    type Error = <Node<Child> as TryFrom<VecDeque<pb::MerklePathChunk>>>::Error;
360
361    fn try_from(queue: Vec<pb::MerklePathChunk>) -> Result<Node<Child>, Self::Error> {
362        <Node<Child>>::try_from(VecDeque::from(queue))
363    }
364}
penumbra_sdk_tct/internal/path.rs

penumbra_sdk_tct/internal/
path.rs
