1) Did you use the tame table for the subsequent keys? (I mean while you find the 1st key, you have some tame points - do you use them for the key2, key3, etc... ?) Wild points are not important anymore, but tame ones very helpful as all 16 keys are within the same range; and if you use them, the time needed for the subsequent key will be less, less and less.
No this optimization is not yet done. Reusing tame points will speed up thing by ~2 for others keys. Edit: I'm wondering if using wild point of solved key can be reused also, this should work... 2) How much were your tame and wild tables?
I use the distinguished point method so it varies a lot according to the dpSize. I wrote few notes on it on an other project: https://github.com/JeanLucPons/BTCCollider/blob/master/README.mdAnyway, first GPU release is coming: 16 keys (64bits) solved in 29:44, key by key, no reuse of old points. C:\C++\Kangaroo\VC_CUDA10\x64\Release>Kangaroo.exe -t 0 -gpu ..\..\in.txt
Kangaroo v1.0
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF
Keys :16
Number of CPU thread: 0
Range width: 2^64
Number of random walk: 2^18.58 (Max DP=11)
DP size: 11 [0xFFE0000000000000]
GPU: GPU #0 GeForce GTX 1050 Ti (6x128 cores) Grid(12x256) (45.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^18.58 kangaroos
[115.23 MKey/s][GPU 115.23 MKey/s][Count 2^33.52][Dead 5][02:02][463.9MB]
Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4
[115.22 MKey/s][GPU 115.22 MKey/s][Count 2^32.41][Dead 1][01:01][218.3MB]
Key# 1 Pub: 0x02A50FBBB20757CC0E9C41C49DD9DF261646EE7936272F3F68C740C9DA50D42BCD
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EB5ABC43BEBAD3207
[115.13 MKey/s][GPU 115.13 MKey/s][Count 2^32.99][Dead 0][01:29][323.5MB]
Key# 2 Pub: 0x0304A49211C0FE07C9F7C94695996F8826E09545375A3CF9677F2D780A3EB70DE3
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E5698AAAB6CAC52B3
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^32.66][Dead 0][01:12][258.7MB]
Key# 3 Pub: 0x030B39E3F26AF294502A5BE708BB87AEDD9F895868011E60C1D2ABFCA202CD7A4D
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E59C839258C2AD7A0
[115.22 MKey/s][GPU 115.22 MKey/s][Count 2^33.26][Dead 1][01:47][389.7MB]
Key# 4 Pub: 0x02837A31977A73A630C436E680915934A58B8C76EB9B57A42C3C717689BE8C0493
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E765FB411E63B92B9
[114.51 MKey/s][GPU 114.51 MKey/s][Count 2^34.70][Dead 8][04:42][1044.9MB]
Key# 5 Pub: 0x020ECDB6359D41D2FD37628C718DDA9BE30E65801A88A00C3C5BDF36E7EE6ADBBA
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E7D0E6081C7E0E865
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^32.00][Dead 1][47s][164.7MB]
Key# 6 Pub: 0x0322DD52FCFA3A4384F0AFF199D019E481D335923D8C00BADAD42FFFC80AF8FCF0
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EC737344CA673CE28
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^32.12][Dead 0][51s][179.6MB]
Key# 7 Pub: 0x02DB4F1B249406B8BD662F78CBA46F5E90E20FE27FC69D0FBAA2F06E6E50E53669
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E38160DA9EBEAECD7
[115.06 MKey/s][GPU 115.06 MKey/s][Count 2^33.88][Dead 5][02:42][595.5MB]
Key# 8 Pub: 0x023BD0330D7381917F8860F1949ACBCCFDC7863422EEE2B6DB7EDD551850196687
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E79D808CAB1DECF8D
[115.23 MKey/s][GPU 115.23 MKey/s][Count 2^31.71][Dead 0][39s][136.2MB]
Key# 9 Pub: 0x02332A02CA42C481EAADB7ADB97DF89033B23EA291FDA809BEA3CE5C3B73B20C49
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E54CAD3CFBC2A9C2B
[83.23 MKey/s][GPU 83.23 MKey/s][Count 2^30.23][Dead 0][17s][51.3MB]
Key#10 Pub: 0x02513981849DE1A1327DEF34B51F5011C5070603CA22E6D868263CB7C908525F0C
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0D5ECCC38D0230E6
[114.85 MKey/s][GPU 114.85 MKey/s][Count 2^34.98][Dead 20][05:41][1269.3MB]
Key#11 Pub: 0x03D4E6FA664BD75A508C0FF0ED6F2C52DA2ADD7C3F954D9C346D24318DBD2ECFC6
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EE3579364DE939B0C
[115.22 MKey/s][GPU 115.22 MKey/s][Count 2^33.99][Dead 2][02:54][642.5MB]
Key#12 Pub: 0x0356B468963752924DBF56112633DC57F07C512E3671A16CD7375C58469164599D
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E7C43B8E079AE7278
[115.11 MKey/s][GPU 115.11 MKey/s][Count 2^33.12][Dead 0][01:37][351.9MB]
Key#13 Pub: 0x03D5BE7C653773CEE06A238020E953CFCD0F22BE2D045C6E5B4388A3F11B4586CB
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E8D63EF128EF66B42
[115.22 MKey/s][GPU 115.22 MKey/s][Count 2^31.36][Dead 0][32s][108.8MB]
Key#14 Pub: 0x02B1985389D8AB680DEDD67BBA7CA781D1A9E6E5974AAD2E70518125BAD5783EB5
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E2452DD26BC983CD5
[115.22 MKey/s][GPU 115.22 MKey/s][Count 2^31.49][Dead 0][34s][118.0MB]
Key#15 Pub: 0x0355B95BEF84A6045A505D015EF15E136E0A31CC2AA00FA4BCA62E5DF215EE981B
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E7AD38337C7F173C7
Done: Total time 29:44
|
|
|
|
Jean_Luc, Anybodey can you make a exe file for windows ?
I re added it. Strangely github removed it ?!!! |
|
|
|
Jean_Luc also made the vanity search program, and some guy modified it to work with pollard kangaroo method. The code is here: https://github.com/alek76-2/vs-kangaroo-hybridI beleive that this program should be faster. It uses GPU, not CPU. Of course it is not good to compare CPU and GPU, GPU will always be ahead. Just curious, I wrote a simple Kangaroo program, I didn't test the alek's one because I have a look in his code and see that basic optimizations (at least for CPU) are missed. Especially line 625 of Vanity.cpp ph->Kp = secp->AddAffine(ph->Kp, Sp[pw]); // This requires a modular inversion which can be batched
I published the code here: https://github.com/JeanLucPons/KangarooA comparison between BSGS and Kangaroo, (64bit search, on my old Xeon) : Kangaroo should end in 2^33 iterations (in average). I reached 18.18 MKey/s (here the DP method can be applied to speed up the hashtable and decrease drastically the needed memory, this method can be efficiently implemented on GPU). Kangaroo v1.0
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF
Keys :16
Number of CPU thread: 8
Range width: 2^64
Number of random walk: 2^13.00 (Max DP=17)
DP size: 17 [0xffff800000000000]
Solvekey Thread 0: 1024 TAME kangaroos
Solvekey Thread 1: 1024 TAME kangaroos
Solvekey Thread 2: 1024 TAME kangaroos
Solvekey Thread 3: 1024 TAME kangaroos
Solvekey Thread 4: 1024 WILD kangaroos
Solvekey Thread 5: 1024 WILD kangaroos
Solvekey Thread 6: 1024 WILD kangaroos
Solvekey Thread 7: 1024 WILD kangaroos
[18.00 MKey/s][Count 2^34.40][20:47][Dead 10][20.2MB]
Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4
[18.18 MKey/s][Count 2^33.80][13:44][Dead 3][15.4MB]
Key# 1 Pub: 0x02A50FBBB20757CC0E9C41C49DD9DF261646EE7936272F3F68C740C9DA50D42BCD
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EB5ABC43BEBAD3207
[18.07 MKey/s][Count 2^30.28][01:12][Dead 1][2.8MB]
Key# 2 Pub: 0x0304A49211C0FE07C9F7C94695996F8826E09545375A3CF9677F2D780A3EB70DE3
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E5698AAAB6CAC52B3
[18.18 MKey/s][Count 2^32.78][06:44][Dead 2][9.4MB]
Key# 3 Pub: 0x030B39E3F26AF294502A5BE708BB87AEDD9F895868011E60C1D2ABFCA202CD7A4D
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E59C839258C2AD7A0
[18.18 MKey/s][Count 2^33.82][13:54][Dead 3][15.6MB]
Key# 4 Pub: 0x02837A31977A73A630C436E680915934A58B8C76EB9B57A42C3C717689BE8C0493
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E765FB411E63B92B9
[18.18 MKey/s][Count 2^33.07][08:16][Dead 1][10.9MB]
Key# 5 Pub: 0x020ECDB6359D41D2FD37628C718DDA9BE30E65801A88A00C3C5BDF36E7EE6ADBBA
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E7D0E6081C7E0E865
[18.18 MKey/s][Count 2^34.45][21:27][Dead 4][20.7MB]
Key# 6 Pub: 0x0322DD52FCFA3A4384F0AFF199D019E481D335923D8C00BADAD42FFFC80AF8FCF0
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EC737344CA673CE28
I'll post the full result for the 16 keys on github when ended. |
|
|
|
core i7 3770 8 RAM 28 mins
28 min per key with 8Gb RAM ? |
|
|
|
Ah, I understand difference bettwen our hashtables.
When you make pubkey you compare pubkey (masked pubkey) with each of element of hashtable( in last optimisation you add sorting for this)
But i try to use other way. i don`t need to compare pubkey with each elements becouse i have table of 2^24
In that case i need only 1 lookup to the table to get hash and i get result - hash exist or not and if exist get pointer to memory where stored G counter or few G counters if collision.
Ok, If I understand well your startegy, you face the birthday paradox problem. When you fill your hashtable, you will start to have collision around the sqrt(2^24)=2^12th insertion. So for 2^24 G counters, you will need a hashtable of ~2^48 entries to avoid collision. |
|
|
|
f you use a 24bit hashtable and 2^30 keys for baby step: You will have (in average) a list of 2^(30-24) = 64 items per hash. Each items of this list contains the generator index and an additional part of the key. typedef struct {
uint32_t b0; // LSB key (24 bit) + HSB Offset (8 bit)
uint32_t p; // LSB Offset
} ENTRY;
The hash is 3 byte of MSB of the key. b0 is 3 byte of LSB of the key. So we store 48 bits of the key. p (offset) is the "generator index" corresponding to the key p.G Then to access it , you compute the hash (one simple & operation) and you have direct access to this small list. You can sort each list according to the part of key and you will need 6 operations (in average) to get the generator index. I did like this in HashTable::Get(). Then as I don't store the full X value of p.G, i have some false collision, than i need to check by a computePublicKey. A false collision happens every 2^(24+24 - 30) = 2^18 giant steps, that means that I need to perform an extra EC multiplication every 262144 giant steps. According to the memory you have, you may need to adjust the HASH size, and the number of bit of the key stored in the entry in order to have a minimum of false collision. |
|
|
|
Nice job! Thank you.
You're welcome  So, your total time for 16 keys is 216 minutes, including 9 minutes for 2^30 precomputations. That means that for 16 keys search you need 207 minutes, or approx. 13 minute per one 64bit key. As i saw from your results, the time per one 64 key varied from 2 min to 19 min.
Avg time 13minute is very good. I guess it is faster than the result reqched by Pollard Kangaroo method sahred in BurtW topic.
If you look at the key who has been solved in 19min, you see that ...7D0E6081C7E0E865 is close to ...8000000000000000 (end range of thread #3) and that it requires a total of 2^33.86 giant steps (max 2^34) so we are close to the end of the range. It takes ~20 minutes to browse the full 2^64 range, so the theoretical average time to solve a key should be 10min without taking into account the baby step precalculation. |
|
|
|
I did few optimizations (commited to github), I reached 13.6M giant steps of 2^30 per second on my Xeon X5647 2.93GHz with 12GB of RAM. It solves the 16 keys of the odolvlobo's set in 3:35:53 from scratch, I mean without any precomputation. If I convert to the Etar's unit: It does 14.6 PKey/s. I posted the result in the readme of my program: https://github.com/JeanLucPons/BSGS/blob/master/README.mdThanks to odolvlobo to provide this challenge. Best wishes to Etar to optimize his program and fix his issue on GPU. |
|
|
|
How and where can you store all 2^40 keys?
I store only 49bits (25+24) per key (using a HASH_SIZE of 25 in https://github.com/JeanLucPons/BSGS/blob/master/HashTable.h). I accept to have few false collisions and to make little more calculations to handle them. Each item in the table is a 64bits item, 40 bit for the generator index and 24 bit for a part of the key. I choose this maximum of 40 bit (32+8) because more than 2^32 keys is possible but you're right 2^40 can be decreased and few bits can be used for the key and decrease the probability of false collision. This program is here to be modified and adapted... |
|
|
|
|
This problem is typically a time memory trade off problem so the goal is to find all best time memory tradeoff.
I store only 40 bits for the generator index (so 2^40 key max in my hash table) and 24 (+ 25 bits) of the x value. 64 bits per items and an array of 2^25 pointers + 2 * 2^25 short arrays.
So i get few false collisions (one every 2^(49-30) giant steps in average) that i need to check but I win lots of memory, my giant step is much larger.
I'm able to browse the 64bit range in 24min with my 9 year old Xeon (12GB)
|
|
|
|
|
I passed my hashtable to a hash size of 25bit (always 2^30 points inside), i win 20% of speed for a 500MB overhead.
Edit:
Concerning GPU the access to global memory is slower than local memory but I'm surprised that it is so slow in your case.
For other programs, i implemented binary search on global memory (millions of items) with very good performances.
In that case a hashtable is better than binary search.
|
|
|
|
|
There is an horrible call in your loop. Try to remove it and implement the comparison locally.
|
|
|
|
|
How did you implement the binary search on the GPU ? Iterative or recursive ?
I already implemented binary searches on GPU without having such an issue.
|
|
|
|
Just curious, I made a small program that does this. I used a 24bits hash table (no binary search) and a table of 2^30 point (~9GB), the hash table is not well optimized for insertion in order to save memory and to avoid fragmentation (not constant speed). It is obviously possible to make further optimizations to speed it up. I ran this program on an old Xeon X5647 2.93GHz with 12GB of RAM. It takes 9min to fill the 2^30 baby step table and ~32min to browse the full 2^64 range so it can solve the 16 keys of odolvlobo in ~9h00 (max). I published the code: https://github.com/JeanLucPons/BSGSHere the key #10 and #11 of the odolvlobo set (expressed in compressed format) BSGS v1.0
BabyStep:0x40000000
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EFFFFFFFFFFFFFFFF
Keys :7
Number of CPU thread: 8
BabyStep Thread 2: 0x10000001 -> 0x18000000
BabyStep Thread 4: 0x20000001 -> 0x28000000
BabyStep Thread 1: 0x8000001 -> 0x10000000
BabyStep Thread 0: 0x1 -> 0x8000000
BabyStep Thread 5: 0x28000001 -> 0x30000000
BabyStep Thread 3: 0x18000001 -> 0x20000000
BabyStep Thread 6: 0x30000001 -> 0x38000000
BabyStep Thread 7: 0x38000001 -> 0x40000000
[1.82 MKs][Cnt 2^30.00][09:03][8575.9MB]
GiantStep Thread 1: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E2000000000000000
GiantStep Thread 0: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0000000000000000
GiantStep Thread 2: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E4000000000000000
GiantStep Thread 3: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E6000000000000000
GiantStep Thread 4: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E8000000000000000
GiantStep Thread 5: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EA000000000000000
GiantStep Thread 6: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EC000000000000000
GiantStep Thread 7: 49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EE000000000000000
[8.57 MKs][Cnt 2^33.37][21:38][8575.9MB]
Key# 10 Pub: 0x02332A02CA42C481EAADB7ADB97DF89033B23EA291FDA809BEA3CE5C3B73B20C49
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E54CAD3CFBC2A9C2B
[8.58 MKs][Cnt 2^32.74][13:53][8575.9MB]
Key# 11 Pub: 0x02513981849DE1A1327DEF34B51F5011C5070603CA22E6D868263CB7C908525F0C
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5E0D5ECCC38D0230E6
|
|
|
|
|
"meet in the middle" is a generic term to design attack algorithm that makes time/memory tradeoff to reduce time complexity of basic brute force attack.
In that case, the best tradeoff brings O(sqrt(n)).
The algorithm that I show you on the power point, is a basic one, lots of variants exist... since more than 50 years...
|
|
|
|
So BSGS can`t be launched with n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
You can use this algorithm with the memory you want. Of course, if you want to use it on the full range, you won't be able to get running time in O(sqrt(n)) because you won't have enough memory. BSGS is a simple time memory/tradeoff, if you have enough memory you can get the best complexity in O(sqrt(n)), if you don't have memory (you don't use a lookup table) then the algorithm get a complexity in O(n). For the basic BSGS, If x is the size of the lookup table, and n the search space size, the total number of needed group operations is x (to fill the memory) + n/x (to solve the key) and the minimum of this function is obtained when x = sqrt(n), then the total number of group operation is 2*sqrt(n). We neglect here the time spent by the search (or the insertion) in the lookup table which can be done very efficiently by combining hash table and binary search. Ex: for n=2^64, we see that the minimum is well at x=2^32 (~4.295E9)  |
|
|
|
That isn't impressive at all and wouldn't prove your claim. Because you fix a range, you could simply have a table of 2^31 entries (1G, 2G, 3G) based on X-only, you step by twice the size of your table, checking only the X to get a positive and negative offset, and find the match in one hour at a terribly slow rate of 1.2 million keys a second.
gmaxwell posted this method in the beginning of this topic, (an optimized version using negation), without a starting offset in that case but easy to add one. It took 3 pages to etar to understand. BSGS is quite a very simple and intuitive algorithm and there are plenty of possible optimizations to speed it up. gmaxwell is right, according to the "attracting" title of this topic and to the refusal of Etar to post his code, to add this warning. |
|
|
|
|
Show Posts
