labrador/commitments/
hierarchical_commitment.rs

1use crate::commitments::ajtai_commitment::{
2    AjtaiCommitment, AjtaiParameters, CommitError, Opening, ParameterError, VerificationError,
3};
4use crate::ring::rq::Rq;
5use crate::ring::rq_matrix::RqMatrix;
6use crate::ring::rq_vector::RqVector;
7use crate::ring::zq::Zq;
8use thiserror::Error;
9
10#[derive(Debug, Error)]
11pub enum HierarchicalError {
12    #[error("parameter error: {0}")]
13    ParameterError(#[from] ParameterError),
14    #[error("commit error: {0}")]
15    CommitError(#[from] CommitError),
16    #[error("verification error: {0}")]
17    VerificationError(#[from] VerificationError),
18    #[error("invalid decomposition base: {0}")]
19    InvalidBase(Zq),
20    #[error("invalid number of parts: {0}")]
21    InvalidPartCount(usize),
22    #[error("empty witness batch")]
23    EmptyWitnessBatch,
24}
25
26/// Parameters for polynomial decomposition in hierarchical commitments
27/// The base parameter controls how coefficients are decomposed
28/// The num_parts parameter determines how many parts each coefficient is split into
29#[derive(Debug, Clone)]
30pub struct DecompositionParameters {
31    base: Zq,
32    num_parts: usize,
33}
34
35impl DecompositionParameters {
36    /// Creates new decomposition parameters with validation
37    /// - base must be greater than 1 for meaningful decomposition
38    /// - num_parts must be positive to ensure decomposition occurs
39    pub fn new(base: Zq, num_parts: usize) -> Result<Self, HierarchicalError> {
40        if base <= Zq::ONE {
41            return Err(HierarchicalError::InvalidBase(base));
42        }
43        if num_parts == 0 {
44            return Err(HierarchicalError::InvalidPartCount(num_parts));
45        }
46
47        Ok(Self { base, num_parts })
48    }
49
50    /// Returns the decomposition base
51    pub fn base(&self) -> Zq {
52        self.base
53    }
54
55    /// Returns the number of decomposition parts
56    pub fn num_parts(&self) -> usize {
57        self.num_parts
58    }
59}
60
61/// Proof structure for hierarchical commitments
62/// Contains all information needed to verify the commitment structure:
63/// - Outer commitment and its opening
64/// - All inner commitments and their openings
65/// - The flattened decomposed parts for consistency checking
66#[derive(Debug, Clone)]
67pub struct HierarchicalProof<const M: usize, const N: usize, const D: usize> {
68    /// Outer commitment that summarizes inner commitments
69    pub outer_commitment: RqVector<M, D>,
70    /// Opening information for the outer commitment
71    pub outer_opening: Opening<N, D>,
72    /// Inner commitments for individual witnesses
73    pub inner_commitments: Vec<RqVector<M, D>>,
74    /// Opening information for each inner commitment
75    pub inner_openings: Vec<Opening<N, D>>,
76    /// Flattened parts of all inner commitments
77    pub flattened_parts: Vec<Rq<D>>,
78}
79
80/// Two-layer commitment structure with inner and outer commitments
81/// - M: Size of commitment output
82/// - N: Size of witness vector
83/// - D: Degree of the polynomials
84#[derive(Debug)]
85pub struct HierarchicalCommitment<const M: usize, const N: usize, const D: usize> {
86    // Inner commitment scheme for individual witnesses
87    inner_scheme: AjtaiCommitment<M, N, D>,
88    // Outer commitment scheme for summarizing inner commitments
89    outer_scheme: AjtaiCommitment<M, N, D>,
90    // Parameters for decomposing polynomials
91    decomp_params: DecompositionParameters,
92}
93
94impl<const M: usize, const N: usize, const D: usize> HierarchicalCommitment<M, N, D> {
95    /// Creates a new hierarchical commitment scheme with separate matrices for inner and outer commitments
96    /// Both schemes use the same AjtaiParameters for consistent security
97    pub fn new(
98        params: AjtaiParameters,
99        inner_matrix: RqMatrix<M, N, D>,
100        outer_matrix: RqMatrix<M, N, D>,
101        decomp_params: DecompositionParameters,
102    ) -> Result<Self, HierarchicalError> {
103        let inner_scheme = AjtaiCommitment::new(params.clone(), inner_matrix)?;
104        let outer_scheme = AjtaiCommitment::new(params, outer_matrix)?;
105
106        Ok(Self {
107            inner_scheme,
108            outer_scheme,
109            decomp_params,
110        })
111    }
112
113    fn decompose_polynomial(&self, poly: &Rq<D>) -> Vec<Rq<D>> {
114        poly.decompose(self.decomp_params.base(), self.decomp_params.num_parts())
115    }
116
117    /// Helper method to decompose all inner commitments into a single flattened vector
118    /// This collects all the decomposed parts from all polynomials in all commitments
119    fn decompose_all_commitments(&self, commitments: &[RqVector<M, D>]) -> Vec<Rq<D>> {
120        let capacity = commitments.len() * M * self.decomp_params.num_parts();
121        let mut all_parts = Vec::with_capacity(capacity);
122        for commitment in commitments {
123            for poly in commitment.iter() {
124                let decomposed_parts = self.decompose_polynomial(poly);
125                all_parts.extend(decomposed_parts);
126            }
127        }
128        all_parts
129    }
130
131    /// Creates a valid outer witness from decomposed parts
132    /// This involves:
133    /// 1. Selecting N polynomials from the decomposed parts
134    /// 2. Ensuring all coefficients are within the witness bound
135    /// 3. Using centered representatives to minimize coefficient size
136    fn create_outer_witness(&self, parts: &[Rq<D>]) -> RqVector<N, D> {
137        let witness_bound = self.outer_scheme.witness_bound();
138        let mut combined_coeffs = Vec::with_capacity(N);
139
140        // Handle the case where we have more or fewer parts than N
141        if parts.len() >= N {
142            // Take the first N parts
143            for part in parts.iter().take(N) {
144                combined_coeffs.push(part.clone());
145            }
146        } else {
147            // Use all available parts and pad with zeros
148            for part in parts {
149                combined_coeffs.push(part.clone());
150            }
151
152            // Pad with zeros to reach size N
153            while combined_coeffs.len() < N {
154                combined_coeffs.push(Rq::zero());
155            }
156        }
157
158        // Apply witness bounds to ensure all coefficients are valid
159        let mut bounded_coeffs = Vec::with_capacity(N);
160        for poly in &combined_coeffs {
161            // Create a new polynomial with bounded coefficients
162            let mut bounded_coeffs_array = [Zq::ZERO; D];
163            for (i, coeff) in poly.get_coefficients().iter().enumerate() {
164                bounded_coeffs_array[i] = coeff.centered_mod(witness_bound);
165            }
166            bounded_coeffs.push(Rq::new(bounded_coeffs_array));
167        }
168
169        RqVector::from(bounded_coeffs)
170    }
171
172    /// Commits to a batch of witnesses using the hierarchical structure
173    /// This creates both inner commitments for each witness and an outer commitment
174    /// that summarizes them all, providing a more compact representation
175    pub fn commit_batch(
176        &self,
177        witnesses: &[RqVector<N, D>],
178    ) -> Result<HierarchicalProof<M, N, D>, HierarchicalError> {
179        if witnesses.is_empty() {
180            return Err(HierarchicalError::EmptyWitnessBatch);
181        }
182
183        // Generate inner commitments and openings
184        let mut inner_commitments = Vec::with_capacity(witnesses.len());
185        let mut inner_openings = Vec::with_capacity(witnesses.len());
186
187        for witness in witnesses {
188            let (commitment, opening) = self.inner_scheme.commit(witness.clone())?;
189            inner_commitments.push(commitment);
190            inner_openings.push(opening);
191        }
192
193        // Decompose inner commitments and create a flattened vector for the outer commitment
194        let flattened_parts = self.decompose_all_commitments(&inner_commitments);
195
196        // Create a valid outer witness
197        let outer_witness = self.create_outer_witness(&flattened_parts);
198
199        // Create outer commitment
200        let (outer_commitment, outer_opening) = self.outer_scheme.commit(outer_witness)?;
201
202        Ok(HierarchicalProof {
203            outer_commitment,
204            outer_opening,
205            inner_commitments,
206            inner_openings,
207            flattened_parts,
208        })
209    }
210
211    /// Verifies a hierarchical proof
212    /// This ensures:
213    /// 1. All inner commitments match their openings
214    /// 2. The decomposed parts match what's stored in the proof
215    /// 3. The outer commitment correctly summarizes the inner commitments
216    /// 4. The outer commitment matches its opening
217    pub fn verify(&self, proof: &HierarchicalProof<M, N, D>) -> Result<(), HierarchicalError> {
218        // Verify each inner commitment
219        for (commitment, opening) in proof
220            .inner_commitments
221            .iter()
222            .zip(proof.inner_openings.iter())
223        {
224            self.inner_scheme.verify(commitment, opening)?;
225        }
226
227        // Verify outer commitment consistency
228        // First, decompose inner commitments
229        let flattened_parts = self.decompose_all_commitments(&proof.inner_commitments);
230
231        // Compare with stored flattened parts
232        if flattened_parts != proof.flattened_parts {
233            return Err(HierarchicalError::VerificationError(
234                VerificationError::CommitmentMismatch,
235            ));
236        }
237
238        // Create the same outer witness
239        let outer_witness = self.create_outer_witness(&flattened_parts);
240
241        // Create expected outer commitment
242        let (expected_outer, _) = self.outer_scheme.commit(outer_witness)?;
243
244        // Check if outer commitment matches expected
245        if proof.outer_commitment != expected_outer {
246            return Err(HierarchicalError::VerificationError(
247                VerificationError::CommitmentMismatch,
248            ));
249        }
250
251        // Verify outer opening
252        self.outer_scheme
253            .verify(&proof.outer_commitment, &proof.outer_opening)?;
254
255        Ok(())
256    }
257
258    /// Returns a reference to the inner commitment scheme
259    pub fn inner_scheme(&self) -> &AjtaiCommitment<M, N, D> {
260        &self.inner_scheme
261    }
262
263    /// Returns a reference to the outer commitment scheme
264    pub fn outer_scheme(&self) -> &AjtaiCommitment<M, N, D> {
265        &self.outer_scheme
266    }
267
268    /// Returns a reference to the decomposition parameters
269    pub fn decomp_params(&self) -> &DecompositionParameters {
270        &self.decomp_params
271    }
272}
273
274#[cfg(test)]
275mod tests {
276    use super::*;
277    use rand::rng;
278
279    const TEST_M: usize = 8;
280    const TEST_N: usize = 8;
281    const TEST_D: usize = 4;
282
283    // Test helpers
284    fn create_test_scheme() -> HierarchicalCommitment<TEST_M, TEST_N, TEST_D> {
285        let beta = Zq::ONE;
286        let witness_bound = Zq::ONE;
287        let params = AjtaiParameters::new(beta, witness_bound).unwrap();
288
289        let mut rng = rng();
290        let inner_matrix = RqMatrix::<TEST_M, TEST_N, TEST_D>::random(&mut rng);
291        let outer_matrix = RqMatrix::<TEST_M, TEST_N, TEST_D>::random(&mut rng);
292
293        let decomp_params = DecompositionParameters::new(Zq::new(8), 2).unwrap();
294
295        HierarchicalCommitment::new(params, inner_matrix, outer_matrix, decomp_params).unwrap()
296    }
297
298    fn create_random_witnesses(count: usize) -> Vec<RqVector<TEST_N, TEST_D>> {
299        let mut rng = rng();
300        (0..count)
301            .map(|_| RqVector::random_ternary(&mut rng))
302            .collect()
303    }
304
305    #[test]
306    fn test_decomposition_parameters() {
307        assert!(DecompositionParameters::new(Zq::ZERO, 2).is_err());
308        assert!(DecompositionParameters::new(Zq::TWO, 0).is_err());
309        let params = DecompositionParameters::new(Zq::new(8), 3).unwrap();
310        assert_eq!(params.base(), Zq::new(8));
311        assert_eq!(params.num_parts(), 3);
312    }
313
314    #[test]
315    fn test_hierarchical_creation() {
316        let _ = create_test_scheme();
317    }
318
319    #[test]
320    fn test_commit_and_verify() {
321        let scheme = create_test_scheme();
322        let witnesses = create_random_witnesses(3);
323
324        let proof = scheme.commit_batch(&witnesses).unwrap();
325        assert!(scheme.verify(&proof).is_ok());
326    }
327
328    #[test]
329    fn test_tampered_inner_commitment() {
330        let scheme = create_test_scheme();
331        let witnesses = create_random_witnesses(3);
332
333        let mut proof = scheme.commit_batch(&witnesses).unwrap();
334
335        // Tamper with an inner commitment
336        let mut rng = rng();
337        proof.inner_commitments[0] = RqVector::random(&mut rng);
338
339        assert!(scheme.verify(&proof).is_err());
340    }
341
342    #[test]
343    fn test_tampered_outer_commitment() {
344        let scheme = create_test_scheme();
345        let witnesses = create_random_witnesses(3);
346
347        let mut proof = scheme.commit_batch(&witnesses).unwrap();
348
349        // Tamper with the outer commitment
350        let mut rng = rng();
351        proof.outer_commitment = RqVector::random(&mut rng);
352
353        assert!(scheme.verify(&proof).is_err());
354    }
355}
labrador/commitments/hierarchical_commitment.rs

labrador/commitments/
hierarchical_commitment.rs
