Eth2.0-specs: Alternative G2 Co-Factor

[nisdas]

After some discussion with @herumi, he brought a potential optimization when hashing to G2. Currently when hashing a binary string to G2, we multiply it by a large co-factor which is computationally expensive to perform.

However we can utilize a faster co-factor for this based on this paper by Burdoni and Pintore

        Q = (z(z-1)-1)P + Frob((z-1)P) + Frob^2(2P)
        fast-cofactor = org-cofactor * X, where X is a fixed constant.

An implementation of the algorithm is over here .

However the downside that with using the faster co-factor, the value of MapToG2 changes correspondingly.

[herumi]

FYI
I've found and implemented using a faster co-factor algorithm without modifying eth2 spec. @nisdas benchmark result.

The idea is the followings:

P; the base point in G1
g2cofactorAdj ; a constant value in Fr

sec; secret key in Fr
pub = P * sec ; public key in G1

MapToG2(msg) = MapToG2fast(msg) * g2cofactorAdj ; requires one scalar multiplication of G2

Sign(sec, msg) = sec * MapToG2(msg)                     ; (1)
             = (sec * g2cofactroAdj) * MapToG2fast(msg) ; (2) is 1.8 times faster than (1) because Fr multiplication is very faster than G2 scalar multiplication.

sig = sec * MapToG2(msg)

Verify(pub, sig, msg) check
    e(P, sig) == e(pub, MapToG2(msg))
<=> e(P, sig) == e(pub,  MapToG2fast(msg) * g2cofactorAdj)
<=> e((1/g2cofactorAdj) * P, sig) == e(pub, MapToG2fast(msg))

Then let set PadjInv := (1/g2cofactorAdj) * P, then we can check e(PadjInv, sig) == e(pub, MapToG2fast(msg)), which is the same cost of using MapToG2 .

[JustinDrake]

the value of MapToG2 changes correspondingly

We don't want to deviate from the BLS standard :)

I've found and implemented using a faster co-factor algorithm without modifying eth2 spec.

Yay! Closing this issue.