forked from Consensys/gnark-crypto
-
Notifications
You must be signed in to change notification settings - Fork 0
/
pairing.go
149 lines (111 loc) · 3.32 KB
/
pairing.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
// Code generated by internal/pairing DO NOT EDIT
package bls381
// FinalExponentiation computes the final expo x**(p**6-1)(p**2+1)(p**4 - p**2 +1)/r
func (curve *Curve) FinalExponentiation(z *e12, _z ...*e12) e12 {
var result e12
result.Set(z)
// if additional parameters are provided, multiply them into z
for _, e := range _z {
result.Mul(&result, e)
}
result.FinalExponentiation(&result)
return result
}
// MillerLoop Miller loop
func (curve *Curve) MillerLoop(P G1Affine, Q G2Affine, result *e12) *e12 {
// init result
result.SetOne()
if P.IsInfinity() || Q.IsInfinity() {
return result
}
// the line goes through QCur and QNext
var QCur, QNext, QNextNeg G2Jac
var QNeg G2Affine
// Stores -Q
QNeg.Neg(&Q)
// init QCur with Q
Q.ToJacobian(&QCur)
var lEval lineEvalRes
// Miller loop
for i := len(curve.loopCounter) - 2; i >= 0; i-- {
QNext.Set(&QCur)
QNext.Double()
QNextNeg.Neg(&QNext)
result.Square(result)
// evaluates line though Qcur,2Qcur at P
lineEvalJac(QCur, QNextNeg, &P, &lEval)
lEval.mulAssign(result)
if curve.loopCounter[i] == 1 {
// evaluates line through 2Qcur, Q at P
lineEvalAffine(QNext, Q, &P, &lEval)
lEval.mulAssign(result)
QNext.AddMixed(&Q)
} else if curve.loopCounter[i] == -1 {
// evaluates line through 2Qcur, -Q at P
lineEvalAffine(QNext, QNeg, &P, &lEval)
lEval.mulAssign(result)
QNext.AddMixed(&QNeg)
}
QCur.Set(&QNext)
}
return result
}
// lineEval computes the evaluation of the line through Q, R (on the twist) at P
// Q, R are in jacobian coordinates
// The case in which Q=R=Infinity is not handled as this doesn't happen in the SNARK pairing
func lineEvalJac(Q, R G2Jac, P *G1Affine, result *lineEvalRes) {
// converts Q and R to projective coords
Q.ToProjFromJac()
R.ToProjFromJac()
// line eq: w^3*(QyRz-QzRy)x + w^2*(QzRx - QxRz)y + w^5*(QxRy-QyRxz)
// result.r1 = QyRz-QzRy
// result.r0 = QzRx - QxRz
// result.r2 = QxRy-QyRxz
result.r1.Mul(&Q.Y, &R.Z)
result.r0.Mul(&Q.Z, &R.X)
result.r2.Mul(&Q.X, &R.Y)
Q.Z.Mul(&Q.Z, &R.Y)
Q.X.Mul(&Q.X, &R.Z)
Q.Y.Mul(&Q.Y, &R.X)
result.r1.Sub(&result.r1, &Q.Z)
result.r0.Sub(&result.r0, &Q.X)
result.r2.Sub(&result.r2, &Q.Y)
// multiply P.Z by coeffs[2] in case P is infinity
result.r1.MulByElement(&result.r1, &P.X)
result.r0.MulByElement(&result.r0, &P.Y)
//result.r2.MulByElement(&result.r2, &P.Z)
}
// Same as above but R is in affine coords
func lineEvalAffine(Q G2Jac, R G2Affine, P *G1Affine, result *lineEvalRes) {
// converts Q and R to projective coords
Q.ToProjFromJac()
// line eq: w^3*(QyRz-QzRy)x + w^2*(QzRx - QxRz)y + w^5*(QxRy-QyRxz)
// result.r1 = QyRz-QzRy
// result.r0 = QzRx - QxRz
// result.r2 = QxRy-QyRxz
result.r1.Set(&Q.Y)
result.r0.Mul(&Q.Z, &R.X)
result.r2.Mul(&Q.X, &R.Y)
Q.Z.Mul(&Q.Z, &R.Y)
Q.Y.Mul(&Q.Y, &R.X)
result.r1.Sub(&result.r1, &Q.Z)
result.r0.Sub(&result.r0, &Q.X)
result.r2.Sub(&result.r2, &Q.Y)
// multiply P.Z by coeffs[2] in case P is infinity
result.r1.MulByElement(&result.r1, &P.X)
result.r0.MulByElement(&result.r0, &P.Y)
// result.r2.MulByElement(&result.r2, &P.Z)
}
type lineEvalRes struct {
r0 e2 // c0.b1
r1 e2 // c1.b1
r2 e2 // c1.b2
}
func (l *lineEvalRes) mulAssign(z *e12) *e12 {
var a, b, c e12
a.MulByVWNRInv(z, &l.r1)
b.MulByV2NRInv(z, &l.r0)
c.MulByWNRInv(z, &l.r2)
z.Add(&a, &b).Add(z, &c)
return z
}