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