kzg

package
v0.7.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Oct 19, 2023 License: Apache-2.0 Imports: 9 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source
var (
	ErrInvalidNumDigests              = errors.New("number of digests is not the same as the number of polynomials")
	ErrInvalidPolynomialSize          = errors.New("invalid polynomial size (larger than SRS or == 0)")
	ErrVerifyOpeningProof             = errors.New("can't verify opening proof")
	ErrPolynomialMismatchedSizeDomain = errors.New("domain size does not equal the number of evaluations in the polynomial")
	ErrMinSRSSize                     = errors.New("minimum srs size is 2")
)

Functions

func BatchVerifyMultiPoints

func BatchVerifyMultiPoints(commitments []Commitment, proofs []OpeningProof, openKey *OpeningKey) error

BatchVerifyMultiPoints verifies multiple KZG proofs in a batch. See verify_kzg_proof_batch.

  • This method is more efficient than calling Verify multiple times.
  • Randomness is used to combine multiple proofs into one.

Modified from gnark-crypto.

func Verify

func Verify(commitment *Commitment, proof *OpeningProof, openKey *OpeningKey) error

Verify a single KZG proof. See verify_kzg_proof_impl. Returns `nil` if verification was successful, an error otherwise. If verification failed due to the pairings check it will return ErrVerifyOpeningProof.

Note: We could make this method faster by storing pre-computations for the generators in G1 and G2 as we only do scalar multiplications with those in this method.

Modified from gnark-crypto.

Types

type CommitKey

type CommitKey struct {
	// These are the G1 elements from the trusted setup.
	// In the specs this is denoted as `KZG_SETUP_G1` before
	// we processed it with `ifftG1`. Once we compute `ifftG1`
	// then this list is denoted as `KZG_SETUP_LAGRANGE` in the specs.
	G1 []bls12381.G1Affine
}

CommitKey holds the data needed to commit to polynomials and by proxy make opening proofs

func (*CommitKey) ReversePoints

func (c *CommitKey) ReversePoints()

ReversePoints applies the bit reversal permutation to the G1 points stored inside the CommitKey c.

type Commitment

type Commitment = bls12381.G1Affine

A commitment to a polynomial Excluding tests, this will be produced by committing to a polynomial in lagrange form

func Commit

func Commit(p Polynomial, ck *CommitKey, numGoRoutines int) (*Commitment, error)

Commit commits to a polynomial using a multi exponentiation with the Commitment key.

numGoRoutines is used to configure the amount of concurrency needed. Setting this value to a negative number or 0 will make it default to the number of CPUs.

type Domain

type Domain struct {
	// Size of the domain as a uint64. This must be a power of 2.
	// Since the base field has 2^i'th roots of unity for i<=32, Cardinality is <= 2^32)
	Cardinality uint64
	// Inverse of the size of the domain as
	// a field element. This is useful for
	// inverse FFTs.
	CardinalityInv fr.Element
	// Generator for the multiplicative subgroup
	// Not a primitive element (i.e. generator) for the *whole* field.
	//
	// This generator will have order equal to the
	// cardinality of the domain.
	Generator fr.Element
	// Inverse of the Generator. This is precomputed
	// and useful for inverse FFTs.
	GeneratorInv fr.Element

	// Roots of unity for the multiplicative subgroup
	// Note that these may or may not be in bit-reversed order.
	Roots []fr.Element

	// Precomputed inverses of the domain which
	// we will use to speed up the computation of
	// f(x)/g(x) where g(x) is a linear polynomial
	// which vanishes on a point on the domain
	PreComputedInverses []fr.Element
}

Domain is a struct defining the set of points that polynomials are evaluated over. To enable efficient FFT-based algorithms, these points are chosen as 2^i'th roots of unity and we precompute and store certain values related to that inside the struct.

func NewDomain

func NewDomain(x uint64) *Domain

NewDomain returns a new domain with the desired number of points x.

We only support powers of 2 for x.

Modified from gnark-crypto.

func (*Domain) EvaluateLagrangePolynomial

func (domain *Domain) EvaluateLagrangePolynomial(poly Polynomial, evalPoint fr.Element) (*fr.Element, error)

EvaluateLagrangePolynomial evaluates a Lagrange polynomial at the given point of evaluation.

The input polynomial is given in evaluation form, meaning a list of evaluations at the points in the domain. If len(poly) != domain.Cardinality, returns an error.

func (*Domain) FftG1

func (domain *Domain) FftG1(values []bls12381.G1Affine) []bls12381.G1Affine

Computes an FFT (Fast Fourier Transform) of the G1 elements.

The elements are returned in order as opposed to being returned in bit-reversed order.

func (*Domain) IfftG1

func (domain *Domain) IfftG1(values []bls12381.G1Affine) []bls12381.G1Affine

Computes an IFFT(Inverse Fast Fourier Transform) of the G1 elements.

The elements are returned in order as opposed to being returned in bit-reversed order.

func (*Domain) ReverseRoots

func (domain *Domain) ReverseRoots()

ReverseRoots applies the bit-reversal permutation to the list of precomputed roots of unity and their inverses in the domain.

type OpeningKey

type OpeningKey struct {
	// This is the degree-0 G_1 element in the trusted setup.
	// In the specs, this is denoted as `KZG_SETUP_G1[0]`
	GenG1 bls12381.G1Affine
	// This is the degree-0 G_2 element in the trusted setup.
	// In the specs, this is denoted as `KZG_SETUP_G2[0]`
	GenG2 bls12381.G2Affine
	// This is the degree-1 G_2 element in the trusted setup.
	// In the specs, this is denoted as `KZG_SETUP_G2[1]`
	AlphaG2 bls12381.G2Affine
}

OpeningKey is the key used to verify opening proofs

type OpeningProof

type OpeningProof struct {
	// Commitment to quotient polynomial (f(X) - f(z))/(X-z)
	QuotientCommitment bls12381.G1Affine

	// Point that we are evaluating the polynomial at : `z`
	InputPoint fr.Element

	// ClaimedValue purported value : `f(z)`
	ClaimedValue fr.Element
}

OpeningProof is a struct holding a (cryptographic) proof to the claim that a polynomial f(X) (represented by a commitment to it) evaluates at a point `z` to `f(z)`.

func Open

func Open(domain *Domain, p Polynomial, evaluationPoint fr.Element, ck *CommitKey, numGoRoutines int) (OpeningProof, error)

Open verifies that a polynomial f(x) when evaluated at a point `z` is equal to `f(z)`

numGoRoutines is used to configure the amount of concurrency needed. Setting this value to a negative number or 0 will make it default to the number of CPUs.

type Polynomial

type Polynomial = []fr.Element

A polynomial in lagrange form

type SRS

type SRS struct {
	CommitKey  CommitKey
	OpeningKey OpeningKey
}

SRS holds the structured reference string (SRS) for making and verifying KZG proofs

This codebase is only concerned with polynomials in Lagrange form, so we only expose methods to create the SRS in Lagrange form

The monomial SRS methods are solely used for testing.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL