Trait triton_vm::table::master_table::MasterTable

pub trait MasterTable<FF>: Sync
where
    FF: FiniteField + MulAssign<BFieldElement> + Mul<BFieldElement, Output = FF> + From<BFieldElement>,
    Standard: Distribution<FF>,
{
    // Required methods
    fn trace_domain(&self) -> ArithmeticDomain;
    fn randomized_trace_domain(&self) -> ArithmeticDomain;
    fn quotient_domain(&self) -> ArithmeticDomain;
    fn fri_domain(&self) -> ArithmeticDomain;
    fn trace_table(&self) -> ArrayView2<'_, FF>;
    fn trace_table_mut(&mut self) -> ArrayViewMut2<'_, FF>;
    fn randomized_trace_table(&self) -> ArrayView2<'_, FF>;
    fn randomized_trace_table_mut(&mut self) -> ArrayViewMut2<'_, FF>;
    fn quotient_domain_table(&self) -> ArrayView2<'_, FF>;
    fn fri_domain_table(&self) -> ArrayView2<'_, FF>;
    fn memoize_low_degree_extended_table(
        &mut self,
        low_degree_extended_columns: Array2<FF>
    );
    fn low_degree_extended_table(&self) -> ArrayView2<'_, FF>;
    fn memoize_interpolation_polynomials(
        &mut self,
        interpolation_polynomials: Array1<Polynomial<FF>>
    );
    fn interpolation_polynomials(
        &self
    ) -> ArrayView1<'_, Polynomial<XFieldElement>>;
    fn row(&self, row_index: XFieldElement) -> Array1<XFieldElement>;
    fn hash_one_row(row: ArrayView1<'_, FF>) -> Digest;

    // Provided methods
    fn randomize_trace(&mut self) { ... }
    fn low_degree_extend_all_columns(&mut self) { ... }
    fn merkle_tree(
        &self,
        maybe_profiler: &mut Option<TritonProfiler>
    ) -> MerkleTree<Tip5> { ... }
    fn hash_all_fri_domain_rows(&self) -> Vec<Digest> { ... }
}

A Master Table is, in some sense, a top-level table of Triton VM. It contains all the data but little logic beyond bookkeeping and presenting the data in useful ways. Conversely, the individual tables contain no data but all the respective logic. Master Tables are responsible for managing the individual tables and for presenting the right data to the right tables, serving as a clean interface between the VM and the individual tables.

As a mental model, it is perfectly fine to think of the data for the individual tables as completely separate from each other. Only the cross-table arguments link all tables together.

Conceptually, there are two Master Tables: the MasterBaseTable (“main”), the Master Extension Table (“auxiliary”). The lifecycle of the Master Tables is as follows:

1. The MasterBaseTable is instantiated and filled using the Algebraic Execution Trace.
2. The MasterBaseTable is padded using logic from the individual tables.
3. The still-empty entries in the MasterBaseTable are filled with random elements. This step is also known as “trace randomization.”
4. Each column of the MasterBaseTable is low-degree extended. The results are stored in the MasterBaseTable. Methods quotient_domain_table, fri_domain_table, interpolation_polynomials, and row can now be used without causing panic.
5. The MasterBaseTable is used to derive the MasterExtensionTable using logic from the individual tables.
6. The MasterExtensionTable is trace-randomized.
7. Each column of the MasterExtensionTable is low-degree extended. The effects are the same as for the MasterBaseTable.
8. Using the MasterBaseTable and the MasterExtensionTable, the quotient codeword is derived using the AIR. Each individual table defines that part of the AIR that is relevant to it.

The following points are of note:

• The MasterExtensionTable’s rightmost columns are the randomizer codewords. These are necessary for zero-knowledge.
• The cross-table argument has zero width for the MasterBaseTable and MasterExtensionTable but does induce a nonzero number of constraints and thus terms in the quotient combination.

Required Methods

fn trace_domain(&self) -> ArithmeticDomain

fn randomized_trace_domain(&self) -> ArithmeticDomain

fn quotient_domain(&self) -> ArithmeticDomain

fn fri_domain(&self) -> ArithmeticDomain

fn trace_table(&self) -> ArrayView2<'_, FF>

Presents underlying trace data, excluding trace randomizers and randomizer polynomials.

fn trace_table_mut(&mut self) -> ArrayViewMut2<'_, FF>

Mutably presents underlying trace data, excluding trace randomizers and randomizer polynomials.

fn randomized_trace_table(&self) -> ArrayView2<'_, FF>

fn randomized_trace_table_mut(&mut self) -> ArrayViewMut2<'_, FF>

fn quotient_domain_table(&self) -> ArrayView2<'_, FF>

The low-degree extended randomized trace data over the quotient domain. Includes randomizer polynomials. Requires having called low_degree_extend_all_columns first.

fn fri_domain_table(&self) -> ArrayView2<'_, FF>

The low-degree extended randomized trace data over the FRI domain. Includes randomizer polynomials. Requires having called low_degree_extend_all_columns first.

fn memoize_low_degree_extended_table( &mut self, low_degree_extended_columns: Array2<FF> )

Not intended for direct use, but through Self::low_degree_extend_all_columns.

fn low_degree_extended_table(&self) -> ArrayView2<'_, FF>

Requires having called low_degree_extend_all_columns first.

fn memoize_interpolation_polynomials( &mut self, interpolation_polynomials: Array1<Polynomial<FF>> )

Memoize the polynomials interpolating the columns. Not intended for direct use, but through Self::low_degree_extend_all_columns.

fn interpolation_polynomials(&self) -> ArrayView1<'_, Polynomial<XFieldElement>>

Requires having called low_degree_extend_all_columns first.

fn row(&self, row_index: XFieldElement) -> Array1<XFieldElement>

Get one row of the table at an arbitrary index. Notably, the index does not have to be in any of the domains. In other words, can be used to compute out-of-domain rows. Requires having called low_degree_extend_all_columns first. Does not include randomizer polynomials.

fn hash_one_row(row: ArrayView1<'_, FF>) -> Digest

Provided Methods

fn randomize_trace(&mut self)

Set all rows not part of the actual (padded) trace to random values.

fn low_degree_extend_all_columns(&mut self)

Low-degree extend all columns of the randomized trace domain table. The resulting low-degree extended columns can be accessed using quotient_domain_table and fri_domain_table.

fn merkle_tree( &self, maybe_profiler: &mut Option<TritonProfiler> ) -> MerkleTree<Tip5>

Compute a Merkle tree of the FRI domain table. Every row gives one leaf in the tree. The function hash_row is used to hash each row.

fn hash_all_fri_domain_rows(&self) -> Vec<Digest>

Object Safety

This trait is not object safe.

Implementors

impl MasterTable<BFieldElement> for MasterBaseTable

impl MasterTable<XFieldElement> for MasterExtTable