kzg-commitments-study/arithmetic_test.go

package kzg

import (
	"bytes"
	"crypto/rand"
	"math/big"
	"testing"

	"github.com/stretchr/testify/assert"
)

func randBI() *big.Int {
	maxbits := 256
	b := make([]byte, (maxbits/8)-1)
	_, err := rand.Read(b)
	if err != nil {
		panic(err)
	}
	r := new(big.Int).SetBytes(b)
	return new(big.Int).Mod(r, Q)
}

func neg(a *big.Int) *big.Int {
	return new(big.Int).Neg(a)
}

func TestPolynomial(t *testing.T) {
	b0 := big.NewInt(int64(0))
	b1 := big.NewInt(int64(1))
	b2 := big.NewInt(int64(2))
	b3 := big.NewInt(int64(3))
	b4 := big.NewInt(int64(4))
	b5 := big.NewInt(int64(5))
	b6 := big.NewInt(int64(6))
	b16 := big.NewInt(int64(16))

	a := []*big.Int{b1, b0, b5}
	b := []*big.Int{b3, b0, b1}

	// new Finite Field
	r, ok := new(big.Int).SetString("21888242871839275222246405745257275088548364400416034343698204186575808495617", 10) //nolint:lll
	assert.True(nil, ok)

	// polynomial multiplication
	o := polynomialMul(a, b)
	assert.Equal(t, o, []*big.Int{b3, b0, b16, b0, b5})

	// polynomial division
	quo, rem := polynomialDiv(a, b)
	assert.Equal(t, quo[0].Int64(), int64(5))
	// check the rem result without modulo
	assert.Equal(t, new(big.Int).Sub(rem[0], r).Int64(), int64(-14))

	c := []*big.Int{neg(b4), b0, neg(b2), b1}
	d := []*big.Int{neg(b3), b1}
	quo2, rem2 := polynomialDiv(c, d)
	assert.Equal(t, quo2, []*big.Int{b3, b1, b1})
	assert.Equal(t, rem2[0].Int64(), int64(5))

	// polynomial addition
	o = polynomialAdd(a, b)
	assert.Equal(t, o, []*big.Int{b4, b0, b6})

	// polynomial subtraction
	o1 := polynomialSub(a, b)
	o2 := polynomialSub(b, a)
	o = polynomialAdd(o1, o2)
	assert.True(t, bytes.Equal(b0.Bytes(), o[0].Bytes()))
	assert.True(t, bytes.Equal(b0.Bytes(), o[1].Bytes()))
	assert.True(t, bytes.Equal(b0.Bytes(), o[2].Bytes()))

	c = []*big.Int{b5, b6, b1}
	d = []*big.Int{b1, b3}
	o = polynomialSub(c, d)
	assert.Equal(t, o, []*big.Int{b4, b3, b1})

	// NewPolZeroAt
	o = newPolZeroAt(3, 4, b4)
	assert.Equal(t, polynomialEval(o, big.NewInt(3)), b4)
	o = newPolZeroAt(2, 4, b3)
	assert.Equal(t, polynomialEval(o, big.NewInt(2)), b3)

	// polynomialEval
	// 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, "x³ + x¹ + 5", PolynomialToString(p))
	assert.Equal(t, "35", polynomialEval(p, big.NewInt(3)).String())
	assert.Equal(t, "1015", polynomialEval(p, big.NewInt(10)).String())
	assert.Equal(t, "16777477", polynomialEval(p, big.NewInt(256)).String())
	assert.Equal(t, "125055", polynomialEval(p, big.NewInt(50)).String())
	assert.Equal(t, "7", polynomialEval(p, big.NewInt(1)).String())
}

func BenchmarkArithmetic(b *testing.B) {
	// generate arrays with bigint
	var p, q []*big.Int
	for i := 0; i < 1000; i++ {
		pi := randBI()
		p = append(p, pi)
	}
	for i := 1000 - 1; i >= 0; i-- {
		q = append(q, p[i])
	}

	b.Run("polynomialSub", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			polynomialSub(p, q)
		}
	})
	b.Run("polynomialMul", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			polynomialMul(p, q)
		}
	})
	b.Run("polynomialDiv", func(b *testing.B) {
		for i := 0; i < b.N; i++ {
			polynomialDiv(p, q)
		}
	})
}

func TestLagrangeInterpolation(t *testing.T) {
	x0 := big.NewInt(3)
	y0 := big.NewInt(35)
	x1 := big.NewInt(10)
	y1 := big.NewInt(1015)
	x2 := big.NewInt(256)
	y2 := big.NewInt(16777477)
	x3 := big.NewInt(50)
	y3 := big.NewInt(125055)

	xs := []*big.Int{x0, x1, x2, x3}
	ys := []*big.Int{y0, y1, y2, y3}

	p, err := LagrangeInterpolation(xs, ys)
	assert.Nil(t, err)
	assert.Equal(t, "x³ + x¹ + 5", PolynomialToString(p))

	assert.Equal(t, y0, polynomialEval(p, x0))
	assert.Equal(t, y1, polynomialEval(p, x1))
	assert.Equal(t, y2, polynomialEval(p, x2))
}

func TestZeroPolynomial(t *testing.T) {
	x0 := big.NewInt(1)
	x1 := big.NewInt(40)
	x2 := big.NewInt(512)
	xs := []*big.Int{x0, x1, x2}

	z := zeroPolynomial(xs)
	assert.Equal(t, "x³ "+
		"+ 21888242871839275222246405745257275088548364400416034343698204186575808495064x² "+
		"+ 21032x¹ + 21888242871839275222246405745257275088548364400416034343698204186575808475137",
		PolynomialToString(z))

	assert.Equal(t, "0", polynomialEval(z, x0).String())
	assert.Equal(t, "0", polynomialEval(z, x1).String())
	assert.Equal(t, "0", polynomialEval(z, x2).String())
}