kzg

package
v0.9.1 Latest Latest
Warning

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

 Go to latest Published: Oct 16, 2023 License: Apache-2.0 Imports: 18 Imported by: 4

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"
)

type KZGVerificationCircuit[S algebra.ScalarT, G1El algebra.G1ElementT, G2El algebra.G2ElementT, GTEl algebra.GtElementT] struct {
	kzg.VerifyingKey[G2El]
	kzg.Commitment[G1El]
	kzg.OpeningProof[S, G1El]
}

func (c *KZGVerificationCircuit[S, G1El, G2El, GTEl]) Define(api frontend.API) error {
	curve, err := algebra.GetCurve[S, G1El](api)
	if err != nil {
		return fmt.Errorf("get curve: %w", err)
	}
	pairing, err := algebra.GetPairing[G1El, G2El, GTEl](api)
	if err != nil {
		return fmt.Errorf("get pairing: %w", err)
	}
	verifier := kzg.NewVerifier(c.VerifyingKey, curve, pairing)
	if err := verifier.AssertProof(c.Commitment, c.OpeningProof); 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 and the evaluation point
	wProof, err := kzg.ValueOfOpeningProof[sw_bn254.Scalar, sw_bn254.G1Affine](point, proof)
	if err != nil {
		panic("opening proof witness failed: " + err.Error())
	}

	// create a witness element of the SRS
	wVk, err := kzg.ValueOfVerifyingKey[sw_bn254.G2Affine](srs.Vk)
	if err != nil {
		panic("verifying key witness failed: " + err.Error())
	}
	assignment := KZGVerificationCircuit[sw_bn254.Scalar, sw_bn254.G1Affine, sw_bn254.G2Affine, sw_bn254.GTEl]{
		VerifyingKey: wVk,
		Commitment:   wCmt,
		OpeningProof: wProof,
	}
	circuit := KZGVerificationCircuit[sw_bn254.Scalar, 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())
	}
	fmt.Println("done")
}

Output:

done
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 and the evaluation point
wProof, err := kzg.ValueOfOpeningProof[sw_bls12377.Scalar, sw_bls12377.G1Affine](point, proof)
if err != nil {
	panic("opening proof witness failed: " + err.Error())
}

// create a witness element of the SRS
wVk, err := kzg.ValueOfVerifyingKey[sw_bls12377.G2Affine](srs.Vk)
if err != nil {
	panic("verifying key witness failed: " + err.Error())
}
assignment := KZGVerificationCircuit[sw_bls12377.Scalar, sw_bls12377.G1Affine, sw_bls12377.G2Affine, sw_bls12377.GT]{
	VerifyingKey: wVk,
	Commitment:   wCmt,
	OpeningProof: wProof,
}
circuit := KZGVerificationCircuit[sw_bls12377.Scalar, 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())
}
fmt.Println("done")

Output:

done

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

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[S algebra.ScalarT, G1El algebra.G1ElementT] struct {
	QuotientPoly G1El
	ClaimedValue S
	Point        S
}

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[S algebra.ScalarT, G1El algebra.G1ElementT](point any, proof any) (OpeningProof[S, 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[S algebra.ScalarT, G1El algebra.G1ElementT, G2El algebra.G2ElementT, GtEl algebra.G2ElementT] struct {
	VerifyingKey[G2El]
	// contains filtered or unexported fields
}

Verifier allows verifying KZG opening proofs.

func NewVerifier 

func NewVerifier[S algebra.ScalarT, G1El algebra.G1ElementT, G2El algebra.G2ElementT, GtEl algebra.G2ElementT](vk VerifyingKey[G2El], curve algebra.Curve[S, G1El], pairing algebra.Pairing[G1El, G2El, GtEl]) *Verifier[S, G1El, G2El, GtEl]

NewVerifier initializes a new Verifier instance.

func (*Verifier[S, G1El, G2El, GtEl]) AssertProof 

func (vk *Verifier[S, G1El, G2El, GtEl]) AssertProof(commitment Commitment[G1El], proof OpeningProof[S, G1El]) error

AssertProof asserts the validity of the opening proof for the given commitment.

type VerifyingKey 

type VerifyingKey[G2El algebra.G2ElementT] struct {
	SRS [2]G2El
}

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

func ValueOfVerifyingKey 

func ValueOfVerifyingKey[G2El algebra.G2ElementT](vk any) (VerifyingKey[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.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.