Author

Topic: Pollard's kangaroo ECDLP solver - page 116. (Read 56355 times)

full member
Activity: 1050
Merit: 219
Shooters Shoot...
May 29, 2020, 05:16:53 PM
I was testing "directory merge" function and RAM memory is quickly exhausted. I was thinking that I forgot to free temp HashTable in each reading iteration; but I changed the code and the problem remains Sad
The merged saveFile is 5GB, and in merge process takes up about 14GB of RAM.

I think the more obvious solution is to sort files from bigger to smallest when are merged; or use only small saveFiles.


On the other hand, the -ws flag I think is problematic when using -wsplit, generating larger files than necessary. Do you think it is interesting to separate the DP and the kangaroos into different save files?


As next improvements, I will work on improving the export of the DPs and the possibility of modifying the DP bits in a save file to reduce its size if we have chosen a too low DP value. It can also be interesting to remove from a save file the distances to share it without gifting the prize.

I tested dir merge on PC with 24GB RAM and 10 dir files that were probably 500MB a piece but I didn't check the RAM usage.

Alek76's version is similar to what you are talking about as far as separating files. He has (in current version) 8 text files that are generated, 4 tames and 4 wild. I modified it a little bit and used 2 tames and 4 wilds. Then, he has a python comparator that compares all the files to check for a solved key. I tried/trying to figure out how to merge that with JP's (this) version, but can't figure out how to read the files well enough to understand how to build the python comparator.
member
Activity: 316
Merit: 34
May 29, 2020, 04:23:32 PM
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..

Because the Tame Kangaroos are dependent only on the interval size, while the Wild Kangaroos are dependent on the interval size and the public key. We want to keep the algorithm as generic as possible, and also the ability to reuse the Tame Kangaroos for multiple key searches.

As relating to the Wild Kangaroos, [working_public_key] = [(original_public_key) - (beginning_range)*(secp256k1_generator_point)].
[distinguished_point] = [(+-traveled_distance)*(secp256k1_generator_point)] + [working_public key]

You will need to add back the (beginning_range) when there’s a collision to solve for the (original_public_key).


" and also the ability to reuse the Tame Kangaroos for multiple key searches. "

can we aspect multi pubkeys support coming, maybe yes or maybe no, its all depand dev thinking, maybe he prefer to work a lot more calc for client/server, or maybe he he think add this func and then optimize all thing togather
sr. member
Activity: 616
Merit: 312
May 29, 2020, 03:53:08 PM
-snip-
been seeing this one.
1:30:21  [GETWORK] INVALID CRC32 FILE > NEED:ffffffffd52c4232, GOT:79ffe57 is this still ok. thanks man, great piece.
It is not a problem, if CRC32 invalid, that file will be send in next time.
full member
Activity: 427
Merit: 105
May 29, 2020, 03:40:12 PM
If someone wants to run a solver with small DPs, but the server’s resources don’t allow it, then you can use the -wsplit option,
which appears in version 1.7 of the solver.
But in any case, you must have a PC that can merge files. I just had such a problem.
Now I can safely merge files on my home PC. In order not to do it all manually, you need a grabber and a merger.
File grabber is launched on the server, merger is launched on the home PC.
Merger communicates with the grabber and requests files from him. The graber sends, if any, and then removes them from the server.
The merger, in turn, after receiving the file from the grabber, starts the merge process, during which it is possible to find the key, after merge temp file deleted.
Grabber gives files only to an authorized merger.
If it helps someone, archive with source codes, compiled programs and example .bat files: https://drive.google.com/file/d/1wQWLCRsYY2s4DH2OZHmyTMMxIPn8kdsz
Edit: fixed little memory leak at grabber side.

As before, the sources under Purebasic.
mergeServer(grabber):
Code:
-pass >password for merger authorization
-port >listening port, where merger will be connect
-ext  >by this extension, the grabber will search for files in the folder,
       for ex. using -ext part, than you should start server with -w xxxx.part
mergeClient(merger):
Code:
-jobtime 60000>request a file from the grabber every 60s
-name >it is name of your merger, useless, just for stats
-pass >password for authorization(should be the same as in grabber)
-server >host:port grabber
-workfile >name of your masterfile
-merger >Kangaroo.exe by default
been seeing this one.
1:30:21  [GETWORK] INVALID CRC32 FILE > NEED:ffffffffd52c4232, GOT:79ffe57 is this still ok. thanks man, great piece.
newbie
Activity: 17
Merit: 0
May 29, 2020, 03:34:54 PM
I was testing "directory merge" function and RAM memory is quickly exhausted. I was thinking that I forgot to free temp HashTable in each reading iteration; but I changed the code and the problem remains Sad
The merged saveFile is 5GB, and in merge process takes up about 14GB of RAM.

I think the more obvious solution is to sort files from bigger to smallest when are merged; or use only small saveFiles.


On the other hand, the -ws flag I think is problematic when using -wsplit, generating larger files than necessary. Do you think it is interesting to separate the DP and the kangaroos into different save files?


As next improvements, I will work on improving the export of the DPs and the possibility of modifying the DP bits in a save file to reduce its size if we have chosen a too low DP value. It can also be interesting to remove from a save file the distances to share it without gifting the prize.
sr. member
Activity: 616
Merit: 312
May 29, 2020, 03:20:56 PM
-snip-
I also shared some files earlier.
Can you please upload your files to here: https://gofile.io
You can do it without registration, and you can delete them with your admin link at any time. Unfortunately google does not allow do download your file without google account.
i was try several times but got this
Code:
Error
The upload has failed
Please try again later, Gofile could be in maintenance.
try now dp=31 https://drive.google.com/file/d/1zmrmcQJ3NSbwnF2AJ4RH-vbab0VOgJSt
dp=28 https://drive.google.com/file/d/1eZNnWJnNdRhWp-ZnaxYhwfRVKZHiadEg
sr. member
Activity: 443
Merit: 350
May 29, 2020, 03:16:30 PM
-snip-
There is link to DP=31 file https://drive.google.com/file/d/1zmrmcQJ3NSbwnF2AJ4RH-vbab0VOgJSt

P.S. If somebody can share  work it will be good. Maybe one of us can solve key in this way.

I also shared some files earlier.
Can you please upload your files to here: https://gofile.io
You can do it without registration, and you can delete them with your admin link at any time. Unfortunately google does not allow do download your file without google account.
sr. member
Activity: 616
Merit: 312
May 29, 2020, 03:00:02 PM
-snip-
Did you lose all the DPs @ 31, when you dropped to 28?
I did not lose any DPs, they are only reduced to 28bit. Somewere i have file with dp=31, if you need i can share
Code:
DP bits   : 31
Start     : 2000000000000000000000000000
Stop      : 3FFFFFFFFFFFFFFFFFFFFFFFFFFF
Key       : 0309976BA5570966BF889196B7FDF5A0F9A1E9AB340556EC29F8BB60599616167D
Count     : 0 2^-inf
Time      : 00s
DP Size   : 383.0/485.2MB
DP Count  : 12483809 2^23.574
HT Max    : 85 [@ 03430F]
HT Min    : 19 [@ 00B5CE]
HT Avg    : 47.62
HT SDev   : 6.90
There is link to DP=31 file https://drive.google.com/file/d/1zmrmcQJ3NSbwnF2AJ4RH-vbab0VOgJSt

P.S. If somebody can share  work it will be good. Maybe one of us can solve key in this way.
full member
Activity: 1050
Merit: 219
Shooters Shoot...
May 29, 2020, 02:53:16 PM
Here is my merged workfile for pazzle#110(109bit)
https://drive.google.com/file/d/1eZNnWJnNdRhWp-ZnaxYhwfRVKZHiadEg
DP=28. there is not so many DPs because i start with DP=31(collected half of expected Dps) than drop to 28.
Maybe somebody it can help to solve key.
Code:
DP bits   : 28
Start     : 2000000000000000000000000000
Stop      : 3FFFFFFFFFFFFFFFFFFFFFFFFFFF
Key       : 0309976BA5570966BF889196B7FDF5A0F9A1E9AB340556EC29F8BB60599616167D
Count     : 0 2^-inf
Time      : 00s
DP Size   : 801.1/1216.5MB
DP Count  : 26183698 2^24.642
HT Max    : 152 [@ 02F8EB]
HT Min    : 57 [@ 029D90]
HT Avg    : 99.88
HT SDev   : 9.99
Did you lose all the DPs @ 31, when you dropped to 28?
sr. member
Activity: 616
Merit: 312
May 29, 2020, 02:38:06 PM
Here is my merged workfile for pazzle#110(109bit)
https://drive.google.com/file/d/1eZNnWJnNdRhWp-ZnaxYhwfRVKZHiadEg
DP=28. there is not so many DPs because i start with DP=31(collected half of expected Dps) than drop to 28.
Maybe somebody it can help to solve key.
Code:
DP bits   : 28
Start     : 2000000000000000000000000000
Stop      : 3FFFFFFFFFFFFFFFFFFFFFFFFFFF
Key       : 0309976BA5570966BF889196B7FDF5A0F9A1E9AB340556EC29F8BB60599616167D
Count     : 0 2^-inf
Time      : 00s
DP Size   : 801.1/1216.5MB
DP Count  : 26183698 2^24.642
HT Max    : 152 [@ 02F8EB]
HT Min    : 57 [@ 029D90]
HT Avg    : 99.88
HT SDev   : 9.99
full member
Activity: 1050
Merit: 219
Shooters Shoot...
May 29, 2020, 02:28:44 PM
-snip-
PS. Actually instead of solving pk110 within the range [2^109 ... 2^110-1] the program solves the key pk110s within the range [0 ... 2^109-1]
Thanks for the detailed answer. This is very clear now.
Can you help make it clear to me Smiley

So the tames work from range 0...meaning 0x0 to 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFF  (for pubkey 110)?

The range is shifted, not expanded. Shift means the move of start and end values both by the SAME value.
Instead of range [2000000000000000000000000000 ... 3fffffffffffffffffffffffffff] the program works with range [0 ... 1fffffffffffffffffffffffffff]

PS. Do you really like these hex values posted here? They are difficult to understand by a human (as difficult to count "f" and "0" signs). So i represented them earlier by the powers of 2 (2^109 and 2^110) which is much easier to understand.
I'll have to digest this Smiley the SAME value is throwing me off a little. It makes sense by what you said; you subtracted the 20000....from both values to get 0 and the 1ffff...
What is the advantage or purpose of shifting?

As far as ranges, I'm good with either, hex or powers, just wanted to keep it simple (for me, maybe for others) since we input a range start and range end on the input file versus a -bits flag.
sr. member
Activity: 443
Merit: 350
May 29, 2020, 02:14:55 PM
-snip-
PS. Actually instead of solving pk110 within the range [2^109 ... 2^110-1] the program solves the key pk110s within the range [0 ... 2^109-1]
Thanks for the detailed answer. This is very clear now.
Can you help make it clear to me Smiley

So the tames work from range 0...meaning 0x0 to 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFF  (for pubkey 110)?

The range is shifted, not expanded. Shift means the move of start and end values both by the SAME value.
Instead of range [2000000000000000000000000000 ... 3fffffffffffffffffffffffffff] the program works with range [0 ... 1fffffffffffffffffffffffffff]

PS. Do you really like these hex values posted here? They are difficult to understand by a human (as difficult to count "f" and "0" signs). So i represented them earlier by the powers of 2 (2^109 and 2^110) which is much easier to understand.
full member
Activity: 1050
Merit: 219
Shooters Shoot...
May 29, 2020, 01:34:57 PM
-snip-
PS. Actually instead of solving pk110 within the range [2^109 ... 2^110-1] the program solves the key pk110s within the range [0 ... 2^109-1]
Thanks for the detailed answer. This is very clear now.
Can you help make it clear to me Smiley

So the tames work from range 0...meaning 0x0 to 0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFF  (for pubkey 110)?
sr. member
Activity: 616
Merit: 312
May 29, 2020, 01:07:00 PM
-snip-
Because the Tame Kangaroos are dependent only on the interval size, while the Wild Kangaroos are dependent on the interval size and the public key. We want to keep the algorithm as generic as possible, and also the ability to reuse the Tame Kangaroos for multiple key searches.

As relating to the Wild Kangaroos, [working_public_key] = [(original_public_key) - (beginning_range)*(secp256k1_generator_point)].
[distinguished_point] = [(+-traveled_distance)*(secp256k1_generator_point)] + [working_public key]

You will need to add back the (beginning_range) when there’s a collision to solve for the (original_public_key).

thanks for answer.
Also can say, that i was made test with previous experience work.
And I can disappoint that it turned out to be slower..
I started to gain experience with the puzzle 54
do job>save work file>separated the tame kangaroos and kept in a new work file(I did not tame wild kangaroos)
This work file was as input for next pazzle..and so on to pazzle 84.
I also launched the same puzzles but without previous experience.
And always in 100% of cases, the key was found faster without using experience.
member
Activity: 144
Merit: 10
May 29, 2020, 12:56:27 PM
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..

Because the Tame Kangaroos are dependent only on the interval size, while the Wild Kangaroos are dependent on the interval size and the public key. We want to keep the algorithm as generic as possible, and also the ability to reuse the Tame Kangaroos for multiple key searches.

As relating to the Wild Kangaroos, [working_public_key] = [(original_public_key) - (beginning_range)*(secp256k1_generator_point)].
[distinguished_point] = [(+-traveled_distance)*(secp256k1_generator_point)] + [working_public key]

You will need to add back the (beginning_range) when there’s a collision to solve for the (original_public_key).
sr. member
Activity: 616
Merit: 312
May 29, 2020, 12:54:30 PM
-snip-
PS. Actually instead of solving pk110 within the range [2^109 ... 2^110-1] the program solves the key pk110s within the range [0 ... 2^109-1]
Thanks for the detailed answer. This is very clear now.
sr. member
Activity: 443
Merit: 350
May 29, 2020, 12:36:43 PM
-snip-
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..

The program shifts the range to 0, and also shifts the Public Key.

Example for puzzle key #110:
We know that public key is (pk110): 0309976ba5570966bf889196b7fdf5a0f9a1e9ab340556ec29f8bb60599616167d
And we also know that it is in the range [2^109 ... 2^110-1]

The GPU Solver shifts the range by 2^109 to the left, and making the search in the range [2^109 - 2^109 ... 2^110-1 - 2^109] which is [0 ... 2^109 - 1]
So, all the tames are generated within this range from 0 to 2^109-1.

As for wilds, they are generated not from the original public key pk110, but from another point: pk110 - 2^109 * G
This shifted point is pk110s: 02e2cec18b0aa6c9fe69f2dfd7b253594957a1840a3506cb17b4d80d1bd8c37d25

All the DPs in hashtable are within the range [0 ... 2^109-1]: for tame with have distance Td in this range and x-coordinate related to it, for wild we have distance Wd which is +/- [0 ... 2^108] and x-coordinate related to pk110s + Wd * G
All the wild points in hash table are also related to the shifted public key.

PS. Actually instead of solving pk110 within the range [2^109 ... 2^110-1] the program solves the key pk110s within the range [0 ... 2^109-1]
sr. member
Activity: 616
Merit: 312
May 29, 2020, 12:13:06 PM
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, 12:06:39 PM
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, 09: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.
Jump to: