Skip to main content

binius_iop/merkle_tree/
scheme.rs

1// Copyright 2024-2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use 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
22/// A binary Merkle tree vector commitment, as seen by the verifier.
23///
24/// A committed vector is cut into equal-size batches of values.
25/// Each batch is hashed into one leaf digest.
26/// Pairs of digests are then folded upward until a single root digest remains.
27pub struct BinaryMerkleTreeScheme<T, H: HashSuite> {
28	/// Two-to-one function folding a pair of child digests into their parent digest.
29	compression: H::Compression,
30	// This makes it so that `BinaryMerkleTreeScheme` remains Send + Sync regardless of `T`.
31	// See https://doc.rust-lang.org/nomicon/phantom-data.html#table-of-phantomdata-patterns
32	_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			// The compression function is stateless, so one default instance serves every call.
45			compression: H::Compression::default(),
46			_phantom: PhantomData,
47		}
48	}
49
50	/// Folds a layer of digests down to the single root above it.
51	///
52	/// Each round pairs neighbours and replaces them with their parent, halving the layer:
53	///
54	/// ```text
55	///     [d_0, d_1, ..., d_{n-1}]  ->  [C(d_0, d_1), ..., C(d_{n-2}, d_{n-1})]
56	/// ```
57	///
58	/// After `log_2(n)` rounds exactly one digest is left, and that digest is the root.
59	///
60	/// # Panics
61	///
62	/// Panics unless the number of digests is a non-zero power of two.
63	///
64	/// # Performance
65	///
66	/// One allocation of `n / 2` digests in total, reused by every round after the first.
67	fn fold_to_root(&self, digests: &[Output<H::LeafHash>]) -> Output<H::LeafHash> {
68		// A layer that is not a power of two cannot be paired off cleanly.
69		// An empty layer spans no subtree at all.
70		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		// A lone digest already is the root of its subtree; folding it would invent a level.
76		if let [root] = digests {
77			return root.clone();
78		}
79
80		// The first round reads the caller's slice and writes into fresh space.
81		// That caps the scratch buffer at half the input length.
82		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		// Later rounds halve the buffer in place.
92		// A parent lands strictly below both children it replaces, so nothing is overwritten early.
93		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			// Drop the tail the round just consumed, keeping the allocation.
101			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		// Written out rather than derived: a derived copy would demand a cloneable value type.
113		// No value of that type is ever held.
114		// The compression function is always cloneable through its own trait bound.
115		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		// Written out for the same reason as the copy above.
125		// The compression function carries no formatting bound, and the scheme holds no state
126		// beyond it.
127		f.debug_struct("BinaryMerkleTreeScheme").finish()
128	}
129}
130
131impl<T, H> BinaryMerkleTreeScheme<T, H>
132where
133	T: FixedSizeSerializeBytes,
134	H: HashSuite,
135{
136	/// Hashes one leaf from the values it holds.
137	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		// Raising the layer by one level doubles its width but shortens every branch by one.
151		// The two effects balance where the layer width first reaches the query count.
152		//
153		// A layer can never sit below the leaves, hence the clamp.
154		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		// Depth of the tree spanning the committed vector.
161		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		// Each query walks from its leaf up to the decommitted layer, one sibling per level.
166		// The layer itself is sent once, for all queries together.
167		//
168		//     branches: (log_len - layer_depth) * n_queries
169		//     layer   : 2^layer_depth
170		((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		// A zero-size batch would slice the data into unboundedly many empty leaves.
181		assert_ne!(batch_size, 0, "precondition: batch_size must be non-zero");
182		// Every leaf holds the same number of values, so the split has to come out even.
183		assert!(
184			data.len().is_multiple_of(batch_size),
185			"precondition: data length must be a multiple of batch_size"
186		);
187		// A binary tree only spans a power-of-two number of leaves.
188		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		// Rebuild every leaf digest from the revealed values.
194		let digests = data
195			.chunks(batch_size)
196			.map(|chunk| self.compute_leaf_digest(chunk))
197			.collect::<Result<Vec<_>, _>>()?;
198
199		// Rebuilding the whole tree and landing on the committed root is what binds the data.
200		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		// A layer that many levels below the root holds exactly that many digests.
213		assert_eq!(
214			layer_digests.len(),
215			1 << layer_depth,
216			"precondition: layer_digests must have 2^layer_depth entries"
217		);
218
219		// Folding the claimed layer must reproduce the committed root.
220		// The fold takes one round per level, so a layer only passes at the depth it claims.
221		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		// A layer that many levels below the root holds exactly that many digests.
237		assert_eq!(
238			layer_digests.len(),
239			1 << layer_depth,
240			"precondition: layer_digests must have 2^layer_depth entries"
241		);
242		// The climb runs from the leaves up to the layer, so the layer cannot sit below them.
243		assert!(layer_depth <= tree_depth, "precondition: layer_depth must be at most tree_depth");
244		// A tree of that depth has exactly that many leaves to address.
245		assert!(index < (1 << tree_depth), "precondition: index must be less than 2^tree_depth");
246
247		// Bottom of the authentication path: the leaf the opening claims.
248		let mut digest = self.compute_leaf_digest(values)?;
249
250		// Climb one level per round, folding in the sibling the advice supplies.
251		//
252		//     level k:  running digest + sibling_k  ->  running digest at level k+1
253		//
254		// The low bit of the running index says which side the running digest sits on.
255		for _ in layer_depth..tree_depth {
256			let sibling = proof.read::<Self::Digest>()?;
257			// An even index means the running digest is the left child of its parent.
258			digest = self.compression.compress(if index & 1 == 0 {
259				[digest, sibling]
260			} else {
261				[sibling, digest]
262			});
263			// Discard the bit just consumed, exposing the next level's side bit.
264			index >>= 1;
265		}
266
267		// The climb dropped one bit per level, so what is left addresses the decommitted layer.
268		// Matching the entry there binds the leaf to the already-verified layer, hence the root.
269		if digest != layer_digests[index] {
270			return Err(VerificationError::InvalidProof.into());
271		}
272		Ok(())
273	}
274}