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