1// Copyright 2020 The go-ethereum Authors
2// This file is part of the go-ethereum library.
3//
4// The go-ethereum library is free software: you can redistribute it and/or modify
5// it under the terms of the GNU Lesser General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8//
9// The go-ethereum library is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12// GNU Lesser General Public License for more details.
13//
14// You should have received a copy of the GNU Lesser General Public License
15// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>.
16
17package bls12381
18
19type pair struct {
20	g1 *PointG1
21	g2 *PointG2
22}
23
24func newPair(g1 *PointG1, g2 *PointG2) pair {
25	return pair{g1, g2}
26}
27
28// Engine is BLS12-381 elliptic curve pairing engine
29type Engine struct {
30	G1   *G1
31	G2   *G2
32	fp12 *fp12
33	fp2  *fp2
34	pairingEngineTemp
35	pairs []pair
36}
37
38// NewPairingEngine creates new pairing engine instance.
39func NewPairingEngine() *Engine {
40	fp2 := newFp2()
41	fp6 := newFp6(fp2)
42	fp12 := newFp12(fp6)
43	g1 := NewG1()
44	g2 := newG2(fp2)
45	return &Engine{
46		fp2:               fp2,
47		fp12:              fp12,
48		G1:                g1,
49		G2:                g2,
50		pairingEngineTemp: newEngineTemp(),
51	}
52}
53
54type pairingEngineTemp struct {
55	t2  [10]*fe2
56	t12 [9]fe12
57}
58
59func newEngineTemp() pairingEngineTemp {
60	t2 := [10]*fe2{}
61	for i := 0; i < 10; i++ {
62		t2[i] = &fe2{}
63	}
64	t12 := [9]fe12{}
65	return pairingEngineTemp{t2, t12}
66}
67
68// AddPair adds a g1, g2 point pair to pairing engine
69func (e *Engine) AddPair(g1 *PointG1, g2 *PointG2) *Engine {
70	p := newPair(g1, g2)
71	if !e.isZero(p) {
72		e.affine(p)
73		e.pairs = append(e.pairs, p)
74	}
75	return e
76}
77
78// AddPairInv adds a G1, G2 point pair to pairing engine. G1 point is negated.
79func (e *Engine) AddPairInv(g1 *PointG1, g2 *PointG2) *Engine {
80	e.G1.Neg(g1, g1)
81	e.AddPair(g1, g2)
82	return e
83}
84
85// Reset deletes added pairs.
86func (e *Engine) Reset() *Engine {
87	e.pairs = []pair{}
88	return e
89}
90
91func (e *Engine) isZero(p pair) bool {
92	return e.G1.IsZero(p.g1) || e.G2.IsZero(p.g2)
93}
94
95func (e *Engine) affine(p pair) {
96	e.G1.Affine(p.g1)
97	e.G2.Affine(p.g2)
98}
99
100func (e *Engine) doublingStep(coeff *[3]fe2, r *PointG2) {
101	// Adaptation of Formula 3 in https://eprint.iacr.org/2010/526.pdf
102	fp2 := e.fp2
103	t := e.t2
104	fp2.mul(t[0], &r[0], &r[1])
105	fp2.mulByFq(t[0], t[0], twoInv)
106	fp2.square(t[1], &r[1])
107	fp2.square(t[2], &r[2])
108	fp2.double(t[7], t[2])
109	fp2.add(t[7], t[7], t[2])
110	fp2.mulByB(t[3], t[7])
111	fp2.double(t[4], t[3])
112	fp2.add(t[4], t[4], t[3])
113	fp2.add(t[5], t[1], t[4])
114	fp2.mulByFq(t[5], t[5], twoInv)
115	fp2.add(t[6], &r[1], &r[2])
116	fp2.square(t[6], t[6])
117	fp2.add(t[7], t[2], t[1])
118	fp2.sub(t[6], t[6], t[7])
119	fp2.sub(&coeff[0], t[3], t[1])
120	fp2.square(t[7], &r[0])
121	fp2.sub(t[4], t[1], t[4])
122	fp2.mul(&r[0], t[4], t[0])
123	fp2.square(t[2], t[3])
124	fp2.double(t[3], t[2])
125	fp2.add(t[3], t[3], t[2])
126	fp2.square(t[5], t[5])
127	fp2.sub(&r[1], t[5], t[3])
128	fp2.mul(&r[2], t[1], t[6])
129	fp2.double(t[0], t[7])
130	fp2.add(&coeff[1], t[0], t[7])
131	fp2.neg(&coeff[2], t[6])
132}
133
134func (e *Engine) additionStep(coeff *[3]fe2, r, q *PointG2) {
135	// Algorithm 12 in https://eprint.iacr.org/2010/526.pdf
136	fp2 := e.fp2
137	t := e.t2
138	fp2.mul(t[0], &q[1], &r[2])
139	fp2.neg(t[0], t[0])
140	fp2.add(t[0], t[0], &r[1])
141	fp2.mul(t[1], &q[0], &r[2])
142	fp2.neg(t[1], t[1])
143	fp2.add(t[1], t[1], &r[0])
144	fp2.square(t[2], t[0])
145	fp2.square(t[3], t[1])
146	fp2.mul(t[4], t[1], t[3])
147	fp2.mul(t[2], &r[2], t[2])
148	fp2.mul(t[3], &r[0], t[3])
149	fp2.double(t[5], t[3])
150	fp2.sub(t[5], t[4], t[5])
151	fp2.add(t[5], t[5], t[2])
152	fp2.mul(&r[0], t[1], t[5])
153	fp2.sub(t[2], t[3], t[5])
154	fp2.mul(t[2], t[2], t[0])
155	fp2.mul(t[3], &r[1], t[4])
156	fp2.sub(&r[1], t[2], t[3])
157	fp2.mul(&r[2], &r[2], t[4])
158	fp2.mul(t[2], t[1], &q[1])
159	fp2.mul(t[3], t[0], &q[0])
160	fp2.sub(&coeff[0], t[3], t[2])
161	fp2.neg(&coeff[1], t[0])
162	coeff[2].set(t[1])
163}
164
165func (e *Engine) preCompute(ellCoeffs *[68][3]fe2, twistPoint *PointG2) {
166	// Algorithm 5 in  https://eprint.iacr.org/2019/077.pdf
167	if e.G2.IsZero(twistPoint) {
168		return
169	}
170	r := new(PointG2).Set(twistPoint)
171	j := 0
172	for i := x.BitLen() - 2; i >= 0; i-- {
173		e.doublingStep(&ellCoeffs[j], r)
174		if x.Bit(i) != 0 {
175			j++
176			ellCoeffs[j] = fe6{}
177			e.additionStep(&ellCoeffs[j], r, twistPoint)
178		}
179		j++
180	}
181}
182
183func (e *Engine) millerLoop(f *fe12) {
184	pairs := e.pairs
185	ellCoeffs := make([][68][3]fe2, len(pairs))
186	for i := 0; i < len(pairs); i++ {
187		e.preCompute(&ellCoeffs[i], pairs[i].g2)
188	}
189	fp12, fp2 := e.fp12, e.fp2
190	t := e.t2
191	f.one()
192	j := 0
193	for i := 62; /* x.BitLen() - 2 */ i >= 0; i-- {
194		if i != 62 {
195			fp12.square(f, f)
196		}
197		for i := 0; i <= len(pairs)-1; i++ {
198			fp2.mulByFq(t[0], &ellCoeffs[i][j][2], &pairs[i].g1[1])
199			fp2.mulByFq(t[1], &ellCoeffs[i][j][1], &pairs[i].g1[0])
200			fp12.mulBy014Assign(f, &ellCoeffs[i][j][0], t[1], t[0])
201		}
202		if x.Bit(i) != 0 {
203			j++
204			for i := 0; i <= len(pairs)-1; i++ {
205				fp2.mulByFq(t[0], &ellCoeffs[i][j][2], &pairs[i].g1[1])
206				fp2.mulByFq(t[1], &ellCoeffs[i][j][1], &pairs[i].g1[0])
207				fp12.mulBy014Assign(f, &ellCoeffs[i][j][0], t[1], t[0])
208			}
209		}
210		j++
211	}
212	fp12.conjugate(f, f)
213}
214
215func (e *Engine) exp(c, a *fe12) {
216	fp12 := e.fp12
217	fp12.cyclotomicExp(c, a, x)
218	fp12.conjugate(c, c)
219}
220
221func (e *Engine) finalExp(f *fe12) {
222	fp12 := e.fp12
223	t := e.t12
224	// easy part
225	fp12.frobeniusMap(&t[0], f, 6)
226	fp12.inverse(&t[1], f)
227	fp12.mul(&t[2], &t[0], &t[1])
228	t[1].set(&t[2])
229	fp12.frobeniusMapAssign(&t[2], 2)
230	fp12.mulAssign(&t[2], &t[1])
231	fp12.cyclotomicSquare(&t[1], &t[2])
232	fp12.conjugate(&t[1], &t[1])
233	// hard part
234	e.exp(&t[3], &t[2])
235	fp12.cyclotomicSquare(&t[4], &t[3])
236	fp12.mul(&t[5], &t[1], &t[3])
237	e.exp(&t[1], &t[5])
238	e.exp(&t[0], &t[1])
239	e.exp(&t[6], &t[0])
240	fp12.mulAssign(&t[6], &t[4])
241	e.exp(&t[4], &t[6])
242	fp12.conjugate(&t[5], &t[5])
243	fp12.mulAssign(&t[4], &t[5])
244	fp12.mulAssign(&t[4], &t[2])
245	fp12.conjugate(&t[5], &t[2])
246	fp12.mulAssign(&t[1], &t[2])
247	fp12.frobeniusMapAssign(&t[1], 3)
248	fp12.mulAssign(&t[6], &t[5])
249	fp12.frobeniusMapAssign(&t[6], 1)
250	fp12.mulAssign(&t[3], &t[0])
251	fp12.frobeniusMapAssign(&t[3], 2)
252	fp12.mulAssign(&t[3], &t[1])
253	fp12.mulAssign(&t[3], &t[6])
254	fp12.mul(f, &t[3], &t[4])
255}
256
257func (e *Engine) calculate() *fe12 {
258	f := e.fp12.one()
259	if len(e.pairs) == 0 {
260		return f
261	}
262	e.millerLoop(f)
263	e.finalExp(f)
264	return f
265}
266
267// Check computes pairing and checks if result is equal to one
268func (e *Engine) Check() bool {
269	return e.calculate().isOne()
270}
271
272// Result computes pairing and returns target group element as result.
273func (e *Engine) Result() *E {
274	r := e.calculate()
275	e.Reset()
276	return r
277}
278
279// GT returns target group instance.
280func (e *Engine) GT() *GT {
281	return NewGT()
282}
283