GLV Decomposition for Multi-Scalar Multiplication (MSM)

GLV Decomposition is an efficient way to calculate point scaling \(kP\). This method was originally published by Gallant, Lambert and Vanstone in 2001 [1], and was later integrated into the Bitcoin core code [2]. However, GLV Decomposition was not enabled in Bitcoin until a patent around the GLV method expired in 2020 [3].

A textbook introduction of enomorphisms of elliptic curves can be found in [4].

Problem

Given scalar \(k\) and EC point \(P\), caculate \(kP\).

Property of Enomorphism

Consider the elliptic curve over field \(\mathbb{F}_p\) \[E: y^2 = x^3 + c\\ P=(x,y) \in E\] Denote \[P' = (\beta x, y)\] If \(\beta\) is a cubic root of the base field \(\mathbb{F}_p\), i.e. \(\beta^3 \equiv 1\) (mod p), we know that \(P'\) is also a point on \(E\) since \(y_1^2 = (\beta x_1)^3 + c\) still holds.

If we can find a scalar \(\lambda\) such that \[ \lambda P = P' \\ \lambda (x, y) = (\beta x, y)\] We can use the GLV method to accerlate the calculation of \(kP\).

NOTE: On a particular elliptic curve, \(\lambda\) and \(\beta\) have to be known before GLV method can be applied, where \(\lambda\) and \(\beta\) are certain cube roots of \(1\) in their respective fields.

GLV Decomposition

We first write \(k\) in the following form \[k = k_1 + \lambda k_2 \mod n\]

where the integers \(k_1\) and \(k_2\) are of approximately half the bit length of \(k\).

Then we have, \[kP = k_1P + k_2 \lambda P\\ kP = k_1P + k_2 P'\]

Since \(k_1\) and \(k_2\) are of half the bit length of \(k\), half of the point doublings are eliminated.

The strategy is effective provided that \(k_1, k_2\) and \(P'\) can be computed efficiently. Compute \(P'\) only needs one muliplication \(\beta x_p\).

Decomposition of Scalars

An efficient algorithm for calculating \(k_1\) and \(k_2\) is listed below [4].

Algorithm: decomposition \(k = k_1 + \lambda k_2\)

Algorithm: Extended Euclidean

Implementation

Barret Reduction

A full explaination of Barret Reduction can be found here.

Reference code can be found in Yrrid's and Gregor's implementations.

Constants

Some demo python code for BLS12-381

>>>p=0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
>>>q=0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
>>>z=0xd201000000010000
>>>R=(2**390) % p
0x15de9967f3e804b29f1457663c4a5eec26c26d0b683dcf80dd9a7e0e882431c84b803379b4800ac4676000000d1ff2e
>>>R2=(R*R) % p
0xf696ee04acd918c979001772d32f70a41442921eed21b145efee07b1df507af6ea66ec3a0132243aec641c34510070f
>>> R_inv = pow(R, -1, p)
0xd5484112463df80cd434d6bbe9713b9de9a046ecb252b97586963f65faad0c9315584492c0c63ebccd2ce0964e00276

>>>lambda1=q-z**2
0xac45a4010001a4020000000100000000
>>>lambda1**3 % q
1
>>>beta1=0x5f19672fdf76ce51ba69c6076a0f77eaddb3a93be6f89688de17d813620a00022e01fffffffefffe
>>>beta1**3 % p
1

>>>lambda2=z**2-1
0xac45a4010001a40200000000ffffffff
>>>lambda2**3 % q
1
>>>beta2=0x1a0111ea397fe699ec02408663d4de85aa0d857d89759ad4897d29650fb85f9b409427eb4f49fffd8bfd00000000aaac
>>>beta2**3 % p
1
>>>beta2_mont = (beta2 * R) % p
0x9c6d4856567dd7d18c86532eb0c0550bd16b0d267fd6ffa856e7b9a191c3ebc1bcc91d7b26574c3ef2f79219c907181

>>> inv_approx = hex(2**256 // lambda2)
'0x17c6becf1e01faadd63f6e522f6cfee30'

Beta in montegomery form in Niall's code and Gregor's code

References

[1] Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone, Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms, 2001

[2] https://www.btctimes.com/news/bitcoin-upgrade-glv-enomorphism-tests-show-faster-verification

[3] https://patents.google.com/patent/US7110538B2/en

[4] Darrel Hankerson, Alfred J. Menezes, Scott Vanstone, Guide to Elliptic Curve Cryptography, 2004

[5] bls12-381/glv.go

[6] Barret Reduction

tags: msm zkp public