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
 
static constexpr std::array< size_t, 6 > TOTAL_LENGTH_ADJUSTMENTS
 

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

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

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}

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.

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:

Definition at line 68 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 39 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.

◆ TOTAL_LENGTH_ADJUSTMENTS

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

Definition at line 26 of file memory_relation.hpp.

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