Pages:
Author

Topic: Pollard's kangaroo ECDLP solver - page 65. (Read 59436 times)

full member
Activity: 1162
Merit: 237
Shooters Shoot...
April 05, 2021, 01:59:09 AM
Are kangaroo collisions in the same herd a bad thing? My program (https://github.com/ZenulAbidin/Kangaroo-256) was doing that until I changed the hash table index calculation to use & HASHMASK instead of % HASHMASK.

To my understanding, they don't slow down the search - that happens when your DP size is too small for your search range and initial points are lost - but it just keeps going on forever without colliding the private key in the hash table.
If you are searching with GPU and searching in a decent sized bit range, say 64 bit range and up, you may get a few same herd collisions, but it's not a bad thing. The program just resets those kangaroos to start a different path from a different random point.

Smaller DP and smaller ranges will create more same herd collisions; especially if using GPU.

Does your program solve keys, or just keep running?
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
April 05, 2021, 01:53:11 AM
Are kangaroo collisions in the same herd a bad thing? My program (https://github.com/ZenulAbidin/Kangaroo-256) was doing that until I changed the hash table index calculation to use & HASHMASK instead of % HASHMASK.

To my understanding, they don't slow down the search - that happens when your DP size is too small for your search range and initial points are lost - but it just keeps going on forever without colliding the private key in the hash table.
member
Activity: 406
Merit: 47
April 04, 2021, 10:18:04 AM
code complex more than I can understand
I run pollard-kangaroo-multi.py with config flag_verbose = 2   

look like start from  random tame wild by random with distance tame wild
and get xpoint (how to calculate)
then compare both
and jump to next tame wild (and jump)
if not yet collision do again new random

I am not programmer not yet clear to read complex code

Can I do easy by using python library bit
https://ofek.dev/bit/guide/keys.html

import bit
pvk = random.randrange(2**119,2**120)
key = Key.from_int(pvk)
X,Y = key.public_point

this is same value or not
member
Activity: 406
Merit: 47
April 04, 2021, 07:27:40 AM

Example:
Tame
Code:
D141E70913A6F67CD00DB847B31C28 00CF048E0B6645018CE925D30B01F1
Wild
Code:
D141E70913A6F67CD00DB847B31C28 000F048E0B6645018CE925D30B01F1


Thank you for help answer

kangaroo save file is binary format right
I try to open in text editor it is not work

this one random on range right
00CF048E0B6645018CE925D30B01F1  = 304597017357365078784491997823473

this long how can I calculate
D141E70913A6F67CD00DB847B31C28  = 1086526704572680266696100020277681192

I think kangaroo.exe calculate better

may be difference work with kangaroo.exe and kangaroo python version

example pubkey 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4

command
Code:
python pollard-kangaroo-multi.py 40 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4

results.txt
Code:
000000000000000000000000000000000000000000000000000000e9ae4933d6:03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4

tame.txt
Code:
df01ac74ca510e763ab46bce694a8b57886b75a332c5c4723a97295df3cc0000 938995735797
8035da74a13756443b9dae9ed6bea111479f7f6447539e634e1dc7177e2a0000 987988675717
3997d2cad0f2ccea350bd0b0d0d06bfb70186d6daca5c51a6dc6043548a60000 1041424812707
ec9d5049bd4509aa41e1f5c312de1900d3eac4adba0692a41286b2497e520000 1110317004752

wild.txt
Code:
c3f83617c1d27a2883fbb849e6b990809553db20b3b7b7523d8c7a07f5040000 3343924384
566cf41f4de8b1ec5358fedb956d7c8a2540a24c4f336370723273f9a1fc0000 11271810949
fc241f52dbebdb22cb5b7b68fc98599deebfc7749c272ddb104d7c4d1d6e0000 65004674131
ec9d5049bd4509aa41e1f5c312de1900d3eac4adba0692a41286b2497e520000 106665591802
9ced97b0ce81010e66f87d91d2414af23fe456da6ec1d0a6dcf598d0e71a0000 87061666288


match/collision

tame.txt
ec9d5049bd4509aa41e1f5c312de1900d3eac4adba0692a41286b2497e520000 1110317004752
wild.txt
ec9d5049bd4509aa41e1f5c312de1900d3eac4adba0692a41286b2497e520000 106665591802


number = 1110317004752
and
number = 106665591802

it is random from command = random.randint

and this value
ec9d5049bd4509aa41e1f5c312de1900d3eac4adba0692a41286b2497e520000

Are they come from?
How to calculate?


full member
Activity: 1162
Merit: 237
Shooters Shoot...
April 04, 2021, 01:19:12 AM

Kangaroo calculate  Tame,Wild

Can anybody tell me what number Tame,Wild calculate and How I calculate with what formula?

two number one is hash on hex format and two is random value in range
What is first number on hex

I would like to testing some experiment by  random Tame,Wild (in range) and see can possible to collision or not

Can you give example of what you mean by "two number one is hash on hex format and two is random value in range
What is first number on hex" ?

If you mean the columns from the saved file, for tame and wild both, column/tab 1 is the point, a.k.a pubkey, for tame in column/tab 2 is the distance, a.k.a. privkey and column/tab 2 for the wild is the distance a.k.a. the offset of pubkey you are searching for. If column 1 matches up, then for JLPs kangaroo program, you would subtract column/tab 2 "distances" from each other and then add back the start range you entered in command line.

Example:
Tame
Code:
D141E70913A6F67CD00DB847B31C28 00CF048E0B6645018CE925D30B01F1
Wild
Code:
D141E70913A6F67CD00DB847B31C28 000F048E0B6645018CE925D30B01F1

Both column 1s line up (points) so that is a collision. Now subtract column 2s from each other and add back start range and that is the private key to the pubkey you are searching for.

EDIT: I forgot to mention that the column 1/pubkeys are the least significant bits, the last x amount of characters in the pubkey; so in the example above, if you look at privkey CF048E0B6645018CE925D30B01F1 you will see that D141E70913A6F67CD00DB847B31C28 are the last bits of its pubkey's x coord.

member
Activity: 406
Merit: 47
April 04, 2021, 01:09:41 AM

Kangaroo calculate  Tame,Wild

Can anybody tell me what number Tame,Wild calculate and How I calculate with what formula?

two number one is hash on hex format and two is random value in range
What is first number on hex

I would like to testing some experiment by  random Tame,Wild (in range) and see can possible to collision or not
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
March 29, 2021, 06:00:33 AM
these is the data of that kind speed......

Kangaroo v2.1 : Added Start End Options
~snip
[1948901416.30 MK/s][GPU 1193969262.41 MK/s][Count 2^29.27][Dead 2][16s (Avg 13s)][155.9/201.6MB]

Is this output from my fork? (I did not bump the version number, maybe it would be wise for me to do so)?

I have not changed the code related to speed reporting, and I also haven't made any of the planned optimizations yet.
full member
Activity: 1162
Merit: 237
Shooters Shoot...
March 28, 2021, 11:18:52 PM
Why no body create Kangaroo 120 bit pool?
if can do it make pool fast to found key
I think may be fast before found 64 bit bitcrack pool


compare now bitcrack scan pool already 1 quadrillion from all 9 quadrillion on 64 bit
1,000,000,000,000,000,000 =  1 Quintillion

calculate kangaroo
2**199 = 664613997892457936451903530140172288

split kangaroo for each 2**64 for small keyspace search
2**199/2**64
664613997892457936451903530140172288/18446744073709551616 = 36028797018963968 time(slot)
36,028,797,018,963,968 = 30 Quadrillion scan
1,000,000,000,000,000 = 1 Quadrillion
1,000,000,000,000,000,000 = 1 Quintillion = 1000 Quadrillion

kangaroo is power full can scan 64 bit on 1 minute
For a kangaroo pool, you would not split the keyspace up. You would wind up doing way more group operations versus everyone (all gpus) working on the full keyspace.

The pool would have to have powerful hardware.  Huge SSD harddrives (to hold distinguished points + kangaroo positions of all gpus), lots of RAM, and lots of CPU cores.  Merging the files is the issue/biggest challenge.

That's why I tried with the Baby Step Giant Step. But everyone thinks they can come up with new creative way to solve #120 and do it on their own. Some people probably have the hardware to do so, but not most.

EDIT: Just to add about breaking #120 down into bite size chunks of 64 bits. That would be 72,057,594,037,927,936 ranges to be searched. So that would also be 72,057,594,037,927,936 minutes to search and cover entire range.  But the biggest problem is, you still wouldn't be 100% to find the key unless everyone has high -m option set.   But you are right, It would be faster than brute forcing #64. 50% of brute forcing #64 = 2^63 . Kangaroo only requires 2^60 +-1 .
member
Activity: 406
Merit: 47
March 28, 2021, 11:03:00 PM
Why no body create Kangaroo 120 bit pool?
if can do it make pool fast to found key
I think may be fast before found 64 bit bitcrack pool


compare now bitcrack scan pool already 1 quadrillion from all 9 quadrillion on 64 bit
1,000,000,000,000,000,000 =  1 Quintillion

calculate kangaroo
2**199 = 664613997892457936451903530140172288

split kangaroo for each 2**64 for small keyspace search
2**199/2**64
664613997892457936451903530140172288/18446744073709551616 = 36028797018963968 time(slot)
36,028,797,018,963,968 = 30 Quadrillion scan
1,000,000,000,000,000 = 1 Quadrillion
1,000,000,000,000,000,000 = 1 Quintillion = 1000 Quadrillion

kangaroo is power full can scan 64 bit on 1 minute
full member
Activity: 1162
Merit: 237
Shooters Shoot...
March 28, 2021, 12:57:58 AM
these is the data of that kind speed......

Kangaroo v2.1 : Added Start End Options
Start:4956C9891727D63DA8F9B49FE524C02206504109B416CC454C3E20EB14441F56
Stop :4956C9891727D63DA8F9B49FE524C02206504109B416CC454D3E20EB14441F55
Keys :3
Number of CPU thread: 2
Range width: 2^56
Jump Avg distance: 2^28.01
Number of kangaroos: 2^18.18
Suggested DP: 7
Expected operations: 2^29.12
Expected RAM: 185.6MB
DP size: 7 [0xFE00000000000000]
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos
GPU: GPU #0 Quadro K2100M (3x192 cores) Grid(6x384) (29.5 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^18.17 kangaroos [1.3s]
[1948901416.30 MK/s][GPU 1193969262.41 MK/s][Count 2^29.27][Dead 2][16s (Avg 13s)][155.9/201.6MB]
What is this: "Kangaroo v2.1 : Added Start End Options"

Did you compile yourself? Tweak code?

newbie
Activity: 6
Merit: 0
March 28, 2021, 12:29:24 AM
these is the data of that kind speed......

Kangaroo v2.1 : Added Start End Options
Start:4956C9891727D63DA8F9B49FE524C02206504109B416CC454C3E20EB14441F56
Stop :4956C9891727D63DA8F9B49FE524C02206504109B416CC454D3E20EB14441F55
Keys :3
Number of CPU thread: 2
Range width: 2^56
Jump Avg distance: 2^28.01
Number of kangaroos: 2^18.18
Suggested DP: 7
Expected operations: 2^29.12
Expected RAM: 185.6MB
DP size: 7 [0xFE00000000000000]
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos
GPU: GPU #0 Quadro K2100M (3x192 cores) Grid(6x384) (29.5 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^18.17 kangaroos [1.3s]
[1948901416.30 MK/s][GPU 1193969262.41 MK/s][Count 2^29.27][Dead 2][16s (Avg 13s)][155.9/201.6MB]
full member
Activity: 1162
Merit: 237
Shooters Shoot...
March 27, 2021, 12:15:04 PM
I show a speed of 140168155140.13 MK/S in kangaroo with one rtx 2060..........with 8 x rt 3090, will be more around 10^21 or 22 digits. May be more who knows

Yeah something is wrong with the code in your program or your hardware.

Hate to tell you, if you got that kind of speed with 1 rtx 2060 you could solve every key in the 2^256 range pretty quickly.

Something is wrong in your setup, software or hardware.
newbie
Activity: 6
Merit: 0
March 27, 2021, 12:02:47 PM
I show a speed of 140168155140.13 MK/S in kangaroo with one rtx 2060..........with 8 x rt 3090, will be more around 10^21 or 22 digits. May be more who knows
full member
Activity: 1162
Merit: 237
Shooters Shoot...
March 27, 2021, 11:05:06 AM
No, its 40 000Mk/S cpu and 40 000 MK/S gpu speed..........but these is too slow as I seen a here : https://github.com/JeanLucPons/VanitySearch/issues/97
Yeah that seems way too fast regardless of what you have seen elsewhere. Especially for a CPU to be getting 40,000 MKey/s.

5,000 per 3090 card seems maybe right?  I'm not sure. a V100 gets around 1,600 MKey/s

How many MKey/s are you expecting from one 3090 card?
newbie
Activity: 6
Merit: 0
March 27, 2021, 07:53:08 AM
No, its 40 000Mk/S cpu and 40 000 MK/S gpu speed..........but these is too slow as I seen a here : https://github.com/JeanLucPons/VanitySearch/issues/97
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
March 26, 2021, 10:56:20 AM
I tries running new kangaroo-256 with { 0x86, 128 }, changes to GPUEngine.cu with 8 x RTX 3090 cards and its showing segmentation fault (core dumped error). I also tries running { 0x86, 64 }, with these codes but its slow like 80 000 MK/S.
Sill some changes need to build its capacity.

thanks

Strange. What are your input file range and public keys, and any command line options you used?

EDIT: please also confirm what your reported speed is (total and GPU) because 80,000MKeys/s sounds way too high. Did you mean 80 MKeys/s or something in that ballpark?

Does the segmentation fault happen ONLY when you change the compute cap 8.6 threads constant to 128 [I left it on 64 by default]?
newbie
Activity: 6
Merit: 0
March 26, 2021, 08:11:29 AM
I tries running new kangaroo-256 with { 0x86, 128 }, changes to GPUEngine.cu with 8 x RTX 3090 cards and its showing segmentation fault (core dumped error). I also tries running { 0x86, 64 }, with these codes but its slow like 80 000 MK/S.
Sill some changes need to build its capacity.

thanks


legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
March 26, 2021, 12:33:41 AM
Quote
Yeah I think that's doable, I think when I'm done I'll ask my provider (@Vod) to let me lease an AWS instance with Windows on it for a day or two so that this can be done, it's very cheap.

I am confused. I thought you were trying to get the program so it would store 256 bits in the hashtable? Are you also working on different things inside the program?

I already completed that change  Smiley

Now that that's done I'm working on trying to speed up Int arithmetic (there's a couple of add carry statements which I can replace with SSE2 add instructions if I reserve the upper half of 64-bit bits for carry bits.

Maybe while I'm at it I'll put it on Github as well.
member
Activity: 406
Merit: 47
March 25, 2021, 08:48:26 PM
Hello,
When you will be completing the Kangaroo-256, can you also compile releases .exe for Windows? I am afraid I always get into issues when compiling... Undecided

Yeah I think that's doable, I think when I'm done I'll ask my provider (@Vod) to let me lease an AWS instance with Windows on it for a day or two so that this can be done, it's very cheap.

How can I testing, it works with 256 function upgade?

Try use with 256 bits full keys?

What mean of 256?
Can using wide of keyspace 256bits
or Can using with full 256 keys?

What feature of kangaroo256 upgrade?


I don't know mush about deep technical and deep programing (just user)
Can possible to develop to 512 bits or 1024 bits? Just ask to known
I think over like bitcoin use at 256 bits or sha256, if creator bitcoin think first time 64bit is high enough now is crack already.
512 bits or 1024 bits is thank like buy power supply for PC buy 1100 Watt PSU and using  600W for performance and long time using with no high heat. something like that
may be possible create 512 bits or 1024 bits for high performance and may be no need to update much in future
may be puzzle up to 120 bit and 160 bits with using 256 bit support may be difficult to scan

and or think reversal 64 bit is short right 256 bit is long right  over 4 time (256/64=4) (and 256/128=2)
It scan possible code for double calculate same time like calculate 64bit 4 calculate parallel in 1 one time
or may be flip method combine 64+64+64+64= 256 bit calculate and split
may be GPU system calculate something like that already no need to think about it
sorry just think about number may be can not possible on technic, I don't know computer knowledge mush
full member
Activity: 1162
Merit: 237
Shooters Shoot...
March 25, 2021, 08:42:57 PM
Quote
Yeah I think that's doable, I think when I'm done I'll ask my provider (@Vod) to let me lease an AWS instance with Windows on it for a day or two so that this can be done, it's very cheap.

I am confused. I thought you were trying to get the program so it would store 256 bits in the hashtable? Are you also working on different things inside the program?
Pages:
Jump to: