Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
Public Types | Static Public Member Functions | Static Public Attributes | List of all members
bb::MemoryRelationImpl< FF_ > Class Template Reference

#include <memory_relation.hpp>

Public Types

using FF = FF_
 

Static Public Member Functions

template<typename AllEntities >
static bool skip (const AllEntities &in)
 Returns true if the contribution from all subrelations for the provided inputs is identically zero.
 
template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >
static void accumulate (ContainerOverSubrelations &accumulators, const AllEntities &in, const Parameters &params, const FF &scaling_factor)
 RAM/ROM memory relation.
 

Static Public Attributes

static constexpr std::array< size_t, 6 > SUBRELATION_PARTIAL_LENGTHS
 

Detailed Description

template<typename FF_>
class bb::MemoryRelationImpl< FF_ >

Definition at line 13 of file memory_relation.hpp.

Member Typedef Documentation

◆ FF

template<typename FF_ >
using bb::MemoryRelationImpl< FF_ >::FF = FF_

Definition at line 15 of file memory_relation.hpp.

Member Function Documentation

◆ accumulate()

template<typename FF_ >
template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >
static void bb::MemoryRelationImpl< FF_ >::accumulate ( ContainerOverSubrelations &  accumulators,
const AllEntities &  in,
const Parameters &  params,
const FF &  scaling_factor 
)
inlinestatic

RAM/ROM memory relation.

Adds contributions for identities associated with RAM/ROM memory operations custom gates:

  • RAM/ROM read-write consistency check
  • RAM timestamp difference consistency check
  • RAM/ROM index difference consistency check

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

gate type q_mem q_1 q_2 q_3 q_4 q_m q_c
RAM/ROM access gate 1 1 0 0 0 1 —
RAM timestamp check 1 1 0 0 1 0 —
ROM consistency check 1 1 1 0 0 0 —
RAM consistency check 1 0 0 1 0 0 0

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
evalstransformed to evals + C(in(X)...)*scaling_factor
inan std::array containing the totally extended univariate edges.
parameterscontains beta, gamma, and public_input_delta, ....
scaling_factoroptional term to scale the evaluation before adding to evals.

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 * η₂ + value * η₃

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 * η₂ + value1 * η₃

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 Degree: 1

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

qc + w1 \eta + w2 η₂ + w3 η₃ - w4 = 0

For ROM gates, qc = 0 Here, informally, w4 is the "record" (a.k.a. fingerprint) of the access gate.

ROM Consistency Check Degree: 5

For every ROM read, we require a multiset check applied between the record witnesses and a second set of records that are sorted. (See the Plookup paper.) In fact, due to our implementation, this is automatic; we implicitly have copy-constraints realizing the multiset equality. In other words, the multiset check will be instantiated by a permutation check.

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}

(1) is witnessed jointly with corresponding other constraints in std::get<0>(accumulators)

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 * η + w2 * η₂ + w3 * η₃ - 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.

We apply the following checks for the sorted records:

  1. If adjacent indicies match and next access is a read, then the adjacent values must match.
  2. The index increases by {0, 1}
  3. The next gate access is either a READ or a WRITE (i.e., boolean).

RAM Timestamp Consistency Check

The gates constructed to witness the consistency of the jumps in the timestamp have the following form. They are constructed to be sorted, first with respect to index, then with respect to timestamp. (This is the same structure as the sorted RAM gates.) This is enforced by copy constraints (the witness indices of the gates are the same as those of the sorted RAM gates, so we do not need to explicitly check the lexicographic ordering again.)

| 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.

Note
the timestamp_deltas are range-constrained elsewhere.

The complete RAM/ROM memory identity Degree: 5

Definition at line 59 of file memory_relation.hpp.

◆ skip()

template<typename FF_ >
template<typename AllEntities >
static bool bb::MemoryRelationImpl< FF_ >::skip ( const AllEntities &  in)
inlinestatic

Returns true if the contribution from all subrelations for the provided inputs is identically zero.

Definition at line 30 of file memory_relation.hpp.

Member Data Documentation

◆ SUBRELATION_PARTIAL_LENGTHS

template<typename FF_ >
constexpr std::array<size_t, 6> bb::MemoryRelationImpl< FF_ >::SUBRELATION_PARTIAL_LENGTHS
staticconstexpr
Initial value:
{
6,
6,
6,
6,
6,
6
}

Definition at line 17 of file memory_relation.hpp.

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