proof_of_sql/proof_primitive/dory/
dory_commitment.rs

1//! Module containing the `DoryCommitment` type and its implementation.
2//!
3//! While this can be used as a black box, it can be helpful to understand the underlying structure of the commitment.
4//! Ultimately, the commitment is a commitment to a Matrix. This matrix is filled out from a column in the following fashion.
5//!
6//! We let `sigma` be a parameter that specifies the number of non-zero columns in the matrix.
7//! More specifically, the number of non-zero columns is `2^sigma`.
8//!
9//! For an example, we will set `sigma=2` and thus, the number of columns is 4.
10//! The column `[100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115]` with offset 9 is converted to the following matrix:
11//! ```ignore
12//!  0   0   0   0
13//!  0   0   0   0
14//!  0  100 101 102
15//! 103 104 105 106
16//! 107 108 109 110
17//! 111 112 113 114
18//! 115  0   0   0
19//! ```
20//! This matrix is then committed to using a matrix commitment.
21//!
22//! Note: the `VecCommitmentExt` trait requires using this offset when computing commitments.
23//! This is to allow for updateability of the commitments as well as to allow for smart indexing/partitioning.
24
25use super::{DoryProverPublicSetup, GT};
26use crate::base::{
27    commitment::{Commitment, CommittableColumn},
28    impl_serde_for_ark_serde_checked,
29    scalar::MontScalar,
30};
31use alloc::vec::Vec;
32use ark_ec::pairing::PairingOutput;
33use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
34use core::ops::Mul;
35use derive_more::{AddAssign, Neg, Sub, SubAssign};
36use num_traits::One;
37
38/// The Dory scalar type. (alias for `MontScalar<ark_bls12_381::FrConfig>`)
39pub type DoryScalar = MontScalar<ark_bls12_381::FrConfig>;
40
41#[derive(
42    Debug,
43    Sub,
44    Eq,
45    PartialEq,
46    Neg,
47    Copy,
48    Clone,
49    AddAssign,
50    SubAssign,
51    CanonicalSerialize,
52    CanonicalDeserialize,
53)]
54/// The Dory commitment type.
55pub struct DoryCommitment(pub(super) GT);
56
57/// The default for GT is the additive identity, but should be the multiplicative identity.
58impl Default for DoryCommitment {
59    fn default() -> Self {
60        Self(PairingOutput(One::one()))
61    }
62}
63
64// Traits required for `DoryCommitment` to impl `Commitment`.
65impl_serde_for_ark_serde_checked!(DoryCommitment);
66impl Mul<DoryCommitment> for DoryScalar {
67    type Output = DoryCommitment;
68    fn mul(self, rhs: DoryCommitment) -> Self::Output {
69        DoryCommitment(rhs.0 * self.0)
70    }
71}
72impl<'a> Mul<&'a DoryCommitment> for DoryScalar {
73    type Output = DoryCommitment;
74    fn mul(self, rhs: &'a DoryCommitment) -> Self::Output {
75        DoryCommitment(rhs.0 * self.0)
76    }
77}
78impl Commitment for DoryCommitment {
79    type Scalar = DoryScalar;
80    type PublicSetup<'a> = DoryProverPublicSetup<'a>;
81
82    fn compute_commitments(
83        committable_columns: &[CommittableColumn],
84        offset: usize,
85        setup: &Self::PublicSetup<'_>,
86    ) -> Vec<Self> {
87        super::compute_dory_commitments(committable_columns, offset, setup)
88    }
89
90    fn to_transcript_bytes(&self) -> Vec<u8> {
91        let mut buf = Vec::with_capacity(self.0.compressed_size());
92        self.0.serialize_compressed(&mut buf).unwrap();
93        buf
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    use super::{DoryCommitment, DoryProverPublicSetup, DoryScalar, GT};
100    use crate::{
101        base::{
102            commitment::{Commitment, NumColumnsMismatch, VecCommitmentExt},
103            database::{Column, OwnedColumn},
104            scalar::test_scalar_constants,
105        },
106        proof_primitive::dory::{rand_util::test_rng, ProverSetup, PublicParameters},
107    };
108    use ark_ec::pairing::Pairing;
109    use ark_ff::UniformRand;
110    use rand::{rngs::StdRng, SeedableRng};
111
112    #[test]
113    fn we_have_correct_constants_for_dory_scalar() {
114        test_scalar_constants::<DoryScalar>();
115    }
116
117    #[test]
118    fn we_can_convert_from_columns() {
119        let public_parameters = PublicParameters::test_rand(5, &mut test_rng());
120        let prover_setup = ProverSetup::from(&public_parameters);
121        let setup = DoryProverPublicSetup::new(&prover_setup, 2);
122        let Gamma_1 = &public_parameters.Gamma_1;
123        let Gamma_2 = &public_parameters.Gamma_2;
124
125        // empty case
126        let commitments = Vec::<DoryCommitment>::from_columns_with_offset(
127            Vec::<Column<DoryScalar>>::new(),
128            0,
129            &setup,
130        );
131
132        assert!(commitments.is_empty());
133
134        // nonempty case
135        let column_a = [12i64, 34, 56];
136        let column_b = ["Lorem", "ipsum", "dolor"].map(String::from);
137
138        let columns = vec![
139            OwnedColumn::<DoryScalar>::BigInt(column_a.to_vec()),
140            OwnedColumn::VarChar(column_b.to_vec()),
141        ];
142
143        let commitments = Vec::<DoryCommitment>::from_columns_with_offset(&columns, 0, &setup);
144
145        let mut expected_commitments = vec![DoryCommitment::default(); 2];
146        expected_commitments[0] = DoryCommitment(
147            Pairing::pairing(Gamma_1[0], Gamma_2[0]) * DoryScalar::from(column_a[0]).0
148                + Pairing::pairing(Gamma_1[1], Gamma_2[0]) * DoryScalar::from(column_a[1]).0
149                + Pairing::pairing(Gamma_1[2], Gamma_2[0]) * DoryScalar::from(column_a[2]).0,
150        );
151        expected_commitments[1] = DoryCommitment(
152            Pairing::pairing(Gamma_1[0], Gamma_2[0]) * DoryScalar::from(column_b[0].clone()).0
153                + Pairing::pairing(Gamma_1[1], Gamma_2[0])
154                    * DoryScalar::from(column_b[1].clone()).0
155                + Pairing::pairing(Gamma_1[2], Gamma_2[0])
156                    * DoryScalar::from(column_b[2].clone()).0,
157        );
158
159        assert_eq!(commitments, expected_commitments);
160    }
161
162    #[test]
163    fn we_can_append_rows() {
164        let public_parameters = PublicParameters::test_rand(5, &mut test_rng());
165        let prover_setup = ProverSetup::from(&public_parameters);
166        let setup = DoryProverPublicSetup::new(&prover_setup, 2);
167        let Gamma_1 = &public_parameters.Gamma_1;
168        let Gamma_2 = &public_parameters.Gamma_2;
169
170        let column_a = [12i64, 34, 56, 78, 90];
171        let column_b = ["Lorem", "ipsum", "dolor", "sit", "amet"].map(String::from);
172
173        let columns = vec![
174            OwnedColumn::<DoryScalar>::BigInt(column_a[..3].to_vec()),
175            OwnedColumn::VarChar(column_b[..3].to_vec()),
176        ];
177
178        let mut commitments = Vec::<DoryCommitment>::from_columns_with_offset(&columns, 0, &setup);
179
180        let new_columns = vec![
181            OwnedColumn::<DoryScalar>::BigInt(column_a[3..].to_vec()),
182            OwnedColumn::VarChar(column_b[3..].to_vec()),
183        ];
184
185        commitments
186            .try_append_rows_with_offset(&new_columns, 3, &setup)
187            .unwrap();
188
189        let mut expected_commitments = vec![DoryCommitment::default(); 2];
190        expected_commitments[0] = DoryCommitment(
191            Pairing::pairing(Gamma_1[0], Gamma_2[0]) * DoryScalar::from(column_a[0]).0
192                + Pairing::pairing(Gamma_1[1], Gamma_2[0]) * DoryScalar::from(column_a[1]).0
193                + Pairing::pairing(Gamma_1[2], Gamma_2[0]) * DoryScalar::from(column_a[2]).0
194                + Pairing::pairing(Gamma_1[3], Gamma_2[0]) * DoryScalar::from(column_a[3]).0
195                + Pairing::pairing(Gamma_1[0], Gamma_2[1]) * DoryScalar::from(column_a[4]).0,
196        );
197        expected_commitments[1] = DoryCommitment(
198            Pairing::pairing(Gamma_1[0], Gamma_2[0]) * DoryScalar::from(column_b[0].clone()).0
199                + Pairing::pairing(Gamma_1[1], Gamma_2[0])
200                    * DoryScalar::from(column_b[1].clone()).0
201                + Pairing::pairing(Gamma_1[2], Gamma_2[0])
202                    * DoryScalar::from(column_b[2].clone()).0
203                + Pairing::pairing(Gamma_1[3], Gamma_2[0])
204                    * DoryScalar::from(column_b[3].clone()).0
205                + Pairing::pairing(Gamma_1[0], Gamma_2[1])
206                    * DoryScalar::from(column_b[4].clone()).0,
207        );
208
209        assert_eq!(commitments, expected_commitments);
210    }
211
212    #[test]
213    fn we_cannot_append_rows_with_different_column_count() {
214        let public_parameters = PublicParameters::test_rand(5, &mut test_rng());
215        let prover_setup = ProverSetup::from(&public_parameters);
216        let setup = DoryProverPublicSetup::new(&prover_setup, 2);
217
218        let column_a = [12i64, 34, 56, 78, 90];
219        let column_b = ["Lorem", "ipsum", "dolor", "sit", "amet"].map(String::from);
220
221        let columns = vec![
222            OwnedColumn::<DoryScalar>::BigInt(column_a[..3].to_vec()),
223            OwnedColumn::VarChar(column_b[..3].to_vec()),
224        ];
225
226        let mut commitments = Vec::<DoryCommitment>::from_columns_with_offset(&columns, 0, &setup);
227
228        let new_columns = Vec::<Column<DoryScalar>>::new();
229        assert!(matches!(
230            commitments.try_append_rows_with_offset(&new_columns, 3, &setup),
231            Err(NumColumnsMismatch)
232        ));
233
234        let new_columns = vec![OwnedColumn::<DoryScalar>::BigInt(column_a[3..].to_vec())];
235        assert!(matches!(
236            commitments.try_append_rows_with_offset(&new_columns, 3, &setup),
237            Err(NumColumnsMismatch)
238        ));
239
240        let new_columns = vec![
241            OwnedColumn::<DoryScalar>::BigInt(column_a[3..].to_vec()),
242            OwnedColumn::VarChar(column_b[3..].to_vec()),
243            OwnedColumn::BigInt(column_a[3..].to_vec()),
244        ];
245        assert!(matches!(
246            commitments.try_append_rows_with_offset(&new_columns, 3, &setup),
247            Err(NumColumnsMismatch)
248        ));
249    }
250
251    #[test]
252    fn we_can_extend_columns() {
253        let public_parameters = PublicParameters::test_rand(5, &mut test_rng());
254        let prover_setup = ProverSetup::from(&public_parameters);
255        let setup = DoryProverPublicSetup::new(&prover_setup, 2);
256        let Gamma_1 = &public_parameters.Gamma_1;
257        let Gamma_2 = &public_parameters.Gamma_2;
258
259        let column_a = [12i64, 34, 56];
260        let column_b = ["Lorem", "ipsum", "dolor"].map(String::from);
261        let column_c = ["sit", "amet", "consectetur"].map(String::from);
262        let column_d = [78i64, 90, 1112];
263
264        let columns = vec![
265            OwnedColumn::<DoryScalar>::BigInt(column_a.to_vec()),
266            OwnedColumn::VarChar(column_b.to_vec()),
267        ];
268
269        let mut commitments = Vec::<DoryCommitment>::from_columns_with_offset(&columns, 0, &setup);
270
271        let new_columns = vec![
272            OwnedColumn::<DoryScalar>::VarChar(column_c.to_vec()),
273            OwnedColumn::BigInt(column_d.to_vec()),
274        ];
275
276        commitments.extend_columns_with_offset(&new_columns, 0, &setup);
277
278        let mut expected_commitments = vec![DoryCommitment::default(); 4];
279
280        expected_commitments[0] = DoryCommitment(
281            Pairing::pairing(Gamma_1[0], Gamma_2[0]) * DoryScalar::from(column_a[0]).0
282                + Pairing::pairing(Gamma_1[1], Gamma_2[0]) * DoryScalar::from(column_a[1]).0
283                + Pairing::pairing(Gamma_1[2], Gamma_2[0]) * DoryScalar::from(column_a[2]).0,
284        );
285        expected_commitments[1] = DoryCommitment(
286            Pairing::pairing(Gamma_1[0], Gamma_2[0]) * DoryScalar::from(column_b[0].clone()).0
287                + Pairing::pairing(Gamma_1[1], Gamma_2[0])
288                    * DoryScalar::from(column_b[1].clone()).0
289                + Pairing::pairing(Gamma_1[2], Gamma_2[0])
290                    * DoryScalar::from(column_b[2].clone()).0,
291        );
292        expected_commitments[2] = DoryCommitment(
293            Pairing::pairing(Gamma_1[0], Gamma_2[0]) * DoryScalar::from(column_c[0].clone()).0
294                + Pairing::pairing(Gamma_1[1], Gamma_2[0])
295                    * DoryScalar::from(column_c[1].clone()).0
296                + Pairing::pairing(Gamma_1[2], Gamma_2[0])
297                    * DoryScalar::from(column_c[2].clone()).0,
298        );
299        expected_commitments[3] = DoryCommitment(
300            Pairing::pairing(Gamma_1[0], Gamma_2[0]) * DoryScalar::from(column_d[0]).0
301                + Pairing::pairing(Gamma_1[1], Gamma_2[0]) * DoryScalar::from(column_d[1]).0
302                + Pairing::pairing(Gamma_1[2], Gamma_2[0]) * DoryScalar::from(column_d[2]).0,
303        );
304
305        assert_eq!(commitments, expected_commitments);
306    }
307
308    #[test]
309    fn we_can_add_commitment_collections() {
310        let public_parameters = PublicParameters::test_rand(5, &mut test_rng());
311        let prover_setup = ProverSetup::from(&public_parameters);
312        let setup = DoryProverPublicSetup::new(&prover_setup, 2);
313        let Gamma_1 = &public_parameters.Gamma_1;
314        let Gamma_2 = &public_parameters.Gamma_2;
315
316        let column_a = [12i64, 34, 56, 78, 90];
317        let column_b = ["Lorem", "ipsum", "dolor", "sit", "amet"].map(String::from);
318
319        let columns = vec![
320            OwnedColumn::<DoryScalar>::BigInt(column_a[..3].to_vec()),
321            OwnedColumn::VarChar(column_b[..3].to_vec()),
322        ];
323
324        let commitments_a = Vec::<DoryCommitment>::from_columns_with_offset(&columns, 0, &setup);
325
326        let new_columns = vec![
327            OwnedColumn::<DoryScalar>::BigInt(column_a[3..].to_vec()),
328            OwnedColumn::VarChar(column_b[3..].to_vec()),
329        ];
330
331        let commitments_b =
332            Vec::<DoryCommitment>::from_columns_with_offset(&new_columns, 3, &setup);
333
334        let commitments = commitments_a.try_add(commitments_b).unwrap();
335
336        let mut expected_commitments = vec![DoryCommitment::default(); 2];
337        expected_commitments[0] = DoryCommitment(
338            Pairing::pairing(Gamma_1[0], Gamma_2[0]) * DoryScalar::from(column_a[0]).0
339                + Pairing::pairing(Gamma_1[1], Gamma_2[0]) * DoryScalar::from(column_a[1]).0
340                + Pairing::pairing(Gamma_1[2], Gamma_2[0]) * DoryScalar::from(column_a[2]).0
341                + Pairing::pairing(Gamma_1[3], Gamma_2[0]) * DoryScalar::from(column_a[3]).0
342                + Pairing::pairing(Gamma_1[0], Gamma_2[1]) * DoryScalar::from(column_a[4]).0,
343        );
344        expected_commitments[1] = DoryCommitment(
345            Pairing::pairing(Gamma_1[0], Gamma_2[0]) * DoryScalar::from(column_b[0].clone()).0
346                + Pairing::pairing(Gamma_1[1], Gamma_2[0])
347                    * DoryScalar::from(column_b[1].clone()).0
348                + Pairing::pairing(Gamma_1[2], Gamma_2[0])
349                    * DoryScalar::from(column_b[2].clone()).0
350                + Pairing::pairing(Gamma_1[3], Gamma_2[0])
351                    * DoryScalar::from(column_b[3].clone()).0
352                + Pairing::pairing(Gamma_1[0], Gamma_2[1])
353                    * DoryScalar::from(column_b[4].clone()).0,
354        );
355
356        assert_eq!(commitments, expected_commitments);
357    }
358
359    #[test]
360    fn we_cannot_add_commitment_collections_of_mixed_column_counts() {
361        let public_parameters = PublicParameters::test_rand(5, &mut test_rng());
362        let prover_setup = ProverSetup::from(&public_parameters);
363        let setup = DoryProverPublicSetup::new(&prover_setup, 2);
364
365        let column_a = [12i64, 34, 56, 78, 90];
366        let column_b = ["Lorem", "ipsum", "dolor", "sit", "amet"].map(String::from);
367
368        let columns = vec![
369            OwnedColumn::<DoryScalar>::BigInt(column_a[..3].to_vec()),
370            OwnedColumn::VarChar(column_b[..3].to_vec()),
371        ];
372
373        let commitments = Vec::<DoryCommitment>::from_columns_with_offset(&columns, 0, &setup);
374
375        let new_columns = Vec::<Column<DoryScalar>>::new();
376        let new_commitments =
377            Vec::<DoryCommitment>::from_columns_with_offset(&new_columns, 3, &setup);
378        assert!(matches!(
379            commitments.clone().try_add(new_commitments),
380            Err(NumColumnsMismatch)
381        ));
382
383        let new_columns = vec![OwnedColumn::<DoryScalar>::BigInt(column_a[3..].to_vec())];
384        let new_commitments =
385            Vec::<DoryCommitment>::from_columns_with_offset(&new_columns, 3, &setup);
386        assert!(matches!(
387            commitments.clone().try_add(new_commitments),
388            Err(NumColumnsMismatch)
389        ));
390
391        let new_columns = vec![
392            OwnedColumn::<DoryScalar>::BigInt(column_a[3..].to_vec()),
393            OwnedColumn::VarChar(column_b[3..].to_vec()),
394            OwnedColumn::BigInt(column_a[3..].to_vec()),
395        ];
396        let new_commitments =
397            Vec::<DoryCommitment>::from_columns_with_offset(&new_columns, 3, &setup);
398        assert!(matches!(
399            commitments.try_add(new_commitments),
400            Err(NumColumnsMismatch)
401        ));
402    }
403
404    #[test]
405    fn we_can_sub_commitment_collections() {
406        let public_parameters = PublicParameters::test_rand(5, &mut test_rng());
407        let prover_setup = ProverSetup::from(&public_parameters);
408        let setup = DoryProverPublicSetup::new(&prover_setup, 2);
409        let Gamma_1 = &public_parameters.Gamma_1;
410        let Gamma_2 = &public_parameters.Gamma_2;
411
412        let column_a = [12i64, 34, 56, 78, 90];
413        let column_b = ["Lorem", "ipsum", "dolor", "sit", "amet"].map(String::from);
414
415        let columns = vec![
416            OwnedColumn::<DoryScalar>::BigInt(column_a[..3].to_vec()),
417            OwnedColumn::VarChar(column_b[..3].to_vec()),
418        ];
419
420        let commitments_a = Vec::<DoryCommitment>::from_columns_with_offset(&columns, 0, &setup);
421
422        let full_columns = vec![
423            OwnedColumn::<DoryScalar>::BigInt(column_a.to_vec()),
424            OwnedColumn::VarChar(column_b.to_vec()),
425        ];
426
427        let commitments_b =
428            Vec::<DoryCommitment>::from_columns_with_offset(&full_columns, 0, &setup);
429
430        let commitments = commitments_b.try_sub(commitments_a).unwrap();
431
432        let mut expected_commitments = vec![DoryCommitment::default(); 2];
433
434        expected_commitments[0] = DoryCommitment(
435            Pairing::pairing(Gamma_1[3], Gamma_2[0]) * DoryScalar::from(column_a[3]).0
436                + Pairing::pairing(Gamma_1[0], Gamma_2[1]) * DoryScalar::from(column_a[4]).0,
437        );
438        expected_commitments[1] = DoryCommitment(
439            Pairing::pairing(Gamma_1[3], Gamma_2[0]) * DoryScalar::from(column_b[3].clone()).0
440                + Pairing::pairing(Gamma_1[0], Gamma_2[1])
441                    * DoryScalar::from(column_b[4].clone()).0,
442        );
443
444        assert_eq!(commitments, expected_commitments);
445    }
446
447    #[test]
448    fn we_cannot_sub_commitment_collections_of_mixed_column_counts() {
449        let public_parameters = PublicParameters::test_rand(5, &mut test_rng());
450        let prover_setup = ProverSetup::from(&public_parameters);
451        let setup = DoryProverPublicSetup::new(&prover_setup, 2);
452
453        let column_a = [12i64, 34, 56, 78, 90];
454        let column_b = ["Lorem", "ipsum", "dolor", "sit", "amet"].map(String::from);
455
456        let columns = vec![
457            OwnedColumn::<DoryScalar>::BigInt(column_a[..3].to_vec()),
458            OwnedColumn::VarChar(column_b[..3].to_vec()),
459        ];
460
461        let commitments = Vec::<DoryCommitment>::from_columns_with_offset(&columns, 0, &setup);
462
463        let full_columns = Vec::<Column<DoryScalar>>::new();
464        let full_commitments =
465            Vec::<DoryCommitment>::from_columns_with_offset(&full_columns, 0, &setup);
466        assert!(matches!(
467            full_commitments.clone().try_sub(commitments.clone()),
468            Err(NumColumnsMismatch)
469        ));
470
471        let full_columns = vec![OwnedColumn::<DoryScalar>::BigInt(column_a.to_vec())];
472        let full_commitments =
473            Vec::<DoryCommitment>::from_columns_with_offset(&full_columns, 0, &setup);
474        assert!(matches!(
475            full_commitments.try_sub(commitments.clone()),
476            Err(NumColumnsMismatch)
477        ));
478
479        let full_columns = vec![
480            OwnedColumn::<DoryScalar>::BigInt(column_a.to_vec()),
481            OwnedColumn::VarChar(column_b.to_vec()),
482            OwnedColumn::BigInt(column_a.to_vec()),
483        ];
484        let full_commitments =
485            Vec::<DoryCommitment>::from_columns_with_offset(&full_columns, 0, &setup);
486        assert!(matches!(
487            full_commitments.try_sub(commitments),
488            Err(NumColumnsMismatch)
489        ));
490    }
491
492    #[test]
493    fn we_get_different_transcript_bytes_from_different_dory_commitments() {
494        let mut rng = StdRng::seed_from_u64(42);
495        let commitment1 = DoryCommitment(GT::rand(&mut rng));
496        let commitment2 = DoryCommitment(GT::rand(&mut rng));
497        assert_ne!(
498            commitment1.to_transcript_bytes(),
499            commitment2.to_transcript_bytes()
500        );
501    }
502}
proof_of_sql/proof_primitive/dory/dory_commitment.rs

proof_of_sql/proof_primitive/dory/
dory_commitment.rs
