binius_iop/merkle_tree/
scheme.rs1use std::{
5 fmt::{self, Debug, Formatter},
6 marker::PhantomData,
7};
8
9use binius_hash::{CompressionFunction, HashSuite, hash_serialize};
10use binius_transcript::{Buf, TranscriptReader};
11use binius_utils::{
12 FixedSizeSerializeBytes,
13 checked_arithmetics::{checked_log_2, log2_ceil_usize},
14};
15use digest::{Digest, Output};
16
17use super::{
18 error::{Error, VerificationError},
19 merkle_tree_vcs::MerkleTreeScheme,
20};
21
22pub struct BinaryMerkleTreeScheme<T, H: HashSuite> {
28 compression: H::Compression,
30 _phantom: PhantomData<fn() -> T>,
33}
34
35impl<T, H: HashSuite> Default for BinaryMerkleTreeScheme<T, H> {
36 fn default() -> Self {
37 Self::new()
38 }
39}
40
41impl<T, H: HashSuite> BinaryMerkleTreeScheme<T, H> {
42 pub fn new() -> Self {
43 Self {
44 compression: H::Compression::default(),
46 _phantom: PhantomData,
47 }
48 }
49
50 fn fold_to_root(&self, digests: &[Output<H::LeafHash>]) -> Output<H::LeafHash> {
68 assert!(
71 digests.len().is_power_of_two(),
72 "precondition: the number of digests must be a non-zero power of two"
73 );
74
75 if let [root] = digests {
77 return root.clone();
78 }
79
80 let (pairs, _) = digests.as_chunks::<2>();
83 let mut layer = pairs
84 .iter()
85 .map(|pair| {
86 self.compression
87 .compress([pair[0].clone(), pair[1].clone()])
88 })
89 .collect::<Vec<_>>();
90
91 while layer.len() > 1 {
94 let half = layer.len() / 2;
95 for i in 0..half {
96 layer[i] = self
97 .compression
98 .compress([layer[2 * i].clone(), layer[2 * i + 1].clone()]);
99 }
100 layer.truncate(half);
102 }
103
104 layer
105 .pop()
106 .expect("a non-empty layer folds down to exactly one digest")
107 }
108}
109
110impl<T, H: HashSuite> Clone for BinaryMerkleTreeScheme<T, H> {
111 fn clone(&self) -> Self {
112 Self {
116 compression: self.compression.clone(),
117 _phantom: PhantomData,
118 }
119 }
120}
121
122impl<T, H: HashSuite> Debug for BinaryMerkleTreeScheme<T, H> {
123 fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
124 f.debug_struct("BinaryMerkleTreeScheme").finish()
128 }
129}
130
131impl<T, H> BinaryMerkleTreeScheme<T, H>
132where
133 T: FixedSizeSerializeBytes,
134 H: HashSuite,
135{
136 fn compute_leaf_digest(&self, values: &[T]) -> Result<Output<H::LeafHash>, Error> {
138 Ok(hash_serialize::<T, H::LeafHash>(values)?)
139 }
140}
141
142impl<T, H> MerkleTreeScheme<T> for BinaryMerkleTreeScheme<T, H>
143where
144 T: FixedSizeSerializeBytes,
145 H: HashSuite,
146{
147 type Digest = Output<H::LeafHash>;
148
149 fn optimal_verify_layer(&self, n_queries: usize, tree_depth: usize) -> usize {
150 log2_ceil_usize(n_queries).min(tree_depth)
155 }
156
157 fn proof_size(&self, len: usize, n_queries: usize, layer_depth: usize) -> usize {
158 assert!(len.is_power_of_two(), "precondition: len must be a power of two");
159
160 let log_len = checked_log_2(len);
162
163 assert!(layer_depth <= log_len, "precondition: layer_depth must be at most log2(len)");
164
165 ((log_len - layer_depth) * n_queries + (1 << layer_depth))
171 * <H::LeafHash as Digest>::output_size()
172 }
173
174 fn verify_vector(
175 &self,
176 root: &Self::Digest,
177 data: &[T],
178 batch_size: usize,
179 ) -> Result<(), Error> {
180 assert_ne!(batch_size, 0, "precondition: batch_size must be non-zero");
182 assert!(
184 data.len().is_multiple_of(batch_size),
185 "precondition: data length must be a multiple of batch_size"
186 );
187 assert!(
189 (data.len() / batch_size).is_power_of_two(),
190 "precondition: data.len() / batch_size must be a non-zero power of two"
191 );
192
193 let digests = data
195 .chunks(batch_size)
196 .map(|chunk| self.compute_leaf_digest(chunk))
197 .collect::<Result<Vec<_>, _>>()?;
198
199 if self.fold_to_root(&digests) != *root {
201 return Err(VerificationError::InvalidProof.into());
202 }
203 Ok(())
204 }
205
206 fn verify_layer(
207 &self,
208 root: &Self::Digest,
209 layer_depth: usize,
210 layer_digests: &[Self::Digest],
211 ) -> Result<(), Error> {
212 assert_eq!(
214 layer_digests.len(),
215 1 << layer_depth,
216 "precondition: layer_digests must have 2^layer_depth entries"
217 );
218
219 if self.fold_to_root(layer_digests) != *root {
222 return Err(VerificationError::InvalidProof.into());
223 }
224 Ok(())
225 }
226
227 fn verify_opening<B: Buf>(
228 &self,
229 mut index: usize,
230 values: &[T],
231 layer_depth: usize,
232 tree_depth: usize,
233 layer_digests: &[Self::Digest],
234 proof: &mut TranscriptReader<'_, B>,
235 ) -> Result<(), Error> {
236 assert_eq!(
238 layer_digests.len(),
239 1 << layer_depth,
240 "precondition: layer_digests must have 2^layer_depth entries"
241 );
242 assert!(layer_depth <= tree_depth, "precondition: layer_depth must be at most tree_depth");
244 assert!(index < (1 << tree_depth), "precondition: index must be less than 2^tree_depth");
246
247 let mut digest = self.compute_leaf_digest(values)?;
249
250 for _ in layer_depth..tree_depth {
256 let sibling = proof.read::<Self::Digest>()?;
257 digest = self.compression.compress(if index & 1 == 0 {
259 [digest, sibling]
260 } else {
261 [sibling, digest]
262 });
263 index >>= 1;
265 }
266
267 if digest != layer_digests[index] {
270 return Err(VerificationError::InvalidProof.into());
271 }
272 Ok(())
273 }
274}