Trait MasterTable

pub trait MasterTable: Sync
where
    Standard: Distribution<Self::Field>,
    XFieldElement: Add<Self::Field, Output = XFieldElement> + Add<XFieldElement, Output = XFieldElement>,
{
    type Field: FiniteField + Add<BFieldElement, Output = Self::Field> + MulAssign<BFieldElement> + From<BFieldElement> + BFieldCodec + Mul<BFieldElement, Output = Self::Field> + Mul<XFieldElement, Output = XFieldElement> + 'static;

    const NUM_COLUMNS: usize;

    // 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<'_, Self::Field>;
    fn trace_table_mut(&mut self) -> ArrayViewMut2<'_, Self::Field>;
    fn quotient_domain_table(&self) -> Option<ArrayView2<'_, Self::Field>>;
    fn fri_domain_table(&self) -> Option<ArrayView2<'_, Self::Field>>;
    fn trace_randomizer_seed(&self) -> <StdRng as SeedableRng>::Seed;
    fn num_trace_randomizers(&self) -> usize;

    // Provided methods
    fn evaluation_domain(&self) -> ArithmeticDomain { ... }
    fn maybe_low_degree_extend_all_columns(&mut self) { ... }
    fn out_of_domain_row(
        &self,
        indeterminate: XFieldElement,
    ) -> Array1<XFieldElement> { ... }
    fn randomized_column_interpolant(
        &self,
        idx: usize,
    ) -> Polynomial<'static, Self::Field> { ... }
    fn trace_randomizer_for_column(
        &self,
        idx: usize,
    ) -> Polynomial<'static, Self::Field> { ... }
    fn merkle_tree(&self) -> MerkleTree { ... }
    fn hash_all_fri_domain_rows(&self) -> Vec<Digest> { ... }
    fn weighted_sum_of_columns(
        &self,
        weights: Array1<XFieldElement>,
    ) -> Polynomial<'_, XFieldElement> { ... }
    fn reveal_rows(&self, row_indices: &[usize]) -> Vec<Vec<Self::Field>> { ... }
}

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 MasterMainTable, and the Master Auxiliary Table. The lifecycle of the Master Tables is as follows:

1. The MasterMainTable is instantiated and filled using the Algebraic Execution Trace.
2. The MasterMainTable is padded using logic from the individual tables.
3. The still-empty entries in the MasterMainTable are filled with random elements. This step is also known as “trace randomization.”
4. If there is enough RAM, then each column of the MasterMainTable is low-degree extended. The results are stored on the MasterMainTable for quick access later. If there is not enough RAM, then the low-degree extensions of the trace columns will be computed and sometimes recomputed just-in-time, and the memory freed afterward. The caching behavior can be forced.
5. The MasterMainTable is used to derive the MasterAuxiliaryTable using logic from the individual tables.
6. The MasterAuxiliaryTable is trace-randomized.
7. Each column of the MasterAuxiliaryTable is low-degree extended. The effects are the same as for the MasterMainTable.
8. Using the MasterMainTable and the MasterAuxiliaryTable, 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 MasterAuxiliaryTable’s rightmost columns are the randomizer codewords. These are necessary for zero-knowledge.
• The cross-table argument has zero width for the MasterMainTable and MasterAuxiliaryTable but does induce a nonzero number of constraints and thus terms in the quotient combination.

Required Associated Constants

const NUM_COLUMNS: usize

Required Associated Types

type Field: FiniteField + Add<BFieldElement, Output = Self::Field> + MulAssign<BFieldElement> + From<BFieldElement> + BFieldCodec + Mul<BFieldElement, Output = Self::Field> + Mul<XFieldElement, Output = XFieldElement> + 'static

Required Methods

fn trace_domain(&self) -> ArithmeticDomain

fn randomized_trace_domain(&self) -> ArithmeticDomain

fn quotient_domain(&self) -> ArithmeticDomain

The ArithmeticDomain just large enough to compute all quotients.

fn fri_domain(&self) -> ArithmeticDomain

The ArithmeticDomain large enough for FRI.

fn trace_table(&self) -> ArrayView2<'_, Self::Field>

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

fn trace_table_mut(&mut self) -> ArrayViewMut2<'_, Self::Field>

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

fn quotient_domain_table(&self) -> Option<ArrayView2<'_, Self::Field>>

The quotient-domain view of the cached low-degree-extended table, if

1. the table has been low-degree extended, and
2. the low-degree-extended table has been cached.

fn fri_domain_table(&self) -> Option<ArrayView2<'_, Self::Field>>

Return the FRI domain view of the cached low-degree-extended table, if any.

This method cannot be implemented generically on the trait because it returns a pointer to an array and that array has to live somewhere; it cannot live on stack and from the trait implementation we cannot access the implementing object’s fields.

fn trace_randomizer_seed(&self) -> <StdRng as SeedableRng>::Seed

fn num_trace_randomizers(&self) -> usize

Provided Methods

fn evaluation_domain(&self) -> ArithmeticDomain

The ArithmeticDomain to low-degree extend into. The larger of the quotient_domain and the fri_domain.

fn maybe_low_degree_extend_all_columns(&mut self)

Low-degree extend all columns of the trace table (including randomizers) if it can be cached. In that case, the resulting low-degree extended columns can be accessed using quotient_domain_table and fri_domain_table.

fn out_of_domain_row( &self, indeterminate: 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. Does not include randomizer polynomials.

fn randomized_column_interpolant( &self, idx: usize, ) -> Polynomial<'static, Self::Field>

fn trace_randomizer_for_column( &self, idx: usize, ) -> Polynomial<'static, Self::Field>

Uniquely enables the revelation of up to num_trace_randomizers entries in the corresponding column without compromising zero-knowledge.

In order for the trace randomizer to not influence the trace on the trace domain, it must be multiplied with a polynomial that evaluates to zero on that domain. The polynomial of lowest degree with this property is the corresponding zerofier. The randomized trace column interpolant can then be obtained through:

column + zerofier·randomizer

If you want to multiply the trace randomizer with the zerofier, the most performant approach is ArithmeticDomain::mul_zerofier_with.

Panics

Panics if the idx is larger than or equal to Self::NUM_COLUMNS.

fn merkle_tree(&self) -> MerkleTree

Compute a Merkle tree of the FRI domain table. Every row gives one leaf in the tree.

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

fn weighted_sum_of_columns( &self, weights: Array1<XFieldElement>, ) -> Polynomial<'_, XFieldElement>

The linear combination of the trace-randomized columns using the given weights.

Panics

Panics if the number of supplied weights is unequal to the number of columns.

fn reveal_rows(&self, row_indices: &[usize]) -> Vec<Vec<Self::Field>>

Panics

Panics if any of the requested indices is out of range; that is, larger than min(self.fri_domain().length, u32::MAX).

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl MasterTable for MasterAuxTable

const NUM_COLUMNS: usize = 88usize

type Field = XFieldElement

impl MasterTable for MasterMainTable

const NUM_COLUMNS: usize = 379usize

type Field = BFieldElement