Struct LookupTable 

pub struct LookupTable {
    id: NodeId,
    constraints: Vec<LookupConstraint>,
    table_node_id: NodeId,
    fiat_shamir_challenge_node_id: NodeId,
}

Represents a table of data that can be looked up into, e.g. for a range check. Implements “Improving logarithmic derivative lookups using GKR” (2023) by Papini & Haböck. Note that (as is usual e.g. in permutation checks) we do not check that the product of the denominators is nonzero. This means the soundness of logUp is bounded by |F| / max{num_constrained_values, num_table_values}. To adapt this to a small field setting, consider using Fermat’s Little Theorem.

For a more detailed description of the soundness argument for the above, see https://www.notion.so/LogUp-ext-f846956acc3640a68bad51f7897fe32f?pvs=4#15b68687d27e807fae3fcdff59791174

Fields

id: NodeId

constraints: Vec<LookupConstraint>

The lookups that are performed on this table (will be automatically populated, via LookupTable::add_lookup_constraint, during layout).

table_node_id: NodeId

The id of the node providing the table entries.

fiat_shamir_challenge_node_id: NodeId

The ID of the FiatShamirChallengeNode for the FS challenge.

Implementations

impl LookupTable

pub fn new( table: &dyn CircuitNode, fiat_shamir_challenge_node: &FiatShamirChallengeNode, ) -> Self

Create a new LookupTable to use for subsequent lookups. (To perform a lookup using this table, create a LookupConstraint.)

Requires:

• The length of the table must be a power of two.

pub fn add_lookup_constraint(&mut self, constraint: LookupConstraint)

Add a lookup constraint to this node. (Will be called by the layouter when laying out the circuit.)

pub fn generate_lookup_circuit_description<F: Field>( &self, circuit_map: &mut CircuitMap, ) -> Result<(Vec<LayerDescriptionEnum<F>>, OutputLayerDescription<F>)>

Create the circuit description of a lookup node by returning the corresponding circuit descriptions, and output circuit description needed in order to verify the lookup.

Trait Implementations

impl CircuitNode for LookupTable

fn id(&self) -> NodeId

The unique ID of this node

fn sources(&self) -> Vec<NodeId>

Return the ids of the nodes that this node depends upon, i.e. nodes whose values must be known before the values of this node can be node. These are the source nodes of the directed edges of the DAG that terminate at this node.

fn get_num_vars(&self) -> usize

Get the number of variables used to represent the data in this node.

impl Clone for LookupTable

fn clone(&self) -> LookupTable

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for LookupTable

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<F: Field> From<LookupTable> for NodeEnum<F>

fn from(var: LookupTable) -> NodeEnum<F>

Converts to this type from the input type.