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

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_{\text{last}}(\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_{\text{last}}(\vec X)\cdot Z_{\text{perm, shifted}}(\vec X) = 0 \end{align}

Here, \( \vec X = (X_0,\ldots, X_{d-1})\), and \(L_{\text{last}}\) is "Lagrange last", i.e., the indicator function on the boolean hypercube which is 1 at the point whose corresponding index is the last row of the circuit where the wire polynomails (w_l, w_r, w_o, and w_4) take non-zero values.

Template Parameters

FF_

Note

z_perm[1] == 1. if idx is the unique index such that lagrange_last[idx] == 1, then z_perm[y] == 0 for all y>idx (up to the size of the Boolean hypercube).

This is the only relation in Ultra that requires lagrange_last.

Definition at line 36 of file permutation_relation.hpp.

Member Typedef Documentation

FF

template<typename FF_ >

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

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

Parameters

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

Definition at line 123 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 83 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 60 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 56 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 57 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 49 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 40 of file permutation_relation.hpp.

---

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

• src/barretenberg/relations/permutation_relation.hpp