permutation_lib.hpp File Reference

Contains various functions that help construct Honk and Plonk Sigma and Id polynomials. More...

#include "barretenberg/common/ref_vector.hpp"
#include "barretenberg/ecc/curves/bn254/fr.hpp"
#include "barretenberg/flavor/flavor.hpp"
#include "barretenberg/plonk/proof_system/proving_key/proving_key.hpp"
#include "barretenberg/polynomials/iterate_over_domain.hpp"
#include "barretenberg/polynomials/polynomial.hpp"
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <initializer_list>
#include <string>
#include <utility>
#include <vector>

Go to the source code of this file.

Classes
struct	proof_system::cycle_node
	cycle_node represents the index of a value of the circuit. It will belong to a CyclicPermutation, such that all nodes in a CyclicPermutation must have the value. The total number of constraints is always <2^32 since that is the type used to represent variables, so we can save space by using a type smaller than size_t. More...
struct	proof_system::permutation_subgroup_element
	Permutations subgroup element structure is used to hold data necessary to construct permutation polynomials. More...
struct	proof_system::PermutationMapping< NUM_WIRES >

Typedefs
using	proof_system::CyclicPermutation = std::vector< cycle_node >

Functions
void	proof_system::compute_standard_plonk_lagrange_polynomial (barretenberg::polynomial &output, const std::vector< permutation_subgroup_element > &permutation, const barretenberg::evaluation_domain &small_domain)
template<size_t program_width>
void	proof_system::compute_plonk_permutation_lagrange_polynomials_from_mapping (std::string label, std::array< std::vector< permutation_subgroup_element >, program_width > &mappings, plonk::proving_key *key)
	Compute lagrange polynomial from mapping (used for sigmas or ids)
template<size_t program_width>
void	proof_system::compute_monomial_and_coset_fft_polynomials_from_lagrange (std::string label, plonk::proving_key *key)
	Compute the monomial and coset-fft version of each lagrange polynomial of the given label.
template<typename Flavor >
void	proof_system::compute_standard_plonk_sigma_permutations (const typename Flavor::CircuitBuilder &circuit_constructor, typename Flavor::ProvingKey *key)
	Compute sigma permutation polynomials for standard plonk and put them in the polynomial cache.
template<typename Flavor >
void	proof_system::compute_first_and_last_lagrange_polynomials (const auto &proving_key)
	Compute Lagrange Polynomials L_0 and L_{n-1} and put them in the polynomial cache.
template<typename Flavor >
void	proof_system::compute_plonk_generalized_sigma_permutations (const typename Flavor::CircuitBuilder &circuit_constructor, typename Flavor::ProvingKey *key)
	Compute generalized permutation sigmas and ids for ultra plonk.
template<typename Flavor >
void	proof_system::compute_honk_generalized_sigma_permutations (const typename Flavor::CircuitBuilder &circuit_constructor, typename Flavor::ProvingKey *proving_key)
	Compute generalized permutation sigmas and ids for ultra plonk.

Detailed Description

Contains various functions that help construct Honk and Plonk Sigma and Id polynomials.

It is structured to reuse similar components in Honk and Plonk

Function Documentation

compute_first_and_last_lagrange_polynomials()

template<typename Flavor >

void proof_system::compute_first_and_last_lagrange_polynomials ( const auto &  proving_key )

inline

Compute Lagrange Polynomials L_0 and L_{n-1} and put them in the polynomial cache.

Parameters

key	Proving key where we will save the polynomials

compute_honk_generalized_sigma_permutations()

template<typename Flavor >

void proof_system::compute_honk_generalized_sigma_permutations	(	const typename Flavor::CircuitBuilder &	circuit_constructor,
		typename Flavor::ProvingKey *	proving_key
	)

Compute generalized permutation sigmas and ids for ultra plonk.

Template Parameters

program_width
CircuitBuilder

Parameters

circuit_constructor
proving_key

Returns

std::array<std::vector<permutation_subgroup_element>, program_width>

compute_monomial_and_coset_fft_polynomials_from_lagrange()

template<size_t program_width>

void proof_system::compute_monomial_and_coset_fft_polynomials_from_lagrange	(	std::string	label,
		plonk::proving_key *	key
	)

Compute the monomial and coset-fft version of each lagrange polynomial of the given label.

For Plonk we need the monomial and coset form of the polynomials, so we retrieve the lagrange form from polynomial cache, compute FFT versions and put them in the cache

Template Parameters

program_width

Number of wires

Parameters

key	Pointer to the proving key

compute_plonk_generalized_sigma_permutations()

template<typename Flavor >

void proof_system::compute_plonk_generalized_sigma_permutations	(	const typename Flavor::CircuitBuilder &	circuit_constructor,
		typename Flavor::ProvingKey *	key
	)

Compute generalized permutation sigmas and ids for ultra plonk.

Template Parameters

program_width
CircuitBuilder

Parameters

circuit_constructor
key

Returns

std::array<std::vector<permutation_subgroup_element>, program_width>

compute_plonk_permutation_lagrange_polynomials_from_mapping()

template<size_t program_width>

void proof_system::compute_plonk_permutation_lagrange_polynomials_from_mapping	(	std::string	label,
		std::array< std::vector< permutation_subgroup_element >, program_width > &	mappings,
		plonk::proving_key *	key
	)

Compute lagrange polynomial from mapping (used for sigmas or ids)

Template Parameters

program_width

Parameters

mappings
label
key

compute_standard_plonk_lagrange_polynomial()

void proof_system::compute_standard_plonk_lagrange_polynomial ( barretenberg::polynomial &  output, const std::vector< permutation_subgroup_element > &  permutation, const barretenberg::evaluation_domain &  small_domain  )

inline

Compute sigma permutation polynomial in lagrange base

Parameters

output	Output polynomial.
permuataion	Input permutation.
small_domain	The domain we base our polynomial in.

compute_standard_plonk_sigma_permutations()

template<typename Flavor >

void proof_system::compute_standard_plonk_sigma_permutations	(	const typename Flavor::CircuitBuilder &	circuit_constructor,
		typename Flavor::ProvingKey *	key
	)

Compute sigma permutation polynomials for standard plonk and put them in the polynomial cache.

Template Parameters

program_width	Number of wires
CircuitBuilder	Class holding the circuit

Parameters

circuit_constructor	An object holdingt he circuit
key	Pointer to a proving key