-
Notifications
You must be signed in to change notification settings - Fork 2
/
polynomial.go
192 lines (151 loc) · 4.52 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
// SPDX-License-Identifier: MIT
//
// Copyright (C) 2023 Daniel Bourdrez. All Rights Reserved.
//
// This source code is licensed under the MIT license found in the
// LICENSE file in the root directory of this source tree or at
// https://spdx.org/licenses/MIT.html
package secretsharing
import (
"errors"
group "github.com/bytemare/crypto"
)
var (
errPolyDiffLength = errors.New("destination and source polynomials length differ")
errPolyXIsZero = errors.New("identifier for interpolation is nil or zero")
errPolyHasZeroCoeff = errors.New("one of the polynomial's coefficients is zero")
errPolyHasDuplicates = errors.New("the polynomial has duplicate coefficients")
errPolyHasNilCoeff = errors.New("the polynomial has a nil coefficient")
errPolyCoeffInexistant = errors.New("the coefficient does not exist in the polynomial")
)
// Polynomial over scalars, represented as a list of t+1 coefficients, where t is the threshold.
// The constant term is in the first position and the highest degree coefficient is in the last position.
type Polynomial []*group.Scalar
// NewPolynomial returns a slice of Scalars with the capacity to hold the desired coefficients.
func NewPolynomial(coefficients uint) Polynomial {
return make(Polynomial, coefficients)
}
func copyPolynomial(dst, src Polynomial) error {
if len(dst) != len(src) {
return errPolyDiffLength
}
for index, coeff := range src {
if coeff == nil {
return errPolyHasNilCoeff
}
if coeff.IsZero() {
return errPolyHasZeroCoeff
}
dst[index] = coeff.Copy()
}
return nil
}
// Verify returns an appropriate error if the polynomial has a nil or 0 coefficient, or duplicates.
func (p Polynomial) Verify() error {
if p.hasNil() {
return errPolyHasNilCoeff
}
if p.hasZero() {
return errPolyHasZeroCoeff
}
if p.hasDuplicates() {
return errPolyHasDuplicates
}
return nil
}
func (p Polynomial) verifyInterpolatingInput(id *group.Scalar) error {
if id == nil || id.IsZero() {
return errPolyXIsZero
}
if err := p.Verify(); err != nil {
return err
}
if !p.has(id) {
return errPolyCoeffInexistant
}
return nil
}
// has returns whether s is a coefficient of the polynomial.
func (p Polynomial) hasNil() bool {
for _, si := range p {
if si == nil {
return true
}
}
return false
}
// has returns whether s is a coefficient of the polynomial.
func (p Polynomial) has(s *group.Scalar) bool {
for _, si := range p {
if si.Equal(s) == 1 {
return true
}
}
return false
}
// hasZero returns whether one of the polynomials coefficients is 0.
func (p Polynomial) hasZero() bool {
for _, xj := range p {
if xj.IsZero() {
return true
}
}
return false
}
// hasDuplicates returns whether the polynomial has at least one coefficient that appears more than once.
func (p Polynomial) hasDuplicates() bool {
visited := make(map[string]bool, len(p))
for _, pi := range p {
enc := string(pi.Encode())
if visited[enc] {
return true
}
visited[enc] = true
}
return false
}
// Evaluate evaluates the polynomial p at point x using Horner's method.
func (p Polynomial) Evaluate(x *group.Scalar) *group.Scalar {
// since value is an accumulator and starts with 0, we can skip multiplying by x, and start from the end
value := p[len(p)-1].Copy()
for i := len(p) - 2; i >= 0; i-- {
value.Multiply(x)
value.Add(p[i])
}
return value
}
// DeriveInterpolatingValue derives a value used for polynomial interpolation.
// id and all the coefficients must be non-zero scalars.
func (p Polynomial) DeriveInterpolatingValue(g group.Group, id *group.Scalar) (*group.Scalar, error) {
if err := p.verifyInterpolatingInput(id); err != nil {
return nil, err
}
numerator := g.NewScalar().One()
denominator := g.NewScalar().One()
for _, coeff := range p {
if coeff.Equal(id) == 1 {
continue
}
numerator.Multiply(coeff)
denominator.Multiply(coeff.Copy().Subtract(id))
}
return numerator.Multiply(denominator.Invert()), nil
}
// PolynomialInterpolateConstant recovers the constant term of the interpolating polynomial defined by the set of
// key shares.
func PolynomialInterpolateConstant(g group.Group, shares []*KeyShare) (*group.Scalar, error) {
xCoords := make(Polynomial, len(shares))
for i, share := range shares {
xCoords[i] = g.NewScalar().SetUInt64(share.Identifier)
}
constant := g.NewScalar().Zero()
for i, share := range shares {
iv, err := xCoords.DeriveInterpolatingValue(g, xCoords[i])
if err != nil {
return nil, err
}
delta := share.SecretKey.Copy().Multiply(iv)
constant.Add(delta)
}
return constant, nil
}