proof_of_sql/base/commitment/
table_commitment.rs

1use super::{
2    committable_column::CommittableColumn, AppendColumnCommitmentsError, ColumnCommitments,
3    ColumnCommitmentsMismatch, Commitment, DuplicateIdents,
4};
5use crate::base::{
6    database::{ColumnField, CommitmentAccessor, OwnedTable, TableRef},
7    scalar::Scalar,
8};
9use alloc::vec::Vec;
10use core::ops::Range;
11use serde::{Deserialize, Serialize};
12use snafu::Snafu;
13use sqlparser::ast::Ident;
14
15/// Cannot create a [`TableCommitment`] with a negative range.
16#[derive(Debug, Snafu)]
17#[snafu(display("cannot create a TableCommitment with a negative range"))]
18pub struct NegativeRange;
19
20/// Cannot create a [`TableCommitment`] from columns of mixed length.
21#[derive(Debug, Snafu)]
22#[snafu(display("cannot create a TableCommitment from columns of mixed length"))]
23pub struct MixedLengthColumns;
24
25/// Errors that can occur when trying to create or extend a [`TableCommitment`] from columns.
26#[derive(Debug, Snafu)]
27pub enum TableCommitmentFromColumnsError {
28    /// Cannot construct [`TableCommitment`] from columns of mixed length.
29    #[snafu(transparent)]
30    MixedLengthColumns {
31        /// The underlying source error
32        source: MixedLengthColumns,
33    },
34    /// Cannot construct [`TableCommitment`] from columns with duplicate idents.
35    #[snafu(transparent)]
36    DuplicateIdents {
37        /// The underlying source error
38        source: DuplicateIdents,
39    },
40}
41
42/// Errors that can occur when attempting to append rows to a [`TableCommitment`].
43#[derive(Debug, Snafu)]
44pub enum AppendTableCommitmentError {
45    /// Cannot append columns of mixed length to existing [`TableCommitment`].
46    #[snafu(transparent)]
47    MixedLengthColumns {
48        /// The underlying source error
49        source: MixedLengthColumns,
50    },
51    /// Encountered error when appending internal [`ColumnCommitments`].
52    #[snafu(transparent)]
53    AppendColumnCommitments {
54        /// The underlying source error
55        source: AppendColumnCommitmentsError,
56    },
57}
58
59/// Errors that can occur when performing arithmetic on [`TableCommitment`]s.
60#[derive(Debug, Snafu)]
61pub enum TableCommitmentArithmeticError {
62    /// Cannot perform arithmetic on columns with mismatched metadata.
63    #[snafu(transparent)]
64    ColumnMismatch {
65        /// The underlying source error
66        source: ColumnCommitmentsMismatch,
67    },
68    /// Cannot perform [`TableCommitment`] arithmetic that would result in a negative range.
69    #[snafu(transparent)]
70    NegativeRange {
71        /// The underlying source error
72        source: NegativeRange,
73    },
74    /// Cannot perform arithmetic for noncontiguous table commitments.
75    #[snafu(display(
76        "cannot perform table commitment arithmetic for noncontiguous table commitments"
77    ))]
78    NonContiguous,
79}
80
81/// Commitment for an entire table, with column and table metadata.
82///
83/// Unlike [`ColumnCommitments`], all columns in this commitment must have the same length.
84#[derive(Clone, Default, Debug, PartialEq, Eq, Serialize, Deserialize)]
85pub struct TableCommitment<C>
86where
87    C: Commitment,
88{
89    column_commitments: ColumnCommitments<C>,
90    range: Range<usize>,
91}
92
93impl<C: Commitment> TableCommitment<C> {
94    /// Create a new [`TableCommitment`] for a table from a commitment accessor.
95    #[allow(
96        clippy::missing_panics_doc,
97        reason = "The assertion ensures that from_accessor should not create columns with a negative range"
98    )]
99    pub fn from_accessor_with_max_bounds(
100        table_ref: &TableRef,
101        columns: &[ColumnField],
102        accessor: &impl CommitmentAccessor<C>,
103    ) -> Self {
104        let length = accessor.get_length(table_ref);
105        let offset = accessor.get_offset(table_ref);
106        Self::try_new(
107            ColumnCommitments::from_accessor_with_max_bounds(table_ref, columns, accessor),
108            offset..offset + length,
109        )
110        .expect("from_accessor should not create columns with a negative range")
111    }
112
113    #[cfg(test)]
114    pub(super) fn column_commitments_mut(&mut self) -> &mut ColumnCommitments<C> {
115        &mut self.column_commitments
116    }
117
118    /// Construct a new [`TableCommitment`].
119    ///
120    /// Will error if the range is "negative", i.e. if its end < start.
121    pub fn try_new(
122        column_commitments: ColumnCommitments<C>,
123        range: Range<usize>,
124    ) -> Result<Self, NegativeRange> {
125        if range.start <= range.end {
126            Ok(TableCommitment {
127                column_commitments,
128                range,
129            })
130        } else {
131            Err(NegativeRange)
132        }
133    }
134
135    /// Returns a reference to this type's internal [`ColumnCommitments`].
136    #[must_use]
137    pub fn column_commitments(&self) -> &ColumnCommitments<C> {
138        &self.column_commitments
139    }
140
141    /// Returns a reference to the range of rows this type commits to.
142    #[must_use]
143    pub fn range(&self) -> &Range<usize> {
144        &self.range
145    }
146
147    /// Returns the number of columns in the committed table.
148    #[must_use]
149    pub fn num_columns(&self) -> usize {
150        self.column_commitments.len()
151    }
152
153    /// Returns the number of rows that have been committed to.
154    #[must_use]
155    pub fn num_rows(&self) -> usize {
156        self.range.len()
157    }
158
159    /// Returns a [`TableCommitment`] to the provided columns with the given row offset.
160    ///
161    /// Provided columns must have the same length and no duplicate idents.
162    pub fn try_from_columns_with_offset<'a, COL>(
163        columns: impl IntoIterator<Item = (&'a Ident, COL)>,
164        offset: usize,
165        setup: &C::PublicSetup<'_>,
166    ) -> Result<TableCommitment<C>, TableCommitmentFromColumnsError>
167    where
168        COL: Into<CommittableColumn<'a>>,
169    {
170        let (identifiers, committable_columns): (Vec<&Ident>, Vec<CommittableColumn>) = columns
171            .into_iter()
172            .map(|(identifier, column)| (identifier, column.into()))
173            .unzip();
174
175        let num_rows = num_rows_of_columns(&committable_columns)?;
176
177        let column_commitments = ColumnCommitments::try_from_columns_with_offset(
178            identifiers.into_iter().zip(committable_columns.into_iter()),
179            offset,
180            setup,
181        )?;
182
183        Ok(TableCommitment {
184            column_commitments,
185            range: offset..offset + num_rows,
186        })
187    }
188
189    /// Returns a [`TableCommitment`] to the provided table with the given row offset.
190    #[allow(
191        clippy::missing_panics_doc,
192        reason = "since OwnedTables cannot have columns of mixed length or duplicate idents"
193    )]
194    pub fn from_owned_table_with_offset<S>(
195        owned_table: &OwnedTable<S>,
196        offset: usize,
197        setup: &C::PublicSetup<'_>,
198    ) -> TableCommitment<C>
199    where
200        S: Scalar,
201    {
202        Self::try_from_columns_with_offset(owned_table.inner_table(), offset, setup)
203            .expect("OwnedTables cannot have columns of mixed length or duplicate idents")
204    }
205
206    /// Append rows of data from the provided columns to the existing [`TableCommitment`].
207    ///
208    /// The row offset is assumed to be the end of the [`TableCommitment`]'s current range.
209    ///
210    /// Will error on a variety of mismatches, or if the provided columns have mixed length.
211    pub fn try_append_rows<'a, COL>(
212        &mut self,
213        columns: impl IntoIterator<Item = (&'a Ident, COL)>,
214        setup: &C::PublicSetup<'_>,
215    ) -> Result<(), AppendTableCommitmentError>
216    where
217        COL: Into<CommittableColumn<'a>>,
218    {
219        let (identifiers, committable_columns): (Vec<&Ident>, Vec<CommittableColumn>) = columns
220            .into_iter()
221            .map(|(identifier, column)| (identifier, column.into()))
222            .unzip();
223
224        let num_rows = num_rows_of_columns(&committable_columns)?;
225
226        self.column_commitments.try_append_rows_with_offset(
227            identifiers.into_iter().zip(committable_columns.into_iter()),
228            self.range.end,
229            setup,
230        )?;
231        self.range.end += num_rows;
232
233        Ok(())
234    }
235
236    /// Append data of the provided table to the exiting [`TableCommitment`].
237    ///
238    /// Will error on a variety of mismatches.
239    /// See [`ColumnCommitmentsMismatch`] for an enumeration of these errors.
240    /// # Panics
241    /// Panics if `owned_table` has duplicate idents.
242    /// Panics if `owned_table` contains columns of mixed length.
243    pub fn append_owned_table<S>(
244        &mut self,
245        owned_table: &OwnedTable<S>,
246        setup: &C::PublicSetup<'_>,
247    ) -> Result<(), ColumnCommitmentsMismatch>
248    where
249        S: Scalar,
250    {
251        self.try_append_rows(owned_table.inner_table(), setup)
252            .map_err(|e| match e {
253                AppendTableCommitmentError::AppendColumnCommitments { source: e } => match e {
254                    AppendColumnCommitmentsError::Mismatch { source: e } => e,
255                    AppendColumnCommitmentsError::DuplicateIdents { .. } => {
256                        panic!("OwnedTables cannot have duplicate idents");
257                    }
258                },
259                AppendTableCommitmentError::MixedLengthColumns { .. } => {
260                    panic!("OwnedTables cannot have columns of mixed length");
261                }
262            })
263    }
264
265    /// Add new columns to this [`TableCommitment`].
266    ///
267    /// Columns must have the same length as the current commitment and no duplicate idents.
268    pub fn try_extend_columns<'a, COL>(
269        &mut self,
270        columns: impl IntoIterator<Item = (&'a Ident, COL)>,
271        setup: &C::PublicSetup<'_>,
272    ) -> Result<(), TableCommitmentFromColumnsError>
273    where
274        COL: Into<CommittableColumn<'a>>,
275    {
276        let num_rows = self.range.len();
277
278        let (identifiers, committable_columns): (Vec<&Ident>, Vec<CommittableColumn>) = columns
279            .into_iter()
280            .map(|(identifier, column)| (identifier, column.into()))
281            .unzip();
282
283        let num_rows_of_new_columns = num_rows_of_columns(&committable_columns)?;
284        if num_rows_of_new_columns != num_rows {
285            Err(MixedLengthColumns)?;
286        }
287
288        self.column_commitments.try_extend_columns_with_offset(
289            identifiers.into_iter().zip(committable_columns.into_iter()),
290            self.range.start,
291            setup,
292        )?;
293
294        Ok(())
295    }
296
297    /// Add two [`TableCommitment`]s together.
298    ///
299    /// `self` must end where `other` begins, or vice versa.
300    /// Otherwise, [`TableCommitmentArithmeticError::NonContiguous`] is returned.
301    ///
302    /// This will also error on a variety of mismatches.
303    /// See [`ColumnCommitmentsMismatch`] for an enumeration of these errors.
304    pub fn try_add(self, other: Self) -> Result<Self, TableCommitmentArithmeticError>
305    where
306        Self: Sized,
307    {
308        let range = if self.range.end == other.range.start {
309            self.range.start..other.range.end
310        } else if other.range.end == self.range.start {
311            other.range.start..self.range.end
312        } else {
313            return Err(TableCommitmentArithmeticError::NonContiguous);
314        };
315
316        let column_commitments = self.column_commitments.try_add(other.column_commitments)?;
317
318        Ok(TableCommitment {
319            column_commitments,
320            range,
321        })
322    }
323
324    /// Subtract two [`TableCommitment`]s.
325    ///
326    /// `self` and `other` must begin at the same row number or end at the same row number.
327    /// Otherwise, [`TableCommitmentArithmeticError::NonContiguous`] is returned.
328    ///
329    /// Furthermore, `other`'s range must be smaller or equal to `self`'s.
330    /// Otherwise, [`TableCommitmentArithmeticError::NegativeRange`] is returned.
331    ///
332    /// This will also error on a variety of mismatches.
333    /// See [`ColumnCommitmentsMismatch`] for an enumeration of these errors.
334    pub fn try_sub(self, other: Self) -> Result<Self, TableCommitmentArithmeticError>
335    where
336        Self: Sized,
337    {
338        if self.range.len() < other.range.len() {
339            Err(NegativeRange)?;
340        }
341
342        let range = if self.range.start == other.range.start {
343            other.range.end..self.range.end
344        } else if self.range.end == other.range.end {
345            self.range.start..other.range.start
346        } else {
347            return Err(TableCommitmentArithmeticError::NonContiguous);
348        };
349
350        let column_commitments = self.column_commitments.try_sub(other.column_commitments)?;
351
352        Ok(TableCommitment {
353            column_commitments,
354            range,
355        })
356    }
357}
358
359/// Return the number of rows for the provided columns, erroring if they have mixed length.
360fn num_rows_of_columns<'a>(
361    committable_columns: impl IntoIterator<Item = &'a CommittableColumn<'a>>,
362) -> Result<usize, MixedLengthColumns> {
363    let mut committable_columns_iter = committable_columns.into_iter().peekable();
364    let num_rows = committable_columns_iter
365        .peek()
366        .map_or(0, |committable_column| committable_column.len());
367
368    for committable_column in committable_columns_iter {
369        if committable_column.len() != num_rows {
370            return Err(MixedLengthColumns);
371        }
372    }
373
374    Ok(num_rows)
375}
376
377#[cfg(all(test, feature = "arrow", feature = "blitzar"))]
378mod tests {
379    use super::*;
380    use crate::{
381        base::{
382            commitment::naive_commitment::NaiveCommitment,
383            database::{owned_table_utility::*, Column, OwnedColumn},
384            map::IndexMap,
385            scalar::test_scalar::TestScalar,
386        },
387        record_batch,
388    };
389
390    #[test]
391    #[allow(clippy::reversed_empty_ranges)]
392    fn we_cannot_construct_table_commitment_with_negative_range() {
393        let try_new_result =
394            TableCommitment::<NaiveCommitment>::try_new(ColumnCommitments::default(), 1..0);
395
396        assert!(matches!(try_new_result, Err(NegativeRange)));
397    }
398
399    #[test]
400    fn we_can_construct_table_commitment_from_columns_and_identifiers() {
401        // no-columns case
402        let mut empty_columns_iter: IndexMap<Ident, OwnedColumn<TestScalar>> = IndexMap::default();
403        let empty_table_commitment =
404            TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
405                &empty_columns_iter,
406                0,
407                &(),
408            )
409            .unwrap();
410        assert_eq!(
411            empty_table_commitment.column_commitments(),
412            &ColumnCommitments::try_from_columns_with_offset(&empty_columns_iter, 0, &()).unwrap()
413        );
414        assert_eq!(empty_table_commitment.range(), &(0..0));
415        assert_eq!(empty_table_commitment.num_columns(), 0);
416        assert_eq!(empty_table_commitment.num_rows(), 0);
417
418        // no-rows case
419        empty_columns_iter.insert("column_a".into(), OwnedColumn::BigInt(vec![]));
420        let empty_table_commitment =
421            TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
422                &empty_columns_iter,
423                1,
424                &(),
425            )
426            .unwrap();
427        assert_eq!(
428            empty_table_commitment.column_commitments(),
429            &ColumnCommitments::try_from_columns_with_offset(&empty_columns_iter, 1, &()).unwrap()
430        );
431        assert_eq!(empty_table_commitment.range(), &(1..1));
432        assert_eq!(empty_table_commitment.num_columns(), 1);
433        assert_eq!(empty_table_commitment.num_rows(), 0);
434
435        // nonempty case
436        let owned_table = owned_table::<TestScalar>([
437            bigint("bigint_id", [1, 5, -5, 0]),
438            // "int128_column" => [100i128, 200, 300, 400], TODO: enable this column once blitzar
439            // supports it
440            varchar("varchar_id", ["Lorem", "ipsum", "dolor", "sit"]),
441            scalar("scalar_id", [1000, 2000, -1000, 0]),
442        ]);
443        let table_commitment = TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
444            owned_table.inner_table(),
445            2,
446            &(),
447        )
448        .unwrap();
449        assert_eq!(
450            table_commitment.column_commitments(),
451            &ColumnCommitments::try_from_columns_with_offset(owned_table.inner_table(), 2, &())
452                .unwrap()
453        );
454        assert_eq!(table_commitment.range(), &(2..6));
455        assert_eq!(table_commitment.num_columns(), 3);
456        assert_eq!(table_commitment.num_rows(), 4);
457
458        // matches from_owned_table constructor
459        let table_commitment_from_owned_table =
460            TableCommitment::from_owned_table_with_offset(&owned_table, 2, &());
461        assert_eq!(table_commitment_from_owned_table, table_commitment);
462    }
463
464    #[test]
465    fn we_cannot_construct_table_commitment_from_duplicate_identifiers() {
466        let duplicate_identifier_a = "duplicate_identifier_a".into();
467        let duplicate_identifier_b = "duplicate_identifier_b".into();
468        let unique_identifier = "unique_identifier".into();
469
470        let empty_column = OwnedColumn::<TestScalar>::BigInt(vec![]);
471
472        let from_columns_result = TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
473            [
474                (&duplicate_identifier_a, &empty_column),
475                (&unique_identifier, &empty_column),
476                (&duplicate_identifier_a, &empty_column),
477            ],
478            0,
479            &(),
480        );
481        assert!(matches!(
482            from_columns_result,
483            Err(TableCommitmentFromColumnsError::DuplicateIdents { .. })
484        ));
485
486        let mut table_commitment =
487            TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
488                [
489                    (&duplicate_identifier_a, &empty_column),
490                    (&unique_identifier, &empty_column),
491                ],
492                0,
493                &(),
494            )
495            .unwrap();
496        let column_commitments = table_commitment.column_commitments().clone();
497
498        let extend_columns_result =
499            table_commitment.try_extend_columns([(&duplicate_identifier_a, &empty_column)], &());
500        assert!(matches!(
501            extend_columns_result,
502            Err(TableCommitmentFromColumnsError::DuplicateIdents { .. })
503        ));
504
505        let extend_columns_result = table_commitment.try_extend_columns(
506            [
507                (&duplicate_identifier_b, &empty_column),
508                (&duplicate_identifier_b, &empty_column),
509            ],
510            &(),
511        );
512        assert!(matches!(
513            extend_columns_result,
514            Err(TableCommitmentFromColumnsError::DuplicateIdents { .. })
515        ));
516
517        // make sure the commitment wasn't mutated
518        assert_eq!(table_commitment.num_columns(), 2);
519        assert_eq!(table_commitment.column_commitments(), &column_commitments);
520    }
521
522    #[test]
523    fn we_cannot_construct_table_commitment_from_columns_of_mixed_length() {
524        let column_id_a = "column_a".into();
525        let column_id_b = "column_b".into();
526        let column_id_c = "column_c".into();
527
528        let one_row_column = OwnedColumn::<TestScalar>::BigInt(vec![1]);
529        let two_row_column = OwnedColumn::<TestScalar>::BigInt(vec![1, 2]);
530
531        let from_columns_result = TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
532            [
533                (&column_id_a, &one_row_column),
534                (&column_id_b, &two_row_column),
535            ],
536            0,
537            &(),
538        );
539        assert!(matches!(
540            from_columns_result,
541            Err(TableCommitmentFromColumnsError::MixedLengthColumns { .. })
542        ));
543
544        let mut table_commitment =
545            TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
546                [(&column_id_a, &one_row_column)],
547                0,
548                &(),
549            )
550            .unwrap();
551        let column_commitments = table_commitment.column_commitments().clone();
552
553        let extend_columns_result =
554            table_commitment.try_extend_columns([(&column_id_b, &two_row_column)], &());
555        assert!(matches!(
556            extend_columns_result,
557            Err(TableCommitmentFromColumnsError::MixedLengthColumns { .. })
558        ));
559
560        let extend_columns_result = table_commitment.try_extend_columns(
561            [
562                (&column_id_b, &one_row_column),
563                (&column_id_c, &two_row_column),
564            ],
565            &(),
566        );
567        assert!(matches!(
568            extend_columns_result,
569            Err(TableCommitmentFromColumnsError::MixedLengthColumns { .. })
570        ));
571
572        // make sure the commitment wasn't mutated
573        assert_eq!(table_commitment.num_columns(), 1);
574        assert_eq!(table_commitment.column_commitments(), &column_commitments);
575    }
576
577    #[test]
578    fn we_can_append_rows_to_table_commitment() {
579        let bigint_id: Ident = "bigint_column".into();
580        let bigint_data = [1i64, 5, -5, 0, 10];
581
582        let varchar_id: Ident = "varchar_column".into();
583        let varchar_data = ["Lorem", "ipsum", "dolor", "sit", "amet"];
584
585        let scalar_id: Ident = "scalar_column".into();
586        let scalar_data = [1000, 2000, 3000, -1000, 0];
587
588        let initial_columns: OwnedTable<TestScalar> = owned_table([
589            bigint(bigint_id.value.as_str(), bigint_data[..2].to_vec()),
590            varchar(varchar_id.value.as_str(), varchar_data[..2].to_vec()),
591            scalar(scalar_id.value.as_str(), scalar_data[..2].to_vec()),
592        ]);
593
594        let mut table_commitment =
595            TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
596                initial_columns.inner_table(),
597                0,
598                &(),
599            )
600            .unwrap();
601        let mut table_commitment_clone = table_commitment.clone();
602
603        let append_columns: OwnedTable<TestScalar> = owned_table([
604            bigint(bigint_id.value.as_str(), bigint_data[2..].to_vec()),
605            varchar(varchar_id.value.as_str(), varchar_data[2..].to_vec()),
606            scalar(scalar_id.value.as_str(), scalar_data[2..].to_vec()),
607        ]);
608
609        table_commitment
610            .try_append_rows(append_columns.inner_table(), &())
611            .unwrap();
612
613        let total_columns: OwnedTable<TestScalar> = owned_table([
614            bigint(bigint_id.value.as_str(), bigint_data),
615            varchar(varchar_id.value.as_str(), varchar_data),
616            scalar(scalar_id.value.as_str(), scalar_data),
617        ]);
618
619        let expected_table_commitment =
620            TableCommitment::try_from_columns_with_offset(total_columns.inner_table(), 0, &())
621                .unwrap();
622
623        assert_eq!(table_commitment, expected_table_commitment);
624
625        // matches append_owned_table result
626        table_commitment_clone
627            .append_owned_table(&append_columns, &())
628            .unwrap();
629        assert_eq!(table_commitment, table_commitment_clone);
630    }
631
632    #[test]
633    fn we_cannot_append_mismatched_columns_to_table_commitment() {
634        let base_table: OwnedTable<TestScalar> = owned_table([
635            bigint("column_a", [1, 2, 3, 4]),
636            varchar("column_b", ["Lorem", "ipsum", "dolor", "sit"]),
637        ]);
638        let mut table_commitment =
639            TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
640                base_table.inner_table(),
641                0,
642                &(),
643            )
644            .unwrap();
645        let column_commitments = table_commitment.column_commitments().clone();
646
647        let table_diff_type: OwnedTable<TestScalar> = owned_table([
648            varchar("column_a", ["5", "6", "7", "8"]),
649            varchar("column_b", ["Lorem", "ipsum", "dolor", "sit"]),
650        ]);
651        assert!(matches!(
652            table_commitment.try_append_rows(table_diff_type.inner_table(), &()),
653            Err(AppendTableCommitmentError::AppendColumnCommitments {
654                source: AppendColumnCommitmentsError::Mismatch {
655                    source: ColumnCommitmentsMismatch::ColumnCommitmentMetadata { .. }
656                }
657            })
658        ));
659
660        // make sure the commitment wasn't mutated
661        assert_eq!(table_commitment.num_rows(), 4);
662        assert_eq!(table_commitment.column_commitments(), &column_commitments);
663    }
664
665    #[test]
666    fn we_cannot_append_columns_with_duplicate_identifiers_to_table_commitment() {
667        let column_id_a = "column_a".into();
668        let column_id_b = "column_b".into();
669
670        let column_data = OwnedColumn::<TestScalar>::BigInt(vec![1, 2, 3]);
671
672        let mut table_commitment =
673            TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
674                [(&column_id_a, &column_data), (&column_id_b, &column_data)],
675                0,
676                &(),
677            )
678            .unwrap();
679        let column_commitments = table_commitment.column_commitments().clone();
680
681        let append_column_result = table_commitment.try_append_rows(
682            [
683                (&column_id_a, &column_data),
684                (&column_id_b, &column_data),
685                (&column_id_a, &column_data),
686            ],
687            &(),
688        );
689        assert!(matches!(
690            append_column_result,
691            Err(AppendTableCommitmentError::AppendColumnCommitments {
692                source: AppendColumnCommitmentsError::DuplicateIdents { .. }
693            })
694        ));
695
696        // make sure the commitment wasn't mutated
697        assert_eq!(table_commitment.num_rows(), 3);
698        assert_eq!(table_commitment.column_commitments(), &column_commitments);
699    }
700
701    #[allow(clippy::similar_names)]
702    #[test]
703    fn we_cannot_append_columns_of_mixed_length_to_table_commitment() {
704        let column_id_a: Ident = "column_a".into();
705        let column_id_b: Ident = "column_b".into();
706        let base_table: OwnedTable<TestScalar> = owned_table([
707            bigint(column_id_a.value.as_str(), [1, 2, 3, 4]),
708            varchar(
709                column_id_b.value.as_str(),
710                ["Lorem", "ipsum", "dolor", "sit"],
711            ),
712        ]);
713
714        let mut table_commitment =
715            TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
716                base_table.inner_table(),
717                0,
718                &(),
719            )
720            .unwrap();
721        let column_commitments = table_commitment.column_commitments().clone();
722
723        let column_a_append_data = OwnedColumn::<TestScalar>::BigInt(vec![5, 6, 7]);
724        let column_b_append_data =
725            OwnedColumn::VarChar(["amet", "consectetur"].map(String::from).to_vec());
726
727        let append_result = table_commitment.try_append_rows(
728            [
729                (&column_id_a, &column_a_append_data),
730                (&column_id_b, &column_b_append_data),
731            ],
732            &(),
733        );
734        assert!(matches!(
735            append_result,
736            Err(AppendTableCommitmentError::MixedLengthColumns { .. })
737        ));
738
739        // make sure the commitment wasn't mutated
740        assert_eq!(table_commitment.num_rows(), 4);
741        assert_eq!(table_commitment.column_commitments(), &column_commitments);
742    }
743
744    #[test]
745    fn we_can_extend_columns_to_table_commitment() {
746        let bigint_id: Ident = "bigint_column".into();
747        let bigint_data = [1i64, 5, -5, 0, 10];
748
749        let varchar_id: Ident = "varchar_column".into();
750        let varchar_data = ["Lorem", "ipsum", "dolor", "sit", "amet"];
751
752        let scalar_id: Ident = "scalar_column".into();
753        let scalar_data = [1000, 2000, 3000, -1000, 0];
754
755        let initial_columns: OwnedTable<TestScalar> = owned_table([
756            bigint(bigint_id.value.as_str(), bigint_data),
757            varchar(varchar_id.value.as_str(), varchar_data),
758        ]);
759        let mut table_commitment =
760            TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
761                initial_columns.inner_table(),
762                2,
763                &(),
764            )
765            .unwrap();
766
767        let new_columns =
768            owned_table::<TestScalar>([scalar(scalar_id.value.as_str(), scalar_data)]);
769        table_commitment
770            .try_extend_columns(new_columns.inner_table(), &())
771            .unwrap();
772
773        let expected_columns = owned_table::<TestScalar>([
774            bigint(bigint_id.value.as_str(), bigint_data),
775            varchar(varchar_id.value.as_str(), varchar_data),
776            scalar(scalar_id.value.as_str(), scalar_data),
777        ]);
778        let expected_table_commitment =
779            TableCommitment::try_from_columns_with_offset(expected_columns.inner_table(), 2, &())
780                .unwrap();
781
782        assert_eq!(table_commitment, expected_table_commitment);
783    }
784
785    #[test]
786    fn we_can_add_table_commitments() {
787        let bigint_id: Ident = "bigint_column".into();
788        let bigint_data = [1i64, 5, -5, 0, 10];
789
790        let varchar_id: Ident = "varchar_column".into();
791        let varchar_data = ["Lorem", "ipsum", "dolor", "sit", "amet"];
792
793        let scalar_id: Ident = "scalar_column".into();
794        let scalar_data = [1000, 2000, 3000, -1000, 0];
795
796        let columns_a: OwnedTable<TestScalar> = owned_table([
797            bigint(bigint_id.value.as_str(), bigint_data[..2].to_vec()),
798            varchar(varchar_id.value.as_str(), varchar_data[..2].to_vec()),
799            scalar(scalar_id.value.as_str(), scalar_data[..2].to_vec()),
800        ]);
801
802        let table_commitment_a = TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
803            columns_a.inner_table(),
804            0,
805            &(),
806        )
807        .unwrap();
808
809        let columns_b: OwnedTable<TestScalar> = owned_table([
810            bigint(bigint_id.value.as_str(), bigint_data[2..].to_vec()),
811            varchar(varchar_id.value.as_str(), varchar_data[2..].to_vec()),
812            scalar(scalar_id.value.as_str(), scalar_data[2..].to_vec()),
813        ]);
814        let table_commitment_b =
815            TableCommitment::try_from_columns_with_offset(columns_b.inner_table(), 2, &()).unwrap();
816
817        let columns_sum: OwnedTable<TestScalar> = owned_table([
818            bigint(bigint_id.value.as_str(), bigint_data),
819            varchar(varchar_id.value.as_str(), varchar_data),
820            scalar(scalar_id.value.as_str(), scalar_data),
821        ]);
822        let table_commitment_sum =
823            TableCommitment::try_from_columns_with_offset(columns_sum.inner_table(), 0, &())
824                .unwrap();
825
826        assert_eq!(
827            table_commitment_a
828                .clone()
829                .try_add(table_commitment_b.clone())
830                .unwrap(),
831            table_commitment_sum
832        );
833        // commutativity
834        assert_eq!(
835            table_commitment_b.try_add(table_commitment_a).unwrap(),
836            table_commitment_sum
837        );
838    }
839
840    #[test]
841    fn we_cannot_add_mismatched_table_commitments() {
842        let base_table: OwnedTable<TestScalar> = owned_table([
843            bigint("column_a", [1, 2, 3, 4]),
844            varchar("column_b", ["Lorem", "ipsum", "dolor", "sit"]),
845        ]);
846        let table_commitment = TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
847            base_table.inner_table(),
848            0,
849            &(),
850        )
851        .unwrap();
852
853        let table_diff_type: OwnedTable<TestScalar> = owned_table([
854            varchar("column_a", ["5", "6", "7", "8"]),
855            varchar("column_b", ["Lorem", "ipsum", "dolor", "sit"]),
856        ]);
857        let table_commitment_diff_type =
858            TableCommitment::try_from_columns_with_offset(table_diff_type.inner_table(), 4, &())
859                .unwrap();
860        assert!(matches!(
861            table_commitment.try_add(table_commitment_diff_type),
862            Err(TableCommitmentArithmeticError::ColumnMismatch { .. })
863        ));
864    }
865
866    #[test]
867    fn we_cannot_add_noncontiguous_table_commitments() {
868        let base_table: OwnedTable<TestScalar> = owned_table([
869            bigint("column_a", [1, 2, 3, 4]),
870            varchar("column_b", ["Lorem", "ipsum", "dolor", "sit"]),
871        ]);
872        let table_commitment = TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
873            base_table.inner_table(),
874            5,
875            &(),
876        )
877        .unwrap();
878
879        let high_disjoint_table_commitment =
880            TableCommitment::try_from_columns_with_offset(base_table.inner_table(), 10, &())
881                .unwrap();
882        assert!(matches!(
883            table_commitment
884                .clone()
885                .try_add(high_disjoint_table_commitment),
886            Err(TableCommitmentArithmeticError::NonContiguous)
887        ));
888
889        let high_overlapping_table_commitment =
890            TableCommitment::try_from_columns_with_offset(base_table.inner_table(), 7, &())
891                .unwrap();
892        assert!(matches!(
893            table_commitment
894                .clone()
895                .try_add(high_overlapping_table_commitment),
896            Err(TableCommitmentArithmeticError::NonContiguous)
897        ));
898
899        let equal_range_table_commitment =
900            TableCommitment::try_from_columns_with_offset(base_table.inner_table(), 5, &())
901                .unwrap();
902        assert!(matches!(
903            table_commitment
904                .clone()
905                .try_add(equal_range_table_commitment),
906            Err(TableCommitmentArithmeticError::NonContiguous)
907        ));
908
909        let low_overlapping_table_commitment =
910            TableCommitment::try_from_columns_with_offset(base_table.inner_table(), 3, &())
911                .unwrap();
912        assert!(matches!(
913            table_commitment
914                .clone()
915                .try_add(low_overlapping_table_commitment),
916            Err(TableCommitmentArithmeticError::NonContiguous)
917        ));
918
919        let low_disjoint_table_commitment =
920            TableCommitment::try_from_columns_with_offset(base_table.inner_table(), 0, &())
921                .unwrap();
922        assert!(matches!(
923            table_commitment
924                .clone()
925                .try_add(low_disjoint_table_commitment),
926            Err(TableCommitmentArithmeticError::NonContiguous)
927        ));
928    }
929
930    #[test]
931    fn we_can_sub_table_commitments() {
932        let bigint_id: Ident = "bigint_column".into();
933        let bigint_data = [1i64, 5, -5, 0, 10];
934
935        let varchar_id: Ident = "varchar_column".into();
936        let varchar_data = ["Lorem", "ipsum", "dolor", "sit", "amet"];
937
938        let scalar_id: Ident = "scalar_column".into();
939        let scalar_data = [1000, 2000, 3000, -1000, 0];
940
941        let columns_low: OwnedTable<TestScalar> = owned_table([
942            bigint(bigint_id.value.as_str(), bigint_data[..2].to_vec()),
943            varchar(varchar_id.value.as_str(), varchar_data[..2].to_vec()),
944            scalar(scalar_id.value.as_str(), scalar_data[..2].to_vec()),
945        ]);
946        let table_commitment_low =
947            TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
948                columns_low.inner_table(),
949                0,
950                &(),
951            )
952            .unwrap();
953
954        let columns_high: OwnedTable<TestScalar> = owned_table([
955            bigint(bigint_id.value.as_str(), bigint_data[2..].to_vec()),
956            varchar(varchar_id.value.as_str(), varchar_data[2..].to_vec()),
957            scalar(scalar_id.value.as_str(), scalar_data[2..].to_vec()),
958        ]);
959        let table_commitment_high =
960            TableCommitment::try_from_columns_with_offset(columns_high.inner_table(), 2, &())
961                .unwrap();
962
963        let columns_all: OwnedTable<TestScalar> = owned_table([
964            bigint(bigint_id.value.as_str(), bigint_data),
965            varchar(varchar_id.value.as_str(), varchar_data),
966            scalar(scalar_id.value.as_str(), scalar_data),
967        ]);
968        let table_commitment_all =
969            TableCommitment::try_from_columns_with_offset(columns_all.inner_table(), 0, &())
970                .unwrap();
971
972        // case where we subtract the low commitment off the total to get the high commitment
973        let high_difference = table_commitment_all
974            .clone()
975            .try_sub(table_commitment_low.clone())
976            .unwrap();
977        assert_eq!(
978            high_difference.column_commitments().commitments(),
979            table_commitment_high.column_commitments().commitments()
980        );
981        assert_eq!(high_difference.range(), table_commitment_high.range());
982
983        // case where we subtract the high commitment off the total to get the low commitment
984        let low_difference = table_commitment_all.try_sub(table_commitment_high).unwrap();
985        assert_eq!(
986            low_difference.column_commitments().commitments(),
987            table_commitment_low.column_commitments().commitments()
988        );
989        assert_eq!(low_difference.range(), table_commitment_low.range());
990
991        // subtraction for column metadata is tested more thoroughly at a lower level
992    }
993
994    #[test]
995    fn we_cannot_sub_mismatched_table_commitments() {
996        let base_table: OwnedTable<TestScalar> = owned_table([
997            bigint("column_a", [1, 2, 3, 4]),
998            varchar("column_b", ["Lorem", "ipsum", "dolor", "sit"]),
999        ]);
1000        let table_commitment = TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
1001            base_table.inner_table(),
1002            0,
1003            &(),
1004        )
1005        .unwrap();
1006
1007        let table_diff_type: OwnedTable<TestScalar> = owned_table([
1008            varchar("column_a", ["1", "2"]),
1009            varchar("column_b", ["Lorem", "ipsum"]),
1010        ]);
1011        let table_commitment_diff_type =
1012            TableCommitment::try_from_columns_with_offset(table_diff_type.inner_table(), 0, &())
1013                .unwrap();
1014        assert!(matches!(
1015            table_commitment.try_sub(table_commitment_diff_type),
1016            Err(TableCommitmentArithmeticError::ColumnMismatch { .. })
1017        ));
1018    }
1019
1020    #[test]
1021    fn we_cannot_sub_noncontiguous_table_commitments() {
1022        let bigint_id: Ident = "bigint_column".into();
1023        let bigint_data = [1i64, 5, -5, 0, 10];
1024
1025        let varchar_id: Ident = "varchar_column".into();
1026        let varchar_data = ["Lorem", "ipsum", "dolor", "sit", "amet"];
1027
1028        let scalar_id: Ident = "scalar_column".into();
1029        let scalar_data = [1000, 2000, 3000, -1000, 0];
1030
1031        let columns_minuend: OwnedTable<TestScalar> = owned_table([
1032            bigint(bigint_id.value.as_str(), bigint_data[..].to_vec()),
1033            varchar(varchar_id.value.as_str(), varchar_data[..].to_vec()),
1034            scalar(scalar_id.value.as_str(), scalar_data[..].to_vec()),
1035        ]);
1036
1037        let columns_subtrahend: OwnedTable<TestScalar> = owned_table([
1038            bigint(bigint_id.value.as_str(), bigint_data[..2].to_vec()),
1039            varchar(varchar_id.value.as_str(), varchar_data[..2].to_vec()),
1040            scalar(scalar_id.value.as_str(), scalar_data[..2].to_vec()),
1041        ]);
1042
1043        let minuend_table_commitment =
1044            TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
1045                columns_minuend.inner_table(),
1046                4,
1047                &(),
1048            )
1049            .unwrap();
1050
1051        let high_contiguous_table_commitment =
1052            TableCommitment::try_from_columns_with_offset(columns_subtrahend.inner_table(), 9, &())
1053                .unwrap();
1054        assert!(matches!(
1055            minuend_table_commitment
1056                .clone()
1057                .try_sub(high_contiguous_table_commitment),
1058            Err(TableCommitmentArithmeticError::NonContiguous)
1059        ));
1060
1061        let high_overlapping_table_commitment =
1062            TableCommitment::try_from_columns_with_offset(columns_subtrahend.inner_table(), 6, &())
1063                .unwrap();
1064        assert!(matches!(
1065            minuend_table_commitment
1066                .clone()
1067                .try_sub(high_overlapping_table_commitment),
1068            Err(TableCommitmentArithmeticError::NonContiguous)
1069        ));
1070
1071        let low_overlapping_table_commitment =
1072            TableCommitment::try_from_columns_with_offset(columns_subtrahend.inner_table(), 3, &())
1073                .unwrap();
1074        assert!(matches!(
1075            minuend_table_commitment
1076                .clone()
1077                .try_sub(low_overlapping_table_commitment),
1078            Err(TableCommitmentArithmeticError::NonContiguous)
1079        ));
1080
1081        let low_contiguous_table_commitment =
1082            TableCommitment::try_from_columns_with_offset(columns_subtrahend.inner_table(), 2, &())
1083                .unwrap();
1084        assert!(matches!(
1085            minuend_table_commitment
1086                .clone()
1087                .try_sub(low_contiguous_table_commitment),
1088            Err(TableCommitmentArithmeticError::NonContiguous)
1089        ));
1090    }
1091
1092    #[test]
1093    fn we_cannot_sub_commitments_with_negative_difference() {
1094        let bigint_id: Ident = "bigint_column".into();
1095        let bigint_data = [1i64, 5, -5, 0, 10];
1096
1097        let varchar_id: Ident = "varchar_column".into();
1098        let varchar_data = ["Lorem", "ipsum", "dolor", "sit", "amet"];
1099
1100        let scalar_id: Ident = "scalar_column".into();
1101        let scalar_data = [1000, 2000, 3000, -1000, 0];
1102
1103        let columns_low: OwnedTable<TestScalar> = owned_table([
1104            bigint(bigint_id.value.as_str(), bigint_data[..2].to_vec()),
1105            varchar(varchar_id.value.as_str(), varchar_data[..2].to_vec()),
1106            scalar(scalar_id.value.as_str(), scalar_data[..2].to_vec()),
1107        ]);
1108        let table_commitment_low =
1109            TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(
1110                columns_low.inner_table(),
1111                0,
1112                &(),
1113            )
1114            .unwrap();
1115
1116        let columns_high: OwnedTable<TestScalar> = owned_table([
1117            bigint(bigint_id.value.as_str(), bigint_data[2..].to_vec()),
1118            varchar(varchar_id.value.as_str(), varchar_data[2..].to_vec()),
1119            scalar(scalar_id.value.as_str(), scalar_data[2..].to_vec()),
1120        ]);
1121        let table_commitment_high =
1122            TableCommitment::try_from_columns_with_offset(columns_high.inner_table(), 2, &())
1123                .unwrap();
1124
1125        let columns_all: OwnedTable<TestScalar> = owned_table([
1126            bigint(bigint_id.value.as_str(), bigint_data),
1127            varchar(varchar_id.value.as_str(), varchar_data),
1128            scalar(scalar_id.value.as_str(), scalar_data),
1129        ]);
1130        let table_commitment_all =
1131            TableCommitment::try_from_columns_with_offset(columns_all.inner_table(), 0, &())
1132                .unwrap();
1133
1134        // try to subtract the total commitment off the low to get the "negative" high commitment
1135        let try_negative_high_difference_result =
1136            table_commitment_low.try_sub(table_commitment_all.clone());
1137        assert!(matches!(
1138            try_negative_high_difference_result,
1139            Err(TableCommitmentArithmeticError::NegativeRange { .. })
1140        ));
1141
1142        // try to subtract the total commitment off the high to get the "negative" low commitment
1143        let try_negative_low_difference_result =
1144            table_commitment_high.try_sub(table_commitment_all);
1145        assert!(matches!(
1146            try_negative_low_difference_result,
1147            Err(TableCommitmentArithmeticError::NegativeRange { .. })
1148        ));
1149    }
1150
1151    #[test]
1152    fn we_can_create_and_append_table_commitments_with_record_batches() {
1153        let batch = record_batch!(
1154            "a" => [1i64, 2, 3],
1155            "b" => ["1", "2", "3"],
1156        );
1157
1158        let b_scals = ["1".into(), "2".into(), "3".into()];
1159
1160        let columns = [
1161            (&"a".into(), &Column::<TestScalar>::BigInt(&[1, 2, 3])),
1162            (
1163                &"b".into(),
1164                &Column::<TestScalar>::VarChar((&["1", "2", "3"], &b_scals)),
1165            ),
1166        ];
1167
1168        let mut expected_commitment =
1169            TableCommitment::<NaiveCommitment>::try_from_columns_with_offset(columns, 0, &())
1170                .unwrap();
1171
1172        let mut commitment =
1173            TableCommitment::<NaiveCommitment>::try_from_record_batch(&batch, &()).unwrap();
1174
1175        assert_eq!(commitment, expected_commitment);
1176
1177        let batch2 = record_batch!(
1178            "a" => [4i64, 5, 6],
1179            "b" => ["4", "5", "6"],
1180        );
1181
1182        let b_scals2 = ["4".into(), "5".into(), "6".into()];
1183
1184        let columns2 = [
1185            (&"a".into(), &Column::<TestScalar>::BigInt(&[4, 5, 6])),
1186            (
1187                &"b".into(),
1188                &Column::<TestScalar>::VarChar((&["4", "5", "6"], &b_scals2)),
1189            ),
1190        ];
1191
1192        expected_commitment.try_append_rows(columns2, &()).unwrap();
1193        commitment.try_append_record_batch(&batch2, &()).unwrap();
1194
1195        assert_eq!(commitment, expected_commitment);
1196    }
1197}
proof_of_sql/base/commitment/table_commitment.rs

proof_of_sql/base/commitment/
table_commitment.rs
