1package r1csqap
  2
  3import (
  4	"math/big"
  5
  6	"github.com/arnaucube/go-snark/fields"
  7)
  8
  9func Transpose(matrix [][]*big.Int) [][]*big.Int {
 10	var r [][]*big.Int
 11	for i := 0; i < len(matrix[0]); i++ {
 12		var row []*big.Int
 13		for j := 0; j < len(matrix); j++ {
 14			row = append(row, matrix[j][i])
 15		}
 16		r = append(r, row)
 17	}
 18	return r
 19}
 20
 21func ArrayOfBigZeros(num int) []*big.Int {
 22	bigZero := big.NewInt(int64(0))
 23	var r []*big.Int
 24	for i := 0; i < num; i++ {
 25		r = append(r, bigZero)
 26	}
 27	return r
 28}
 29
 30type PolynomialField struct {
 31	F fields.Fq
 32}
 33
 34func NewPolynomialField(f fields.Fq) PolynomialField {
 35	return PolynomialField{
 36		f,
 37	}
 38}
 39func (pf PolynomialField) Mul(a, b []*big.Int) []*big.Int {
 40	r := ArrayOfBigZeros(len(a) + len(b) - 1)
 41	for i := 0; i < len(a); i++ {
 42		for j := 0; j < len(b); j++ {
 43			r[i+j] = pf.F.Add(
 44				r[i+j],
 45				pf.F.Mul(a[i], b[j]))
 46		}
 47	}
 48	return r
 49}
 50
 51func max(a, b int) int {
 52	if a > b {
 53		return a
 54	}
 55	return b
 56}
 57
 58func (pf PolynomialField) Add(a, b []*big.Int) []*big.Int {
 59	r := ArrayOfBigZeros(max(len(a), len(b)))
 60	for i := 0; i < len(a); i++ {
 61		r[i] = pf.F.Add(r[i], a[i])
 62	}
 63	for i := 0; i < len(b); i++ {
 64		r[i] = pf.F.Add(r[i], b[i])
 65	}
 66	return r
 67}
 68
 69func (pf PolynomialField) Sub(a, b []*big.Int) []*big.Int {
 70	r := ArrayOfBigZeros(max(len(a), len(b)))
 71	for i := 0; i < len(a); i++ {
 72		r[i] = pf.F.Add(r[i], a[i])
 73	}
 74	for i := 0; i < len(b); i++ {
 75		// bneg := pf.F.Mul(b[i], big.NewInt(int64(-1)))
 76		// r[i] = pf.F.Add(r[i], bneg)
 77		r[i] = pf.F.Sub(r[i], b[i])
 78	}
 79	return r
 80}
 81
 82// func FloatPow(a *big.Int, e int) *big.Int {
 83//         if e == 0 {
 84//                 return big.NewInt(int64(1))
 85//         }
 86//         result := new(big.Int).Copy(a)
 87//         for i := 0; i < e-1; i++ {
 88//                 result = new(big.Int).Mul(result, a)
 89//         }
 90//         return result
 91// }
 92
 93func (pf PolynomialField) Eval(v []*big.Int, x *big.Int) *big.Int {
 94	r := big.NewInt(int64(0))
 95	for i := 0; i < len(v); i++ {
 96		// xi := FloatPow(x, i)
 97		xi := pf.F.Exp(x, big.NewInt(int64(i)))
 98		elem := pf.F.Mul(v[i], xi)
 99		r = pf.F.Add(r, elem)
100	}
101	return r
102}
103
104func (pf PolynomialField) NewPolZeroAt(pointPos, totalPoints int, height *big.Int) []*big.Int {
105	fac := 1
106	for i := 1; i < totalPoints+1; i++ {
107		if i != pointPos {
108			fac = fac * (pointPos - i)
109		}
110	}
111	facBig := big.NewInt(int64(fac))
112	hf := pf.F.Div(height, facBig)
113	r := []*big.Int{hf}
114	for i := 1; i < totalPoints+1; i++ {
115		if i != pointPos {
116			ineg := big.NewInt(int64(-i))
117			b1 := big.NewInt(int64(1))
118			r = pf.Mul(r, []*big.Int{ineg, b1})
119		}
120	}
121	return r
122}
123
124func (pf PolynomialField) LagrangeInterpolation(v []*big.Int) []*big.Int {
125	// https://en.wikipedia.org/wiki/Lagrange_polynomial
126	var r []*big.Int
127	for i := 0; i < len(v); i++ {
128		r = pf.Add(r, pf.NewPolZeroAt(i+1, len(v), v[i]))
129	}
130	//
131	return r
132}
133
134func (pf PolynomialField) R1CSToQAP(a, b, c [][]*big.Int) ([][]*big.Int, [][]*big.Int, [][]*big.Int, []*big.Int) {
135	aT := Transpose(a)
136	bT := Transpose(b)
137	cT := Transpose(c)
138	var alpha [][]*big.Int
139	for i := 0; i < len(aT); i++ {
140		alpha = append(alpha, pf.LagrangeInterpolation(aT[i]))
141	}
142	var beta [][]*big.Int
143	for i := 0; i < len(bT); i++ {
144		beta = append(beta, pf.LagrangeInterpolation(bT[i]))
145	}
146	var gamma [][]*big.Int
147	for i := 0; i < len(cT); i++ {
148		gamma = append(gamma, pf.LagrangeInterpolation(cT[i]))
149	}
150	z := []*big.Int{big.NewInt(int64(1))}
151	for i := 1; i < len(aT[0])+1; i++ {
152		ineg := big.NewInt(int64(-i))
153		b1 := big.NewInt(int64(1))
154		z = pf.Mul(z, []*big.Int{ineg, b1})
155	}
156	return alpha, beta, gamma, z
157}