barretenberg
Loading...
Searching...
No Matches
Static Public Member Functions | Static Public Attributes | List of all members
proof_system::plonk::widget::PlookupAuxiliaryKernel< Field, Getters, PolyContainer > Class Template Reference

Plookup Auxiliary Widget. More...

#include <plookup_auxiliary_widget.hpp>

Static Public Member Functions

static std::set< PolynomialIndex > const & get_required_polynomial_ids ()
 
static void accumulate_contribution (PolyContainer &polynomials, const challenge_array &challenges, Field &quotient, const size_t i=0)
 

Static Public Attributes

static constexpr bool use_quotient_mid = false
 
static constexpr size_t num_independent_relations = 4
 
static constexpr uint8_t quotient_required_challenges = CHALLENGE_BIT_ALPHA
 
static constexpr uint8_t update_required_challenges = CHALLENGE_BIT_ALPHA
 

Detailed Description

template<class Field, class Getters, typename PolyContainer>
class proof_system::plonk::widget::PlookupAuxiliaryKernel< Field, Getters, PolyContainer >

Plookup Auxiliary Widget.

Evaluates polynomial identities associated with the following UltraPlonk custom gates:

Multiple selectors are used to 'switch' aux gates on/off according to the following pattern:

gate type q_aux q_1 q_2 q_3 q_4 q_m q_c q_arith
Bigfield Limb Accumulation 1 1 0 0 1 1 0 — 0
Bigfield Limb Accumulation 2 1 0 0 1 0 1 — 0
Bigfield Product 1 1 0 1 1 0 0 — 0
Bigfield Product 2 1 0 1 0 1 0 — 0
Bigfield Product 3 1 0 1 0 0 1 — 0
RAM/ROM access gate 1 1 0 0 0 1 — 0
RAM timestamp check 1 1 0 0 1 0 — 0
ROM consistency check 1 1 1 0 0 0 — 0
RAM consistency check 1 0 0 0 0 0 0 1

N.B. The RAM consistency check identity is degree 3. To keep the overall quotient degree at <=5, only 2 selectors can be used to select it.

N.B.2 The q_c selector is used to store circuit-specific values in the RAM/ROM access gate

Template Parameters
Field
Getters
PolyContainer

Member Function Documentation

◆ accumulate_contribution()

template<class Field , class Getters , typename PolyContainer >
static void proof_system::plonk::widget::PlookupAuxiliaryKernel< Field, Getters, PolyContainer >::accumulate_contribution ( PolyContainer &  polynomials,
const challenge_array &  challenges,
Field &  quotient,
const size_t  i = 0 
)
inlinestatic

Non native field arithmetic gate 2 

        _                                                                               _
       /   _                   _                               _       14                \

q_2 . q_4 | (w_1 . w_2) + (w_1 . w_2) + (w_1 . w_4 + w_2 . w_3 - w_3) . 2 - w_3 - w_4 | _ _/

MEMORY

A RAM memory record contains a tuple of the following fields:

  • i: index of memory cell being accessed
  • t: timestamp of memory cell being accessed (used for RAM, set to 0 for ROM)
  • v: value of memory cell being accessed
  • a: access type of record. read: 0 = read, 1 = write
  • r: record of memory cell. record = access + index * eta + timestamp * eta^2 + value * eta^3

A ROM memory record contains a tuple of the following fields:

  • i: index of memory cell being accessed
  • v: value1 of memory cell being accessed (ROM tables can store up to 2 values per index)
  • v2:value2 of memory cell being accessed (ROM tables can store up to 2 values per index)
  • r: record of memory cell. record = index * eta + value2 * eta^2 + value1 * eta^3

When performing a read/write access, the values of i, t, v, v2, a, r are stored in the following wires + selectors, depending on whether the gate is a RAM read/write or a ROM read

gate type i v2/t v a r
ROM w1 w2 w3 – w4
RAM w1 w2 w3 qc w4

(for accesses where index is a circuit constant, it is assumed the circuit will apply a copy constraint on w2 to fix its value)

Memory Record Check

A ROM/ROM access gate can be evaluated with the identity:

qc + w1 \eta + w2 \eta^2 + w3 \eta^3 - w4 = 0

For ROM gates, qc = 0

ROM Consistency Check

For every ROM read, a set equivalence check is applied between the record witnesses, and a second set of records that are sorted.

We apply the following checks for the sorted records:

  1. w1, w2, w3 correctly map to 'index', 'v1, 'v2' for a given record value at w4
  2. index values for adjacent records are monotonically increasing
  3. if, at gate i, index_i == index_{i + 1}, then value1_i == value1_{i + 1} and value2_i == value2_{i + 1}

RAM Consistency Check

The 'access' type of the record is extracted with the expression w_4 - partial_record_check (i.e. for an honest Prover w1 * eta + w2 * eta^2 + w3 * eta^3 - w4 = access. This is validated by requiring access to be boolean

For two adjacent entries in the sorted list if both A) index values match B) adjacent access value is 0 (i.e. next gate is a READ) then C) both values must match. The gate boolean check is (A && B) => C === !(A && B) || C === !A || !B || C

N.B. it is the responsibility of the circuit writer to ensure that every RAM cell is initialized with a WRITE operation.

RAM Timestamp Consistency Check

| w1 | w2 | w3 | w4 | | index | timestamp | timestamp_check | – |

Let delta_index = index_{i + 1} - index_{i}

Iff delta_index == 0, timestamp_check = timestamp_{i + 1} - timestamp_i Else timestamp_check = 0

The complete RAM/ROM memory identity

The documentation for this class was generated from the following file:
Generated by doxygen 1.9.6