1package r1csqap
  2
  3import (
  4	"bytes"
  5	"math/big"
  6
  7	"github.com/arnaucube/go-snark/fields"
  8)
  9
 10// Transpose transposes the *big.Int matrix
 11func Transpose(matrix [][]*big.Int) [][]*big.Int {
 12	var r [][]*big.Int
 13	for i := 0; i < len(matrix[0]); i++ {
 14		var row []*big.Int
 15		for j := 0; j < len(matrix); j++ {
 16			row = append(row, matrix[j][i])
 17		}
 18		r = append(r, row)
 19	}
 20	return r
 21}
 22
 23// ArrayOfBigZeros creates a *big.Int array with n elements to zero
 24func ArrayOfBigZeros(num int) []*big.Int {
 25	bigZero := big.NewInt(int64(0))
 26	var r []*big.Int
 27	for i := 0; i < num; i++ {
 28		r = append(r, bigZero)
 29	}
 30	return r
 31}
 32func BigArraysEqual(a, b []*big.Int) bool {
 33	if len(a) != len(b) {
 34		return false
 35	}
 36	for i := 0; i < len(a); i++ {
 37		if !bytes.Equal(a[i].Bytes(), b[i].Bytes()) {
 38			return false
 39		}
 40	}
 41	return true
 42}
 43
 44// PolynomialField is the Polynomial over a Finite Field where the polynomial operations are performed
 45type PolynomialField struct {
 46	F fields.Fq
 47}
 48
 49// NewPolynomialField creates a new PolynomialField with the given FiniteField
 50func NewPolynomialField(f fields.Fq) PolynomialField {
 51	return PolynomialField{
 52		f,
 53	}
 54}
 55
 56// Mul multiplies two polinomials over the Finite Field
 57func (pf PolynomialField) Mul(a, b []*big.Int) []*big.Int {
 58	r := ArrayOfBigZeros(len(a) + len(b) - 1)
 59	for i := 0; i < len(a); i++ {
 60		for j := 0; j < len(b); j++ {
 61			r[i+j] = pf.F.Add(
 62				r[i+j],
 63				pf.F.Mul(a[i], b[j]))
 64		}
 65	}
 66	return r
 67}
 68
 69// Div divides two polinomials over the Finite Field, returning the result and the remainder
 70func (pf PolynomialField) Div(a, b []*big.Int) ([]*big.Int, []*big.Int) {
 71	// https://en.wikipedia.org/wiki/Division_algorithm
 72	r := ArrayOfBigZeros(len(a) - len(b) + 1)
 73	rem := a
 74	for len(rem) >= len(b) {
 75		l := pf.F.Div(rem[len(rem)-1], b[len(b)-1])
 76		pos := len(rem) - len(b)
 77		r[pos] = l
 78		aux := ArrayOfBigZeros(pos)
 79		aux1 := append(aux, l)
 80		aux2 := pf.Sub(rem, pf.Mul(b, aux1))
 81		rem = aux2[:len(aux2)-1]
 82	}
 83	return r, rem
 84}
 85
 86func max(a, b int) int {
 87	if a > b {
 88		return a
 89	}
 90	return b
 91}
 92
 93// Add adds two polinomials over the Finite Field
 94func (pf PolynomialField) Add(a, b []*big.Int) []*big.Int {
 95	r := ArrayOfBigZeros(max(len(a), len(b)))
 96	for i := 0; i < len(a); i++ {
 97		r[i] = pf.F.Add(r[i], a[i])
 98	}
 99	for i := 0; i < len(b); i++ {
100		r[i] = pf.F.Add(r[i], b[i])
101	}
102	return r
103}
104
105// Sub subtracts two polinomials over the Finite Field
106func (pf PolynomialField) Sub(a, b []*big.Int) []*big.Int {
107	r := ArrayOfBigZeros(max(len(a), len(b)))
108	for i := 0; i < len(a); i++ {
109		r[i] = pf.F.Add(r[i], a[i])
110	}
111	for i := 0; i < len(b); i++ {
112		r[i] = pf.F.Sub(r[i], b[i])
113	}
114	return r
115}
116
117// Eval evaluates the polinomial over the Finite Field at the given value x
118func (pf PolynomialField) Eval(v []*big.Int, x *big.Int) *big.Int {
119	r := big.NewInt(int64(0))
120	for i := 0; i < len(v); i++ {
121		xi := pf.F.Exp(x, big.NewInt(int64(i)))
122		elem := pf.F.Mul(v[i], xi)
123		r = pf.F.Add(r, elem)
124	}
125	return r
126}
127
128// NewPolZeroAt generates a new polynomial that has value zero at the given value
129func (pf PolynomialField) NewPolZeroAt(pointPos, totalPoints int, height *big.Int) []*big.Int {
130	fac := 1
131	for i := 1; i < totalPoints+1; i++ {
132		if i != pointPos {
133			fac = fac * (pointPos - i)
134		}
135	}
136	facBig := big.NewInt(int64(fac))
137	hf := pf.F.Div(height, facBig)
138	r := []*big.Int{hf}
139	for i := 1; i < totalPoints+1; i++ {
140		if i != pointPos {
141			ineg := big.NewInt(int64(-i))
142			b1 := big.NewInt(int64(1))
143			r = pf.Mul(r, []*big.Int{ineg, b1})
144		}
145	}
146	return r
147}
148
149// LagrangeInterpolation performs the Lagrange Interpolation / Lagrange Polynomials operation
150func (pf PolynomialField) LagrangeInterpolation(v []*big.Int) []*big.Int {
151	// https://en.wikipedia.org/wiki/Lagrange_polynomial
152	var r []*big.Int
153	for i := 0; i < len(v); i++ {
154		r = pf.Add(r, pf.NewPolZeroAt(i+1, len(v), v[i]))
155	}
156	//
157	return r
158}
159
160// R1CSToQAP converts the R1CS values to the QAP values
161func (pf PolynomialField) R1CSToQAP(a, b, c [][]*big.Int) ([][]*big.Int, [][]*big.Int, [][]*big.Int, []*big.Int) {
162	aT := Transpose(a)
163	bT := Transpose(b)
164	cT := Transpose(c)
165	var alphas [][]*big.Int
166	for i := 0; i < len(aT); i++ {
167		alphas = append(alphas, pf.LagrangeInterpolation(aT[i]))
168	}
169	var betas [][]*big.Int
170	for i := 0; i < len(bT); i++ {
171		betas = append(betas, pf.LagrangeInterpolation(bT[i]))
172	}
173	var gammas [][]*big.Int
174	for i := 0; i < len(cT); i++ {
175		gammas = append(gammas, pf.LagrangeInterpolation(cT[i]))
176	}
177	z := []*big.Int{big.NewInt(int64(1))}
178	for i := 1; i < len(alphas)-1; i++ {
179		z = pf.Mul(
180			z,
181			[]*big.Int{
182				pf.F.Neg(
183					big.NewInt(int64(i))),
184				big.NewInt(int64(1)),
185			})
186	}
187	return alphas, betas, gammas, z
188}
189
190// CombinePolynomials combine the given polynomials arrays into one, also returns the P(x)
191func (pf PolynomialField) CombinePolynomials(r []*big.Int, ap, bp, cp [][]*big.Int) ([]*big.Int, []*big.Int, []*big.Int, []*big.Int) {
192	var alpha []*big.Int
193	for i := 0; i < len(r); i++ {
194		m := pf.Mul([]*big.Int{r[i]}, ap[i])
195		alpha = pf.Add(alpha, m)
196	}
197	var beta []*big.Int
198	for i := 0; i < len(r); i++ {
199		m := pf.Mul([]*big.Int{r[i]}, bp[i])
200		beta = pf.Add(beta, m)
201	}
202	var gamma []*big.Int
203	for i := 0; i < len(r); i++ {
204		m := pf.Mul([]*big.Int{r[i]}, cp[i])
205		gamma = pf.Add(gamma, m)
206	}
207
208	px := pf.Sub(pf.Mul(alpha, beta), gamma)
209	return alpha, beta, gamma, px
210}
211
212// DivisorPolynomial returns the divisor polynomial given two polynomials
213func (pf PolynomialField) DivisorPolynomial(px, z []*big.Int) []*big.Int {
214	quo, _ := pf.Div(px, z)
215	return quo
216}