binius_iop_prover/merkle_tree/
mod.rs

1// Copyright 2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use binius_field::PackedField;
5use binius_iop::merkle_tree::{Commitment, MerkleTreeScheme};
6use binius_math::FieldSlice;
7use binius_transcript::{BufMut, TranscriptWriter};
8use binius_utils::{FixedSizeSerializeBytes, rayon::prelude::*};
9
10pub mod prover;
11#[cfg(test)]
12mod tests;
13
14/// The digest type produced by a Merkle tree prover's scheme.
15pub type ProverDigest<T, M> = <<M as MerkleTreeProver<T>>::Scheme as MerkleTreeScheme<T>>::Digest;
16
17/// A Merkle tree prover for a particular scheme.
18///
19/// This is separate from [`MerkleTreeScheme`] so that it may be implemented using a
20/// hardware-accelerated backend.
21pub trait MerkleTreeProver<T: FixedSizeSerializeBytes> {
22	type Scheme: MerkleTreeScheme<T>;
23	/// Data generated during commitment required to generate opening proofs.
24	type Committed;
25
26	/// Returns the Merkle tree scheme used by the prover.
27	fn scheme(&self) -> &Self::Scheme;
28
29	/// Commit a vector of values.
30	///
31	/// ## Preconditions
32	///
33	/// * `data.len()` must be a multiple of `batch_size`, and the resulting leaf count (`data.len()
34	///   / batch_size`) must be a power of two.
35	fn commit(
36		&self,
37		data: &[T],
38		batch_size: usize,
39	) -> (Commitment<ProverDigest<T, Self>>, Self::Committed)
40	where
41		T: Clone + Sync,
42	{
43		self.commit_iterated(
44			data.par_chunks_exact(batch_size)
45				.map(|chunk| chunk.iter().cloned()),
46			batch_size,
47		)
48	}
49
50	/// Commits a field buffer, packing `2^log_leaf_len` scalars into each leaf.
51	///
52	/// Scalars fill leaves in order:
53	///
54	/// ```text
55	/// leaf i  <-  buffer[i * 2^log_leaf_len .. (i+1) * 2^log_leaf_len]
56	/// ```
57	///
58	/// The leaf count is `2^(log_len - log_leaf_len)`, hence a power of two by construction.
59	/// That is what [`commit_iterated`](Self::commit_iterated) requires of it.
60	///
61	/// ## Preconditions
62	///
63	/// * `log_leaf_len` must be at most the buffer's log length.
64	fn commit_field_buffer<P>(
65		&self,
66		buffer: FieldSlice<'_, P>,
67		log_leaf_len: usize,
68	) -> (Commitment<ProverDigest<T, Self>>, Self::Committed)
69	where
70		P: PackedField<Scalar = T>,
71	{
72		// Invariant: leaves are counted in scalar space, never in backing words.
73		// A buffer narrower than one packed word therefore commits no dead lanes.
74		self.commit_iterated(buffer.par_chunk_scalars(log_leaf_len), 1 << log_leaf_len)
75	}
76
77	/// Commit interleaved elements from iterator by val
78	///
79	/// Each leaf is built from exactly `n_items_per_input` elements, which lets the leaf hasher
80	/// specialize for short, constant-length leaves.
81	///
82	/// ## Preconditions
83	///
84	/// * The number of leaves must be a power of two.
85	/// * Each iterator in `leaves` yields exactly `n_items_per_input` elements.
86	fn commit_iterated<ParIter>(
87		&self,
88		leaves: ParIter,
89		n_items_per_input: usize,
90	) -> (Commitment<ProverDigest<T, Self>>, Self::Committed)
91	where
92		ParIter: IndexedParallelIterator<Item: IntoIterator<Item = T, IntoIter: Send>>;
93
94	/// Returns the internal digest layer at the given depth.
95	///
96	/// ## Preconditions
97	///
98	/// * `layer_depth` must be at most the committed tree's depth.
99	fn layer<'a>(
100		&self,
101		committed: &'a Self::Committed,
102		layer_depth: usize,
103	) -> &'a [<Self::Scheme as MerkleTreeScheme<T>>::Digest];
104
105	/// Generate an opening proof for an entry in a committed vector at the given index.
106	///
107	/// ## Arguments
108	///
109	/// * `committed` - helper data generated during commitment
110	/// * `layer_depth` - depth of the layer to prove inclusion in
111	/// * `index` - the entry index
112	///
113	/// ## Preconditions
114	///
115	/// * `index` must be within the committed tree and `layer_depth` at most its depth.
116	fn prove_opening<B: BufMut>(
117		&self,
118		committed: &Self::Committed,
119		layer_depth: usize,
120		index: usize,
121		proof: &mut TranscriptWriter<'_, B>,
122	);
123}
binius_iop_prover/merkle_tree/mod.rs

binius_iop_prover/merkle_tree/
mod.rs
