binius_core/merkle_tree/
prover.rs

1// Copyright 2024-2025 Irreducible Inc.
2
3use binius_field::TowerField;
4use binius_hash::{multi_digest::ParallelDigest, PseudoCompressionFunction};
5use binius_maybe_rayon::iter::IndexedParallelIterator;
6use bytes::BufMut;
7use digest::{core_api::BlockSizeUser, FixedOutputReset, Output};
8use getset::Getters;
9
10use super::{
11	binary_merkle_tree::{self, BinaryMerkleTree},
12	errors::Error,
13	merkle_tree_vcs::{Commitment, MerkleTreeProver},
14	scheme::BinaryMerkleTreeScheme,
15};
16use crate::transcript::TranscriptWriter;
17
18#[derive(Debug, Getters)]
19pub struct BinaryMerkleTreeProver<T, H: ParallelDigest, C> {
20	#[getset(get = "pub")]
21	scheme: BinaryMerkleTreeScheme<T, H::Digest, C>,
22}
23
24impl<T, C, H: ParallelDigest> BinaryMerkleTreeProver<T, H, C> {
25	pub fn new(compression: C) -> Self {
26		Self {
27			scheme: BinaryMerkleTreeScheme::new(compression),
28		}
29	}
30}
31
32impl<F, H, C> MerkleTreeProver<F> for BinaryMerkleTreeProver<F, H, C>
33where
34	F: TowerField,
35	H: ParallelDigest<Digest: BlockSizeUser + FixedOutputReset>,
36	C: PseudoCompressionFunction<Output<H::Digest>, 2> + Sync,
37{
38	type Scheme = BinaryMerkleTreeScheme<F, H::Digest, C>;
39	type Committed = BinaryMerkleTree<Output<H::Digest>>;
40
41	fn scheme(&self) -> &Self::Scheme {
42		&self.scheme
43	}
44
45	fn commit(
46		&self,
47		data: &[F],
48		batch_size: usize,
49	) -> Result<(Commitment<Output<H::Digest>>, Self::Committed), Error> {
50		let tree =
51			binary_merkle_tree::build::<_, H, _>(self.scheme.compression(), data, batch_size)?;
52
53		let commitment = Commitment {
54			root: tree.root(),
55			depth: tree.log_len,
56		};
57
58		Ok((commitment, tree))
59	}
60
61	fn layer<'a>(
62		&self,
63		committed: &'a Self::Committed,
64		depth: usize,
65	) -> Result<&'a [Output<H::Digest>], Error> {
66		committed.layer(depth)
67	}
68
69	fn prove_opening<B: BufMut>(
70		&self,
71		committed: &Self::Committed,
72		layer_depth: usize,
73		index: usize,
74		proof: &mut TranscriptWriter<B>,
75	) -> Result<(), Error> {
76		let branch = committed.branch(index, layer_depth)?;
77		proof.write_slice(&branch);
78		Ok(())
79	}
80
81	#[allow(clippy::type_complexity)]
82	fn commit_iterated<ParIter>(
83		&self,
84		iterated_chunks: ParIter,
85		log_len: usize,
86	) -> Result<
87		(Commitment<<Self::Scheme as super::MerkleTreeScheme<F>>::Digest>, Self::Committed),
88		Error,
89	>
90	where
91		ParIter: IndexedParallelIterator<Item: IntoIterator<Item = F>>,
92	{
93		let tree = binary_merkle_tree::build_from_iterator::<F, H, C, _>(
94			self.scheme.compression(),
95			iterated_chunks,
96			log_len,
97		)?;
98
99		let commitment = Commitment {
100			root: tree.root(),
101			depth: tree.log_len,
102		};
103
104		Ok((commitment, tree))
105	}
106}
binius_core/merkle_tree/prover.rs

binius_core/merkle_tree/
prover.rs
