1package kzg
  2
  3import (
  4	"bytes"
  5	"crypto/rand"
  6	"fmt"
  7	"math/big"
  8	"strconv"
  9
 10	bn256 "github.com/ethereum/go-ethereum/crypto/bn256/cloudflare"
 11)
 12
 13// Q is the order of the integer field (Zq) that fits inside the snark
 14var Q, _ = new(big.Int).SetString(
 15	"21888242871839275222246405745257275088696311157297823662689037894645226208583", 10)
 16
 17// R is the mod of the finite field
 18var R, _ = new(big.Int).SetString(
 19	"21888242871839275222246405745257275088548364400416034343698204186575808495617", 10)
 20
 21func randBigInt() (*big.Int, error) {
 22	maxbits := R.BitLen()
 23	b := make([]byte, (maxbits/8)-1)
 24	_, err := rand.Read(b)
 25	if err != nil {
 26		return nil, err
 27	}
 28	r := new(big.Int).SetBytes(b)
 29	rq := new(big.Int).Mod(r, R)
 30
 31	return rq, nil
 32}
 33
 34func arrayOfZeroes(n int) []*big.Int {
 35	r := make([]*big.Int, n)
 36	for i := 0; i < n; i++ {
 37		r[i] = new(big.Int).SetInt64(0)
 38	}
 39	return r[:]
 40}
 41
 42//nolint:deadcode,unused
 43func arrayOfZeroesG1(n int) []*bn256.G1 {
 44	r := make([]*bn256.G1, n)
 45	for i := 0; i < n; i++ {
 46		r[i] = new(bn256.G1).ScalarBaseMult(big.NewInt(0))
 47	}
 48	return r[:]
 49}
 50
 51//nolint:deadcode,unused
 52func arrayOfZeroesG2(n int) []*bn256.G2 {
 53	r := make([]*bn256.G2, n)
 54	for i := 0; i < n; i++ {
 55		r[i] = new(bn256.G2).ScalarBaseMult(big.NewInt(0))
 56	}
 57	return r[:]
 58}
 59
 60func compareBigIntArray(a, b []*big.Int) bool {
 61	if len(a) != len(b) {
 62		return false
 63	}
 64	for i := 0; i < len(a); i++ {
 65		if a[i] != b[i] {
 66			return false
 67		}
 68	}
 69	return true
 70}
 71
 72func fAdd(a, b *big.Int) *big.Int {
 73	ab := new(big.Int).Add(a, b)
 74	return ab.Mod(ab, R)
 75}
 76
 77func fSub(a, b *big.Int) *big.Int {
 78	ab := new(big.Int).Sub(a, b)
 79	return new(big.Int).Mod(ab, R)
 80}
 81
 82func fMul(a, b *big.Int) *big.Int {
 83	ab := new(big.Int).Mul(a, b)
 84	return ab.Mod(ab, R)
 85}
 86
 87func fDiv(a, b *big.Int) *big.Int {
 88	ab := new(big.Int).Mul(a, new(big.Int).ModInverse(b, R))
 89	return new(big.Int).Mod(ab, R)
 90}
 91
 92//nolint:unused,deadcode // TODO check
 93func fNeg(a *big.Int) *big.Int {
 94	return new(big.Int).Mod(new(big.Int).Neg(a), R)
 95}
 96
 97//nolint:deadcode,unused
 98func fInv(a *big.Int) *big.Int {
 99	return new(big.Int).ModInverse(a, R)
100}
101
102func fExp(base *big.Int, e *big.Int) *big.Int {
103	res := big.NewInt(1)
104	rem := new(big.Int).Set(e)
105	exp := base
106
107	for !bytes.Equal(rem.Bytes(), big.NewInt(int64(0)).Bytes()) {
108		// if BigIsOdd(rem) {
109		if rem.Bit(0) == 1 { // .Bit(0) returns 1 when is odd
110			res = fMul(res, exp)
111		}
112		exp = fMul(exp, exp)
113		rem.Rsh(rem, 1)
114	}
115	return res
116}
117
118func max(a, b int) int {
119	if a > b {
120		return a
121	}
122	return b
123}
124
125func polynomialAdd(a, b []*big.Int) []*big.Int {
126	r := arrayOfZeroes(max(len(a), len(b)))
127	for i := 0; i < len(a); i++ {
128		r[i] = fAdd(r[i], a[i])
129	}
130	for i := 0; i < len(b); i++ {
131		r[i] = fAdd(r[i], b[i])
132	}
133	return r
134}
135
136func polynomialSub(a, b []*big.Int) []*big.Int {
137	r := arrayOfZeroes(max(len(a), len(b)))
138	for i := 0; i < len(a); i++ {
139		r[i] = fAdd(r[i], a[i])
140	}
141	for i := 0; i < len(b); i++ {
142		r[i] = fSub(r[i], b[i])
143	}
144	return r
145}
146
147func polynomialMul(a, b []*big.Int) []*big.Int {
148	r := arrayOfZeroes(len(a) + len(b) - 1)
149	for i := 0; i < len(a); i++ {
150		for j := 0; j < len(b); j++ {
151			r[i+j] = fAdd(r[i+j], fMul(a[i], b[j]))
152		}
153	}
154	return r
155}
156
157func polynomialDiv(a, b []*big.Int) ([]*big.Int, []*big.Int) {
158	// https://en.wikipedia.org/wiki/Division_algorithm
159	r := arrayOfZeroes(len(a) - len(b) + 1)
160	rem := a
161	for len(rem) >= len(b) {
162		l := fDiv(rem[len(rem)-1], b[len(b)-1])
163		pos := len(rem) - len(b)
164		r[pos] = l
165		aux := arrayOfZeroes(pos)
166		aux1 := append(aux, l)
167		aux2 := polynomialSub(rem, polynomialMul(b, aux1))
168		rem = aux2[:len(aux2)-1]
169	}
170	return r, rem
171}
172
173// polynomialEval evaluates the polinomial over the Finite Field at the given value x
174func polynomialEval(p []*big.Int, x *big.Int) *big.Int {
175	r := big.NewInt(int64(0))
176	for i := 0; i < len(p); i++ {
177		xi := fExp(x, big.NewInt(int64(i)))
178		elem := fMul(p[i], xi)
179		r = fAdd(r, elem)
180	}
181	return r
182}
183
184// newPolZeroAt generates a new polynomial that has value zero at the given value
185func newPolZeroAt(pointPos, totalPoints int, height *big.Int) []*big.Int {
186	fac := 1
187	for i := 1; i < totalPoints+1; i++ {
188		if i != pointPos {
189			fac = fac * (pointPos - i)
190		}
191	}
192	facBig := big.NewInt(int64(fac))
193	hf := fDiv(height, facBig)
194	r := []*big.Int{hf}
195	for i := 1; i < totalPoints+1; i++ {
196		if i != pointPos {
197			ineg := big.NewInt(int64(-i))
198			b1 := big.NewInt(int64(1))
199			r = polynomialMul(r, []*big.Int{ineg, b1})
200		}
201	}
202	return r
203}
204
205var sNums = map[string]string{
206	"0": "⁰",
207	"1": "¹",
208	"2": "²",
209	"3": "³",
210	"4": "⁴",
211	"5": "⁵",
212	"6": "⁶",
213	"7": "⁷",
214	"8": "⁸",
215	"9": "⁹",
216}
217
218func intToSNum(n int) string {
219	s := strconv.Itoa(n)
220	sN := ""
221	for i := 0; i < len(s); i++ {
222		sN += sNums[string(s[i])]
223	}
224	return sN
225}
226
227// PolynomialToString converts a polynomial represented by a *big.Int array,
228// into its string human readable representation
229func PolynomialToString(p []*big.Int) string {
230	s := ""
231	for i := len(p) - 1; i >= 1; i-- {
232		if !bytes.Equal(p[i].Bytes(), big.NewInt(0).Bytes()) {
233			s += fmt.Sprintf("%sx%s + ", p[i], intToSNum(i))
234		}
235	}
236	s += p[0].String()
237	return s
238}
239
240// TODO add method to 'clean' the polynomial, to remove right-zeroes