Pollard's kangaroo ECDLP solver - page 71.

fxsniper

member

Activity: 406

Merit: 47

Quote from: NotATether on March 10, 2021, 01:36:55 PM

Where in the warping cyberspace is "PRIx64" defined? Huh

Kangaroo.cpp, line 169, function SetDP(int size) [I think that's the name of it off the top of my head]

Code:

::printf("DP size: %d [0x%" PRIx64 "]\n",dpSize,dMask);

This is ostensibly supposed to be the Unix format code for a 64-bit hex number, but it's not defined anywhere in the program. Could it be in a standard header file?

I have to change it to 256-bit (4 64-bit format codes strung together) because I wound up having to increase the DP size to 256 bits as well because I didn't feel like having ANOTHER field just for a truncated lowest-64 bits of the kangaroo position, especially when said field is shoved inside Int.bits64[3] of a 128-bit kangaroo and all the code references that.

There are 2 more occurrences of this which you can see with https://github.com/JeanLucPons/Kangaroo/search?q=PRIx64&type=

Could you help to fork update to version 256bit (for use up to #160 puzzle)?
may be work better than limited to fit 120 bits

JeanLucPons still on forum, Can possible to update? or may be limited because of have some problem technic when use work with high bits or not?

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Where in the warping cyberspace is "PRIx64" defined? Huh

Kangaroo.cpp, line 169, function SetDP(int size) [I think that's the name of it off the top of my head]

Code:

::printf("DP size: %d [0x%" PRIx64 "]\n",dpSize,dMask);

This is ostensibly supposed to be the Unix format code for a 64-bit hex number, but it's not defined anywhere in the program. Could it be in a standard header file?

I have to change it to 256-bit (4 64-bit format codes strung together) because I wound up having to increase the DP size to 256 bits as well because I didn't feel like having ANOTHER field just for a truncated lowest-64 bits of the kangaroo position, especially when said field is shoved inside Int.bits64[3] of a 128-bit kangaroo and all the code references that.

There are 2 more occurrences of this which you can see with https://github.com/JeanLucPons/Kangaroo/search?q=PRIx64&type=

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: fxsniper on March 10, 2021, 06:35:22 AM

Quote from: NotATether on March 10, 2021, 05:04:16 AM

Quote from: fxsniper on March 07, 2021, 11:42:27 PM

both script do same but feel pollard-kangaroo-multi.py work better pollard_kangaroo.txt

It's also sending some useless stuff over the network to Kangaroo servers, e.g "h" the hash table index, this is useless because the hash table is local to one host, but it's stuffed in the "x" 128-bit member so it's sent anyway. Same with the kangaroo type which is already embedded in the lowest by of "kIdx", it makes no sense to put it in a hash entry struct as well, hash entries aren't even sent across the network. Nitty gritty details that complicate transitioning it to unsigned 256 bit.

if we solve puzzle #120 already so, What next?
how can extend 120 bits

or that mean limited wide of range scan for 120 bit and for high bit like 160 bits need to split 2 keyspace or 4 keyspace and scan each method use program something like that

Do I miss understands.

Currently with JLPs program you can search up to #125 of the puzzle. There is only enough "room" to store the #125s distance traveled (private key)

fxsniper

member

Activity: 406

Merit: 47

Quote from: NotATether on March 10, 2021, 05:04:16 AM

Quote from: fxsniper on March 07, 2021, 11:42:27 PM

both script do same but feel pollard-kangaroo-multi.py work better pollard_kangaroo.txt

Very educational scripts you shared. It's dumbed down enough for someone to follow along the different stages (preparing the tame and wild herds within two different ranges, showing how the jump table of G points is made, converting the DP mask to a difficulty etc. which I leaned doesn't have to have all bits adjacent to it.

Something that's bothering me about Jean_Luc's program though is how we stuff the kangaroo type in the distance 128-bit number but we have a separate member "kIdx" in ITEM and DP structs that can be modulus'ed by 2 to give the kangaroo type - The kangaroos in a vector alternate between wild and time, which corresponds to what these scripts are showing.

It's also sending some useless stuff over the network to Kangaroo servers, e.g "h" the hash table index, this is useless because the hash table is local to one host, but it's stuffed in the "x" 128-bit member so it's sent anyway. Same with the kangaroo type which is already embedded in the lowest by of "kIdx", it makes no sense to put it in a hash entry struct as well, hash entries aren't even sent across the network. Nitty gritty details that complicate transitioning it to unsigned 256 bit.

That script can show newbies who interest or want to know how it works just setting to show message on working
script is one file easy to read too
old script but record to try use it study, try use with low key space and low number of puzzle under 40 bits fast to found and learn how it works

and What mean Kangaroo limited 120 bits
However all Kangaroo version have limited for 120 bits only right both Jean_Luc's program have problem with limited 120 bits.
if we solve puzzle #120 already so, What next?
how can extend 120 bits

or that mean limited wide of range scan for 120 bit and for high bit like 160 bits need to split 2 keyspace or 4 keyspace and scan each method use program something like that

Do I miss understands.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: fxsniper on March 07, 2021, 11:42:27 PM

both script do same but feel pollard-kangaroo-multi.py work better pollard_kangaroo.txt

Very educational scripts you shared. It's dumbed down enough for someone to follow along the different stages (preparing the tame and wild herds within two different ranges, showing how the jump table of G points is made, converting the DP mask to a difficulty etc. which I leaned doesn't have to have all bits adjacent to it.

Something that's bothering me about Jean_Luc's program though is how we stuff the kangaroo type in the distance 128-bit number but we have a separate member "kIdx" in ITEM and DP structs that can be modulus'ed by 2 to give the kangaroo type - The kangaroos in a vector alternate between wild and time, which corresponds to what these scripts are showing.

It's also sending some useless stuff over the network to Kangaroo servers, e.g "h" the hash table index, this is useless because the hash table is local to one host, but it's stuffed in the "x" 128-bit member so it's sent anyway. Same with the kangaroo type which is already embedded in the lowest by of "kIdx", it makes no sense to put it in a hash entry struct as well, hash entries aren't even sent across the network. Nitty gritty details that complicate transitioning it to unsigned 256 bit.

fxsniper

member

Activity: 406

Merit: 47

Quote from: itod on March 09, 2021, 12:53:26 PM

Quote from: fxsniper on March 09, 2021, 08:48:39 AM

However old python code may be interesting if someone can use python connect and work with AI. tensor flow and Keras do deep learning work with kangaroo I mean modify to work beater

What has AI to do with finding the private keys? AI can not help at all with kangaroos.

I don't really know much

if we still use pure kangaroo , now we still stuck with high bits high range high keyspace

kangaroo need to jump a lot may be too many days jumps and jumps to new position scan

I don't know how kangaroo use pubkey XY to calculate but point XY use for calculate

Can possible to create dataset use method private key generate with public point and train AI to give some value and use kangaroo to get point to jump or do something like that ?
Use AI. predict key space and give it to kangaroo ?

Any idea?

still need to AI. expert help to analysist

itod

legendary

Activity: 1988

Merit: 1077

Honey badger just does not care

Quote from: fxsniper on March 09, 2021, 08:48:39 AM

However old python code may be interesting if someone can use python connect and work with AI. tensor flow and Keras do deep learning work with kangaroo I mean modify to work beater

What has AI to do with finding the private keys? AI can not help at all with kangaroos.

fxsniper

member

Activity: 406

Merit: 47

Quote from: bigvito19 on March 09, 2021, 07:49:24 AM

Everyone just about knows of that old version of kangaroo with python already. We are on the new version of kangaroo that uses distinguished points (DP) method now.

Thanks
rights that old python code, I just use learning about how Kangaroo it works (easy to show how it work and read code on one files or print show display data how it works for use this tools better

For real use use JeanLucPons Kangaroo with GPU is faster
https://github.com/JeanLucPons/Kangaroo

However old python code may be interesting if someone can use python connect and work with AI. tensor flow and Keras do deep learning work with kangaroo I mean modify to work beater

bigvito19

full member

Activity: 706

Merit: 111

Quote from: fxsniper on March 09, 2021, 12:30:28 AM

if anyone try using python script and require to use gmpy2 library

http://bitchain.pl/100btc/pollard_kangaroo.txt
https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo.py
https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo-multi.py

or use BSGS and script use gmpy2
or other script generate bitcoin address and use gmpy2 to accelerate calculate for faster

use library gmpy2 make calculate faster

install gmpy2 on linux

need to install libgmp first after that then install gmpy2 normal

Code:

apt-get install libgmp-dev
apt-get install libmpfr-dev
apt-get install libmpc-dev

pip install gmpy2

install gmpy2 on anaconda (windows 10)
Anaconda Individual Edition or Miniconda
use conda install
command

Code:

conda install gmpy2

install gmpy2 on python windows 10
download gmpy2 from this url
https://www.lfd.uci.edu/~gohlke/pythonlibs/
choose version macth with you python version
example download
gmpy2‑2.0.8‑cp39‑cp39‑win_amd64.whl

command

Code:

pip install gmpy2‑2.0.8‑cp39‑cp39‑win_amd64.whl

Everyone just about knows of that old version of kangaroo with python already. We are on the new version of kangaroo that uses distinguished points (DP) method now.

fxsniper

member

Activity: 406

Merit: 47

if anyone try using python script and require to use gmpy2 library

http://bitchain.pl/100btc/pollard_kangaroo.txt
https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo.py
https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo-multi.py

or use BSGS and script use gmpy2
or other script generate bitcoin address and use gmpy2 to accelerate calculate for faster

use library gmpy2 make calculate faster

install gmpy2 on linux

need to install libgmp first after that then install gmpy2 normal

Code:

apt-get install libgmp-dev
apt-get install libmpfr-dev
apt-get install libmpc-dev

pip install gmpy2

install gmpy2 on anaconda (windows 10)
Anaconda Individual Edition or Miniconda
use conda install
command

Code:

conda install gmpy2

install gmpy2 on python windows 10
download gmpy2 from this url
https://www.lfd.uci.edu/~gohlke/pythonlibs/
choose version macth with you python version
example download
gmpy2‑2.0.8‑cp39‑cp39‑win_amd64.whl

command

Code:

pip install gmpy2‑2.0.8‑cp39‑cp39‑win_amd64.whl

fxsniper

member

Activity: 406

Merit: 47

reference with this kangaroo python script
http://bitchain.pl/100btc/pollard_kangaroo.txt

easy to understand how kangaroo. works

What value in hex they random for match
calculate from what formula? (or them random)

tame.txt

Code:

25231ba5231e46285d928fa2bef328227c1c510bcdabb7dd8b0161eec5bbae98 74319
25f3154199d497085b1798b6786d52fd74944ff4cd891844e923aab8e4561eb8 69734
7c6d52862d161ddbf90c5d1649397d3276471876b9ca4fed98e322b8c42648f0 77088
f02ba4892f446cb051104c5840c4f62ef94f6941e826277c531daa1848e9d420 57009
9f34d91a41d61c0e0d26d8ce856640020c12daccd076150787cbd16d3e78ef98 74399
8a0866dd4452056244d588f101c4801d856781a02b777f72439124dbb2b5a908 61382
15e4b924f87ef2c65e83ab1cbc501c7d0fec4227c10254e517c4af646af2eb00 57049

wild.txt

Code:

d280dc5d4915740ccf80bda64e07455fc58eaba90d9072589f726f5763ecf788 14021
b8e2cb115afb3f652e9b5451750d1b0e83659ea29b670380c7a76716ede4dfb0 27618
e7f9306469bdfbbf6099dd520c0a1469deb0a7cd61b1851d69d46b2e2cf6fe98 27874
076681af5c9838ce36787b84afc19bf5c0faf5c3bf0c6faff63959af3844f3f0 35316
a67e03aff0b98a930762dc399b46b69ed6104e97069eddce107ee77e3f889cf0 16981
15e4b924f87ef2c65e83ab1cbc501c7d0fec4227c10254e517c4af646af2eb00 5539
5a24b5bcc6b4f5a02620c2daa903cd81f568f426a41b1c1dc8c18f8a049622b0 28299
9f0e02a15a6dc2be1b338f9f4b0ea95e887d5e6eef30007e4d63d0729093d910 12160
e12b8339a1086c3c58bd69adf6516af5f2f0ec21d71666073aed56a97d6d09c0 28619

match
15e4b924f87ef2c65e83ab1cbc501c7d0fec4227c10254e517c4af646af2eb00 57049

15e4b924f87ef2c65e83ab1cbc501c7d0fec4227c10254e517c4af646af2eb00 5539

Study kangaroo
https://github.com/Telariust/pollard-kangaroo
setup option flag_verbose

flag_verbose = 2 # 0, 1, 2

warning show verbose work show a lot of information

both script do same but feel pollard-kangaroo-multi.py work better pollard_kangaroo.txt

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: fxsniper on March 06, 2021, 03:23:21 AM

How can we know what happen with higher bits or large range ?

I'm currently working on increasing the maximum range - when that's done I'll release the code so you guys can test this for yourselves.

fxsniper

member

Activity: 406

Merit: 47

Quote from: WanderingPhilospher on March 05, 2021, 11:10:03 PM

@fx; the quick version. The kangaroo program basically creates wild and tame kangaroos. Both are set out to look for the distinguish point size you designate. So let's say you set dp to 20 (that will be a pubkey that has 5 leading zeros 0x00000; 5x4 = 20). Each time a dp is found, it is recorded in a hash table (the location and the distance traveled), if a tame visits a dp and a wild visits the same dp, then the key is solved. The kangaroos keep hopping around until a "collision" occurs when a tame and wild visit same dp (location).
Now, you talk about modifying it to not make it a kangaroo program, what would you want or change? Might be a better program to tweak to suit what you are looking for.

Thank you very very much WanderingPhilospher

you explain quick version and with image illustration on JeanLucPons Kangaroo github page now I understand better
https://raw.githubusercontent.com/JeanLucPons/Kangaroo/master/DOC/paths.jpg
first time I just read code and try understand

good to know how tools it works (better than use tools only)

How can we know what happen with higher bits or large range ?
may be start point long too much difference
I try to find what problem and fix that point

I think may be try to write code to save data to can read like image illustration plot graph

How 2 public point X, Y (from public key) use to calculate on Kangaroo?

I think I need to more learn fundamental basic and help can figure out

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: fxsniper on March 05, 2021, 10:22:01 PM

I would like to learn more about kangaroo code for modify.
may be start from kangaroo python script one file easy to modify than C++ code
(sorry I am not coding I am not programmer, just power user know more about computer more end user)

may be my mistake modify code will make kangaroo jump to hit target LOL.

I know kangaroo is code best already. may be change it make it not kangaroo.

just want try to so some possible.

What is kangaroo variable to can modify it like add more value to high?

What is kangaroo power variable on code?

What is tame and wild on kangaroo ?
look like two array and program do compare two value inside right?

@fx; the quick version. The kangaroo program basically creates wild and tame kangaroos. Both are set out to look for the distinguish point size you designate. So let's say you set dp to 20 (that will be a pubkey that has 5 leading zeros 0x00000; 5x4 = 20). Each time a dp is found, it is recorded in a hash table (the location and the distance traveled), if a tame visits a dp and a wild visits the same dp, then the key is solved. The kangaroos keep hopping around until a "collision" occurs when a tame and wild visit same dp (location).
Now, you talk about modifying it to not make it a kangaroo program, what would you want or change? Might be a better program to tweak to suit what you are looking for.

fxsniper

member

Activity: 406

Merit: 47

I would like to learn more about kangaroo code for modify.
may be start from kangaroo python script one file easy to modify than C++ code
(sorry I am not coding I am not programmer, just power user know more about computer more end user)

may be my mistake modify code will make kangaroo jump to hit target LOL.

I know kangaroo is code best already. may be change it make it not kangaroo.

just want try to so some possible.

What is kangaroo variable to can modify it like add more value to high?

What is kangaroo power variable on code?

What is tame and wild on kangaroo ?
look like two array and program do compare two value inside right?

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: NotATether on March 05, 2021, 10:55:52 AM

Quote from: WanderingPhilospher on March 05, 2021, 08:52:50 AM

Here are what they look like:

Code:

63a169e28af90b75159c93ac88638314 -0000006f7d4a376f241adf3febd1ce73
779155e640a6f97c0d87b47ee5eec0f6 00000bc152a6b02a0bc5730dd5be8ae0

Since these are all 128-bit numbers I'm guessing the left numbers are tame kangaroo positions and the right numbers are distances (with their bit 126 set to 0=TAME constant) right?

This might sound like a dumb question but I also assume the px and py pointers above are the public keys right? No way those can be private keys or kangaroo positions because there are two of these.

These are wild DPs, tames do not use the '-' signs as they are all positive?

Yes, if you looked at a tame file, the left is pubkey x coord and that pubkey's priv key is on the right side. For the wild, the distance is based off of Y coord position, not distance traveled...I do believe that's how it works. Basically, if you took a wild dp and ran the priv key, it wouldn't correlate to the pubkey but the tames do.

Here are examples of mine:
Tames

Code:

3AA3BB15292F3A2688A85F1DC635E159BF18120631AE07AA4844EF9D00000000 000000000000000000000000000000000000000000136B4461F2984CBB55F8CA
1B91BF8C8C3993578623E10E9D979FE8C3FAE2C390A48997930416A700000000 0000000000000000000000000000000000000000001E70CC8AAB08D481DD25AD

Wilds

Code:

087A24CA49535730AAEFBAB161100740BECF3187F27E9F94FA34709B00000000 0000000000000000000000000000000000000000000A021D0CD9D38B5BA7639D
79E73EC2D79A6E794B692B03910D31137936859E9505B92316AA807000000000 00000000000000000000000000000000000000000001D3C65E1F9264DECB72ED

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: WanderingPhilospher on March 05, 2021, 08:52:50 AM

Here are what they look like:

Code:

63a169e28af90b75159c93ac88638314 -0000006f7d4a376f241adf3febd1ce73
779155e640a6f97c0d87b47ee5eec0f6 00000bc152a6b02a0bc5730dd5be8ae0

Since these are all 128-bit numbers I'm guessing the left numbers are tame kangaroo positions and the right numbers are distances (with their bit 126 set to 0=TAME constant) right?

This might sound like a dumb question but I also assume the px and py pointers above are the public keys right? No way those can be private keys or kangaroo positions because there are two of these.

WanderingPhilospher

full member

Activity: 1232

Merit: 242

Shooters Shoot...

Quote from: NotATether on March 05, 2021, 04:21:01 AM

Note: This was posted in the VanitySearch thread by mistake and I later moved it here.

Does anyone here know if the GPU engine makes use of the flags at the end of "distance"? In the ITEM struct there is px,py for X and Y coordinate of a kangaroo and then there's a "d" member 128-bits long that's for the distance.

In the CPU engine the 126'th bit is used as the kangaroo type and the 127'th bit is used as a sign bit.

It in GPU/GPUEngine.cu it doesn't look like the type bit is used at all:

In my (experimental in-development) build of Kangaroo I moved the flags out to an extra parameter so I would like to know if I can safely remove that from here.

Here are what they look like:

Code:

63a169e28af90b75159c93ac88638314 -0000006f7d4a376f241adf3febd1ce73
779155e640a6f97c0d87b47ee5eec0f6 00000bc152a6b02a0bc5730dd5be8ae0

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Note: This was posted in the VanitySearch thread by mistake and I later moved it here.

Does anyone here know if the GPU engine makes use of the flags at the end of "distance"? In the ITEM struct there is px,py for X and Y coordinate of a kangaroo and then there's a "d" member 128-bits long that's for the distance.

In the CPU engine the 126'th bit is used as the kangaroo type and the 127'th bit is used as a sign bit.

It in GPU/GPUEngine.cu it doesn't look like the type bit is used at all:

Code:

void GPUEngine::SetKangaroo(uint64_t kIdx,Int *px,Int *py,Int *d) {

  int gSize = KSIZE * GPU_GRP_SIZE;
  int strideSize = nbThreadPerGroup * KSIZE;
  int blockSize = nbThreadPerGroup * gSize;

  uint64_t t = kIdx % nbThreadPerGroup;
  uint64_t g = (kIdx / nbThreadPerGroup) % GPU_GRP_SIZE;
  uint64_t b = kIdx / (nbThreadPerGroup*GPU_GRP_SIZE);
...

In my (experimental in-development) build of Kangaroo I moved the flags out to an extra parameter so I would like to know if I can safely remove that from here.

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: mamuu on March 01, 2021, 01:55:12 PM

OpenCL or Cuda? I am currently using Nvidia Card. As far as I understand, OpenCL looks more advantageous. My goal is to reach the EllipticCurve Point Arithmetic library that works with more than one graphics card. Running Graphics Cards Rig line or Graphics card sharing system such as https://vast.ai
For now, I want to try it on my own computer.

Sounds like you should go with OpenCL then. I think there's an SDK bundled with CUDA toolkit IIRC, but you definitely already have OpenCL drivers provided by NVIDIA installed.

You are better off skimming an OpenCL tutorial first such as https://www.codeproject.com/Articles/92788/Introductory-Tutorial-to-OpenCL without actually writing the example code in there since you don't need them.

I'd probably move out the file saving code from the GPU, you'll only be able to save files from C language on CPU.

Topic: Pollard's kangaroo ECDLP solver - page 71. (Read 60189 times)