sumcheck

Documentation

Overview

Package sumcheck implements non-native sumcheck verifier.

Sumcheck protocol is an interactive protocol between the prover and verifier to prove the evaluation

H = ∑_{x_j ∈ {0,1}, 1 ≤ j ≤ n} g((x_j)_{1 ≤ j ≤ n})

for a multivariate function g: 𝔽ⁿ -> 𝔽.

The sumcheck protocol runs in rounds, where first the prover sends the claimed value H, then the verifier sends in every round i random challenge r_i for which the prover responds with the univariate polynomial g_i(X)

g_i(X) = ∑_{x_j ∈ {0,1}, j ≥ i+1} g((r_j)_{j < i}, X, (x_j)_{j ≥ i+1}).

The verifier checks that gᵢ(r_i) = gᵢ₊₁(0) + gᵢ₊₁(1) for every round. After the last round the verifier has to evaluate g((r_j){1 ≤ j ≤ n}) on its own.

To allow for incorporating the sumcheck protocol inside a larger GKR protocol, parallel verification and different types of function g, the protocol instead defines LazyClaims interface which defines the aspects of the claimable function:

• the number of parallel proofs being verified (method [LazyClaims.NbClaims]) and the combined folded evaluation (method [LazyClaims.CominedSum]).
• the number of variables the function takes (method [LazyClaims.NbVars])
• the degree of the univariate polynomial for the i-th variable (method [LazyClaims.Degree])
• how to perform the final evaluation of the function (method [LazyClaims.AssertEvaluation]):
• the claim can directly evaluate the function itself (plain sumcheck),
• the evaluation is deferred as an input to another sumcheck protocol run (as in GKR),
• by opening a multivariate polynomial opening by letting prover to provide the opening proof.

The package is still work in progress. We do not yet expose prover for creating the sumcheck proofs but aim to integrate the proof creation to be automatic given the specific claim type.

Index

• type EvaluationProof
• type LazyClaims
• type Option
  • func WithClaimPrefix(prefix string) Option
• type Proof
• type Verifier
  • func NewVerifier[FR emulated.FieldParams](api frontend.API, opts ...Option) (*Verifier[FR], error)
  • func (v *Verifier[FR]) Verify(claims LazyClaims[FR], proof Proof[FR], opts ...VerifyOption[FR]) error
• type VerifyOption
  • func WithBaseChallenges[FR emulated.FieldParams](baseChallenges []*emulated.Element[FR]) VerifyOption[FR]

Types

type EvaluationProof

type EvaluationProof any

EvaluationProof is proof for allowing the sumcheck verifier to perform the final evaluation needed to complete the check. It is untyped as it depends how the final evaluation is implemented:

• if sumcheck verifier directly evaluates the function, then it is nil,
• if it is multivariate polynomial opening proof, then it is the opening value,
• if it is deferred, then it is a slice.

type LazyClaims

type LazyClaims[FR emulated.FieldParams] interface {
	// NbClaims is the number of parallel sumcheck proofs. If larger than one then sumcheck verifier computes a challenge for combining the claims.
	NbClaims() int
	// NbVars is the number of variables for the evaluatable function. Defines the number of rounds in the sumcheck protocol.
	NbVars() int
	// CombinedSum returns the folded claim for parallel verification.
	CombinedSum(coeff *emulated.Element[FR]) *emulated.Element[FR]
	// Degree returns the maximum degree of the variable i-th variable.
	Degree(i int) int
	// AssertEvaluation (lazily) asserts the correctness of the evaluation value expectedValue of the claim at r.
	AssertEvaluation(r []*emulated.Element[FR], combinationCoeff, expectedValue *emulated.Element[FR], proof EvaluationProof) error
}

LazyClaims allows to verify the sumcheck proof by allowing different final evaluations.

type Option

type Option func(c *config) error

Option allows to alter the sumcheck verifier behaviour.

func WithClaimPrefix

func WithClaimPrefix(prefix string) Option

WithClaimPrefix prepends the given string to the challenge names when computing the challenges inside the sumcheck verifier. The option is used in a higher level protocols to ensure that sumcheck claims are not interchanged.

type Proof

type Proof[FR emulated.FieldParams] struct {
	// RoundPolyEvaluations is polynomial representation in evaluation form
	RoundPolyEvaluations []polynomial.Univariate[FR]
	// FinalEvalProof is the witness for helping the verifier to compute the
	// final round of the sumcheck protocol.
	FinalEvalProof EvaluationProof
}

Proof contains the prover messages in the sumcheck protocol.

type Verifier

type Verifier[FR emulated.FieldParams] struct {
	// contains filtered or unexported fields
}

Verifier allows to check sumcheck proofs. See NewVerifier for initializing the instance.

func NewVerifier

func NewVerifier[FR emulated.FieldParams](api frontend.API, opts ...Option) (*Verifier[FR], error)

NewVerifier initializes a new sumcheck verifier for the parametric emulated field FR. It returns an error if the given options are invalid or when initializing emulated arithmetic fails.

func (*Verifier[FR]) Verify

func (v *Verifier[FR]) Verify(claims LazyClaims[FR], proof Proof[FR], opts ...VerifyOption[FR]) error

Verify verifies the sumcheck proof for the given (lazy) claims.

type VerifyOption

type VerifyOption[FR emulated.FieldParams] func(c *verifyCfg[FR]) error

VerifyOption allows to alter the behaviour of the single sumcheck proof verification.

func WithBaseChallenges

func WithBaseChallenges[FR emulated.FieldParams](baseChallenges []*emulated.Element[FR]) VerifyOption[FR]

WithBaseChallenges allows to bind to additional baseChallenges (in addition to the current sumcheck protocol transcript) when computing the challenges.