**Halo2 Circuit Development: Sin7Y Tech Review (20)**

Multi-Scalar Multiplication (MSM) is the algorithm for calculating the sum of multiple scalar multiplications. Usually, G is a cyclic group defined on the elliptic curve of y^2=x^3+ax+b on the finite field of F_p. If the group operation is conducted by the plain algorithm of fast exponentiation, the number of group operations needed for every a_i.P_i is 1.5bn times on average.

Sin7Y is a tech team that explores layer 2, cross-chain, ZK, and privacy computing. #WHAT IS HAPPENING IN BLOCKCHAIN#

Let * G* be a cyclic group,

We can split the * b* bit scalar into c width windows: reduce the scalar to

Here, **Q_j=∑_{i=1}^{n**} * a_{i j} P_{i}*, so we reduce the original algorithm issue of

For example, when **c = 3**, it is calculated as:

When calculating **∑kS_k**, set the partial sum T_l=S_l+⋯+S_k, then

However, the operation results of * T_l* can be obtained through the recurrence sequence

In summary, we can conclude that the total number of group operations required by the method of the Windowing Technique of a width of * c* is

Set **c = logn**, then the number of group operations is **2bn/logn**. When **n≈10^5** , the number of group operations reduces to **1/12** of its original value.

For the cyclic group * G* on the elliptic curve

When **λ = −1, α = 1, β = −1**. The reverse value of one point can be obtained only by taking the opposite number from the ordinate. Based on this feature, in the plain fast exponentiation algorithm, the scalar can be written into the non-adjacent form (NAF), namely ** ∑e_{i}.2^{i}, e_{i} ∈ {−1,0,1}** and any two adjacent

conduct the following operation:

The result of **a_i=∑_{j=0}^{b / c-1} a’_{i, j}^2^{j c}** and -**2^{c-1} <= a’_{i, j}^ <= 2^{c-1}** can be obtained. Since the complexity of addition and subtraction in group operation of an elliptic curve is the same, we can put these terms into a bucket according to the absolute value of scalars. Therefore, the number of groups can be reduced from the original 2c to **2^c** , and the overall number of group operations required is reduced from (1) to:

If the parameters of the elliptic curve are special, for example, the BLS curve can be written as * y^2=x^3+b*, and

Algorithm 1: Signed Digits

In addition, **λ3 ≡ 1(mod |G| )**. Then the multiplication operation can be optimized as follows:

From [1], we can find a small enough scalar |**m1**|, |**m2**|<√**G** to make the above equation true, which gives us a way to reduce the multiplication of bb bits into the multiplication of two **b/2** bits. Use it into the Windowing Technique, and the number of group operations is reduced to

In summary, both the above two optimization methods can reduce the number of group operations by **5.5%** when **n=10^5**.

[1] Francesco Sica, Mathieu Ciet, and Jean-Jacques Quisquater. Analysis of the gallant-lambert-vanstone method based on eﬀicient endomorphisms: Elliptic and hyperelliptic curves. In International Workshop on Selected Areas in Cryptography, pages 21–36. Springer, 2002.

L O A D I N G

. . . comments & more!

. . . comments & more!