# 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$ ![Decomposition: $k = k_1 + \lambda k_2$](https://i.imgur.com/lmMQESr.png) Algorithm: Extended Euclidean ![Extended Euclidean](https://i.imgur.com/6qx2uYq.png) ## Implementation ### Barret Reduction A full explaination of Barret Reduction can be found [here](https://hackmd.io/@chaosma/SyAvcYFxh). Reference code can be found in [Yrrid's](https://github.com/yrrid/submission-wasm-msm/blob/a4a753b09ae37ba9699da08c1eb5e0af5b3346d6/C/LambdaQR.c#L105) and [Gregor's](https://github.com/mitschabaude/montgomery/blob/34bc6374312e69cb3c68b6b8e256998da96acc30/src/finite-field-generate.js#L1368) implementations. ### Constants Some demo python code for BLS12-381 ```python >>>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](https://github.com/yrrid/submission-wasm-msm/blob/a4a753b09ae37ba9699da08c1eb5e0af5b3346d6/C/Field.c#L48) and [Gregor's code](https://github.com/mitschabaude/montgomery/blob/34bc6374312e69cb3c68b6b8e256998da96acc30/src/wasm/finite-field.wat#L6262) ## References [1] Robert P. Gallant, Robert J. Lambert, and Scott A. Vanstone, [Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms](https://www.iacr.org/archive/crypto2001/21390189.pdf), 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_](https://link.springer.com/book/10.1007/b97644), 2004 [5] [bls12-381/glv.go](https://github.com/kilic/bls12-381/blob/ca162e8a70f456f4cf733097edfd60d0e9deca2c/glv.go#L7) [6] [Barret Reduction](https://hackmd.io/@chaosma/SyAvcYFxh) ###### tags: `msm` `zkp` `public`
Last changed by  
 
drouyang.eth
Co-founder @ Snarkify Network, Former FB Research Scientist, Ph.D. in Operating Systems
1122

Read more

Signed Bucket Indexes for Multi-Scalar Multiplication (MSM)

If we treat bucket indexes as signed integers, we are able to saves one bit in bucket index encoding, and therefore reduce number of buckets and bucket memory usage by half. The method is denoted as the signed-bucket-index method, and also known as NAF method. This method was reported in [1] and implemented by top-2 performers of the zPrize MSM-WASM track.

10/25/2023
Optimizing Multi-Scalar Multiplication (MSM): Learning from ZPRIZE

The following algorithms and techniques are used by the top-2 performers of ZPrize 2022 MSM-WSAM track.

10/25/2023
Pippenger Algorithm for Multi-Scalar Multiplication (MSM)

Problem Give $n$ scalars ${k_i}$ and $n$ EC points ${P_i}$, calculate $P$ such that $$P=\sum_{i=0}^n k_i P_i$$ The Pippenger / Bucket Algorithm Step 1: partition scalars into windows Let's first partition each scalar into $m$ windows each has $w$ bits, then $$k_i = k_{i,0} + k_{i,1} 2^{w} + ... + k_{i,(m-1)} 2^{(m-1)w}$$ You can think each scalar $k_i$ as a bignum and representing it as a multi-precision integer with limb size $w$.

10/1/2023
Montgomery Multiplication

Algorithm Consider prime field $\mathbb{F}_p$, select power of two $2^w$ such that $R=2^w > p$, we know that mod by R can be computed by bit shifting. Montgomery Form For $x \in \mathbb{F}_p$, define Montgomery form of $x$ as, $$\bar{x} = xR \pmod p$$ Transform To Montgomery Form Transforming $x$ to Montgomery form can be done by left-shift $x$ by $w$ and reduce modulo $p$. In practice, $x$ and $y$ are transformed to Montgomery form at the beginning of a computation, and transformed back at the end.

2/27/2023
Read more from drouyang.eth
Published on HackMD