Author

Topic: Pollard's kangaroo ECDLP solver - page 119. (Read 58667 times)

sr. member
Activity: 617
Merit: 312
May 29, 2020, 11:13:06 AM
Anybody can explain why tame DP shifted to zero?
For test i use pubkey 04e6dabff2705a80acc23ae121956873c4ff9fd31cb0faca522c33624e23657e04125c04d29ea83 874332ea8aef3b3467f22665a4970df415be756bcdf5675e569
range ffff...fffffffffffff  -dp 4
when i look to hashtable i see this
x: 5311104a8554e94684e07e9d8c0d112f
d: 0000000000000000000589fd3365a64e
Before i was think that programm add begin range to tame DP, but i see now that there no addiding.
becouse when 0000000000000000000589fd3365a64e * G get 6b4599cecd305b927a266d311d800005311104a8554e94684e07e9d8c0d112f and this is our x
In this case i have a question for what distance for ex.2AA need if range start from ffff Huh
ok, when we will start range from for ex. 2^109 in that case all distance before will be useless?
becouse they are will produce x-coordinates that is before range 2^109.
I do not understand this moment..
sr. member
Activity: 443
Merit: 350
May 29, 2020, 11:06:39 AM
Yes, right. There is a trade-off between time and memory. Zielar said he had enough memory.
Due to overhead the graph should be shifted to the right.

Jean_Luc, by the way, i read one article and it leads to twitter of a guy trying to brute the specific range. The article says he is bruteforcing all the bitcoin wallets, however as i read his tweet and saw the screenshot - I found your GPU solver. It is absolutely your program (Count, Deads and SaveWork). And he is running kangaroos for the specific range, probably #110  Cheesy

EDIT:
https://twitter.com/MasterChangz/status/1264653806916124672
member
Activity: 144
Merit: 10
May 29, 2020, 08:54:07 AM
zielar, how are you?

You used to perform 4sqrt(N) group operations, so your probability to find the #110 should be approx 90%. But why the funds still have not been transferred? from #110?
Don’t forget about Time-Memory Trade-Off (TMTO), there’s difference between just solving the challenge vs solving it as fast as possible. Your choice of distinguished points mask matters a lot as the interval size gets larger. If you want to minimize the distinguished points overhead, you need to use as much memory as possible. And 1.2TB of RAM should be sufficient to solve the 110-bit private key challenge as fast as possible even in the worst case.
sr. member
Activity: 462
Merit: 696
May 29, 2020, 08:43:47 AM
The plot does not take into consideration the DP overhead.
In his first try, zielar had a setup which create a very large overhead (too much kangaroos). An overhead more than 2 times bigger than the expected number of op, so he didn't manage to get something.
I helped him a bit yesterday to have a clean setup.
If all is going well, he will reach 50% probability Saturday evening (UTC+2).
Unfortunately no news from him since yesterday Sad
sr. member
Activity: 443
Merit: 350
May 29, 2020, 08:35:22 AM
zielar, how are you?

You used to perform 4sqrt(N) group operations, so your probability to find the #110 should be approx 90%. But why the funds still have not been transferred? from #110?
sr. member
Activity: 462
Merit: 696
May 29, 2020, 07:39:51 AM
@JeanLuc tell me please about shifting.
Indeed, in order to use the DP from the previous work, we still need to shift the range and subtract the range of the public key?

You can do without shifting, the shift is done only once at the beginning. Of course, if in one case you shit and in one case you do no shift all will be incompatible.

Anyway, I'm working on the merger to reduce memory consumption.
I added the plot of probability of success:



legendary
Activity: 1932
Merit: 2077
May 29, 2020, 06:41:46 AM
Question from newbie, please redirect me if it was already explained:
let's say I have public key (uncompressed, 04....). Is there a way to find the expected start/stop range?

No.
sr. member
Activity: 617
Merit: 312
May 29, 2020, 06:28:51 AM
Question from newbie, please redirect me if it was already explained:
let's say I have public key (uncompressed, 04....). Is there a way to find the expected start/stop range?
no or 0x01...0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
sr. member
Activity: 617
Merit: 312
May 29, 2020, 05:18:40 AM
@JeanLuc tell me please about shifting.
Indeed, in order to use the DP from the previous work, we still need to shift the range and subtract the range of the public key?

Example, what will happen if we do not shift the range (for example leading zero not used):
Start range 0, distance 1 so x coordinate  79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
ok we save this DP for next pazzle
New range for ex start from 32
32+distance 1 = 33 it is 1697ffa6fd9de627c077e3d2fe541084ce13300b0bec1146f95ae57f0d0bd6a5
So this DP will be incorrect
We need shift new range to zero and subtract the range of the public key.
Only in this case, in my opinion, the DP will be true.

And the second question. in your opinion .. will the previous DP help in finding a new key or is it a little extra weight since we need the points to be randomly scattered over the range, and not to be in one place?
sr. member
Activity: 462
Merit: 696
May 29, 2020, 04:14:55 AM
ok thanks.
Note that the count in the work files are inaccurate due to the counting granularity especially when using GPUs.
The good value to take in consideration is the DP count and the total number of iteration is ~DPcount*2^dpbit if all work files that has been merged have the same dpbit.
full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 29, 2020, 04:07:55 AM
In "wsplit" mode, the time and count should be reset after every save? When I merged all split files the total time are incorrect.

Yes you're right. I will fix this.
Thanks for the useful work, I will take your mods (work on windows ?) and apd it to the official release.
Wink


I've used the mods on windows and they work.
sr. member
Activity: 462
Merit: 696
May 29, 2020, 04:00:41 AM
In "wsplit" mode, the time and count should be reset after every save? When I merged all split files the total time are incorrect.

Yes you're right. I will fix this.
Thanks for the useful work, I will take your mods (work on windows ?) and apd it to the official release.
Wink
full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 29, 2020, 03:32:02 AM
In "wsplit" mode, the time and count should be reset after every save? When I merged all split files the total time are incorrect.

Code:
kangaroo -ws -d 22 -w 70/70-22 -wsplit -wi 30 70.txt

kangaroo -winfo 70/70-22_29May20_0
  Count     : 17936959488 2^34.062
  Time      : 20s

kangaroo -winfo 70/70-22_29May20_084011
  Count     : 42612829184 2^35.311
  Time      : 50s

kangaroo -winfo 70/70-22_29May20_092015
  Count     : 704108078080 2^39.357
  Time      : 14:12

What is the best way to combine all the save files?

I added a "Directory Merge" option to merge more than two files at once (https://github.com/PatatasFritas/FriedKangaroo/commit/f36c560135710f9956677eb3dcda78ffd1ccb0a4)




Nice addition!
sr. member
Activity: 462
Merit: 696
May 29, 2020, 02:50:05 AM
Hi,

I did a small program to calculate chance of finding the key (without taking in consideration DP overhead) after a certain number or group operation.
Each value are the result of 100.000 trials so we can expect a precision of 0.3%.

0.5*sqrt(N) P=4.606 %
1.0*sqrt(N) P=17.162 %
1.5*sqrt(N) P=34.138 %
2.0*sqrt(N) P=52.314 %
2.5*sqrt(N) P=68.049 %
3.0*sqrt(N) P=80.350 %
3.5*sqrt(N) P=88.846 %
4.0*sqrt(N) P=94.103 %
4.5*sqrt(N) P=97.164 %
5.0*sqrt(N) P=98.746 %
5.5*sqrt(N) P=99.424 %
6.0*sqrt(N) P=99.752 %

I will increase accuracy and number of point and add a nice plot to the README of the Kangaroo program.
newbie
Activity: 17
Merit: 0
May 29, 2020, 02:39:46 AM
In "wsplit" mode, the time and count should be reset after every save? When I merged all split files the total time are incorrect.

Code:
kangaroo -ws -d 22 -w 70/70-22 -wsplit -wi 30 70.txt

kangaroo -winfo 70/70-22_29May20_0
  Count     : 17936959488 2^34.062
  Time      : 20s

kangaroo -winfo 70/70-22_29May20_084011
  Count     : 42612829184 2^35.311
  Time      : 50s

kangaroo -winfo 70/70-22_29May20_092015
  Count     : 704108078080 2^39.357
  Time      : 14:12

What is the best way to combine all the save files?

I added a "Directory Merge" option to merge more than two files at once (https://github.com/PatatasFritas/FriedKangaroo/commit/f36c560135710f9956677eb3dcda78ffd1ccb0a4)


sr. member
Activity: 617
Merit: 312
May 29, 2020, 01:45:00 AM
Example with 40bits key

pubkey: 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4
priv: 0xe9ae4933d6

We get a wild DP from savefile, x-coord and distance
Code:
2bff14d4321506319af572ab7604e22f2d172 0000000000000000000000100d3439c4

Distance: 0x100d3439c4
Starting point (offset): 2^39 = 0x8000000000

Code:
0xe9ae4933d6 + 0x100d3439c4  - 2^39 = 0x79bb7d6d9a

The tame distance 0x79bb7d6d9a returns X-coord 0000157f1985299f1bda6646dd76bff14d4321506319af572ab7604e22f2d172.
I agree that you can tame wild kangaroos.


-snip-
I was "crack" my brain but cant understand how get this coordinates

(374deeae22c93f955cb83ad2071f7e2256f6e109cad7bca6d71dc7b24414bb36,171165b64fcd4f9916032c06f806f7293828d66300e543217875bea98daf734a)

for this starting point  - 40000000000000
-snip-
it is just 40000000000000 * G = (public key of 40000000000000)
You not need to do this, as say MrFreeDragon DP already shifted.
newbie
Activity: 17
Merit: 0
May 28, 2020, 07:38:02 PM
Example with 40bits key

pubkey: 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4
priv: 0xe9ae4933d6

We get a wild DP from savefile, x-coord and distance
Code:
2bff14d4321506319af572ab7604e22f2d172 0000000000000000000000100d3439c4

Distance: 0x100d3439c4
Starting point (offset): 2^39 = 0x8000000000

Code:
0xe9ae4933d6 + 0x100d3439c4  - 2^39 = 0x79bb7d6d9a

The tame distance 0x79bb7d6d9a returns X-coord 0000157f1985299f1bda6646dd76bff14d4321506319af572ab7604e22f2d172.
member
Activity: 873
Merit: 22
$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk
May 28, 2020, 06:43:52 PM
@JeanLuc and other folks who has knowledge in this area..
From what I realized that DP is just the x coordinate with a certain number of leading zeros .. like a brilliant among stones.
Kangaroo algorithm, creates a tribe of tame and a tribe of wild kangaroos.
Tame kangaroos are tied to a range, and wild to the desired public key.
Now the idea itself .. Why can not we use the experience of previous work?
What I mean. For example, we’ll start accumulating experience with a 54-bit key
The range where this private key located is
40000000000000
7fffffffffffff
and seek public key 0385a30d8413af4f8f9e6312400f2d194fe14f02e719b24c3f83bf1fd233a8f963
we can shift the range to 0
and subtract the beginning of the range from the public key
(0x85a30d8413af4f8f9e6312400f2d194fe14f02e719b24c3f83bf1fd233a8f963,0x0eb400323654cec63999b56f4ba44e8b21ab92d9d697fabe4666df3678585669)
-
(374deeae22c93f955cb83ad2071f7e2256f6e109cad7bca6d71dc7b24414bb36,171165b64fcd4f9916032c06f806f7293828d66300e543217875bea98daf734a)
=
(b1f8ba606a61026d1ecaa93d9e9ceb12260c33e92809ed1ecb0850a2856accc1,ac46d892583d7fdd24a25a229b6ea8d17add77b1f410a9d30441e0acbec19c74)
and range
0
3fffffffffffff
as result we will have key 0x2ABE1F9B67E114
if we add range we can regenerate real key
0x2ABE1F9B67E114+0x40000000000000=0x6ABE1F9B67E114
So we have a saved working file, where there are DP both tame and wild kangaroos in range 0-3fffffffffffff
DP of wild kangaroos we do not need more  so they are tied to the public key.
We can cut only tame kangaroos points from the work file and save to a new file.
And this tame will be correct for next puzzle because they are in the same range as next pazzle(after shifting ofcourse)
So we can use this file like initial to next pazzle
Next 59bit Puzzle..
range
800000000000000
fffffffffffffff
and seek public key 0348e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d
do the same thing, shift the range to 0 and subtract the beginning of the range from the public key
(0x48e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d,0xd094fcabf8995e2a25c73298a9f7419720db622daff89c67fd5535f6ac29720f)
-
(8991225911b9132d28f5c6bc763ceab7d18c37060e8bd1d7ed44db7560788c1e,da8b4d987cc9ac9b27b8763559b136fa36969c84fdef9e11635c42228e8f0ef1)
=
(2b90a8680d08cf81e15e209acadbb16b7bdff19787d6d13ca6a7852fee8d1013,447a29425ea9773471ad9810d21a976cf5bd4bdb46d0c8ae537591dce43252f2)
and range
0
7ffffffffffffff
Don`t forget that we already have some tame DPs on this range(0-3fffffffffffff), so we should find collision faster!
result key is 0x7C07A1825367BBE
add range and real key
0x7C07A1825367BBE+0x800000000000000=0xFC07A1825367BBE
than do the same, cut from work file only tame kangaroos, save and solve next pazzle...
In this case, after each puzzle, we will already have more and more DP points from tame kangaroos.
What you think?


Etar, can You explain how You get coordinates for starting point of range ?

Quote

40000000000000
7fffffffffffff
and seek public key 0385a30d8413af4f8f9e6312400f2d194fe14f02e719b24c3f83bf1fd233a8f963
we can shift the range to 0
and subtract the beginning of the range from the public key
(0x85a30d8413af4f8f9e6312400f2d194fe14f02e719b24c3f83bf1fd233a8f963,0x0eb400323654cec63999b56f4ba44e8b21ab92d9d697fabe4666df3678585669)
-
(374deeae22c93f955cb83ad2071f7e2256f6e109cad7bca6d71dc7b24414bb36,171165b64fcd4f9916032c06f806f7293828d66300e543217875bea98daf734a)
=
(b1f8ba606a61026d1ecaa93d9e9ceb12260c33e92809ed1ecb0850a2856accc1,ac46d892583d7fdd24a25a229b6ea8d17add77b1f410a9d30441e0acbec19c74)
and range
0
3fffffffffffff


I was "crack" my brain but cant understand how get this coordinates

(374deeae22c93f955cb83ad2071f7e2256f6e109cad7bca6d71dc7b24414bb36,171165b64fcd4f9916032c06f806f7293828d66300e543217875bea98daf734a)

for this starting point  - 40000000000000

 Huh

Please.

With respect to you !!!


BR !
full member
Activity: 1162
Merit: 237
Shooters Shoot...
May 28, 2020, 05:04:01 PM
Jean_Luc, I want to look at the table which is saved to workfile. But as I understood, only 128bit are saved for X-coordinate and 126bit for distance (together with 1 bit for sign and 1 bit for kangaroo type).

Anyway, what is the easiest way to receive the whole table in txt format. I easily could read from binary file the head, dp, start/stop ranges, x/y coordinates for key. After that the hash table is saved with a lot of 0 bytes....
Can you just briefly describe the hash table structure which is saved to binary file?

if you still haven't managed to export the workfile, here are the changes I made to the code to export the DPs to txt.

The X-coord is 128+18 bits and distance 126bits. The X-coordinate could be re-generated from the distance if necessary.

https://github.com/PatatasFritas/FriedKangaroo/commit/1669df5f91ef2cc8a7619b21f66883fa164ab602

Any way, to export everything, headers and all so that it is like a text work file that can be merged with another text work file?
sr. member
Activity: 443
Merit: 350
May 28, 2020, 04:48:20 PM
-snip-
What is the best way to compare TXT lists?  I'm going to separate wild and tame in two different files, merge+sort with my own files and use uniq -d to find duplicates.
-snip-

I uploaded tames and wilds in different files: https://gofile.io/d/trLIMy
However I see you have already made a bash script to separate them Smiley

To compare txt files for unique records you can also can use sets by python: set(A)&set(B) --> set of unique records, where A and B are lists from different txt files.
Jump to: