kzg

README

kzg-commitments-study

Doing this to study and learn KZG commitments, do not use in production. More details at https://arnaucube.com/blog/kzg-commitments.html .

Thanks to Dankrad Feist, Alin Tomescu, Tom Walton-Pocock for their articles, which helped me understand a bit the KZG Commitments.

It uses the ethereum bn256.

Usage

// p(x) = x^3 + x + 5
p := []*big.Int{
	big.NewInt(5),
	big.NewInt(1), // x^1
	big.NewInt(0), // x^2
	big.NewInt(1), // x^3
}
assert.Equal(t, "1x³ + 1x¹ + 5", PolynomialToString(p))

// TrustedSetup
ts, err := NewTrustedSetup(p)
assert.Nil(t, err)

// Commit
c := Commit(ts, p)

// p(z)=y --> p(3)=35
z := big.NewInt(3)
y := big.NewInt(35)

// z & y: to prove an evaluation p(z)=y
proof, err := EvaluationProof(ts, p, z, y)
assert.Nil(t, err)

// verification
v := Verify(ts, c, proof, z, y)
assert.True(t, v)

Batch Proofs:

// zs & ys contain the f(z_i)=y_i values that will be proved inside a batch proof
zs := []*big.Int{z0, z1, z2}
ys := []*big.Int{y0, y1, y2}

// prove an evaluation of the multiple z_i & y_i
proof, err := EvaluationBatchProof(ts, p, zs, ys)
assert.Nil(t, err)

// batch proof verification
v := VerifyBatchProof(ts, c, proof, zs, ys)
assert.True(t, v)

Documentation

Index

• Variables
• func Commit(ts *TrustedSetup, p []*big.Int) *bn256.G1
• func EvaluationBatchProof(ts *TrustedSetup, p []*big.Int, zs, ys []*big.Int) (*bn256.G1, error)
• func EvaluationProof(ts *TrustedSetup, p []*big.Int, z, y *big.Int) (*bn256.G1, error)
• func LagrangeInterpolation(x, y []*big.Int) ([]*big.Int, error)
• func PolynomialToString(p []*big.Int) string
• func Verify(ts *TrustedSetup, c, proof *bn256.G1, z, y *big.Int) bool
• func VerifyBatchProof(ts *TrustedSetup, c, proof *bn256.G1, zs, ys []*big.Int) bool
• type TrustedSetup
  • func NewTrustedSetup(l int) (*TrustedSetup, error)

Variables

var Q, _ = new(big.Int).SetString(
	"21888242871839275222246405745257275088696311157297823662689037894645226208583", 10)

Q is the order of the integer field (Zq) that fits inside the snark

var R, _ = new(big.Int).SetString(
	"21888242871839275222246405745257275088548364400416034343698204186575808495617", 10)

R is the mod of the finite field

Functions

func Commit

func Commit(ts *TrustedSetup, p []*big.Int) *bn256.G1

Commit generates the commitment to the polynomial p(x)

func EvaluationBatchProof

func EvaluationBatchProof(ts *TrustedSetup, p []*big.Int, zs, ys []*big.Int) (*bn256.G1, error)

EvaluationBatchProof generates the evalutation proof for the given list of points

func EvaluationProof

func EvaluationProof(ts *TrustedSetup, p []*big.Int, z, y *big.Int) (*bn256.G1, error)

EvaluationProof generates the evaluation proof

func LagrangeInterpolation

func LagrangeInterpolation(x, y []*big.Int) ([]*big.Int, error)

LagrangeInterpolation implements the Lagrange interpolation: https://en.wikipedia.org/wiki/Lagrange_polynomial

func PolynomialToString

func PolynomialToString(p []*big.Int) string

PolynomialToString converts a polynomial represented by a *big.Int array, into its string human readable representation

func Verify

func Verify(ts *TrustedSetup, c, proof *bn256.G1, z, y *big.Int) bool

Verify computes the KZG commitment verification

func VerifyBatchProof

func VerifyBatchProof(ts *TrustedSetup, c, proof *bn256.G1, zs, ys []*big.Int) bool

VerifyBatchProof computes the KZG batch proof commitment verification

Types

type TrustedSetup

type TrustedSetup struct {
	Tau1 []*bn256.G1
	Tau2 []*bn256.G2
}

TrustedSetup also named Reference String

func NewTrustedSetup

func NewTrustedSetup(l int) (*TrustedSetup, error)

NewTrustedSetup returns a new trusted setup. This step should be done in a secure & distributed way