proof_of_sql/base/database/
accessor.rs

1use crate::base::{
2    commitment::Commitment,
3    database::{Column, ColumnType, Table, TableOptions, TableRef},
4    map::{IndexMap, IndexSet},
5    scalar::Scalar,
6};
7use alloc::vec::Vec;
8use sqlparser::ast::Ident;
9
10/// Access metadata of a table span in a database.
11///
12/// Both Prover and Verifier use this information when processing a query.
13///
14/// Note: we assume that the query has already been validated so that we
15/// will only be accessing information about tables that exist in the database.
16pub trait MetadataAccessor {
17    /// Return the data span's length in the table (not the full table length)
18    fn get_length(&self, table_ref: &TableRef) -> usize;
19
20    /// Return the data span's offset in the table
21    ///
22    /// If the data span has its first row starting at the ith table row,
23    /// this `get_offset` should then return `i`.
24    fn get_offset(&self, table_ref: &TableRef) -> usize;
25}
26
27/// Access commitments of database columns.
28///
29/// Verifier uses this information to process a query.
30///
31/// In pseudo-code, here is a sketch of how [`CommitmentAccessor`] fits in
32/// with the verification workflow:
33///
34/// ```ignore
35/// verify(proof, query, commitment_database) {
36///     if(!validate_query(query, commitment_database)) {
37///         // if the query references columns that don't exist
38///         // we should error here before going any further
39///         return invalid-query()
40///     }
41///     commitment_database.reader_lock()
42///     // we can't be updating commitments while verifying
43///     accessor <- make-commitment-accessor(commitment_database)
44///     verify_result <- verify-valid-query(proof, query, accessor)
45///     commitment_database.reader_unlock()
46///     return verify_result
47/// }
48/// ```
49///
50/// Note: we assume that the query has already been validated so that we
51/// will only be accessing information about columns that exist in the database.
52pub trait CommitmentAccessor<C: Commitment>: MetadataAccessor {
53    /// Return the full table column commitment
54    fn get_commitment(&self, table_ref: &TableRef, column_id: &Ident) -> C;
55}
56
57/// Access database columns of an in-memory table span.
58///
59/// Prover uses this information to process a query.
60///
61/// In pseudo-code, here is a sketch of how [`DataAccessor`] fits in
62/// with the prove workflow:
63///
64/// ```ignore
65/// prove(query, database) {
66///       if(!validate_query(query, database)) {
67///           // if the query references columns that don't exist
68///           // we should error here before going any further
69///           invalid-query()
70///       }
71///       update-cached-columns(database, query)
72///            // if the database represents an in-memory cache of an externally persisted
73///            // database we should update the cache so that any column referenced in the query
74///            // will be available
75///       database.reader_lock()
76///           // we can't be updating the database while proving
77///       accessor <- make-data-accessor(database)
78///       proof <- prove-valid-query(query, accessor)
79///       database.reader_unlock()
80///       return proof
81/// }
82/// ```
83///
84/// Note: we assume that the query has already been validated so that we
85/// will only be accessing information about columns that exist in the database.
86pub trait DataAccessor<S: Scalar>: MetadataAccessor {
87    /// Return the data span in the table (not the full-table data)
88    fn get_column(&self, table_ref: &TableRef, column_id: &Ident) -> Column<S>;
89
90    /// Creates a new [`Table`] from a [`TableRef`] and [`Ident`]s.
91    ///
92    /// Columns are retrieved from the [`DataAccessor`] using the provided [`TableRef`] and [`Ident`]s.
93    /// The only reason why [`table_ref`] is needed is because [`column_ids`] can be empty.
94    /// # Panics
95    /// Column length mismatches can occur in theory. In practice, this should not happen.
96    fn get_table(&self, table_ref: &TableRef, column_ids: &IndexSet<Ident>) -> Table<S> {
97        if column_ids.is_empty() {
98            let input_length = self.get_length(table_ref);
99            Table::<S>::try_new_with_options(
100                IndexMap::default(),
101                TableOptions::new(Some(input_length)),
102            )
103        } else {
104            Table::<S>::try_from_iter(column_ids.into_iter().map(|column_id| {
105                let column = self.get_column(table_ref, column_id);
106                (column_id.clone(), column)
107            }))
108        }
109        .expect("Failed to create table from table and column references")
110    }
111}
112
113/// Access tables and their schemas in a database.
114///
115/// This accessor should be implemented by both the prover and verifier
116/// and then used by the Proof of SQL code to convert an `IntermediateAst`
117/// into a [`ProofPlan`](crate::sql::proof::ProofPlan).
118pub trait SchemaAccessor {
119    /// Lookup the column's data type in the specified table
120    ///
121    /// Return:
122    ///   - Some(type) if the column exists, where `type` is the column's data type
123    ///   - None in case the column does not exist in the table
124    ///
125    /// Precondition 1: the table must exist and be tamperproof.
126    /// Precondition 2: `table_ref` and `column_id` must always be lowercase.
127    fn lookup_column(&self, table_ref: &TableRef, column_id: &Ident) -> Option<ColumnType>;
128
129    /// Lookup all the column names and their data types in the specified table
130    ///
131    /// Return:
132    ///   - The list of column names with their data types
133    ///
134    /// Precondition 1: the table must exist and be tamperproof.
135    /// Precondition 2: `table_name` must be lowercase.
136    fn lookup_schema(&self, table_ref: &TableRef) -> Vec<(Ident, ColumnType)>;
137}
proof_of_sql/base/database/accessor.rs

proof_of_sql/base/database/
accessor.rs
