binius_core/merkle_tree_vcs/
prover.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
// Copyright 2024 Irreducible Inc.

use super::{
	binary_merkle_tree::BinaryMerkleTree,
	errors::Error,
	merkle_tree_vcs::{Commitment, MerkleTreeProver},
	scheme::BinaryMerkleTreeScheme,
};
use binius_field::PackedField;
use binius_hash::Hasher;
use p3_symmetric::PseudoCompressionFunction;
use rayon::iter::IndexedParallelIterator;
use std::marker::PhantomData;

pub struct BinaryMerkleTreeProver<D, H, C> {
	compression: C,
	scheme: BinaryMerkleTreeScheme<D, H, C>,
	_phantom: PhantomData<(D, H)>,
}

impl<D, C: Clone, H> BinaryMerkleTreeProver<D, H, C> {
	pub fn new(compression: C) -> Self {
		let scheme = BinaryMerkleTreeScheme::new(compression.clone());

		Self {
			compression,
			scheme,
			_phantom: PhantomData,
		}
	}
}

impl<T, D, H, C> MerkleTreeProver<T> for BinaryMerkleTreeProver<D, H, C>
where
	D: PackedField,
	T: Sync,
	H: Hasher<T, Digest = D> + Send,
	C: PseudoCompressionFunction<D, 2> + Sync,
{
	type Scheme = BinaryMerkleTreeScheme<D, H, C>;

	type Committed = BinaryMerkleTree<D>;

	fn scheme(&self) -> &Self::Scheme {
		&self.scheme
	}

	fn commit(
		&self,
		data: &[T],
		batch_size: usize,
	) -> Result<(Commitment<D>, Self::Committed), Error> {
		let tree = BinaryMerkleTree::build::<_, H, _>(&self.compression, data, batch_size)?;

		let commitment = Commitment {
			root: tree.root(),
			depth: tree.log_len,
		};

		Ok((commitment, tree))
	}

	fn layer<'a>(&self, committed: &'a Self::Committed, depth: usize) -> Result<&'a [D], Error> {
		committed.layer(depth)
	}

	fn prove_opening(
		&self,
		committed: &Self::Committed,
		layer_depth: usize,
		index: usize,
	) -> Result<Vec<D>, Error> {
		committed.branch(index, layer_depth)
	}

	fn commit_iterated<ParIter>(
		&self,
		iterated_chunks: ParIter,
		log_len: usize,
	) -> Result<
		(Commitment<<Self::Scheme as super::MerkleTreeScheme<T>>::Digest>, Self::Committed),
		Error,
	>
	where
		ParIter: IndexedParallelIterator<Item: IntoIterator<Item = T>>,
	{
		let tree = BinaryMerkleTree::build_from_iterator::<T, H, C, ParIter>(
			&self.compression,
			iterated_chunks,
			log_len,
		)?;

		let commitment = Commitment {
			root: tree.root(),
			depth: tree.log_len,
		};

		Ok((commitment, tree))
	}
}