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

Activity: 448
Merit: 692


View Profile
July 02, 2020, 08:24:44 PM
Merited by ETFbitcoin (3), vapourminer (1)
 #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
1695724484
Hero Member
*
Offline Offline

Posts: 1695724484

View Profile Personal Message (Offline)

Ignore
1695724484
Reply with quote  #2

1695724484
Report to moderator
1695724484
Hero Member
*
Offline Offline

Posts: 1695724484

View Profile Personal Message (Offline)

Ignore
1695724484
Reply with quote  #2

1695724484
Report to moderator
"Bitcoin: the cutting edge of begging technology." -- Giraffe.BTC
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction.
1695724484
Hero Member
*
Offline Offline

Posts: 1695724484

View Profile Personal Message (Offline)

Ignore
1695724484
Reply with quote  #2

1695724484
Report to moderator
1695724484
Hero Member
*
Offline Offline

Posts: 1695724484

View Profile Personal Message (Offline)

Ignore
1695724484
Reply with quote  #2

1695724484
Report to moderator
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4018
Merit: 7844



View Profile WWW
July 02, 2020, 08:44:10 PM
Last edit: July 02, 2020, 09:21:44 PM by gmaxwell
Merited by ETFbitcoin (2)
 #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 Offline

Activity: 448
Merit: 692


View Profile
July 03, 2020, 07:52:19 AM
 #3

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

Activity: 448
Merit: 692


View Profile
July 03, 2020, 11:44:30 AM
Last edit: July 03, 2020, 12:15:18 PM by Jean_Luc
Merited by vapourminer (1)
 #4

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 Huh
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
r1=5363AD4CC05C30E0A5261C028812645A122E22EA20816678DF02967C1B23BD72

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

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

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

j2002ba2
Full Member
***
Offline Offline

Activity: 189
Merit: 399


View Profile
July 03, 2020, 01:53:22 PM
 #5

@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))

s72=1839468DB3DC795B42AD17D3CA5C15137
t72=-4A5D84C4FAD1D149815130F31C84462E4
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 Offline

Activity: 448
Merit: 692


View Profile
July 03, 2020, 02:29:09 PM
 #6

Thanks Wink I found the issue.
COBRAS
Member
**
Offline Offline

Activity: 756
Merit: 20

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk


View Profile
July 03, 2020, 07:05:55 PM
 #7

Thanks Wink I found the issue.

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

Br

$$$ P2P NETWORK FOR BTC WALLET.DAT BRUTE F ORCE .JOIN NOW=GET MANY COINS NOW !!!
https://github.com/phrutis/LostWallet  https://t.me/+2niP9bQ8uu43MDg6
Jean_Luc (OP)
Sr. Member
****
Offline Offline

Activity: 448
Merit: 692


View Profile
July 04, 2020, 07:11:58 AM
 #8

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 Offline

Activity: 1844
Merit: 2017


View Profile
July 04, 2020, 07:41:11 AM
 #9


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 Offline

Activity: 756
Merit: 20

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk


View Profile
July 04, 2020, 10:58:13 AM
Last edit: July 06, 2020, 01:28:41 AM by gmaxwell
 #10

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 ?

$$$ P2P NETWORK FOR BTC WALLET.DAT BRUTE F ORCE .JOIN NOW=GET MANY COINS NOW !!!
https://github.com/phrutis/LostWallet  https://t.me/+2niP9bQ8uu43MDg6
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4018
Merit: 7844



View Profile WWW
July 06, 2020, 01:30:05 AM
 #11

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 Offline

Activity: 448
Merit: 692


View Profile
July 06, 2020, 05:44:23 AM
Last edit: July 06, 2020, 06:09:30 AM by Jean_Luc
 #12

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 Wink
arulbero
Legendary
*
Offline Offline

Activity: 1844
Merit: 2017


View Profile
July 06, 2020, 06:09:17 AM
Last edit: July 06, 2020, 06:41:49 AM by arulbero
Merited by gmaxwell (2), ETFbitcoin (2)
 #13

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 Wink


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 Offline

Activity: 448
Merit: 692


View Profile
July 06, 2020, 06:57:50 AM
Merited by gmaxwell (2), ETFbitcoin (1)
 #14

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
*
expert
Offline Offline

Activity: 4018
Merit: 7844



View Profile WWW
July 06, 2020, 07:31:08 AM
 #15

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 Offline

Activity: 756
Merit: 20

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk


View Profile
July 06, 2020, 09:00:21 AM
 #16

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.

$$$ P2P NETWORK FOR BTC WALLET.DAT BRUTE F ORCE .JOIN NOW=GET MANY COINS NOW !!!
https://github.com/phrutis/LostWallet  https://t.me/+2niP9bQ8uu43MDg6
Jean_Luc (OP)
Sr. Member
****
Offline Offline

Activity: 448
Merit: 692


View Profile
July 06, 2020, 09:47:53 AM
 #17

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

Activity: 756
Merit: 20

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk


View Profile
July 06, 2020, 10:32:55 AM
 #18

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


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

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

$$$ P2P NETWORK FOR BTC WALLET.DAT BRUTE F ORCE .JOIN NOW=GET MANY COINS NOW !!!
https://github.com/phrutis/LostWallet  https://t.me/+2niP9bQ8uu43MDg6
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!