How the GLV Endomorphism Speeds Up Scalar Multiplication in libsecp256k1
The GLV (Gallant-Lambert-Vanstone) endomorphism is a mathematical optimization to accelerate the scalar multiplication defined by Q=kPQ=kP in the secp256k1 curve. It basically transforms a 256-bit scalar multiplication into two 128-bit scalars. This only works because of some special algebraic relation in the specific curve secp256k1.
And this goes on for as much as you need. So the dumb algorithm would be to add QQ to itself kk times. The optimized strategy would be to do something like this:
2Q=Q+Q2Q=Q+Q 4Q=2Q+2Q4Q=2Q+2Q
Two doublings and zero additions instead of four additions. Every time we add the same number like this 2Q=Q+Q2Q=Q+Q we call that a doubling, and adding different points (3Q=2Q+Q3Q=2Q+Q) we call addition.
Let's take the number 1313 for example. We could use the dumb method and just perform 1212 additions of QQ, or we could use a more optimized algorithm:
So instead of 1212 operations, we got 33 doublings and 22 additions, a total of only five operations! The number 1313 in binary can be represented by 1101, a 4 bit number, which can be written by adding base 2 exponents:
The bits 1 tell us to use that base 2 exponent and the bits 0 tell us to ditch it. I guess it's easier to see now that we got 2 additions and 3 doublings.
Let's calculate 1313 as an example:
13=110113=1101
The first bit is 1, so we start with:
R=QR=Q
The next bit is also 1, so we double it and add QQ:
R=2R=2QR=2R=2Q R=2Q+QR=2Q+Q
Now the next bit is 0, we only double it and do not add anything:
So the algorithm can be reduced by those two rules:
For each bit double
If the bit is 1, add
Just to be clear on why reading the binary to perform the operations works. Multiply by 2 is equivalent to a bit-shift to the left, meaning that if we start with a bit 1 and multiply by 2 we get 10, then the next bit is 1 and we add. The next bit is 0, so we multiply by 2 and get 110, since it is 0 we don't add. The last bit is 1, multiply by 2 and we get 1100, then we add, and finally get 1101.
If kk has mm bits, we don't do anything for the first bit, and we need to double every time for the rest of the bits, so the number of doublings:
doublings=m−1doublings=m-1
The number of additions is dependent entirely on the number of bits 1 we got in the number, however the first bit is used to initialize things, so it doesn't count.
additions=weight(k)−1additions=weight(k)-1
where weight(k)weight(k) simply means how many bits 1 we got in the binary representation of the number (kk).
For scalar multiplication in libsecp we are dealing with 256-bit numbers, so in the worst case scenario we could be dealing with 255255 doublings, and for a random chosen number we could hope to get roughly half the bits being 1, so 256/2≈127256/2\approx127 (This is to exemplify the "roughly" half, of course 256/2256/2 is 128 duh) and 255 additions for the 2256−12^{256}-1 number. In total we could get something like 255 doublings and something around 127 or 128 additions, a total of 382 or 383 operations performed.
A morphism is a structure-preserving transformation from one object to another. In programming it represents a function that takes an input of one type and returns an output of a different type, preserving the underlying logic or data structure. For example, mapping a list of integers to a list of strings.
A group homomorphism is a map that preserves the group operation:
ϕ(P+Q)=ϕ(P)+ϕ(Q)\phi(P+Q)=\phi(P)+\phi(Q)
An endomorphism is a specific kind of morphism where the source and the target are the exact same object. The prefix "endo" means inside, within, so an endomorphism is a journey from A to A, instead of one from A to B.
A⟹AA\Longrightarrow A
Or, better, can be defined as a homomorphism from a group to itself:
Regarding ECC and libsecp256k1, the endomorphism is a way to represent something in another way, still keeping the same type, meaning being the same thing, however, that other representation that keeps everything the same, can give us some advantages regarding the speed of calculations. That is the main point behind the GLV endomorphism.
There exists a special symmetry in the curve secp256k1 that allows us to find two numbers, β\beta and λ\lambda that "live" in two different worlds but are connected in an advantageous way for us.
Our curve is formulated by the following short Weierstrass equation:
y2=x3+ax+by^2=x^3+ax+b
Where for secp256k1 a=0a=0:
y2=x3+7y^2=x^3+7
So here for every xx we need to find a corresponding yy that fits the equation, and that the xx can result in a quadratic residue. The coordinates are elements of the field Fp\mathbb F_p and are operated modulo pp.
y2=x3+7(modp)y^2=x^3+7\pmod p
So we get a bunch of pairs (x,y)(x,y) that fit the curve. The values xx and yy live in this finite field, so we call them field elements.
So in our finite field we have pp elements, meaning that for a pair of elements (x,y)(x,y) we have p2p^2 possible pairs/coordinates. However, given a fixed xx, if we use the curve equation and try to calculate roots for yy, we get two possible outcomes, either we have zero solutions or we have two (a quadratic residue). If we take a given xx and
y2=x3+7y^2=x^3+7
Then the right side of the equation becomes just a number, let's call it rr.
r=x3+7(modp)r=x^3+7\pmod p
Then we need to find a yy that satisfies it:
y2=r(modp)y^2=r\pmod p
and rr needs to be a quadratic residue in order for that xx to produce a valid point on the curve. A quadratic residue is a number that is the square of another number modulo pp. So, rr needs to be a quadratic residue in order for a corresponding yy to exist modulo pp.
For each rr, we can have 0, 1, or 2 solutions for yy. On our curve we mostly get two cases for r≠0r\neq0, either 0 solutions or 2 solutions, which is the case of a quadratic residue.
Exactly half of the nonzero values of Fp\mathbb F_p are quadratic residues, however our equation x3+7x^3+7 does not necessarily balance them in a 50/50 proportion so we can say that approximately half the elements of Fp\mathbb F_p when put through x3+7x^3+7 will land on quadratic residues.
Hasse's theorem makes this intuition rigorous by bounding how far the actual count can deviate from p+1p+1. Then the number of possible valid points we have is closer to pp.
To give a more intuitive look, we have approximately p/2p/2 possible xx-values that result in quadratic residues, and each such xx gives 2 possible yy-values, so:
p2⋅2≈p\frac p2\cdot2\approx p
Then all the valid coordinates/points (x,y)(x,y) we have are about pp, and the group order of points is nn, which is n≈pn\approx p.
Now we've got a bunch of pairs (x,y)(x,y) that fit the equation, let's call it E(Fp)E(\mathbb F_p), meaning all the points generated by the equation modulo pp plus the infinity point.
Hasse's theorem gives us an interval. So the number of points we have (plus the infinity point) is approximately p+1p+1.
However, it's not as if we could predict that half the xx of pp are quadratic residues; it's not a 50/50 thing. This is just an estimate. Then we get to Hasse.
Hasse's theorem gives a tight bound on the number of points of an elliptic curve over a finite field Fp\mathbb F_p:
∣#E(Fp)−(p+1)∣≤2p\left|#E(\mathbb F_p)-(p+1)\right|\leq2\sqrt p
So basically Hasse's theorem tells us that the number of points on the curve cannot deviate from our estimate by more than 2p2\sqrt p.
Related to it there is a quantity called trace of Frobenius, which tells us how much the actual number of points deviates from our approximate estimate.
For secp256k1, the exact order of the curve is nn, and we have a very nice property, which is the cofactor being 1:
h=#E(Fp)n=1h=\frac{#E(\mathbb F_p)}n=1
And this leads to the number of coordinates from quadratic residues plus the infinity point being equal to the group order nn:
#E(Fp)=n#E(\mathbb F_p)=n
This matters for the GLV endomorphism because it means that the entire group of curve points is the cyclic subgroup generated by GG. Therefore, every point QQ can be written as
Q=[q]GQ=[q]G
As a result, the endomorphism
ϕ(Q)=(βx,y)\phi(Q)=(\beta x,y)
can be represented consistently as scalar multiplication by a single value λ\lambda:
The whole idea is that we can find a relation like this that allows us to replace a scalar multiplication of group elements bounded by the order nn with another operation on the field elements plane bounded by pp:
λP=(βPx,Py)\lambda P=(\beta P_x,P_y)
Given kk, our scalar, and PP our point in the curve:
k⋅Pk\cdot P
By separating the 256-bit scalar kk into two smaller parts and also applying GLV:
k=k1+λk2(modn)k=k_1+\lambda k_2\pmod n
where both k1k_1 and k2k_2 are only about 128 bits.
Then:
k⋅P=(k1+λk2)⋅Pk\cdot P=(k_1+\lambda k_2)\cdot P k⋅P=k1⋅P+k2(λ⋅P)k\cdot P=k_1\cd
Intuition about the GLV endomorphism on secp256k1
How the GLV Endomorphism Speeds Up Scalar Multiplication in libsecp256k1
The GLV (Gallant-Lambert-Vanstone) endomorphism is a mathematical optimization to accelerate the scalar multiplication defined by Q=kPQ=kP in the secp256k1 curve. It basically transforms a 256-bit scalar multiplication into two 128-bit scalars. This only works because of some special algebraic relation in the specific curve secp256k1.
The problem of scalar multiplication
In ECC we can add points like this:
2Q=Q+Q2Q=Q+Q 3Q=Q+Q+Q3Q=Q+Q+Q 4Q=Q+Q+Q+Q4Q=Q+Q+Q+Q
And this goes on for as much as you need. So the dumb algorithm would be to add QQ to itself kk times. The optimized strategy would be to do something like this:
2Q=Q+Q2Q=Q+Q 4Q=2Q+2Q4Q=2Q+2Q
Two doublings and zero additions instead of four additions. Every time we add the same number like this 2Q=Q+Q2Q=Q+Q we call that a doubling, and adding different points (3Q=2Q+Q3Q=2Q+Q) we call addition.
Let's take the number 1313 for example. We could use the dumb method and just perform 1212 additions of QQ, or we could use a more optimized algorithm:
2Q=Q+Q2Q=Q+Q 4Q=2Q+2Q4Q=2Q+2Q 8Q=4Q+4Q8Q=4Q+4Q 12Q=8Q+4Q12Q=8Q+4Q 13Q=12Q+Q13Q=12Q+Q
So instead of 1212 operations, we got 33 doublings and 22 additions, a total of only five operations! The number 1313 in binary can be represented by 1101, a 4 bit number, which can be written by adding base 2 exponents:
13=8+4+1⟹13=1⋅23+1⋅22+0⋅21+1⋅2013=8+4+1\Longrightarrow13=1\cdot2^3+1\cdot2^2+0\cdot2^1+1\cdot2^0
The bits 1 tell us to use that base 2 exponent and the bits 0 tell us to ditch it. I guess it's easier to see now that we got 2 additions and 3 doublings.
Let's calculate 1313 as an example:
13=110113=1101
The first bit is 1, so we start with:
R=QR=Q
The next bit is also 1, so we double it and add QQ:
R=2R=2QR=2R=2Q R=2Q+QR=2Q+Q
Now the next bit is 0, we only double it and do not add anything:
R=2(3Q)=6QR=2(3Q)=6Q
The last bit is 1 again, so we double it and add:
R=2(6Q)=12QR=2(6Q)=12Q R=12Q+Q=13QR=12Q+Q=13Q R=13QR=13Q
So the algorithm can be reduced by those two rules:
Just to be clear on why reading the binary to perform the operations works. Multiply by 2 is equivalent to a bit-shift to the left, meaning that if we start with a bit 1 and multiply by 2 we get 10, then the next bit is 1 and we add. The next bit is 0, so we multiply by 2 and get 110, since it is 0 we don't add. The last bit is 1, multiply by 2 and we get 1100, then we add, and finally get 1101.
The number of steps
If kk has mm bits, we don't do anything for the first bit, and we need to double every time for the rest of the bits, so the number of doublings:
doublings=m−1doublings=m-1
The number of additions is dependent entirely on the number of bits 1 we got in the number, however the first bit is used to initialize things, so it doesn't count.
additions=weight(k)−1additions=weight(k)-1
where weight(k)weight(k) simply means how many bits 1 we got in the binary representation of the number (kk).
secp256k1 speed and steps
For scalar multiplication in libsecp we are dealing with 256-bit numbers, so in the worst case scenario we could be dealing with 255255 doublings, and for a random chosen number we could hope to get roughly half the bits being 1, so 256/2≈127256/2\approx127 (This is to exemplify the "roughly" half, of course 256/2256/2 is 128 duh) and 255 additions for the 2256−12^{256}-1 number. In total we could get something like 255 doublings and something around 127 or 128 additions, a total of 382 or 383 operations performed.
What is an endomorphism
A morphism is a structure-preserving transformation from one object to another. In programming it represents a function that takes an input of one type and returns an output of a different type, preserving the underlying logic or data structure. For example, mapping a list of integers to a list of strings.
A group homomorphism is a map that preserves the group operation:
ϕ(P+Q)=ϕ(P)+ϕ(Q)\phi(P+Q)=\phi(P)+\phi(Q)
An endomorphism is a specific kind of morphism where the source and the target are the exact same object. The prefix "endo" means inside, within, so an endomorphism is a journey from A to A, instead of one from A to B.
A⟹AA\Longrightarrow A
Or, better, can be defined as a homomorphism from a group to itself:
ϕ:E(Fp)→E(Fp)\phi:E(\mathbb F_p)\rightarrow E(\mathbb F_p)
Regarding ECC and libsecp256k1, the endomorphism is a way to represent something in another way, still keeping the same type, meaning being the same thing, however, that other representation that keeps everything the same, can give us some advantages regarding the speed of calculations. That is the main point behind the GLV endomorphism.
Special symmetry of secp256k1
There exists a special symmetry in the curve secp256k1 that allows us to find two numbers, β\beta and λ\lambda that "live" in two different worlds but are connected in an advantageous way for us.
Two different worlds
Our curve is formulated by the following short Weierstrass equation:
y2=x3+ax+by^2=x^3+ax+b
Where for secp256k1 a=0a=0:
y2=x3+7y^2=x^3+7
So here for every xx we need to find a corresponding yy that fits the equation, and that the xx can result in a quadratic residue. The coordinates are elements of the field Fp\mathbb F_p and are operated modulo pp.
y2=x3+7(modp)y^2=x^3+7\pmod p
So we get a bunch of pairs (x,y)(x,y) that fit the curve. The values xx and yy live in this finite field, so we call them field elements.
Hasse's theorem
So in our finite field we have pp elements, meaning that for a pair of elements (x,y)(x,y) we have p2p^2 possible pairs/coordinates. However, given a fixed xx, if we use the curve equation and try to calculate roots for yy, we get two possible outcomes, either we have zero solutions or we have two (a quadratic residue). If we take a given xx and
y2=x3+7y^2=x^3+7
Then the right side of the equation becomes just a number, let's call it rr.
r=x3+7(modp)r=x^3+7\pmod p
Then we need to find a yy that satisfies it:
y2=r(modp)y^2=r\pmod p
and rr needs to be a quadratic residue in order for that xx to produce a valid point on the curve. A quadratic residue is a number that is the square of another number modulo pp. So, rr needs to be a quadratic residue in order for a corresponding yy to exist modulo pp.
For each rr, we can have 0, 1, or 2 solutions for yy. On our curve we mostly get two cases for r≠0r\neq0, either 0 solutions or 2 solutions, which is the case of a quadratic residue.
Exactly half of the nonzero values of Fp\mathbb F_p are quadratic residues, however our equation x3+7x^3+7 does not necessarily balance them in a 50/50 proportion so we can say that approximately half the elements of Fp\mathbb F_p when put through x3+7x^3+7 will land on quadratic residues.
Hasse's theorem makes this intuition rigorous by bounding how far the actual count can deviate from p+1p+1. Then the number of possible valid points we have is closer to pp.
To give a more intuitive look, we have approximately p/2p/2 possible xx-values that result in quadratic residues, and each such xx gives 2 possible yy-values, so:
p2⋅2≈p\frac p2\cdot2\approx p
Then all the valid coordinates/points (x,y)(x,y) we have are about pp, and the group order of points is nn, which is n≈pn\approx p.
Now we've got a bunch of pairs (x,y)(x,y) that fit the equation, let's call it E(Fp)E(\mathbb F_p), meaning all the points generated by the equation modulo pp plus the infinity point.
Hasse's theorem gives us an interval. So the number of points we have (plus the infinity point) is approximately p+1p+1.
However, it's not as if we could predict that half the xx of pp are quadratic residues; it's not a 50/50 thing. This is just an estimate. Then we get to Hasse.
Hasse's theorem gives a tight bound on the number of points of an elliptic curve over a finite field Fp\mathbb F_p:
∣#E(Fp)−(p+1)∣≤2p\left|#E(\mathbb F_p)-(p+1)\right|\leq2\sqrt p
So basically Hasse's theorem tells us that the number of points on the curve cannot deviate from our estimate by more than 2p2\sqrt p.
Related to it there is a quantity called trace of Frobenius, which tells us how much the actual number of points deviates from our approximate estimate.
t=(p+1)−#E(Fp)t=(p+1)-#E(\mathbb F_p) #E(Fp)=p+1−t#E(\mathbb F_p)=p+1-t
And Hasse tells us that:
∣t∣≤2p|t|\leq2\sqrt p
For secp256k1, the exact order of the curve is nn, and we have a very nice property, which is the cofactor being 1:
h=#E(Fp)n=1h=\frac{#E(\mathbb F_p)}n=1
And this leads to the number of coordinates from quadratic residues plus the infinity point being equal to the group order nn:
#E(Fp)=n#E(\mathbb F_p)=n
This matters for the GLV endomorphism because it means that the entire group of curve points is the cyclic subgroup generated by GG. Therefore, every point QQ can be written as
Q=[q]GQ=[q]G
As a result, the endomorphism
ϕ(Q)=(βx,y)\phi(Q)=(\beta x,y)
can be represented consistently as scalar multiplication by a single value λ\lambda:
ϕ(Q)=[λ]Q\phi(Q)=[\lambda]Q
for every point in the group.
What is GLV
The whole idea is that we can find a relation like this that allows us to replace a scalar multiplication of group elements bounded by the order nn with another operation on the field elements plane bounded by pp:
λP=(βPx,Py)\lambda P=(\beta P_x,P_y)
Given kk, our scalar, and PP our point in the curve:
k⋅Pk\cdot P
By separating the 256-bit scalar kk into two smaller parts and also applying GLV:
k=k1+λk2(modn)k=k_1+\lambda k_2\pmod n
where both k1k_1 and k2k_2 are only about 128 bits.
Then:
k⋅P=(k1+λk2)⋅Pk\cdot P=(k_1+\lambda k_2)\cdot P k⋅P=k1⋅P+k2(λ⋅P)k\cdot P=k_1\cd