proof_system::honk::pcs::gemini Namespace Reference

Protocol for opening several multi-linear polynomials at the same point. More...

Classes
class	GeminiProver_
class	GeminiTest
class	GeminiVerifier_
struct	ProverOutput
	Prover output (evalutation pair, witness) that can be passed on to Shplonk batch opening. More...

Typedefs
using	ParamsTypes = ::testing::Types< curve::BN254, curve::Grumpkin >

Functions
template<class Fr >
std::vector< Fr >	powers_of_rho (const Fr rho, const size_t num_powers)
	Compute powers of challenge ρ
template<class Fr >
std::vector< Fr >	squares_of_r (const Fr r, const size_t num_squares)
	Compute squares of folding challenge r.
	TYPED_TEST_SUITE (GeminiTest, ParamsTypes)
	TYPED_TEST (GeminiTest, Single)
	TYPED_TEST (GeminiTest, SingleShift)
	TYPED_TEST (GeminiTest, Double)
	TYPED_TEST (GeminiTest, DoubleWithShift)

Detailed Description

Protocol for opening several multi-linear polynomials at the same point.

m = number of variables n = 2ᵐ u = (u₀,...,uₘ₋₁) f₀, …, fₖ₋₁ = multilinear polynomials, g₀, …, gₕ₋₁ = shifted multilinear polynomial, Each gⱼ is the left-shift of some f↺ᵢ, and gⱼ points to the same memory location as fᵢ. v₀, …, vₖ₋₁, v↺₀, …, v↺ₕ₋₁ = multilinear evalutions s.t. fⱼ(u) = vⱼ, and gⱼ(u) = f↺ⱼ(u) = v↺ⱼ

We use a challenge ρ to create a random linear combination of all fⱼ, and actually define A₀ = F + G↺, where F = ∑ⱼ ρʲ fⱼ G = ∑ⱼ ρᵏ⁺ʲ gⱼ, G↺ = is the shift of G where fⱼ is normal, and gⱼ is shifted. The evaluations are also batched, and v = ∑ ρʲ⋅vⱼ + ∑ ρᵏ⁺ʲ⋅v↺ⱼ = F(u) + G↺(u)

The prover then creates the folded polynomials A₀, ..., Aₘ₋₁, and opens them at different points, as univariates.

We open A₀ as univariate at r and -r. Since A₀ = F + G↺, but the verifier only has commitments to the gⱼs, we need to partially evaluate A₀ at both evaluation points. As univariate, we have A₀(X) = F(X) + G↺(X) = F(X) + G(X)/X So we define

• A₀₊(X) = F(X) + G(X)/r
• A₀₋(X) = F(X) − G(X)/r So that A₀₊(r) = A₀(r) and A₀₋(-r) = A₀(-r). The verifier is able to computed the simulated commitments to A₀₊(X) and A₀₋(X) since they are linear-combinations of the commitments [fⱼ] and [gⱼ].

Function Documentation

powers_of_rho()

template<class Fr >

std::vector< Fr > proof_system::honk::pcs::gemini::powers_of_rho ( const Fr  rho, const size_t  num_powers  )

inline

Compute powers of challenge ρ

Template Parameters

Fr

Parameters

rho
num_powers

Returns

std::vector<Fr>

squares_of_r()

template<class Fr >

std::vector< Fr > proof_system::honk::pcs::gemini::squares_of_r ( const Fr  r, const size_t  num_squares  )

inline

Compute squares of folding challenge r.

Parameters

r
num_squares	The number of foldings

Returns

std::vector<typename Curve::ScalarField>