G1 point `-xp` and `-yp` can be precomputed before miller loop
Closed this issue · 0 comments
IAvecilla commented
Context: EcPairing.yul#L1474
Description: We can use precomputed values of G1 point coordinates to optimize gas usage by the main loop Recommendation: Precompute -xp and -yp values before main loop and adjust adding and doubling formulas accordingly.
diff --git a/precompiles/EcPairing.yul b/precompiles/EcPairing.yul
index d9e08c5..2f2b1e6 100644
--- a/precompiles/EcPairing.yul
+++ b/precompiles/EcPairing.yul
@@ -1309,7 +1309,8 @@ object "EcPairing" {
t130, t131 := fp2Add(t130, t131, t120, t121)
// l0
- l00, l01 := fp2Neg(t80, t81)
+ l00 := t80
+ l01 := t81
l10 := zero
l11 := zero
l20 := zero
@@ -1389,7 +1390,8 @@ object "EcPairing" {
l21 := zero
// l1
- l30, l31 := fp2Neg(t10, t11)
+ l30 := t10
+ l31 := t11
// l2
l40 := t90
@@ -1504,11 +1506,13 @@ object "EcPairing" {
let naf := NAF_REPRESENTATIVE()
let n_iter := 63
let l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51 := FP12_ONE()
+ let myp := montgomerySub(0, yp)
+ let mxp := montgomerySub(0, xp)
// Computes the first iteration of Millers loop outside to avoid unecesariy square
// NAF[64] == 0
l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51, t00, t01, t10, t11, t20, t21 := doubleStep(t00, t01, t10, t11, t20, t21)
- l00, l01 := fp2ScalarMul(l00, l01, yp)
+ l00, l01 := fp2ScalarMul(l00, l01, myp)
l30, l31 := fp2ScalarMul(l30, l31, xp)
f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121 := fp12Mul(f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121, l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51)
@@ -1523,14 +1527,14 @@ object "EcPairing" {
f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121 := fp12Mul(f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121, l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51)
l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51, t00, t01, t10, t11, t20, t21 := mixedAdditionStep(xq0, xq1, yq0, yq1, t00, t01, t10, t11, t20, t21)
l00, l01 := fp2ScalarMul(l00, l01, yp)
- l30, l31 := fp2ScalarMul(l30, l31, xp)
+ l30, l31 := fp2ScalarMul(l30, l31, mxp)
f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121 := fp12Mul(f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121, l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51)
for {let i := 0} lt(i, n_iter) { i := add(i, 1) } {
f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121 := fp12Square(f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121)
l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51, t00, t01, t10, t11, t20, t21 := doubleStep(t00, t01, t10, t11, t20, t21)
- l00, l01 := fp2ScalarMul(l00, l01, yp)
+ l00, l01 := fp2ScalarMul(l00, l01, myp)
l30, l31 := fp2ScalarMul(l30, l31, xp)
f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121 := fp12Mul(f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121, l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51)
@@ -1538,7 +1542,7 @@ object "EcPairing" {
if and(naf, 2) {
l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51, t00, t01, t10, t11, t20, t21 := mixedAdditionStep(xq0, xq1, yq0, yq1, t00, t01, t10, t11, t20, t21)
l00, l01 := fp2ScalarMul(l00, l01, yp)
- l30, l31 := fp2ScalarMul(l30, l31, xp)
+ l30, l31 := fp2ScalarMul(l30, l31, mxp)
f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121 := fp12Mul(f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121, l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51)
}
@@ -1546,7 +1550,7 @@ object "EcPairing" {
if and(naf, 4) {
l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51, t00, t01, t10, t11, t20, t21 := mixedAdditionStep(mq00, mq01, mq10, mq11, t00, t01, t10, t11, t20, t21)
l00, l01 := fp2ScalarMul(l00, l01, yp)
- l30, l31 := fp2ScalarMul(l30, l31, xp)
+ l30, l31 := fp2ScalarMul(l30, l31, mxp)
f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121 := fp12Mul(f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121, l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51)
}
@@ -1564,12 +1568,12 @@ object "EcPairing" {
l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51, t00, t01, t10, t11, t20, t21 := mixedAdditionStep(r00, r01, r10, r11, t00, t01, t10, t11, t20, t21)
l00, l01 := fp2ScalarMul(l00, l01, yp)
- l30, l31 := fp2ScalarMul(l30, l31, xp)
+ l30, l31 := fp2ScalarMul(l30, l31, mxp)
f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121 := fp12Mul(f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121, l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51)
l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51, t00, t01, t10, t11, t20, t21 := mixedAdditionStep(r20, r21, r30, r31, t00, t01, t10, t11, t20, t21)
l00, l01 := fp2ScalarMul(l00, l01, yp)
- l30, l31 := fp2ScalarMul(l30, l31, xp)
+ l30, l31 := fp2ScalarMul(l30, l31, mxp)
f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121 := fp12Mul(f000, f001, f010, f011, f020, f021, f100, f101, f110, f111, f120, f121, l00, l01, l10, l11, l20, l21, l30, l31, l40, l41, l50, l51)
}
GAS consumption comparison for ecpairing_two_point_match_3: before: 9179324 after: 9162460
zkSync:
Spearbit: