Bitcoin Forum
September 26, 2023, 09:13:25 AM
 News: Latest Bitcoin Core release: 25.0 [Torrent]
 Home Help Search Login Register More
 Pages: [1]
 Author Topic: Using secp256k1 endomorphism  (Read 283 times)
Jean_Luc (OP)
Sr. Member

Offline

Activity: 448
Merit: 692

 July 02, 2020, 08:24:44 PMMerited by ETFbitcoin (3), vapourminer (1)

The existence of the endomorphism is a roughly 20% speedup in a plain multi-exp due to halving the number of doublings. What it does is gives many algorithms which could be batched across multiple point the efficiency they'd have at twice the number of pubkeys.  It's a pretty big speedup and AFAIK at an equivalent level of optimization it makes secp256k1 the fastest to verify of any widely deployed curve. So the motivation there is pretty clear, I think.

Could you give more info on this because I don't see how to have efficient decomposition k.P= (k1+k2.lambda).P using such lambda.
Thanks
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1695719605
Hero Member

Offline

Posts: 1695719605

Ignore
 1695719605

1695719605
 Report to moderator
1695719605
Hero Member

Offline

Posts: 1695719605

Ignore
 1695719605

1695719605
 Report to moderator
gmaxwell
Moderator
Legendary

Offline

Activity: 4018
Merit: 7844

 July 02, 2020, 08:44:10 PMLast edit: July 02, 2020, 09:21:44 PM by gmaxwellMerited by ETFbitcoin (2)

Could you give more info on this because I don't see how to have efficient decomposition k.P= (k1+k2.lambda).P using such lambda.

Sure!

You rewrite   k*P as  k1*P + k2*lambda*P  --  lambda*P is trivial to compute, since its {beta * P.x, P.y} and k1 and k2 are 128-bit numbers instead of 256. Then this sum of products can be computed efficiently using Strauss' algorithm (also called Shamir Trick) or similar.

Here is an implementation that splits k into k1 and k2 for secp256k1: https://github.com/bitcoin-core/secp256k1/blob/master/src/scalar_impl.h#L268  with a couple scalar operations.

The endomorphism optimization in libsecp256k1 is (currently) disabled by default (and can be enabled via a configure option) because it's potentially covered by a patent that expires pretty soon. (I think history suggests that the patent is actually invalid, but the benefit isn't great enough to worry about it).

The implementation in libsecp256k1 is a little more complicated than described above due to some common and some novel optimizations in its version of Strauss' algorithm.  It uses WNAF so it pre-computes a small table of P times odd numbers using an efficient addition ladder. It then performs all the additions over an alternative isomorphic curve so that it's able to treat the precomputed P multiplies as affine points without needing an inverse to reproject them.  As a result the application of beta is done on demand late in the algorithm rather than needing to compute two tables.
Jean_Luc (OP)
Sr. Member

Offline

Activity: 448
Merit: 692

 July 03, 2020, 07:52:19 AM

@gmaxwell
Many thanks
I discovered this book "Guide to Elliptic Curve Cryptography" which is great
Jean_Luc (OP)
Sr. Member

Offline

Activity: 448
Merit: 692

 July 03, 2020, 11:44:30 AMLast edit: July 03, 2020, 12:15:18 PM by Jean_LucMerited by vapourminer (1)

I implemented the algorithm 3.74 of the above book and I found different results:
At iteration #70/#71, I well found the same constants a1 and a2 that are mentioned in the comment of the code.
but b1 and b2 are different and strangely b2=a1 in the comment
I would expect b1 = -1839468DB3DC795B42AD17D3CA5C15137 and b2 = 4A5AC2BF7B5F37F9F1DB10D7A2A9C981.
I didn't check yet g1 and g1 constants.

Code:
* "Guide to Elliptic Curve Cryptography" (Hankerson, Menezes, Vanstone) gives an algorithm
* (algorithm 3.74) to find k1 and k2 given k, such that k1 + k2 * lambda == k mod n, and k1
* and k2 have a small size.
* It relies on constants a1, b1, a2, b2. These constants for the value of lambda above are:
*
* - a1 =      {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}
* - b1 =     -{0xe4,0x43,0x7e,0xd6,0x01,0x0e,0x88,0x28,0x6f,0x54,0x7f,0xa9,0x0a,0xbf,0xe4,0xc3}
* - a2 = {0x01,0x14,0xca,0x50,0xf7,0xa8,0xe2,0xf3,0xf6,0x57,0xc1,0x10,0x8d,0x9d,0x44,0xcf,0xd8}
* - b2 =      {0x30,0x86,0xd2,0x21,0xa7,0xd4,0x6b,0xcd,0xe8,0x6c,0x90,0xe4,0x92,0x84,0xeb,0x15}

Code:
s0=1
t0=0
r0=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

s1=0
t1=1

s2=1
t2=E
r2=5D4F819BEEB6D5E108DABF867C8D2F0842474284DC46CD122CA9B187ECB08EB
...

s70=FCE9B1DD4EB7DD2718A2906787061B2
t70=4A5AC2BF7B5F37F9F1DB10D7A2A9C981
r70=114CA50F7A8E2F3F657C1108D9D44CFD8   (>sqrt(n))

s71=4A5AC2BF7B5F37F9F1DB10D7A2A9C981
r71=3086D221A7D46BCDE86C90E49284EB15  (<sqrt(n))

j2002ba2
Full Member

Offline

Activity: 189
Merit: 399

 July 03, 2020, 01:53:22 PM

@Jean_Luc Your code for EEA seems incorrect. Here are the correct values:
Code:
s70=FCE9B1DD4EB7DD2718A2906787061B2
t70=-3086D221A7D46BCDE86C90E49284EB15
r70=114CA50F7A8E2F3F657C1108D9D44CFD8   (>=sqrt(n))

s71=-4A5AC2BF7B5F37F9F1DB10D7A2A9C981
t71=E4437ED6010E88286F547FA90ABFE4C3
r71=3086D221A7D46BCDE86C90E49284EB15  (<sqrt(n))

r72=2228364F61BCD8F0CDA23C16C0AC386F

Code:
(a1, b1) = (r71, -t71) = (3086D221A7D46BCDE86C90E49284EB15, -E4437ED6010E88286F547FA90ABFE4C3)
(a2, b2) = (r70, -t70) = (114CA50F7A8E2F3F657C1108D9D44CFD8, 3086D221A7D46BCDE86C90E49284EB15)
r70^2 + t70^2 = 13477B4472B4233ECA232A74B45B8E7F37640C02AF64BF4EEAEE3ABED3D0695F9
r72^2 + t72^2 = 159EC1A05B158DF471EAE76C8FA0CDA199E5599D41EC1E5915FBD403A750EC1B31
Jean_Luc (OP)
Sr. Member

Offline

Activity: 448
Merit: 692

 July 03, 2020, 02:29:09 PM

Thanks I found the issue.
COBRAS
Member

Offline

Activity: 756
Merit: 20

 July 03, 2020, 07:05:55 PM

Thanks I found the issue.

Jean_Luc, hi. Then you include endomorfism to yout project - vanitysearch and kangaroo ?

Br

＄＄＄ Ｐ２Ｐ ＮＥＴＷＯＲＫ ＦＯＲ ＢＴＣ ＷＡＬＬＥＴ．ＤＡＴ ＢＲＵＴＥ F ＯＲＣＥ ．ＪＯＩＮ ＮＯＷ＝ＧＥＴ ＭＡＮＹ ＣＯＩＮＳ ＮＯＷ ！！！
https://github.com/phrutis/LostWallet  https://t.me/+2niP9bQ8uu43MDg6
Jean_Luc (OP)
Sr. Member

Offline

Activity: 448
Merit: 692

 July 04, 2020, 07:11:58 AM

Jean_Luc, hi. Then you include endomorfism to yout project - vanitysearch and kangaroo ?

VanitySearch already use endomorphism and for kangaroo, I will see if it is possible to do something but I'm note sure it is possible to define equivalence classes for endomorphism as for symmetry.

Quote
Now we need a rule to define a unique representative for each equivalence class {P,−P}. A simple rule in this case is: treat they-coordinate of P as an integer 0≤yP< qand let the unique representative be (xP,min{yP,q−yP}). The pseudorandomwalk is then defined using the unique equivalence class representative.
https://www.iacr.org/archive/pkc2010/60560372/60560372.pdf

But symmetry is not interesting on large range due to small cycle apparition in random walks. The overhead needed to limit cycle is more than the gain of using equivalence class, especially on GPU where the cache usage can drastically decrease performance.
arulbero
Legendary

Offline

Activity: 1844
Merit: 2017

 July 04, 2020, 07:41:11 AM

But symmetry is not interesting on large range due to small cycle apparition in random walks. The overhead needed to limit cycle is more than the gain of using equivalence class, especially on GPU where the cache usage can drastically decrease performance.

I did some tests with symmetry (python for cpu), with num_jumps = 32 you can get 1.6 / 1.7.sqrt(N) steps (instead of 2.08.sqrt(N)) if the DP is 12 or lower.

With longer paths you have to increase the number of the jumps, and that decreases the performance.
COBRAS
Member

Offline

Activity: 756
Merit: 20

 July 04, 2020, 10:58:13 AMLast edit: July 06, 2020, 01:28:41 AM by gmaxwell

Jean_Luc, hi. Then you include endomorfism to yout project - vanitysearch and kangaroo ?

VanitySearch already use endomorphism and for kangaroo, I will see if it is possible to do something but I'm note sure it is possible to define equivalence classes for endomorphism as for symmetry.

Maybe 128 byte keys is more good I think. 256 byte is harde to fined !!! Implement please endomorphism in Kangaroo Bro ?

＄＄＄ Ｐ２Ｐ ＮＥＴＷＯＲＫ ＦＯＲ ＢＴＣ ＷＡＬＬＥＴ．ＤＡＴ ＢＲＵＴＥ F ＯＲＣＥ ．ＪＯＩＮ ＮＯＷ＝ＧＥＴ ＭＡＮＹ ＣＯＩＮＳ ＮＯＷ ！！！
https://github.com/phrutis/LostWallet  https://t.me/+2niP9bQ8uu43MDg6
gmaxwell
Moderator
Legendary

Offline

Activity: 4018
Merit: 7844

 July 06, 2020, 01:30:05 AM

I'm note sure it is possible to define equivalence classes for endomorphism as for symmetry.
All six points related through negation and endomorphism share the same value for x^3. (see your forum messages from me, from a few months back)
Jean_Luc (OP)
Sr. Member

Offline

Activity: 448
Merit: 692

 July 06, 2020, 05:44:23 AMLast edit: July 06, 2020, 06:09:30 AM by Jean_Luc

All six points related through negation and endomorphism share the same value for x^3. (see your forum messages from me, from a few months back

Yes I know, but I don't see how to use this property in the random walk. For the symmetry you can select the next point according to the sign of the y value and then select always the positive point which divide by 2 the search space. It is easy to calculate the corresponding distance at each step of the random walk but it generates useless cycles.
If I cube the x value of a DP and look for collision on x^3 then the gain is negligible due to the fact that the selection is not done at each step of the random walk.
Any idea would be welcome
arulbero
Legendary

Offline

Activity: 1844
Merit: 2017

 July 06, 2020, 06:09:17 AMLast edit: July 06, 2020, 06:41:49 AM by arulberoMerited by gmaxwell (2), ETFbitcoin (2)

All six points related through negation and endomorphism share the same value for x^3. (see your forum messages from me, from a few months back

Yes I know, but I don't see how to use this property in the random walk. For the symmetry you can select the next point according to the sign of the y value and then select always the positive point which divide by 2 the search space. It is easy to calculate the corresponding distance at each step of the random walk but it generates useless cycles.
If I cube the x value of a DP and look for collision on x^3 then the gain is negligible due to the fact that the selection is not done at each step of the random walk.
Any idea would be welcome

Each step (each jump) must depend on the last bits of x^3 mod p.  But you have no advantage in the search in [-(a+b)/2,(a+b)/2] interval, you have a speedup only in the union of 3 intervals:  [-(a+b)/2,(a+b)/2] U [-lambda*(a+b)/2,lambda*(a+b)/2] U [-lambda^2*(a+b)/2,lambda^2*(a+b)/2]
Jean_Luc (OP)
Sr. Member

Offline

Activity: 448
Merit: 692

 July 06, 2020, 06:57:50 AMMerited by gmaxwell (2), ETFbitcoin (1)

Yes and the overlap between these ranges will be very small unless you search on very large range.
I'm wondering if something can be do using x^(P-1)/3 (mod p) with give 1,beta or beta^2 with uniform distribution.
Of course computing a modexp is expensive but just for try...

Code:
0^((P-1)/3): 0
1^((P-1)/3): 1
2^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
3^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
4^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
5^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
6^((P-1)/3): 1
7^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
8^((P-1)/3): 1
9^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
10^((P-1)/3): 1
11^((P-1)/3): 1
12^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
13^((P-1)/3): 1
14^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
15^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
16^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
17^((P-1)/3): 1
18^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
19^((P-1)/3): 1
20^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
gmaxwell
Moderator
Legendary

Offline

Activity: 4018
Merit: 7844

 July 06, 2020, 07:31:08 AM

Each step (each jump) must depend on the last bits of x^3 mod p.  But you have no advantage in the search in [-(a+b)/2,(a+b)/2] interval, you have a speedup only in the union of 3 intervals:  [-(a+b)/2,(a+b)/2] U [-lambda*(a+b)/2,lambda*(a+b)/2] U [-lambda^2*(a+b)/2,lambda^2*(a+b)/2]
Right.  I don't know a way to use the endomorphism to get a speedup over a single compact interval-- and I somewhat doubt that it's possible.  If it were, then I think in the application of endomorphism to the multiexp it would be possible to recursively apply the endomorphism to decompose to smaller and smaller scalars, but it isn't.

The speedup over the set of three intervals is still potentially interesting:  e.g. imagine you have an elgammal encryption where the decryption leaves with with a point you need to take the discrete log. And you can arrange that the DL is in some small enough range that this isn't unrealistic, and could potentially support the sparse ranges.

This shows up in things like electronic voting or in confidential transactions. (In CT I avoided the need to solve a DL in the receiver by sneaking an encryption of it into a sidechannel in the range proofs).... or just for DL challenge bragging rights.

COBRAS
Member

Offline

Activity: 756
Merit: 20

 July 06, 2020, 09:00:21 AM

Yes and the overlap between these ranges will be very small unless you search on very large range.
I'm wondering if something can be do using x^(P-1)/3 (mod p) with give 1,beta or beta^2 with uniform distribution.
Of course computing a modexp is expensive but just for try...

Code:
0^((P-1)/3): 0
1^((P-1)/3): 1
2^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
3^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
4^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
5^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
6^((P-1)/3): 1
7^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
8^((P-1)/3): 1
9^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
10^((P-1)/3): 1
11^((P-1)/3): 1
12^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
13^((P-1)/3): 1
14^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
15^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
16^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE
17^((P-1)/3): 1
18^((P-1)/3): 851695D49A83F8EF919BB86153CBCB16630FB68AED0A766A3EC693D68E6AFA40
19^((P-1)/3): 1
20^((P-1)/3): 7AE96A2B657C07106E64479EAC3434E99CF0497512F58995C1396C28719501EE

Good Day everybody.

128 bytes is big range i think, if endomorphism can solve so ranges it will be supper. But if no method for solve 128-256 bytes, I think all solutions will hard work with something another then puzzle addresses.

＄＄＄ Ｐ２Ｐ ＮＥＴＷＯＲＫ ＦＯＲ ＢＴＣ ＷＡＬＬＥＴ．ＤＡＴ ＢＲＵＴＥ F ＯＲＣＥ ．ＪＯＩＮ ＮＯＷ＝ＧＥＴ ＭＡＮＹ ＣＯＩＮＳ ＮＯＷ ！！！
https://github.com/phrutis/LostWallet  https://t.me/+2niP9bQ8uu43MDg6
Jean_Luc (OP)
Sr. Member

Offline

Activity: 448
Merit: 692

 July 06, 2020, 09:47:53 AM

A 128bit range compared to a 256bit range is very very small. 340282366920938463463374607431768211456 times smaller
COBRAS
Member

Offline

Activity: 756
Merit: 20

 July 06, 2020, 10:32:55 AM

A 128bit range compared to a 256bit range is very very small. 340282366920938463463374607431768211456 times smaller

Yes, but with endomorphism needed only 128 bytes for solve 256 and only 64 for solve 128 !!!

p.s. and as i know endomorphism +0.7 fester !!!

＄＄＄ Ｐ２Ｐ ＮＥＴＷＯＲＫ ＦＯＲ ＢＴＣ ＷＡＬＬＥＴ．ＤＡＴ ＢＲＵＴＥ F ＯＲＣＥ ．ＪＯＩＮ ＮＯＷ＝ＧＥＴ ＭＡＮＹ ＣＯＩＮＳ ＮＯＷ ！！！
https://github.com/phrutis/LostWallet  https://t.me/+2niP9bQ8uu43MDg6
 Pages: [1]