forked from Consensys/gnark
-
Notifications
You must be signed in to change notification settings - Fork 0
/
scalarmul_glv.go
135 lines (109 loc) · 4.27 KB
/
scalarmul_glv.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
/*
Copyright © 2022 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.
*/
package twistededwards
import (
"errors"
"math/big"
"sync"
"github.com/consensys/gnark-crypto/ecc"
"github.com/consensys/gnark/constraint/solver"
"github.com/consensys/gnark/frontend"
)
// phi endomorphism √-2 ∈ 𝒪₋₈
// (x,y) → λ × (x,y) s.t. λ² = -2 mod Order
func (p *Point) phi(api frontend.API, p1 *Point, curve *CurveParams, endo *EndoParams) *Point {
xy := api.Mul(p1.X, p1.Y)
yy := api.Mul(p1.Y, p1.Y)
f := api.Sub(1, yy)
f = api.Mul(f, endo.Endo[1])
g := api.Add(yy, endo.Endo[0])
g = api.Mul(g, endo.Endo[0])
h := api.Sub(yy, endo.Endo[0])
p.X = api.DivUnchecked(f, xy)
p.Y = api.DivUnchecked(g, h)
return p
}
type glvParams struct {
lambda, order big.Int
glvBasis ecc.Lattice
}
var DecomposeScalar = func(scalarField *big.Int, inputs []*big.Int, res []*big.Int) error {
// the efficient endomorphism exists on Bandersnatch only
if scalarField.Cmp(ecc.BLS12_381.ScalarField()) != 0 {
return errors.New("no efficient endomorphism is available on this curve")
}
var glv glvParams
var init sync.Once
init.Do(func() {
glv.lambda.SetString("8913659658109529928382530854484400854125314752504019737736543920008458395397", 10)
glv.order.SetString("13108968793781547619861935127046491459309155893440570251786403306729687672801", 10)
ecc.PrecomputeLattice(&glv.order, &glv.lambda, &glv.glvBasis)
})
// sp[0] is always negative because, in SplitScalar(), we always round above
// the determinant/2 computed in PrecomputeLattice() which is negative for Bandersnatch.
// Thus taking -sp[0] here and negating the point in ScalarMul().
// If we keep -sp[0] it will be reduced mod r (the BLS12-381 prime order)
// and not the Bandersnatch prime order (Order) and the result will be incorrect.
// Also, if we reduce it mod Order here, we can't use api.ToBinary(sp[0], 129)
// and hence we can't reduce optimally the number of constraints.
sp := ecc.SplitScalar(inputs[0], &glv.glvBasis)
res[0].Neg(&(sp[0]))
res[1].Set(&(sp[1]))
// figure out how many times we have overflowed
res[2].Mul(res[1], &glv.lambda).Sub(res[2], res[0])
res[2].Sub(res[2], inputs[0])
res[2].Div(res[2], &glv.order)
return nil
}
func init() {
solver.RegisterHint(DecomposeScalar)
}
// ScalarMul computes the scalar multiplication of a point on a twisted Edwards curve
// p1: base point (as snark point)
// curve: parameters of the Edwards curve
// scal: scalar as a SNARK constraint
// Standard left to right double and add
func (p *Point) scalarMulGLV(api frontend.API, p1 *Point, scalar frontend.Variable, curve *CurveParams, endo *EndoParams) *Point {
// the hints allow to decompose the scalar s into s1 and s2 such that
// s1 + λ * s2 == s mod Order,
// with λ s.t. λ² = -2 mod Order.
sd, err := api.NewHint(DecomposeScalar, 3, scalar)
if err != nil {
// err is non-nil only for invalid number of inputs
panic(err)
}
s1, s2 := sd[0], sd[1]
// -s1 + λ * s2 == s + k*Order
api.AssertIsEqual(api.Sub(api.Mul(s2, endo.Lambda), s1), api.Add(scalar, api.Mul(curve.Order, sd[2])))
// Normally s1 and s2 are of the max size sqrt(Order) = 128
// But in a circuit, we force s1 to be negative by rounding always above.
// This changes the size bounds to 2*sqrt(Order) = 129.
n := 129
b1 := api.ToBinary(s1, n)
b2 := api.ToBinary(s2, n)
var res, _p1, p2, p3, tmp Point
_p1.neg(api, p1)
p2.phi(api, p1, curve, endo)
p3.add(api, &_p1, &p2, curve)
res.X = api.Lookup2(b1[n-1], b2[n-1], 0, _p1.X, p2.X, p3.X)
res.Y = api.Lookup2(b1[n-1], b2[n-1], 1, _p1.Y, p2.Y, p3.Y)
for i := n - 2; i >= 0; i-- {
res.double(api, &res, curve)
tmp.X = api.Lookup2(b1[i], b2[i], 0, _p1.X, p2.X, p3.X)
tmp.Y = api.Lookup2(b1[i], b2[i], 1, _p1.Y, p2.Y, p3.Y)
res.add(api, &res, &tmp, curve)
}
p.X = res.X
p.Y = res.Y
return p
}