forked from taurusgroup/multi-party-sig
-
Notifications
You must be signed in to change notification settings - Fork 0
/
lagrange.go
74 lines (65 loc) · 2.76 KB
/
lagrange.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
package polynomial
import (
"github.com/cronokirby/saferith"
"github.com/MixinNetwork/multi-party-sig/pkg/math/curve"
"github.com/MixinNetwork/multi-party-sig/pkg/party"
)
// Lagrange returns the Lagrange coefficients at 0 for all parties in the interpolation domain.
func Lagrange(group curve.Curve, interpolationDomain []party.ID) map[party.ID]curve.Scalar {
return LagrangeFor(group, interpolationDomain, interpolationDomain...)
}
// LagrangeFor returns the Lagrange coefficients at 0 for all parties in the given subset.
func LagrangeFor(group curve.Curve, interpolationDomain []party.ID, subset ...party.ID) map[party.ID]curve.Scalar {
// numerator = x₀ * … * xₖ
scalars, numerator := getScalarsAndNumerator(group, interpolationDomain)
coefficients := make(map[party.ID]curve.Scalar, len(subset))
for _, j := range subset {
coefficients[j] = lagrange(group, scalars, numerator, j)
}
return coefficients
}
// LagrangeSingle returns the lagrange coefficient at 0 of the party with index j.
func LagrangeSingle(group curve.Curve, interpolationDomain []party.ID, j party.ID) curve.Scalar {
return LagrangeFor(group, interpolationDomain, j)[j]
}
// getScalarsAndNumerator returns the Scalars associated to the list of party.IDs.
func getScalarsAndNumerator(group curve.Curve, interpolationDomain []party.ID) (map[party.ID]curve.Scalar, curve.Scalar) {
// numerator = x₀ * … * xₖ
numerator := group.NewScalar().SetNat(new(saferith.Nat).SetUint64(1))
scalars := make(map[party.ID]curve.Scalar, len(interpolationDomain))
for _, id := range interpolationDomain {
xi := id.Scalar(group)
scalars[id] = xi
numerator.Mul(xi)
}
return scalars, numerator
}
// lagrange returns the Lagrange coefficient lⱼ(0), for j in the interpolation domain.
// The numerator is provided beforehand for efficiency reasons.
//
// The following formulas are taken from
// https://en.wikipedia.org/wiki/Lagrange_polynomial
// x₀ ⋅⋅⋅ xₖ
// lⱼ(0) = --------------------------------------------------
// xⱼ⋅(x₀ - xⱼ)⋅⋅⋅(xⱼ₋₁ - xⱼ)⋅(xⱼ₊₁ - xⱼ)⋅⋅⋅(xₖ - xⱼ).
func lagrange(group curve.Curve, interpolationDomain map[party.ID]curve.Scalar, numerator curve.Scalar, j party.ID) curve.Scalar {
xJ := interpolationDomain[j]
tmp := group.NewScalar()
// denominator = xⱼ⋅(xⱼ - x₀)⋅⋅⋅(xⱼ₋₁ - xⱼ)⋅(xⱼ₊₁ - xⱼ)⋅⋅⋅(xₖ - xⱼ)
denominator := group.NewScalar().SetNat(new(saferith.Nat).SetUint64(1))
for i, xI := range interpolationDomain {
if i == j {
// lⱼ *= xⱼ
denominator.Mul(xJ)
continue
}
// tmp = xᵢ - xⱼ
tmp.Set(xJ).Negate().Add(xI)
// lⱼ *= xᵢ - xⱼ
denominator.Mul(tmp)
}
// lⱼ = numerator/denominator
lJ := denominator.Invert()
lJ.Mul(numerator)
return lJ
}