1package kzg
  2
  3import (
  4	"bytes"
  5	"crypto/rand"
  6	"math/big"
  7	"testing"
  8
  9	cryptoConstants "github.com/iden3/go-iden3-crypto/constants"
 10	"github.com/stretchr/testify/assert"
 11)
 12
 13func randBI() *big.Int {
 14	maxbits := 256
 15	b := make([]byte, (maxbits/8)-1)
 16	_, err := rand.Read(b)
 17	if err != nil {
 18		panic(err)
 19	}
 20	r := new(big.Int).SetBytes(b)
 21	return new(big.Int).Mod(r, cryptoConstants.Q)
 22}
 23
 24func neg(a *big.Int) *big.Int {
 25	return new(big.Int).Neg(a)
 26}
 27
 28func TestPolynomial(t *testing.T) {
 29	b0 := big.NewInt(int64(0))
 30	b1 := big.NewInt(int64(1))
 31	b2 := big.NewInt(int64(2))
 32	b3 := big.NewInt(int64(3))
 33	b4 := big.NewInt(int64(4))
 34	b5 := big.NewInt(int64(5))
 35	b6 := big.NewInt(int64(6))
 36	b16 := big.NewInt(int64(16))
 37
 38	a := []*big.Int{b1, b0, b5}
 39	b := []*big.Int{b3, b0, b1}
 40
 41	// new Finite Field
 42	r, ok := new(big.Int).SetString("21888242871839275222246405745257275088548364400416034343698204186575808495617", 10) //nolint:lll
 43	assert.True(nil, ok)
 44
 45	// polynomial multiplication
 46	o := polynomialMul(a, b)
 47	assert.Equal(t, o, []*big.Int{b3, b0, b16, b0, b5})
 48
 49	// polynomial division
 50	quo, rem := polynomialDiv(a, b)
 51	assert.Equal(t, quo[0].Int64(), int64(5))
 52	// check the rem result without modulo
 53	assert.Equal(t, new(big.Int).Sub(rem[0], r).Int64(), int64(-14))
 54
 55	c := []*big.Int{neg(b4), b0, neg(b2), b1}
 56	d := []*big.Int{neg(b3), b1}
 57	quo2, rem2 := polynomialDiv(c, d)
 58	assert.Equal(t, quo2, []*big.Int{b3, b1, b1})
 59	assert.Equal(t, rem2[0].Int64(), int64(5))
 60
 61	// polynomial addition
 62	o = polynomialAdd(a, b)
 63	assert.Equal(t, o, []*big.Int{b4, b0, b6})
 64
 65	// polynomial subtraction
 66	o1 := polynomialSub(a, b)
 67	o2 := polynomialSub(b, a)
 68	o = polynomialAdd(o1, o2)
 69	assert.True(t, bytes.Equal(b0.Bytes(), o[0].Bytes()))
 70	assert.True(t, bytes.Equal(b0.Bytes(), o[1].Bytes()))
 71	assert.True(t, bytes.Equal(b0.Bytes(), o[2].Bytes()))
 72
 73	c = []*big.Int{b5, b6, b1}
 74	d = []*big.Int{b1, b3}
 75	o = polynomialSub(c, d)
 76	assert.Equal(t, o, []*big.Int{b4, b3, b1})
 77
 78	// NewPolZeroAt
 79	o = newPolZeroAt(3, 4, b4)
 80	assert.Equal(t, polynomialEval(o, big.NewInt(3)), b4)
 81	o = newPolZeroAt(2, 4, b3)
 82	assert.Equal(t, polynomialEval(o, big.NewInt(2)), b3)
 83
 84	// polynomialEval
 85	// p(x) = x^3 + x + 5
 86	p := []*big.Int{
 87		big.NewInt(5),
 88		big.NewInt(1), // x^1
 89		big.NewInt(0), // x^2
 90		big.NewInt(1), // x^3
 91	}
 92	assert.Equal(t, "1x³ + 1x¹ + 5", PolynomialToString(p))
 93	assert.Equal(t, "35", polynomialEval(p, big.NewInt(3)).String())
 94	assert.Equal(t, "1015", polynomialEval(p, big.NewInt(10)).String())
 95	assert.Equal(t, "16777477", polynomialEval(p, big.NewInt(256)).String())
 96	assert.Equal(t, "125055", polynomialEval(p, big.NewInt(50)).String())
 97	assert.Equal(t, "7", polynomialEval(p, big.NewInt(1)).String())
 98}
 99
100func BenchmarkArithmetic(b *testing.B) {
101	// generate arrays with bigint
102	var p, q []*big.Int
103	for i := 0; i < 1000; i++ {
104		pi := randBI()
105		p = append(p, pi)
106	}
107	for i := 1000 - 1; i >= 0; i-- {
108		q = append(q, p[i])
109	}
110
111	b.Run("polynomialSub", func(b *testing.B) {
112		for i := 0; i < b.N; i++ {
113			polynomialSub(p, q)
114		}
115	})
116	b.Run("polynomialMul", func(b *testing.B) {
117		for i := 0; i < b.N; i++ {
118			polynomialMul(p, q)
119		}
120	})
121	b.Run("polynomialDiv", func(b *testing.B) {
122		for i := 0; i < b.N; i++ {
123			polynomialDiv(p, q)
124		}
125	})
126}
127
128func TestLagrangeInterpolation(t *testing.T) {
129	x0 := big.NewInt(3)
130	y0 := big.NewInt(35)
131	x1 := big.NewInt(10)
132	y1 := big.NewInt(1015)
133	x2 := big.NewInt(256)
134	y2 := big.NewInt(16777477)
135	x3 := big.NewInt(50)
136	y3 := big.NewInt(125055)
137
138	xs := []*big.Int{x0, x1, x2, x3}
139	ys := []*big.Int{y0, y1, y2, y3}
140
141	p, err := LagrangeInterpolation(xs, ys)
142	assert.Nil(t, err)
143	assert.Equal(t, "1x³ + 1x¹ + 5", PolynomialToString(p))
144
145	assert.Equal(t, y0, polynomialEval(p, x0))
146	assert.Equal(t, y1, polynomialEval(p, x1))
147	assert.Equal(t, y2, polynomialEval(p, x2))
148}
149
150func TestZeroPolynomial(t *testing.T) {
151	x0 := big.NewInt(1)
152	x1 := big.NewInt(40)
153	x2 := big.NewInt(512)
154	xs := []*big.Int{x0, x1, x2}
155
156	z := zeroPolynomial(xs)
157	assert.Equal(t, "1x³ "+
158		"+ 21888242871839275222246405745257275088548364400416034343698204186575808495064x² "+
159		"+ 21032x¹ + 21888242871839275222246405745257275088548364400416034343698204186575808475137",
160		PolynomialToString(z))
161
162	assert.Equal(t, "0", polynomialEval(z, x0).String())
163	assert.Equal(t, "0", polynomialEval(z, x1).String())
164	assert.Equal(t, "0", polynomialEval(z, x2).String())
165}