binius_iop_prover/merkle_tree/
prover.rs

1// Copyright 2024-2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use binius_compute::{Allocator, GlobalAllocator};
5use binius_field::Field;
6use binius_hash_prover::{BinaryMerkleTree, ParallelHashSuite};
7use binius_iop::merkle_tree::{BinaryMerkleTreeScheme, Commitment};
8use binius_transcript::{BufMut, TranscriptWriter};
9use binius_utils::rayon::iter::IndexedParallelIterator;
10use digest::Output;
11use getset::Getters;
12
13use super::{MerkleTreeProver, ProverDigest};
14
15/// Builds Merkle trees over an allocator, which every tree it commits draws its nodes from.
16///
17/// The allocator is state rather than a per-call argument because [`MerkleTreeProver::Committed`]
18/// names the tree, and an associated type cannot depend on a method's generic parameter.
19#[derive(Getters)]
20pub struct BinaryMerkleTreeProver<T, H: ParallelHashSuite, A: Allocator = GlobalAllocator> {
21	#[getset(get = "pub")]
22	scheme: BinaryMerkleTreeScheme<T, H>,
23	alloc: A,
24}
25
26impl<T, H: ParallelHashSuite> BinaryMerkleTreeProver<T, H, GlobalAllocator> {
27	/// Commits trees on the global heap.
28	pub fn new() -> Self {
29		Self::with_allocator(GlobalAllocator)
30	}
31}
32
33impl<T, H: ParallelHashSuite, A: Allocator> BinaryMerkleTreeProver<T, H, A> {
34	/// Commits trees whose nodes are drawn from `alloc`.
35	///
36	/// Pass `&BufferPool` to recycle node buffers across the proofs one prover runs.
37	pub fn with_allocator(alloc: A) -> Self {
38		Self {
39			scheme: BinaryMerkleTreeScheme::new(),
40			alloc,
41		}
42	}
43}
44
45impl<T, H: ParallelHashSuite> Default for BinaryMerkleTreeProver<T, H, GlobalAllocator> {
46	fn default() -> Self {
47		Self::new()
48	}
49}
50
51impl<F, H, A> MerkleTreeProver<F> for BinaryMerkleTreeProver<F, H, A>
52where
53	F: Field,
54	H: ParallelHashSuite,
55	A: Allocator,
56{
57	type Scheme = BinaryMerkleTreeScheme<F, H>;
58	type Committed = BinaryMerkleTree<Output<H::LeafHash>, A>;
59
60	fn scheme(&self) -> &Self::Scheme {
61		&self.scheme
62	}
63
64	fn layer<'a>(&self, committed: &'a Self::Committed, depth: usize) -> &'a [Output<H::LeafHash>] {
65		committed
66			.layer(depth)
67			.expect("precondition: layer_depth must be at most the committed tree's depth")
68	}
69
70	fn prove_opening<B: BufMut>(
71		&self,
72		committed: &Self::Committed,
73		layer_depth: usize,
74		index: usize,
75		proof: &mut TranscriptWriter<'_, B>,
76	) {
77		let branch = committed
78			.branch(index, layer_depth)
79			.expect("precondition: index and layer_depth must be within the committed tree");
80		proof.write_slice(&branch);
81	}
82
83	fn commit_iterated<ParIter>(
84		&self,
85		leaves: ParIter,
86		n_items_per_input: usize,
87	) -> (Commitment<ProverDigest<F, Self>>, Self::Committed)
88	where
89		ParIter: IndexedParallelIterator<Item: IntoIterator<Item = F, IntoIter: Send>>,
90	{
91		let tree = BinaryMerkleTree::from_leaves::<F, H, _>(leaves, n_items_per_input, &self.alloc);
92
93		let commitment = Commitment {
94			root: tree.root(),
95			depth: tree.log_len,
96		};
97
98		(commitment, tree)
99	}
100}
binius_iop_prover/merkle_tree/prover.rs

binius_iop_prover/merkle_tree/
prover.rs
