kzg

package
v0.2.9 Latest Latest
Warning

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

Go to latest
Published: Feb 6, 2024 License: Apache-2.0 Imports: 27 Imported by: 0

Documentation

Overview

Package kzg implements KZG polynomial commitment verification.

KZG polynomial commitment allows for the prover to commit to a polynomial and then selectively prove evaluations of the said polynomial. The size of the commitment is a single G1 element and the size of the evaluation proof is also a single G1 element. However, KZG polynomial commitment scheme requires a trusted SRS.

This package supersedes previous type-specific implementations and allows to use any implemented pairing-friendly curve implementation, being defined over a 2-chain (native implementation) or using field emulation.

Example (Emulated)

Example of using KZG verifier using emulated pairing implementation.

package main

import (
	"crypto/rand"
	"fmt"

	"github.com/consensys/gnark-crypto/ecc"
	fr_bn254 "github.com/consensys/gnark-crypto/ecc/bn254/fr"
	kzg_bn254 "github.com/consensys/gnark-crypto/ecc/bn254/kzg"
	"github.com/consensys/gnark/backend/groth16"
	"github.com/consensys/gnark/frontend"
	"github.com/consensys/gnark/frontend/cs/r1cs"
	"github.com/consensys/gnark/std/algebra"
	"github.com/consensys/gnark/std/algebra/emulated/sw_bn254"
	"github.com/consensys/gnark/std/commitments/kzg"
	"github.com/consensys/gnark/std/math/emulated"
)

type KZGVerificationCircuit[FR emulated.FieldParams, G1El algebra.G1ElementT, G2El algebra.G2ElementT, GTEl algebra.GtElementT] struct {
	kzg.VerifyingKey[G1El, G2El]
	kzg.Commitment[G1El]
	kzg.OpeningProof[FR, G1El]
	Point emulated.Element[FR]
}

func (c *KZGVerificationCircuit[FR, G1El, G2El, GTEl]) Define(api frontend.API) error {
	verifier, err := kzg.NewVerifier[FR, G1El, G2El, GTEl](api)
	if err != nil {
		return fmt.Errorf("new verifier: %w", err)
	}
	if err := verifier.CheckOpeningProof(c.Commitment, c.OpeningProof, c.Point, c.VerifyingKey); err != nil {
		return fmt.Errorf("assert proof: %w", err)
	}
	return nil
}

// Example of using KZG verifier using emulated pairing implementation.
func main() {
	// !!! UNSAFE SRS. FOR EXAMPLE PURPOSES ONLY. We create a trusted SRS for
	// KZG polynomial commitment scheme. In practice this must be prepared using
	// MPC or by reusing existing SRS. !!!

	const (
		// size of the SRS. Defines the maximum degree of the polynomial which can be committed to
		kzgSize = 128
		// degree of the random polynomial in the example
		polynomialSize = 100
	)

	// create new SRS for example purposes (NB! UNSAFE!)
	alpha, err := rand.Int(rand.Reader, ecc.BN254.ScalarField())
	if err != nil {
		panic("sampling alpha failed: " + err.Error())
	}
	srs, err := kzg_bn254.NewSRS(kzgSize, alpha) // UNSAFE!
	if err != nil {
		panic("new SRS failed: " + err.Error())
	}

	// sample the random polynomial by sampling the coefficients.
	f := make([]fr_bn254.Element, polynomialSize)
	for i := range f {
		f[i].SetRandom()
	}

	// natively commit to the polynomial using SRS
	com, err := kzg_bn254.Commit(f, srs.Pk)
	if err != nil {
		panic("commitment failed: " + err.Error())
	}

	// sample random evaluation point
	var point fr_bn254.Element
	point.SetRandom()

	// construct a proof of correct opening. The evaluation value is proof.ClaimedValue
	proof, err := kzg_bn254.Open(f, point, srs.Pk)
	if err != nil {
		panic("test opening failed: " + err.Error())
	}

	// test opening proof natively
	if err = kzg_bn254.Verify(&com, &proof, point, srs.Vk); err != nil {
		panic("test verify failed: " + err.Error())
	}

	// create a witness element of the commitment
	wCmt, err := kzg.ValueOfCommitment[sw_bn254.G1Affine](com)
	if err != nil {
		panic("commitment witness failed: " + err.Error())
	}

	// create a witness element of the opening proof
	wProof, err := kzg.ValueOfOpeningProof[sw_bn254.ScalarField, sw_bn254.G1Affine](proof)
	if err != nil {
		panic("opening proof witness failed: " + err.Error())
	}

	// create a witness element of the SRS
	wVk, err := kzg.ValueOfVerifyingKey[sw_bn254.G1Affine, sw_bn254.G2Affine](srs.Vk)
	if err != nil {
		panic("verifying key witness failed: " + err.Error())
	}

	// create a witness element of the evaluation point
	wPt, err := kzg.ValueOfScalar[sw_bn254.ScalarField](point)
	if err != nil {
		panic("point witness failed: " + err.Error())
	}

	assignment := KZGVerificationCircuit[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl]{
		VerifyingKey: wVk,
		Commitment:   wCmt,
		OpeningProof: wProof,
		Point:        wPt,
	}
	circuit := KZGVerificationCircuit[sw_bn254.ScalarField, sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl]{}

	// as we are currently using the emulated implementation of BN254
	// in-circuit, then we can compile to any curve. For example purposes, here
	// we use BN254.
	ccs, err := frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, &circuit)
	if err != nil {
		panic("compile failed: " + err.Error())
	}

	// create Groth16 setup. NB! UNSAFE
	pk, vk, err := groth16.Setup(ccs) // UNSAFE! Use MPC
	if err != nil {
		panic("setup failed: " + err.Error())
	}

	// create prover witness from the assignment
	secretWitness, err := frontend.NewWitness(&assignment, ecc.BN254.ScalarField())
	if err != nil {
		panic("secret witness failed: " + err.Error())
	}

	// create public witness from the assignment
	publicWitness, err := secretWitness.Public()
	if err != nil {
		panic("public witness failed: " + err.Error())
	}

	// construct the groth16 proof of verifying KZG commitment opening in-circuit
	circuitProof, err := groth16.Prove(ccs, pk, secretWitness)
	if err != nil {
		panic("proving failed: " + err.Error())
	}

	// verify the Groth16 proof
	err = groth16.Verify(circuitProof, vk, publicWitness)
	if err != nil {
		panic("circuit verification failed: " + err.Error())
	}
}
Output:

Example (Native)

Example of using KZG verifier using 2-chains of curves. It is significantly more efficient than using field emulation, but requires a specific chain of inner and outer curves.

// !!! UNSAFE SRS. FOR EXAMPLE PURPOSES ONLY. We create a trusted SRS for
// KZG polynomial commitment scheme. In practice this must be prepared using
// MPC or by reusing existing SRS. !!!

const (
	// size of the SRS. Defines the maximum degree of the polynomial which can be committed to
	kzgSize = 128
	// degree of the random polynomial in the example
	polynomialSize = 100
)

// create new SRS for example purposes (NB! UNSAFE!)
alpha, err := rand.Int(rand.Reader, ecc.BLS12_377.ScalarField())
if err != nil {
	panic("sampling alpha failed: " + err.Error())
}
srs, err := kzg_bls12377.NewSRS(kzgSize, alpha) // UNSAFE!
if err != nil {
	panic("new SRS failed: " + err.Error())
}

// sample the random polynomial by sampling the coefficients.
f := make([]fr_bls12377.Element, polynomialSize)
for i := range f {
	f[i].SetRandom()
}

// natively commit to the polynomial using SRS
com, err := kzg_bls12377.Commit(f, srs.Pk)
if err != nil {
	panic("commitment failed: " + err.Error())
}

// sample random evaluation point
var point fr_bls12377.Element
point.SetRandom()

// construct a proof of correct opening. The evaluation value is proof.ClaimedValue
proof, err := kzg_bls12377.Open(f, point, srs.Pk)
if err != nil {
	panic("test opening failed: " + err.Error())
}

// test opening proof natively
if err = kzg_bls12377.Verify(&com, &proof, point, srs.Vk); err != nil {
	panic("test verify failed: " + err.Error())
}

// create a witness element of the commitment
wCmt, err := kzg.ValueOfCommitment[sw_bls12377.G1Affine](com)
if err != nil {
	panic("commitment witness failed: " + err.Error())
}

// create a witness element of the opening proof
wProof, err := kzg.ValueOfOpeningProof[sw_bls12377.ScalarField, sw_bls12377.G1Affine](proof)
if err != nil {
	panic("opening proof witness failed: " + err.Error())
}

// create a witness element of the SRS
wVk, err := kzg.ValueOfVerifyingKey[sw_bls12377.G1Affine, sw_bls12377.G2Affine](srs.Vk)
if err != nil {
	panic("verifying key witness failed: " + err.Error())
}

// create a witness element of the evaluation point
wPt, err := kzg.ValueOfScalar[sw_bls12377.ScalarField](point)
if err != nil {
	panic("point witness failed: " + err.Error())
}

assignment := KZGVerificationCircuit[sw_bls12377.ScalarField, sw_bls12377.G1Affine, sw_bls12377.G2Affine, sw_bls12377.GT]{
	VerifyingKey: wVk,
	Commitment:   wCmt,
	OpeningProof: wProof,
	Point:        wPt,
}
circuit := KZGVerificationCircuit[sw_bls12377.ScalarField, sw_bls12377.G1Affine, sw_bls12377.G2Affine, sw_bls12377.GT]{}

// because we are using 2-chains then the outer curve must correspond to the
// inner curve. For inner BLS12-377 the outer curve is BW6-761.
ccs, err := frontend.Compile(ecc.BW6_761.ScalarField(), r1cs.NewBuilder, &circuit)
if err != nil {
	panic("compile failed: " + err.Error())
}

// create Groth16 setup. NB! UNSAFE
pk, vk, err := groth16.Setup(ccs) // UNSAFE! Use MPC
if err != nil {
	panic("setup failed: " + err.Error())
}

// create prover witness from the assignment
secretWitness, err := frontend.NewWitness(&assignment, ecc.BW6_761.ScalarField())
if err != nil {
	panic("secret witness failed: " + err.Error())
}

// create public witness from the assignment
publicWitness, err := secretWitness.Public()
if err != nil {
	panic("public witness failed: " + err.Error())
}

// construct the groth16 proof of verifying KZG commitment opening in-circuit
circuitProof, err := groth16.Prove(ccs, pk, secretWitness)
if err != nil {
	panic("proving failed: " + err.Error())
}

// verify the Groth16 proof
err = groth16.Verify(circuitProof, vk, publicWitness)
if err != nil {
	panic("circuit verification failed: " + err.Error())
}
Output:

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func ValueOfScalar

func ValueOfScalar[FR emulated.FieldParams](scalar any) (emulated.Element[FR], error)

ValueOfScalar initializes a scalar in a witness from a native scalar (Fr) point. The scalars are always emulated.

Types

type BatchOpeningProof

type BatchOpeningProof[FR emulated.FieldParams, G1El algebra.G1ElementT] struct {
	Quotient      G1El
	ClaimedValues []emulated.Element[FR]
}

func ValueOfBatchOpeningProof

func ValueOfBatchOpeningProof[FR emulated.FieldParams, G1El any](proof any) (BatchOpeningProof[FR, G1El], error)

type Commitment

type Commitment[G1El algebra.G1ElementT] struct {
	G1El G1El
}

Commitment is an KZG commitment to a polynomial. Use ValueOfCommitment to initialize a witness from the native commitment.

func ValueOfCommitment

func ValueOfCommitment[G1El algebra.G1ElementT](cmt any) (Commitment[G1El], error)

ValueOfCommitment initializes a KZG commitment witness from a native commitment. It returns an error if there is a conflict between the type parameters and provided native commitment type.

type OpeningProof

type OpeningProof[FR emulated.FieldParams, G1El algebra.G1ElementT] struct {
	Quotient     G1El
	ClaimedValue emulated.Element[FR]
}

OpeningProof embeds the opening proof that polynomial evaluated at Point is equal to ClaimedValue. Use ValueOfOpeningProof to initialize a witness from a native opening proof.

func ValueOfOpeningProof

func ValueOfOpeningProof[FR emulated.FieldParams, G1El algebra.G1ElementT](proof any) (OpeningProof[FR, G1El], error)

ValueOfOpeningProof initializes an opening proof from the given proof and point. It returns an error if there is a mismatch between the type parameters and types of the provided point and proof.

type Verifier

type Verifier[FR emulated.FieldParams, G1El algebra.G1ElementT, G2El algebra.G2ElementT, GtEl algebra.G2ElementT] struct {
	// contains filtered or unexported fields
}

Verifier allows verifying KZG opening proofs.

func NewVerifier

func NewVerifier[FR emulated.FieldParams, G1El algebra.G1ElementT, G2El algebra.G2ElementT, GtEl algebra.G2ElementT](api frontend.API) (*Verifier[FR, G1El, G2El, GtEl], error)

NewVerifier initializes a new Verifier instance.

func (*Verifier[FR, G1El, G2El, GTEl]) BatchVerifyMultiPoints

func (v *Verifier[FR, G1El, G2El, GTEl]) BatchVerifyMultiPoints(digests []Commitment[G1El], proofs []OpeningProof[FR, G1El], points []emulated.Element[FR], vk VerifyingKey[G1El, G2El]) error

BatchVerifyMultiPoints verifies multiple opening proofs at different points.

func (*Verifier[FR, G1El, G2El, GTEl]) BatchVerifySinglePoint

func (v *Verifier[FR, G1El, G2El, GTEl]) BatchVerifySinglePoint(digests []Commitment[G1El], batchOpeningProof BatchOpeningProof[FR, G1El], point emulated.Element[FR], vk VerifyingKey[G1El, G2El], dataTranscript ...emulated.Element[FR]) error

BatchVerifySinglePoint verifies multiple opening proofs at a single point.

func (*Verifier[FR, G1El, G2El, GTEl]) CheckOpeningProof

func (v *Verifier[FR, G1El, G2El, GTEl]) CheckOpeningProof(commitment Commitment[G1El], proof OpeningProof[FR, G1El], point emulated.Element[FR], vk VerifyingKey[G1El, G2El]) error

CheckOpeningProof asserts the validity of the opening proof for the given commitment at point.

func (*Verifier[FR, G1El, G2El, GTEl]) FoldProof

func (v *Verifier[FR, G1El, G2El, GTEl]) FoldProof(digests []Commitment[G1El], batchOpeningProof BatchOpeningProof[FR, G1El], point emulated.Element[FR], dataTranscript ...emulated.Element[FR]) (OpeningProof[FR, G1El], Commitment[G1El], error)

FoldProof folds multiple commitments and a batch opening proof for a single opening check.

func (*Verifier[FR, G1El, G2El, GTEl]) FoldProofsMultiPoint

func (v *Verifier[FR, G1El, G2El, GTEl]) FoldProofsMultiPoint(digests []Commitment[G1El], proofs []OpeningProof[FR, G1El], points []emulated.Element[FR], vk VerifyingKey[G1El, G2El]) (*G1El, *G1El, error)

FoldProofsMultiPoint folds multiple proofs with openings at multiple points. Used for batch verification of different opening proofs. See also Verifier.BatchVerifyMultiPoints.

type VerifyingKey

type VerifyingKey[G1El algebra.G1ElementT, G2El algebra.G2ElementT] struct {
	G2 [2]G2El
	G1 G1El
}

VerifyingKey is the trusted setup for KZG polynomial commitment scheme. Use ValueOfVerifyingKey to initialize a witness from the native VerifyingKey.

func PlaceholderVerifyingKey

func PlaceholderVerifyingKey[G1El algebra.G1ElementT, G2El algebra.G2ElementT]() VerifyingKey[G1El, G2El]

PlaceholderVerifyingKey returns a placeholder value for the verifying key for compiling if the witness is going to be in precomputed form using ValueOfVerifyingKeyFixed.

func ValueOfVerifyingKey

func ValueOfVerifyingKey[G1El algebra.G1ElementT, G2El algebra.G2ElementT](vk any) (VerifyingKey[G1El, G2El], error)

ValueOfVerifyingKey initializes verifying key witness from the native verifying key. It returns an error if there is a mismatch between the type parameters and the provided verifying key type.

func ValueOfVerifyingKeyFixed

func ValueOfVerifyingKeyFixed[G1El algebra.G1ElementT, G2El algebra.G2ElementT](vk any) (VerifyingKey[G1El, G2El], error)

ValueOfVerifyingKeyFixed initializes verifying key witness from the native verifying key and perform pre-computations for G2 elements. It returns an error if there is a mismatch between the type parameters and the provided verifying key type. Such witness is significantly larger than without precomputations. If witness size is important, then use ValueOfVerifyingKey instead.

Jump to

Keyboard shortcuts

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