1package kzg
  2
  3import (
  4	"fmt"
  5	"math/big"
  6
  7	bn256 "github.com/ethereum/go-ethereum/crypto/bn256/cloudflare"
  8)
  9
 10// TrustedSetup also named Reference String
 11type TrustedSetup struct {
 12	Tau1 []*bn256.G1
 13	Tau2 []*bn256.G2
 14}
 15
 16// NewTrustedSetup returns a new trusted setup. This step should be done in a
 17// secure & distributed way
 18func NewTrustedSetup(l int) (*TrustedSetup, error) {
 19	// compute random s
 20	s, err := randBigInt()
 21	if err != nil {
 22		return nil, err
 23	}
 24
 25	// Notation: [x]₁=xG ∈ 𝔾₁, [x]₂=xH ∈ 𝔾₂
 26	// τ₁: [x₀]₁, [x₁]₁, [x₂]₁, ..., [x n₋₁]₁
 27	// τ₂: [x₀]₂, [x₁]₂, [x₂]₂, ..., [x n₋₁]₂
 28
 29	// sPow := make([]*big.Int, l)
 30	tauG1 := make([]*bn256.G1, l)
 31	tauG2 := make([]*bn256.G2, l)
 32	for i := 0; i < l; i++ {
 33		sPow := fExp(s, big.NewInt(int64(i)))
 34		tauG1[i] = new(bn256.G1).ScalarBaseMult(sPow)
 35		tauG2[i] = new(bn256.G2).ScalarBaseMult(sPow)
 36	}
 37
 38	return &TrustedSetup{tauG1, tauG2}, nil
 39}
 40
 41// Commit generates the commitment to the polynomial p(x)
 42func Commit(ts *TrustedSetup, p []*big.Int) *bn256.G1 {
 43	c := evaluateG1(ts, p)
 44	return c
 45}
 46
 47func evaluateG1(ts *TrustedSetup, p []*big.Int) *bn256.G1 {
 48	c := new(bn256.G1).ScalarMult(ts.Tau1[0], p[0])
 49	for i := 1; i < len(p); i++ {
 50		sp := new(bn256.G1).ScalarMult(ts.Tau1[i], p[i])
 51		c = new(bn256.G1).Add(c, sp)
 52	}
 53	return c
 54}
 55
 56//nolint:deadcode,unused
 57func evaluateG2(ts *TrustedSetup, p []*big.Int) *bn256.G2 {
 58	c := new(bn256.G2).ScalarMult(ts.Tau2[0], p[0])
 59	for i := 1; i < len(p); i++ {
 60		sp := new(bn256.G2).ScalarMult(ts.Tau2[i], p[i])
 61		c = new(bn256.G2).Add(c, sp)
 62	}
 63	return c
 64}
 65
 66// EvaluationProof generates the evaluation proof
 67func EvaluationProof(ts *TrustedSetup, p []*big.Int, z, y *big.Int) (*bn256.G1, error) {
 68	n := polynomialSub(p, []*big.Int{y}) // p-y
 69	// n := p // we can omit y (p(z))
 70	d := []*big.Int{fNeg(z), big.NewInt(1)} // x-z
 71	q, rem := polynomialDiv(n, d)
 72	if compareBigIntArray(rem, arrayOfZeroes(len(rem))) {
 73		return nil,
 74			fmt.Errorf("remainder should be 0, instead is %d", rem)
 75	}
 76
 77	// proof: e = [q(t)]₁
 78	e := evaluateG1(ts, q)
 79	return e, nil
 80}
 81
 82// Verify computes the KZG commitment verification
 83func Verify(ts *TrustedSetup, c, proof *bn256.G1, z, y *big.Int) bool {
 84	s2 := ts.Tau2[1] // [t]₂ = sG ∈ 𝔾₂ = Tau2[1]
 85	zG2Neg := new(bn256.G2).Neg(
 86		new(bn256.G2).ScalarBaseMult(z)) // [z]₂ = zG ∈ 𝔾₂
 87	// [t]₂ - [z]₂
 88	sz := new(bn256.G2).Add(s2, zG2Neg)
 89
 90	yG1Neg := new(bn256.G1).Neg(
 91		new(bn256.G1).ScalarBaseMult(y)) // [y]₁ = yG ∈ 𝔾₁
 92	// c - [y]₁
 93	cy := new(bn256.G1).Add(c, yG1Neg)
 94
 95	h := new(bn256.G2).ScalarBaseMult(big.NewInt(1)) // H ∈ 𝔾₂
 96
 97	// e(proof, [t]₂ - [z]₂) == e(c - [y]₁, H)
 98	e1 := bn256.Pair(proof, sz)
 99	e2 := bn256.Pair(cy, h)
100	return e1.String() == e2.String()
101}
102
103//
104// Batch proofs
105//
106
107// EvaluationBatchProof generates the evalutation proof for the given list of points
108func EvaluationBatchProof(ts *TrustedSetup, p []*big.Int, zs, ys []*big.Int) (*bn256.G1, error) {
109	if len(zs) != len(ys) {
110		return nil, fmt.Errorf("len(zs)!=len(ys), %d!=%d", len(zs), len(ys))
111	}
112	if len(p) <= len(zs)+1 {
113		return nil, fmt.Errorf("polynomial p(x) can not be of degree"+
114			" equal or smaller than the number of given points+1."+
115			" Polynomial p(x) degree: %d, number of points: %d",
116			len(p), len(zs))
117	}
118
119	// z(x) = (x-z0)(x-z1)...(x-zn)
120	z := zeroPolynomial(zs)
121
122	// I(x) = Lagrange interpolation through (z0, y0), (z1, y1), ...
123	i, err := LagrangeInterpolation(zs, ys)
124	if err != nil {
125		return nil, err
126	}
127
128	// q(x) = ( p(x) - I(x) ) / z(x)
129	pMinusI := polynomialSub(p, i)
130	q, rem := polynomialDiv(pMinusI, z)
131	if compareBigIntArray(rem, arrayOfZeroes(len(rem))) {
132		return nil,
133			fmt.Errorf("remainder should be 0, instead is %d", rem)
134	}
135
136	// proof: e = [q(t)]₁
137	e := evaluateG1(ts, q)
138	return e, nil
139}
140
141// VerifyBatchProof computes the KZG batch proof commitment verification
142func VerifyBatchProof(ts *TrustedSetup, c, proof *bn256.G1, zs, ys []*big.Int) bool {
143	// [z(s)]₂
144	z := zeroPolynomial(zs)
145	zG2 := evaluateG2(ts, z) // [z(t)]₂ = z(t) G ∈ 𝔾₂
146
147	// I(x) = Lagrange interpolation through (z0, y0), (z1, y1), ...
148	i, err := LagrangeInterpolation(zs, ys)
149	if err != nil {
150		return false
151	}
152	// [i(t)]₁
153	iG1 := evaluateG1(ts, i) // [i(t)]₁ = i(t) G ∈ 𝔾₁
154
155	// c - [i(t)]₁
156	iG1Neg := new(bn256.G1).Neg(iG1)
157	ciG1 := new(bn256.G1).Add(c, iG1Neg)
158
159	h := new(bn256.G2).ScalarBaseMult(big.NewInt(1)) // H ∈ 𝔾₂
160
161	// e(proof, [z(t)]₂) == e(c - [I(t)]₁, H)
162	e1 := bn256.Pair(proof, zG2)
163	e2 := bn256.Pair(ciG1, h)
164	return e1.String() == e2.String()
165}