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::UltraPermutationRelationImpl< FF_ > Class Template Reference

Ultra Permutation Relation. More...

#include <permutation_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.
 
static auto & get_grand_product_polynomial (auto &in)
 
static auto & get_shifted_grand_product_polynomial (auto &in)
 
template<typename Accumulator , typename AllEntities , typename Parameters >
static Accumulator compute_grand_product_numerator (const AllEntities &in, const Parameters &params)
 
template<typename Accumulator , typename AllEntities , typename Parameters >
static Accumulator compute_grand_product_denominator (const AllEntities &in, const Parameters &params)
 
template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >
static void accumulate (ContainerOverSubrelations &accumulators, const AllEntities &in, const Parameters &params, const FF &scaling_factor)
 Compute contribution of the permutation relation for a given edge (internal function)
 

Static Public Attributes

static constexpr std::array< size_t, 2 > SUBRELATION_PARTIAL_LENGTHS
 
static constexpr std::array< size_t, 2 > TOTAL_LENGTH_ADJUSTMENTS
 

Detailed Description

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

Ultra Permutation Relation.

The Ultra Permutation Relation is given by the equation

\begin{align} \left( Z_{\text{perm}}(\vec X) + L_{0}(\vec X) \right) \cdot \left[ (w_1(\vec X) + id_1(\vec X) \cdot \beta + \gamma) \cdot (w_2(\vec X) + id_2(\vec X) \cdot \beta + \gamma) \cdot (w_3(\vec X) + id_3(\vec X) \cdot \beta + \gamma) \cdot (w_4(\vec X) + id_4(\vec X) \cdot \beta + \gamma)\right] &\ - \\ \left(Z_{\text{perm, shifted}}(\vec X) + L_{2^d-1}(\vec X) \cdot \delta_{\text{pub}} \right) \cdot \left[ (w_1(\vec X) + \sigma_1(\vec X) \cdot \beta + \gamma) \cdot (w_2(\vec X) + \sigma_2(\vec X) \cdot \beta + \gamma) \cdot (w_3(\vec X) + \sigma_3 (\vec X) \cdot \beta + \gamma) \cdot (w_4 (\vec X) + \sigma_4(\vec X) \cdot \beta + \gamma)\right] &\ = 0 \end{align}

and

\begin{align} L_{2^d-1}(\vec X)\cdot Z_{\text{perm, shifted}}(\vec X) = 0 \end{align}

Here, \( \vec X = (X_0,\ldots, X_{d-1})\), where \( d \) is the log of the circuit size.

Template Parameters
FF_

Definition at line 30 of file permutation_relation.hpp.

Member Typedef Documentation

◆ FF

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

Definition at line 32 of file permutation_relation.hpp.

Member Function Documentation

◆ accumulate()

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

Compute contribution of the permutation relation for a given edge (internal function)

This relation confirms faithful calculation of the grand product polynomial \( Z_{\text{perm}}\). In Sumcheck Prover Round, this method adds to accumulators evaluations of subrelations at the point \((u_0,\ldots, u_{i-1}, k, \vec\ell)\) for \( k=0,\ldots, D\), where \( \vec \ell\) is a point on the Boolean hypercube \(\{0,1\}^{d-1-i}\) and \( D \) is specified by the calling class. It does so by taking as input an array of Prover Polynomials partially evaluated at the points \((u_0,\ldots, u_{i-1}, k, \vec\ell)\) and computing point-wise evaluations of the sub-relations.

Todo:
Protogalaxy Accumulation
Parameters
evalstransformed to evals + C(in(X)...)*scaling_factor
inan std::array containing the fully extended Univariate edges.
parameterscontains beta, gamma, and public_input_delta, ....
scaling_factoroptional term to scale the evaluation before adding to evals.

Definition at line 122 of file permutation_relation.hpp.

◆ compute_grand_product_denominator()

template<typename FF_ >
template<typename Accumulator , typename AllEntities , typename Parameters >
static Accumulator bb::UltraPermutationRelationImpl< FF_ >::compute_grand_product_denominator ( const AllEntities &  in,
const Parameters &  params 
)
inlinestatic

Definition at line 82 of file permutation_relation.hpp.

◆ compute_grand_product_numerator()

template<typename FF_ >
template<typename Accumulator , typename AllEntities , typename Parameters >
static Accumulator bb::UltraPermutationRelationImpl< FF_ >::compute_grand_product_numerator ( const AllEntities &  in,
const Parameters &  params 
)
inlinestatic

Definition at line 59 of file permutation_relation.hpp.

◆ get_grand_product_polynomial()

template<typename FF_ >
static auto & bb::UltraPermutationRelationImpl< FF_ >::get_grand_product_polynomial ( auto &  in)
inlinestatic

Definition at line 55 of file permutation_relation.hpp.

◆ get_shifted_grand_product_polynomial()

template<typename FF_ >
static auto & bb::UltraPermutationRelationImpl< FF_ >::get_shifted_grand_product_polynomial ( auto &  in)
inlinestatic

Definition at line 56 of file permutation_relation.hpp.

◆ skip()

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

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

Definition at line 48 of file permutation_relation.hpp.

Member Data Documentation

◆ SUBRELATION_PARTIAL_LENGTHS

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

Definition at line 34 of file permutation_relation.hpp.

◆ TOTAL_LENGTH_ADJUSTMENTS

template<typename FF_ >
constexpr std::array<size_t, 2> bb::UltraPermutationRelationImpl< FF_ >::TOTAL_LENGTH_ADJUSTMENTS
staticconstexpr
Initial value:
{
5,
0
}

Definition at line 39 of file permutation_relation.hpp.

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