binius_core/merkle_tree/
merkle_tree_vcs.rs

1// Copyright 2024-2025 Irreducible Inc.
2
3use binius_maybe_rayon::iter::IndexedParallelIterator;
4use bytes::{Buf, BufMut};
5
6use super::errors::Error;
7use crate::transcript::{TranscriptReader, TranscriptWriter};
8
9/// A Merkle tree commitment.
10///
11/// This struct includes the depth of the tree to guard against attacks that exploit the
12/// indistinguishability of leaf digests from inner node digests.
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub struct Commitment<Digest> {
15	/// The root digest of the Merkle tree.
16	pub root: Digest,
17	/// The depth of the Merkle tree.
18	pub depth: usize,
19}
20
21/// A Merkle tree scheme.
22pub trait MerkleTreeScheme<T>: Sync {
23	type Digest: Clone + PartialEq + Eq;
24
25	/// Returns the optimal layer that the verifier should verify only once.
26	fn optimal_verify_layer(&self, n_queries: usize, tree_depth: usize) -> usize;
27
28	/// Returns the total byte-size of a proof for multiple opening queries.
29	///
30	/// ## Arguments
31	///
32	/// * `len` - the length of the committed vector
33	/// * `n_queries` - the number of opening queries
34	fn proof_size(&self, len: usize, n_queries: usize, layer_depth: usize) -> Result<usize, Error>;
35
36	/// Verify the opening of the full vector.
37	fn verify_vector(
38		&self,
39		root: &Self::Digest,
40		data: &[T],
41		batch_size: usize,
42	) -> Result<(), Error>;
43
44	/// Verify a given layer of the Merkle tree.
45	///
46	/// When a protocol requires verification of many openings at independent and randomly sampled
47	/// indices, it is more efficient for the verifier to verifier an internal layer once, then
48	/// verify all openings with respect to that layer.
49	fn verify_layer(
50		&self,
51		root: &Self::Digest,
52		layer_depth: usize,
53		layer_digests: &[Self::Digest],
54	) -> Result<(), Error>;
55
56	/// Verify an opening proof for an entry in a committed vector at the given index.
57	fn verify_opening<B: Buf>(
58		&self,
59		index: usize,
60		values: &[T],
61		layer_depth: usize,
62		tree_depth: usize,
63		layer_digests: &[Self::Digest],
64		proof: &mut TranscriptReader<B>,
65	) -> Result<(), Error>;
66}
67
68/// A Merkle tree prover for a particular scheme.
69///
70/// This is separate from [`MerkleTreeScheme`] so that it may be implemented using a
71/// hardware-accelerated backend.
72pub trait MerkleTreeProver<T>: Sync {
73	type Scheme: MerkleTreeScheme<T>;
74	/// Data generated during commitment required to generate opening proofs.
75	type Committed;
76
77	/// Returns the Merkle tree scheme used by the prover.
78	fn scheme(&self) -> &Self::Scheme;
79
80	/// Commit a vector of values.
81	#[allow(clippy::type_complexity)]
82	fn commit(
83		&self,
84		data: &[T],
85		batch_size: usize,
86	) -> Result<(Commitment<<Self::Scheme as MerkleTreeScheme<T>>::Digest>, Self::Committed), Error>;
87
88	/// Commit interleaved elements from iterator by val
89	#[allow(clippy::type_complexity)]
90	fn commit_iterated<ParIter>(
91		&self,
92		iterated_chunks: ParIter,
93		log_len: usize,
94	) -> Result<(Commitment<<Self::Scheme as MerkleTreeScheme<T>>::Digest>, Self::Committed), Error>
95	where
96		ParIter: IndexedParallelIterator<Item: IntoIterator<Item = T>>;
97
98	/// Returns the internal digest layer at the given depth.
99	fn layer<'a>(
100		&self,
101		committed: &'a Self::Committed,
102		layer_depth: usize,
103	) -> Result<&'a [<Self::Scheme as MerkleTreeScheme<T>>::Digest], Error>;
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	fn prove_opening<B: BufMut>(
113		&self,
114		committed: &Self::Committed,
115		layer_depth: usize,
116		index: usize,
117		proof: &mut TranscriptWriter<B>,
118	) -> Result<(), Error>;
119}
binius_core/merkle_tree/merkle_tree_vcs.rs

binius_core/merkle_tree/
merkle_tree_vcs.rs
