proof_system::AuxiliaryRelationImpl< FF_ > Class Template Reference

Public Types
using	FF = FF_

Static Public Member Functions
template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >
static void	accumulate (ContainerOverSubrelations &accumulators, const AllEntities &in, const Parameters &params, const FF &scaling_factor)
	Expression for the generalized permutation sort gate.

Static Public Attributes
static constexpr std::array< size_t, 6 >	SUBRELATION_PARTIAL_LENGTHS
static constexpr std::array< size_t, 6 >	TOTAL_LENGTH_ADJUSTMENTS

Member Function Documentation

accumulate()

template<typename FF_ >

template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >

static void proof_system::AuxiliaryRelationImpl< FF_ >::accumulate ( ContainerOverSubrelations &  accumulators, const AllEntities &  in, const Parameters &  params, const FF &  scaling_factor  )

inlinestatic

Expression for the generalized permutation sort gate.

The following explanation is reproduced from the Plonk analog 'plookup_auxiliary_widget': Adds contributions for identities associated with several custom gates:

• RAM/ROM read-write consistency check
• RAM timestamp difference consistency check
• RAM/ROM index difference consistency check
• Bigfield product evaluation (3 in total)
• Bigfield limb accumulation (2 in total)

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

Parameters

evals	transformed to evals + C(in(X)...)*scaling_factor
in	an std::array containing the Totaly extended Univariate edges.
parameters	contains beta, gamma, and public_input_delta, ....
scaling_factor	optional term to scale the evaluation before adding to evals.

Non native field arithmetic gate 2 deg 4

        _                                                                               _
       /   _                   _                               _       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 Partial degree: 1 Total degree: 4

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 Partial degree: 1 Total degree: 4

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 Partial degree:

Member Data Documentation

SUBRELATION_PARTIAL_LENGTHS

template<typename FF_ >

constexpr std::array<size_t, 6> proof_system::AuxiliaryRelationImpl< FF_ >::SUBRELATION_PARTIAL_LENGTHS

staticconstexpr

Initial value:

{
        6, 
        6, 
        6, 
        6, 
        6, 
        6  
    }

TOTAL_LENGTH_ADJUSTMENTS

template<typename FF_ >

constexpr std::array<size_t, 6> proof_system::AuxiliaryRelationImpl< FF_ >::TOTAL_LENGTH_ADJUSTMENTS

staticconstexpr

Initial value:

{
        6, 
        6, 
        6, 
        6, 
        6, 
        6  
    }

---

The documentation for this class was generated from the following file:

• src/barretenberg/relations/auxiliary_relation.hpp