-
Notifications
You must be signed in to change notification settings - Fork 158
/
polynomial.go
427 lines (376 loc) · 11.7 KB
/
polynomial.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
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
// Copyright 2020 ConsenSys Software Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// Code generated by consensys/gnark-crypto DO NOT EDIT
package iop
import (
"encoding/binary"
"io"
"math/big"
"math/bits"
"github.com/consensys/gnark-crypto/ecc/bls12-377/fr"
"github.com/consensys/gnark-crypto/ecc/bls12-377/fr/fft"
)
// Basis indicates the basis in which a polynomial is represented.
type Basis uint32
const (
Canonical Basis = 1 << iota
Lagrange
LagrangeCoset
)
// Layout indicates if a polynomial has a BitReverse or a Regular layout
type Layout uint32
const (
Regular Layout = 8 << iota
BitReverse
)
// Form describes the form of a polynomial.
// TODO should be a regular enum?
type Form struct {
Basis Basis
Layout Layout
}
// enum of the possible Form values for type-safe switches
// in this package
var (
canonicalRegular = Form{Canonical, Regular}
canonicalBitReverse = Form{Canonical, BitReverse}
lagrangeRegular = Form{Lagrange, Regular}
lagrangeBitReverse = Form{Lagrange, BitReverse}
lagrangeCosetRegular = Form{LagrangeCoset, Regular}
lagrangeCosetBitReverse = Form{LagrangeCoset, BitReverse}
)
// Polynomial wraps a polynomial so that it is
// interpreted as P'(X)=P(\omega^{s}X).
// Size is the real size of the polynomial (seen as a vector).
// For instance if len(P)=32 but P.Size=8, it means that P has been
// extended (e.g. it is evaluated on a larger set) but P is a polynomial
// of degree 7.
// blindedSize is the size of the polynomial when it is blinded. By
// default blindedSize=Size, until the polynomial is blinded.
type Polynomial struct {
*polynomial
shift int
size int
blindedSize int
}
// NewPolynomial returned a Polynomial from the provided coefficients in the given form.
// A Polynomial can be seen as a "shared pointer" on a list of coefficients.
// It is the responsibility of the user to call the Clone method if the coefficients
// shouldn't be mutated.
func NewPolynomial(coeffs *[]fr.Element, form Form) *Polynomial {
return &Polynomial{
polynomial: newPolynomial(coeffs, form),
size: len(*coeffs),
blindedSize: len(*coeffs),
}
}
// Shift the wrapped polynomial; it doesn't modify the underlying data structure,
// but flag the Polynomial such that it will be interpreted as p(\omega^shift X)
func (p *Polynomial) Shift(shift int) *Polynomial {
p.shift = shift
return p
}
// BlindedSize returns the the size of the polynomial when it is blinded. By
// default blindedSize=Size, until the polynomial is blinded.
func (p *Polynomial) BlindedSize() int {
return p.blindedSize
}
// Blind blinds a polynomial q by adding Q(X)*(X^{n}-1),
// where deg Q = blindingOrder and Q is random, and n is the
// size of q. Sets the result to p and returns it.
//
// blindingOrder is the degree of Q, where the blinding is Q(X)*(X^{n}-1)
// where n is the size of p. The size of p is modified since the underlying
// polynomial is of bigger degree now. The new size is p.Size+1+blindingOrder.
//
// /!\ The code panics if wq is not in canonical, regular layout
func (p *Polynomial) Blind(blindingOrder int) *Polynomial {
// check that p is in canonical basis
if p.Form != canonicalRegular {
panic("the input must be in canonical basis, regular layout")
}
// we add Q*(x^{n}-1) so the new size is deg(Q)+n+1
// where n is the size of wq.
newSize := p.size + blindingOrder + 1
// Resize p. The size of wq might has already been increased
// (e.g. when the polynomial is evaluated on a larger domain),
// if that's the case we don't resize the polynomial.
p.grow(newSize)
// blinding: we add Q(X)(X^{n}-1) to P, where deg(Q)=blindingOrder
var r fr.Element
for i := 0; i <= blindingOrder; i++ {
r.SetRandom()
(*p.coefficients)[i].Sub(&(*p.coefficients)[i], &r)
(*p.coefficients)[i+p.size].Add(&(*p.coefficients)[i+p.size], &r)
}
p.blindedSize = newSize
return p
}
// Evaluate evaluates p at x.
// The code panics if the function is not in canonical form.
func (p *Polynomial) Evaluate(x fr.Element) fr.Element {
if p.shift == 0 {
return p.polynomial.evaluate(x)
}
// TODO find a way to retrieve the root properly instead of re generating the fft domain
d := fft.NewDomain(uint64(p.size))
var g fr.Element
if p.shift <= 5 {
g = smallExp(d.Generator, p.shift)
x.Mul(&x, &g)
return p.polynomial.evaluate(x)
}
bs := big.NewInt(int64(p.shift))
g = *g.Exp(g, bs)
x.Mul(&x, &g)
return p.polynomial.evaluate(x)
}
// Clone returns a deep copy of p. The underlying polynomial is cloned;
// see also ShallowClone to perform a ShallowClone on the underlying polynomial.
// If capacity is provided, the new coefficient slice capacity will be set accordingly.
func (p *Polynomial) Clone(capacity ...int) *Polynomial {
res := p.ShallowClone()
res.polynomial = p.polynomial.clone(capacity...)
return res
}
// ShallowClone returns a shallow copy of p. The underlying polynomial coefficient
// is NOT cloned and both objects will point to the same coefficient vector.
func (p *Polynomial) ShallowClone() *Polynomial {
res := *p
return &res
}
// GetCoeff returns the i-th entry of p, taking the layout in account.
func (p *Polynomial) GetCoeff(i int) fr.Element {
n := p.coefficients.Len()
rho := n / p.size
if p.polynomial.Form.Layout == Regular {
return (*p.coefficients)[(i+rho*p.shift)%n]
} else {
nn := uint64(64 - bits.TrailingZeros(uint(n)))
iRev := bits.Reverse64(uint64((i+rho*p.shift)%n)) >> nn
return (*p.coefficients)[iRev]
}
}
// polynomial represents a polynomial, the vector of coefficients
// along with the basis and the layout.
type polynomial struct {
coefficients *fr.Vector
Form
}
// Coefficients returns a slice on the underlying data structure.
func (p *polynomial) Coefficients() []fr.Element {
return (*p.coefficients)
}
// newPolynomial creates a new polynomial. The slice coeff NOT copied
// but directly assigned to the new polynomial.
func newPolynomial(coeffs *[]fr.Element, form Form) *polynomial {
return &polynomial{coefficients: (*fr.Vector)(coeffs), Form: form}
}
// clone returns a deep copy of the underlying data structure.
func (p *polynomial) clone(capacity ...int) *polynomial {
c := p.coefficients.Len()
if len(capacity) == 1 && capacity[0] > c {
c = capacity[0]
}
newCoeffs := make(fr.Vector, p.coefficients.Len(), c)
r := &polynomial{
coefficients: &newCoeffs,
Form: p.Form,
}
copy((*r.coefficients), (*p.coefficients))
return r
}
// evaluate evaluates p at x.
// The code panics if the function is not in canonical form.
func (p *polynomial) evaluate(x fr.Element) fr.Element {
var r fr.Element
if p.Basis != Canonical {
panic("p must be in canonical basis")
}
if p.Layout == Regular {
for i := p.coefficients.Len() - 1; i >= 0; i-- {
r.Mul(&r, &x).Add(&r, &(*p.coefficients)[i])
}
} else {
nn := uint64(64 - bits.TrailingZeros(uint(p.coefficients.Len())))
for i := p.coefficients.Len() - 1; i >= 0; i-- {
iRev := bits.Reverse64(uint64(i)) >> nn
r.Mul(&r, &x).Add(&r, &(*p.coefficients)[iRev])
}
}
return r
}
// ToRegular changes the layout of p to Regular.
// Leaves p unchanged if p's layout was already Regular.
func (p *Polynomial) ToRegular() *Polynomial {
if p.Layout == Regular {
return p
}
fft.BitReverse((*p.coefficients))
p.Layout = Regular
return p
}
// ToBitReverse changes the layout of p to BitReverse.
// Leaves p unchanged if p's layout was already BitReverse.
func (p *Polynomial) ToBitReverse() *Polynomial {
if p.Layout == BitReverse {
return p
}
fft.BitReverse((*p.coefficients))
p.Layout = BitReverse
return p
}
// ToLagrange converts p to Lagrange form.
// Leaves p unchanged if p was already in Lagrange form.
func (p *Polynomial) ToLagrange(d *fft.Domain) *Polynomial {
id := p.Form
p.grow(int(d.Cardinality))
switch id {
case canonicalRegular:
p.Layout = BitReverse
d.FFT((*p.coefficients), fft.DIF)
case canonicalBitReverse:
p.Layout = Regular
d.FFT((*p.coefficients), fft.DIT)
case lagrangeRegular, lagrangeBitReverse:
return p
case lagrangeCosetRegular:
p.Layout = Regular
d.FFTInverse((*p.coefficients), fft.DIF, true)
d.FFT((*p.coefficients), fft.DIT)
case lagrangeCosetBitReverse:
p.Layout = BitReverse
d.FFTInverse((*p.coefficients), fft.DIT, true)
d.FFT((*p.coefficients), fft.DIF)
default:
panic("unknown ID")
}
p.Basis = Lagrange
return p
}
// ToCanonical converts p to canonical form.
// Leaves p unchanged if p was already in Canonical form.
func (p *Polynomial) ToCanonical(d *fft.Domain) *Polynomial {
id := p.Form
p.grow(int(d.Cardinality))
switch id {
case canonicalRegular, canonicalBitReverse:
return p
case lagrangeRegular:
p.Layout = BitReverse
d.FFTInverse((*p.coefficients), fft.DIF)
case lagrangeBitReverse:
p.Layout = Regular
d.FFTInverse((*p.coefficients), fft.DIT)
case lagrangeCosetRegular:
p.Layout = BitReverse
d.FFTInverse((*p.coefficients), fft.DIF, true)
case lagrangeCosetBitReverse:
p.Layout = Regular
d.FFTInverse((*p.coefficients), fft.DIT, true)
default:
panic("unknown ID")
}
p.Basis = Canonical
return p
}
func (p *polynomial) grow(newSize int) {
offset := newSize - p.coefficients.Len()
if offset > 0 {
(*p.coefficients) = append((*p.coefficients), make(fr.Vector, offset)...)
}
}
// ToLagrangeCoset Sets p to q, in LagrangeCoset form and returns it.
func (p *Polynomial) ToLagrangeCoset(d *fft.Domain) *Polynomial {
id := p.Form
p.grow(int(d.Cardinality))
switch id {
case canonicalRegular:
p.Layout = BitReverse
d.FFT((*p.coefficients), fft.DIF, true)
case canonicalBitReverse:
p.Layout = Regular
d.FFT((*p.coefficients), fft.DIT, true)
case lagrangeRegular:
p.Layout = Regular
d.FFTInverse((*p.coefficients), fft.DIF)
d.FFT((*p.coefficients), fft.DIT, true)
case lagrangeBitReverse:
p.Layout = BitReverse
d.FFTInverse((*p.coefficients), fft.DIT)
d.FFT((*p.coefficients), fft.DIF, true)
case lagrangeCosetRegular, lagrangeCosetBitReverse:
return p
default:
panic("unknown ID")
}
p.Basis = LagrangeCoset
return p
}
// WriteTo implements io.WriterTo
func (p *Polynomial) WriteTo(w io.Writer) (int64, error) {
// encode coefficients
n, err := p.polynomial.coefficients.WriteTo(w)
if err != nil {
return n, err
}
// encode Form.Basis, Form.Layout, shift, size & blindedSize as uint32
var data = []uint32{
uint32(p.Basis),
uint32(p.Layout),
uint32(p.shift),
uint32(p.size),
uint32(p.blindedSize),
}
for _, v := range data {
err = binary.Write(w, binary.BigEndian, v)
if err != nil {
return n, err
}
n += 4
}
return n, nil
}
// ReadFrom implements io.ReaderFrom
func (p *Polynomial) ReadFrom(r io.Reader) (int64, error) {
// decode coefficients
if p.polynomial == nil {
p.polynomial = new(polynomial)
}
if p.polynomial.coefficients == nil {
v := make(fr.Vector, 0)
p.polynomial.coefficients = &v
}
n, err := p.polynomial.coefficients.ReadFrom(r)
if err != nil {
return n, err
}
// decode Form.Basis, Form.Layout, shift, size & blindedSize as uint32
var data [5]uint32
var buf [4]byte
for i := range data {
read, err := io.ReadFull(r, buf[:4])
n += int64(read)
if err != nil {
return n, err
}
data[i] = binary.BigEndian.Uint32(buf[:4])
}
p.Basis = Basis(data[0])
p.Layout = Layout(data[1])
p.shift = int(data[2])
p.size = int(data[3])
p.blindedSize = int(data[4])
return n, nil
}