Science Fair Project to trap Bitcoin private keys using Kangaroos!

[MrFreeDragon]

Here is another example of #40

#40 sqr(2^(bit-1))
python pollard-kangaroo-multi.py 40
//privkey = 1003651412950


#40 sqr(2^(bit-2))
python pollard-kangaroo-multi.py 8:3FFFFFFFFF 028dfd0e801ed8d495b6a0b68b38fba4f32d7423af363c717cca6c2ebd1e11a399
//privkey = 179017692118

Addfactor: 824633720832
//result1 = 1003651412950 true

824633720832 is just 0xC000000000
179017692118  is 0x29AE4933D6
1003651412950  is  0xE9AE4933D6

So 0xC000000000 is just the mid point of the normal #40 range 8000000000:FFFFFFFFFF
in other words the #40 sqr(2^(bit-2)) range you are mentioning is just the position of the private key from the mid-point.
You are not doing less work, you've just changed the origin.
Instead of working with the tame kangaroo matching the private key solution, you are working with the corresponding wild kangaroo.

Absolutely!


In general terms, it could be explaind like this: for bit key the range is from 2^(bit-1) up to 2^(bit)-1, where the total number of combinations (range length) is 2^(bit-1).
2^(bit-2) is a half of 2^(bit-1), so 2^(bit-1) + 2^(bit-2) is 1.5 * 2^(bit-1) --> the absolute middle of the total range for the (bit) key.

[1714985245]

1714985245

[1714985245]

1714985245

[st0ffl]

Here is another example of #40

#40 sqr(2^(bit-1))
python pollard-kangaroo-multi.py 40
//privkey = 1003651412950


#40 sqr(2^(bit-2))
python pollard-kangaroo-multi.py 8:3FFFFFFFFF 028dfd0e801ed8d495b6a0b68b38fba4f32d7423af363c717cca6c2ebd1e11a399
//privkey = 179017692118

Addfactor: 824633720832
//result1 = 1003651412950 true

824633720832 is just 0xC000000000
179017692118  is 0x29AE4933D6
1003651412950  is  0xE9AE4933D6

So 0xC000000000 is just the mid point of the normal #40 range 8000000000:FFFFFFFFFF
in other words the #40 sqr(2^(bit-2)) range you are mentioning is just the position of the private key from the mid-point.
You are not doing less work, you've just changed the origin.
Instead of working with the tame kangaroo matching the private key solution, you are working with the corresponding wild kangaroo.

Exactly that was the plan > wraping the space W with the middle of the space to point infinity.
So that actually all x values get halfed.
I thought possibly that when a wild kangaroo jumps, a jump from the tame kangaroo in the negative space in the different direction could also lead to the same result in less time(cause it would be the same distance).
The key is definitely to find in the space(bit-2), however if you say regarding the kangaroo method, that there is no speed gain, the method is useless.
i have to test #35. i would not understand if the key is not findable. like #50 if the key is on the negative side it will find the privatekey and publickey on the positiv side,there will be just no publickey match> Watch it in the console im not sure if gets to the result.txt
Thanks for testing!  

[st0ffl]

I deleted my posts to avoid any confusions.

Now i better understand how kangaroo jumping works, i didn't even know that it is possible to find a publickey which is not in the space we are searching for.
That's why it finds the publickey when you just change Y.
I thought that when a tame kangaroo jumps out of space, a new tame and wild kangaroo would be set within the space to start jumping again.

As my suggestion, it would be the same if you just set the searchspace for from 2^(bit-1) > (2^(bit)-1) to (2^(bit-1) + 2^(bit-2)) > (2(bit)-1).
You would have a 50% chance to find the key in sqr(2^(bit-2)).
In my tests it must have been luck to find the keys not in that 50%chance in less time than average.
The only benefit i see by pushing the space with the middle to Infinity point, would be if a X value match could be detected when a wildkangaroo starts in negative mirrored space. That would possible be a rarely case by the time it catches up to the positive space where all tame kangaroos would start.

[brainless]

I deleted my posts to avoid any confusions.

Now i better understand how kangaroo jumping works, i didn't even know that it is possible to find a publickey which is not in the space we are searching for.
That's why it finds the publickey when you just change Y.
I thought that when a tame kangaroo jumps out of space, a new tame and wild kangaroo would be set within the space to start jumping again.

As my suggestion, it would be the same if you just set the searchspace for from 2^(bit-1) > (2(bit)-1) to (2^(bit-1) + 2^(bit-2)) > (2(bit)-1).
You would have a 50% chance to find the key in sqr(2^(bit-2)).
In my tests it must have been luck to find the keys not in that 50%chance in less time than average.
The only benefit i see by pushing the space with the middle to Infinity point, would be if a X value match could be detected when a wildkangaroo starts in negative mirrored space. That would possible be a rarely case by the time it catches up to the positive space where all tame kangaroos would start.

i sent you PM, 2 time in last 2 days, have some time for reply
Looking Farword

[st0ffl]

i sent you PM, 2 time in last 2 days, have some time for reply
Looking Farword

seems like you need to change your settings too

[brainless]

hi
in script, there is bug, or maybe he unable to catch point, as
if you have 37 bit pubkey
and you command is
./script 40 02xxxxxxpublickey
40 bit mean search in bit range
but script will find key in 37 bit
if you have 42 bit key, and same command for search in 40 bit by apply 40 or 8:fffff.... bit range, script will find 42 key

its not restrict only for define bit range
mean always find start from 8 to onword, so its take time consume, Smiley
test it

[st0ffl]

hi
in script, there is bug, or maybe he unable to catch point, as
if you have 37 bit pubkey
and you command is
./script 40 02xxxxxxpublickey
40 bit mean search in bit range
but script will find key in 37 bit
if you have 42 bit key, and same command for search in 40 bit by apply 40 or 8:fffff.... bit range, script will find 42 key

its not restrict only for define bit range
mean always find start from 8 to onword, so its take time consume, Smiley
test it

Yes, this was my point.
I first thought that there is a parallel behaviour, cause the script was finding the publickey when changing y value only, and we could use it to only make sqr(2^(bit-2)) operations,
unitil i found a completely different pubkey from another space.
You don't have to set from 8:... bitspace it also works with orginal keyspace

It's not a bug i guess...i am cleary not an expert in this matter , but that's what i think:
It seems logical, it will just take longer on average to find the key.
The average jumpsize should be calculated from the searchspace.
When you search for exampe puplic key from 37 bit within 40 bit the average jumpsize should be bigger and the opposite when searching 43bit pubkey within  40 bit.

It's strange, that when you change only the y value of the key, you will find the orginal publickey with privatekey, but not the one you changed.

[Telariust]

..where exactly do you store the tame and wild kangaroos as it is done in the "tame.txt" and "wild.txt" files for the python code..

in hashtable
ok, i will add output to file distinguished points in next release.
there is only one practical use for saving points to disk - distributed enumeration on different devices without a pool.
I myself plan to do so, since writing a pool is much more difficult than collecting a save once a day.

The idea is of course to only make sqr(2^(bit-2)) operations.

x2 speed-up, nice idea, i will add as option of boost in next release

The Hash table is only 1024 entries, is it enough for cases like #110 ?

the formula calculates a number of points about 10 pieces per kangaroo for 100% of the lead time, taking into account the size of the range.
Now the overflow of the table will occur with a probability of 50% if launched on 96 cores or more. It needs to be fixed.

I understand that -t is the number of threads.
The question is why the speed increases, but time does not decrease, more often it even increases.

1) Algo of Pollard is probablistic nature (Birthday Paradox, Kruskal's card trick, etc)
The solution time is not stable; several attempts (timeit loop in python script) are needed to obtain the avg runtime and jumps.
heuristic time rather than deterministic

2) threads should run at equal speed.
If input -t N over than really N cores, so threads will compete, some will be faster and some will be left behind.

3) maybe my code have bug, need more tests

#################
post dedicated cuda/opencl implementations

we have some ways for just ready GPU implement
good candidates to rewrite:

1) cuda, c++, VanitySearch,  by Jean_Luc
https://github.com/JeanLucPons/VanitySearch

2) cuda/opencl, c++, BitCrack, by brichard19
https://github.com/brichard19/BitCrack

2) cuda, python, pollard-rho, by brichard19
https://github.com/brichard19/ecdl

3) cuda, ?, pollard-rho
github.com/beranm14/pollard_rho/

4) opencl, C#, pollard-rho
github.com/twjvdhorst/Parallel-Pollard-Rho/

I intend to evaluate their performance, as well as rewrite one or more to kangaroo.

#################

multicore, CPU only, c++, based on engine VanitySearch1.15
https://github.com/Telariust/vs-kangaroo/releases

bignum lib by Jean_Luc is good, only %15 slower than bitcoin-core/secp256k1 lib (with raw asm mult)

Code:

C:\Users\User\source\repos\VanitySearch-1.15_kangaroo\x64\Rel_SM52>vs-kangaroo -v 1 -t 4 -bits 42
[###########################################################]
[#          Pollard-kangaroo PrivKey Recovery Tool         #]
[#          (based on engine of VanitySearch 1.15)         #]
[#                 bitcoin ecdsa secp256k1                 #]
[#                         ver0.01                         #]
[###########################################################]
[DATE(utc)] 08 Oct 2019 23:07:47
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[pow2bits]      42
[rangeW]        2^41..2^42 ; W = U - L = 2^41
[DPsize]        1024 (hashtable size)
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[pubkey#42] loaded
[Xcoordinate] EEC88385BE9DA803A0D6579798D977A5D0C7F80917DAB49CB73C9E3927142CB6
[Ycoordinate] 28AFEA598588EA50A6B11E552F8574E0B93ABD5595F5AA17EA3BE5304103D255
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] Sp-table of pow2 points - ready
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] recalc Sp-table of multiply UV
[UV] U*V=1*3=3 (0x03)
[optimal_mean_jumpsize] 2097152
[meanjumpsize#24] 2097151(now) <= 2097152(optimal) <= 4026531(next)
[i] Sp[24]|J------------------------------------------------------------|Sp[25]
[JmaxofSp] Sp[24]=2097151 nearer to optimal mean jumpsize of Sp set
[DPmodule] 2^18 = 262144 (0x0000000000040000)
[+] 1T+3W kangaroos - ready
[CPU] threads: 4
[th][tame#1] run..
[th][wild#1] run..
[th][wild#2] run..
[th][wild#3] run..
[|][ 00:00:04 ;   1.1M j/s;   4.0Mj 107.4%; dp/kgr=10.0; 00:00:00 ]
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[prvkey#42] 0x000000000000000000000000000000000000000000000000000002A221C58D8F
[i]   1.0M j/s;   5.0Mj of   4.0Mj 123.6%; DP 1T+3W=8+14=22; dp/kgr=11.0;
[runtime]  00:00:05
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[DATE(utc)] 08 Oct 2019 23:07:53
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[x] EXIT

#################

BitCrack runs at about 715 MKeys/s on Tesla V100 - look here.
If we remove hash160, the rate would be 1430 Mj/s. Mj here stands for million kangaroo jumps.

not

BitCrack use batch packet inversion (x8 speed-up).
We cant(OR CAN?..) use its in kangaroo method, so 1430/8 = 175M j/s

but on screen

https://imgur.com/a/f3zTmTa

see 4xV100=6515M j/s, each 1600M j/s

now unclear..

#################

https://bitcointalk.org/index.php?topic=1306983.msg48224432#msg48224432
November 25, 2018 this man speaks as if he already has a finished implementation.

https://imgur.com/a/f3zTmTa

O great master, j2002ba2, I urge you!   Plz, come and explain to the miserable mortals, which means s2,s1,m3,m4 in your program!

#################
https://docs.nvidia.com/cuda/volta-tuning-guide/index.html
he high-priority recommendations from those guides are as follows:
 - Find ways to parallelize sequential code;
 - Minimize data transfers between the host and the device;
 - Adjust kernel launch configuration to maximize device utilization;
 - Ensure global memory accesses are coalesced;
 - Minimize redundant accesses to global memory whenever possible;
 - Avoid long sequences of diverged execution by threads within the same warp;


about last, " - Avoid long sequences of diverged execution by threads within the same warp;"
parallelism algo by Pollard (U+V) escape problem of collisions between kangaroos of the same herd;
this allows you to completely abandon the correction block because adding IF () inevitably breaks the parallelism of the GPU;

#################

to be continued..

[croxNN]

Telariust, there is nothing in Source Code, only README.md

[PrivatePerson]

-t 4 -bits 55 1.0M j/s [runtime]  00:04:01

-t 16 -bits 55 3.2M j/s [runtime]  00:04:33 

Code:

PS D:\btc\vs-kangaroo-0.01> ./vs-kangaroo_0.01.exe -v 1 -t 4 -bits 55
[###########################################################]
[#          Pollard-kangaroo PrivKey Recovery Tool         #]
[#          (based on engine of VanitySearch 1.15)         #]
[#                 bitcoin ecdsa secp256k1                 #]
[#                         ver0.01                         #]
[###########################################################]
[DATE(utc)] 09 Oct 2019 09:20:10
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[pow2bits]      55
[rangeW]        2^54..2^55 ; W = U - L = 2^54
[DPsize]        1024 (hashtable size)
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[pubkey#55] loaded
[Xcoordinate] 85A30D8413AF4F8F9E6312400F2D194FE14F02E719B24C3F83BF1FD233A8F963
[Ycoordinate] 0EB400323654CEC63999B56F4BA44E8B21AB92D9D697FABE4666DF3678585669
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] Sp-table of pow2 points - ready
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] recalc Sp-table of multiply UV
[UV] U*V=1*3=3 (0x03)
[optimal_mean_jumpsize] 134217728
[meanjumpsize#30] 107374182(now) <= 134217728(optimal) <= 207820998(next)
[i] Sp[30]|----------------J-------------------------------------------|Sp[31]
[i] this Sp set has low efficiency (over -25%) for this mean jumpsize
[JmaxofSp] Sp[30]=107374182 nearer to optimal mean jumpsize of Sp set
[DPmodule] 2^25 = 33554432 (0x0000000002000000)
[+] 1T+3W kangaroos - ready
[CPU] threads: 4
[th][tame#1] run..
[th][wild#1] run..
[th][wild#2] run..
[th][wild#3] run..
[-][ 00:04:00 ;   1.0M j/s; 249.0Mj  92.8%; dp/kgr=1.5; 00:00:18 ]
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[prvkey#55] 0x000000000000000000000000000000000000000000000000006ABE1F9B67E114
[i]   1.0M j/s; 250.0Mj of 268.0Mj  93.4%; DP 1T+3W=2+2=4; dp/kgr=2.0;
[runtime]  00:04:01
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[DATE(utc)] 09 Oct 2019 09:24:12
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[x] EXIT

Code:

PS D:\btc\vs-kangaroo-0.01> ./vs-kangaroo_0.01.exe -v 1 -t 16 -bits 55
[###########################################################]
[#          Pollard-kangaroo PrivKey Recovery Tool         #]
[#          (based on engine of VanitySearch 1.15)         #]
[#                 bitcoin ecdsa secp256k1                 #]
[#                         ver0.01                         #]
[###########################################################]
[DATE(utc)] 09 Oct 2019 09:36:15
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[pow2bits]      55
[rangeW]        2^54..2^55 ; W = U - L = 2^54
[DPsize]        1024 (hashtable size)
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[pubkey#55] loaded
[Xcoordinate] 85A30D8413AF4F8F9E6312400F2D194FE14F02E719B24C3F83BF1FD233A8F963
[Ycoordinate] 0EB400323654CEC63999B56F4BA44E8B21AB92D9D697FABE4666DF3678585669
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] Sp-table of pow2 points - ready
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[+] recalc Sp-table of multiply UV
[UV] U*V=7*9=63 (0x3f)
[optimal_mean_jumpsize] 536870912
[meanjumpsize#28] 603979773(now) <= 536870912(optimal) <= 1166305772(next)
[i] Sp[27]|----------------------------------------------J-------------|Sp[28]
[i] this Sp set has low efficiency (over -25%) for this mean jumpsize
[JmaxofSp] Sp[28]=313174696 nearer to optimal mean jumpsize of Sp set
[DPmodule] 2^25 = 33554432 (0x0000000002000000)
[+] 7T+9W kangaroos - ready
[CPU] threads: 16
[th][tame#1] run..
[th][wild#1] run..
[th][tame#3] run..
[th][tame#4] run..
[th][tame#5] run..
[th][tame#6] run..
[th][tame#7] run..
[th][tame#2] run..
[th][wild#2] run..
[th][wild#3] run..
[th][wild#4] run..
[th][wild#5] run..
[th][wild#6] run..
[th][wild#7] run..
[th][wild#9] run..
[th][wild#8] run..
[|][ 00:03:57 ;   3.2M j/s; 770.0Mj 287.1%; dp/kgr=13.5; 00:00:00 ]
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[prvkey#55] 0x000000000000000000000000000000000000000000000000006ABE1F9B67E114
[i]   2.8M j/s; 776.0Mj of 268.0Mj 289.0%; DP 7T+9W=13+14=27; dp/kgr=13.5;
[runtime]  00:04:33
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[DATE(utc)] 09 Oct 2019 09:40:49
[~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~]
[x] EXIT

[racminer]

..where exactly do you store the tame and wild kangaroos as it is done in the "tame.txt" and "wild.txt" files for the python code..

in hashtable
ok, i will add output to file distinguished points in next release

Thanks for your answer and all your answers.
The Hash table is only 1024 entries, is it enough for cases like #110 ?

[racminer]

-t 4 -bits 55 1.0M j/s [runtime]  00:04:01

-t 16 -bits 55 3.2M j/s [runtime]  00:04:33  

why are you  ?

scaling depends on CPU, ie # of cores (typically 2,4,8 ... or 56 if you have a Intel® Xeon® Platinum 9282 Processor )
 and # of threads per core (which is one or two)

 -t is generally equal to core number ... on some cpu's you might get better performance for -t equal to  2 x core number.
 

[PrivatePerson]

why are you  ?

scaling depends on CPU, ie # of cores (typically 2,4,8 ... or 56 if you have a Intel® Xeon® Platinum 9282 Processor )
 and # of threads per core (which is one or two)

 -t is generally equal to core number ... on some cpu's you might get better performance for -t equal to  2 x core number.
 

This is Ryzen 7 2700 (8 cores 16 threads)
I understand that -t is the number of threads.
The question is why the speed increases, but time does not decrease, more often it even increases.

[racminer]

why are you  ?

scaling depends on CPU, ie # of cores (typically 2,4,8 ... or 56 if you have a Intel® Xeon® Platinum 9282 Processor )
 and # of threads per core (which is one or two)

 -t is generally equal to core number ... on some cpu's you might get better performance for -t equal to  2 x core number.
 

This is Ryzen 7 2700 (8 cores 16 threads)
I understand that -t is the number of threads.
The question is why the speed increases, but time does not decrease, more often it even increases.

Even with higher speeds, runtime may fluctuate a lot.  In order to compare performances, you need  several trials.

[BurtW]

#################

BurtW, maybe I'm too active here, if you don’t like it, then you can ask me to leave and create a separate topic.

#################

No problem.  We enjoy your informative posts and have used several of your ideas in our program.

Right now I am very busy with work and my daughter is very busy in school so we have not had time to work on the program.

We will get back to our version when things slow down a bit.

BTW we keep all our points in memory in a hash table also.  Disk access is a no no, especially when we are targeting a GPU (eventually).

[MrFreeDragon]

BTW we keep all our points in memory in a hash table also.  Disk access is a no no, especially when we are targeting a GPU (eventually).

Can you explain why don't you keep the points on disk, and keep them only in memory? And also please tell which point you keep - every point, or just some multipliers of predefined number (let's say 10^10)?

[st0ffl]

The idea is of course to only make sqr(2^(bit-2)) operations.

nice idea, i will add as option of boost in next release

Thank's Telariust!
It will take time but i could try to implement the kangaroo method myself in c#,
to learn if it would be possible to detect a parallelism for the average usage of sqr(2^(bit-2)) operations, when halfing x values of the searchspace,
unless you can confirm from your experience that there is no such behaviour detectable?

Currently it's just like you would guess in a keyspace of 1024 that the privatekey is greater than 512...
BUT...
If it is possible to find a privatekey less than 512 in less than 150% of sqr(2^(bit-1)) it should be an average overall speedgain.

My current idea to achieve that would be with the cost of an extra wild, when pushing the searchspace to point Infinity.
This wild point could just be the negation point of the orginal point without or with offset.
Cause i don't see ECPoint subtraction implemented in your script, you can use addition:
therefore the ECPoint offset calculation to wrap the space arround Infinity should be G.Multiply(ORDER-SpaceL-(SpaceL/2)).

x2 speed-up, nice idea, i will add as option of boost in next release

Thank's

[PrivatePerson]

Even with higher speeds, runtime may fluctuate a lot.  In order to compare performances, you need  several trials.

Naturally I did a few measurements. Python scripts behaved the same way. The single-core and multi-core scripts showed approximately the same search time, although the multi-core speed was much higher.

[racminer]

Even with higher speeds, runtime may fluctuate a lot.  In order to compare performances, you need  several trials.

Naturally I did a few measurements. Python scripts behaved the same way. The single-core and multi-core scripts showed approximately the same search time, although the multi-core speed was much higher.

In this case, remains the question whether the program stops running immediately or not when one of the threads finds the solution. We need to ask the developper

[brainless]

Seems no more new update in kangroo subject, all waiting GPu ver, but developer have it, and he maybe waiting to find 110 puzzle, but till no news in updates and upgrades in kaangroo
anyway any modification for multiple pubkey find in range space at once, by input file (multiple pubkey)