binius_iop/merkle_tree/
merkle_tree_vcs.rs

1// Copyright 2024-2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4use binius_transcript::{Buf, TranscriptReader};
5use binius_utils::FixedSizeSerializeBytes;
6
7use super::error::Error;
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: FixedSizeSerializeBytes> {
23	/// The digest of a leaf or an inner node.
24	type Digest: Clone + PartialEq + Eq;
25
26	/// Returns the optimal layer that the verifier should verify only once.
27	///
28	/// Decommitting a layer at depth `d` costs `2^d` digests but shortens every one of the
29	/// `n_queries` branches by `d`, so the proof holds
30	///
31	/// ```text
32	/// (tree_depth - d) * n_queries + 2^d
33	/// ```
34	///
35	/// digests. That is minimized at `d = ceil(log2(n_queries))`, clamped to the tree depth.
36	fn optimal_verify_layer(&self, n_queries: usize, tree_depth: usize) -> usize;
37
38	/// Returns the total byte-size of a proof for multiple opening queries.
39	///
40	/// ## Arguments
41	///
42	/// * `len` - the length of the committed vector
43	/// * `n_queries` - the number of opening queries
44	/// * `layer_depth` - the depth of the internal layer the verifier decommits once and verifies
45	///   all openings against (see [`Self::optimal_verify_layer`])
46	///
47	/// ## Preconditions
48	///
49	/// * `len` must be a power of two.
50	/// * `layer_depth` must be at most `log2(len)`.
51	fn proof_size(&self, len: usize, n_queries: usize, layer_depth: usize) -> usize;
52
53	/// Verify the opening of the full vector.
54	///
55	/// The committed values are the whole opening, so there is no decommitment advice to read.
56	///
57	/// ## Preconditions
58	///
59	/// * `batch_size` must be non-zero.
60	/// * `data.len()` must be a multiple of `batch_size`.
61	/// * `data.len() / batch_size` must be a non-zero power of two.
62	fn verify_vector(
63		&self,
64		root: &Self::Digest,
65		data: &[T],
66		batch_size: usize,
67	) -> Result<(), Error>;
68
69	/// Verify a given layer of the Merkle tree.
70	///
71	/// When a protocol requires verification of many openings at independent and randomly sampled
72	/// indices, it is more efficient for the verifier to verifier an internal layer once, then
73	/// verify all openings with respect to that layer.
74	///
75	/// ## Preconditions
76	///
77	/// * `layer_digests.len()` must equal `2^layer_depth`.
78	fn verify_layer(
79		&self,
80		root: &Self::Digest,
81		layer_depth: usize,
82		layer_digests: &[Self::Digest],
83	) -> Result<(), Error>;
84
85	/// Verify an opening proof for an entry in a committed vector at the given index.
86	///
87	/// ## Preconditions
88	///
89	/// * `layer_digests.len()` must equal `2^layer_depth`.
90	/// * `layer_depth` must be at most `tree_depth`.
91	/// * `index` must be less than `2^tree_depth`.
92	fn verify_opening<B: Buf>(
93		&self,
94		index: usize,
95		values: &[T],
96		layer_depth: usize,
97		tree_depth: usize,
98		layer_digests: &[Self::Digest],
99		proof: &mut TranscriptReader<'_, B>,
100	) -> Result<(), Error>;
101}
binius_iop/merkle_tree/merkle_tree_vcs.rs

binius_iop/merkle_tree/
merkle_tree_vcs.rs
