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$

$$\begin{gathered} E:y^2=x^3+c \\ P=(x,y)\in E \end{gathered}$$ Denote

$$P^{\prime }=(\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^{\prime }$ 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

$$\begin{gathered} \lambda P=P^{\prime } \\ \lambda (x,y)=(\beta x,y) \end{gathered}$$ 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\mathrm{mod}n$$

where the integers

$k_1$ and

$k_2$ are of approximately half the bit length of

$k$.

Then we have,

$$\begin{gathered} kP=k_{1}P+k_2\lambda P \\ kP=k_{1}P+k_2{P}^{\prime } \end{gathered}$$

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^{\prime }$ can be computed efficiently. Compute

$P^{\prime }$ 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