p3_symmetric/
hash.rs

1use alloc::vec;
2use alloc::vec::{IntoIter, Vec};
3use core::borrow::Borrow;
4use core::marker::PhantomData;
5
6use p3_util::log2_strict_usize;
7use serde::{Deserialize, Serialize};
8
9/// A wrapper around an array digest, with a phantom type parameter to ensure that the digest is
10/// associated with a particular field.
11#[derive(Clone, Copy, Debug, PartialEq, Eq, Serialize, Deserialize)]
12#[serde(bound(serialize = "[W; DIGEST_ELEMS]: Serialize"))]
13#[serde(bound(deserialize = "[W; DIGEST_ELEMS]: Deserialize<'de>"))]
14pub struct Hash<F, W, const DIGEST_ELEMS: usize> {
15    value: [W; DIGEST_ELEMS],
16    _marker: PhantomData<F>,
17}
18
19/// The Merkle cap of height `h` of a Merkle tree is the `h`-th layer (from the root) of the tree.
20/// It can be used in place of the root to verify Merkle paths, which are `h` elements shorter.
21///
22/// A cap of height 0 contains a single element (the root), while a cap of height `h` contains
23/// `2^h` elements. The `Digest` type is the full digest (e.g. `[W; DIGEST_ELEMS]`).
24#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
25#[serde(bound(serialize = "Digest: Serialize"))]
26#[serde(bound(deserialize = "Digest: Deserialize<'de>"))]
27pub struct MerkleCap<F, Digest> {
28    cap: Vec<Digest>,
29    _marker: PhantomData<F>,
30}
31
32impl<F, Digest: Default> Default for MerkleCap<F, Digest> {
33    fn default() -> Self {
34        Self {
35            cap: vec![Digest::default()],
36            _marker: PhantomData,
37        }
38    }
39}
40
41impl<F, Digest> MerkleCap<F, Digest> {
42    /// Create a new `MerkleCap` from a vector of digests.
43    pub fn new(cap: Vec<Digest>) -> Self {
44        assert!(cap.len().is_power_of_two() || cap.is_empty());
45        Self {
46            cap,
47            _marker: PhantomData,
48        }
49    }
50
51    /// Returns the number of digests in the cap.
52    #[must_use]
53    pub const fn num_roots(&self) -> usize {
54        self.cap.len()
55    }
56
57    /// Returns the height of the cap (log2 of the number of elements).
58    /// A cap with 1 element has height 0, a cap with 2 elements has height 1, etc.
59    #[must_use]
60    pub const fn height(&self) -> usize {
61        log2_strict_usize(self.num_roots())
62    }
63
64    /// Returns a reference to the underlying slice of digests.
65    #[must_use]
66    pub fn roots(&self) -> &[Digest] {
67        &self.cap
68    }
69
70    /// Flattens the cap into a single vector of digest words.
71    pub fn into_roots(self) -> Vec<Digest> {
72        self.cap.into_iter().collect()
73    }
74}
75
76impl<F, Digest> From<Vec<Digest>> for MerkleCap<F, Digest> {
77    fn from(cap: Vec<Digest>) -> Self {
78        Self::new(cap)
79    }
80}
81
82impl<F, W, const N: usize> From<Hash<F, W, N>> for MerkleCap<F, [W; N]> {
83    fn from(hash: Hash<F, W, N>) -> Self {
84        Self::new(vec![hash.into()])
85    }
86}
87
88impl<F, Digest> Borrow<[Digest]> for MerkleCap<F, Digest> {
89    fn borrow(&self) -> &[Digest] {
90        &self.cap
91    }
92}
93
94impl<F, Digest> AsRef<[Digest]> for MerkleCap<F, Digest> {
95    fn as_ref(&self) -> &[Digest] {
96        &self.cap
97    }
98}
99
100impl<F, Digest> core::ops::Index<usize> for MerkleCap<F, Digest> {
101    type Output = Digest;
102
103    fn index(&self, index: usize) -> &Self::Output {
104        &self.cap[index]
105    }
106}
107
108impl<F, Digest> IntoIterator for MerkleCap<F, Digest> {
109    type Item = Digest;
110    type IntoIter = IntoIter<Digest>;
111
112    fn into_iter(self) -> Self::IntoIter {
113        self.cap.into_iter()
114    }
115}
116
117impl<F, W, const DIGEST_ELEMS: usize> From<[W; DIGEST_ELEMS]> for Hash<F, W, DIGEST_ELEMS> {
118    fn from(value: [W; DIGEST_ELEMS]) -> Self {
119        Self {
120            value,
121            _marker: PhantomData,
122        }
123    }
124}
125
126impl<F, W, const DIGEST_ELEMS: usize> From<Hash<F, W, DIGEST_ELEMS>> for [W; DIGEST_ELEMS] {
127    fn from(value: Hash<F, W, DIGEST_ELEMS>) -> [W; DIGEST_ELEMS] {
128        value.value
129    }
130}
131
132impl<F, W: PartialEq, const DIGEST_ELEMS: usize> PartialEq<[W; DIGEST_ELEMS]>
133    for Hash<F, W, DIGEST_ELEMS>
134{
135    fn eq(&self, other: &[W; DIGEST_ELEMS]) -> bool {
136        self.value == *other
137    }
138}
139
140impl<F, W, const DIGEST_ELEMS: usize> IntoIterator for Hash<F, W, DIGEST_ELEMS> {
141    type Item = W;
142    type IntoIter = core::array::IntoIter<W, DIGEST_ELEMS>;
143
144    fn into_iter(self) -> Self::IntoIter {
145        self.value.into_iter()
146    }
147}
148
149impl<F, W, const DIGEST_ELEMS: usize> Borrow<[W; DIGEST_ELEMS]> for Hash<F, W, DIGEST_ELEMS> {
150    fn borrow(&self) -> &[W; DIGEST_ELEMS] {
151        &self.value
152    }
153}
154
155impl<F, W, const DIGEST_ELEMS: usize> AsRef<[W; DIGEST_ELEMS]> for Hash<F, W, DIGEST_ELEMS> {
156    fn as_ref(&self) -> &[W; DIGEST_ELEMS] {
157        &self.value
158    }
159}
p3_symmetric/hash.rs

p3_symmetric/
hash.rs
