Pollard's kangaroo ECDLP solver

[Jean_Luc]

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.

[WanderingPhilospher]

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!

[Jean_Luc]

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.

[WanderingPhilospher]

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.

I've used the mods on windows and they work.

[Jean_Luc]

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.

[Etar]

@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?

[Etar]

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

[arulbero]

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.

[Jean_Luc]

@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:

[MrFreeDragon]

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?

[Jean_Luc]

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

[HardwareCollector]

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.

[MrFreeDragon]

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 

EDIT:
https://twitter.com/MasterChangz/status/1264653806916124672

[Etar]

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
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..

[MrFreeDragon]

-snip-
In this case i have a question for what distance for ex.2AA need if range start from ffff
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]

[Etar]

-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.

[HardwareCollector]

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
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).

[Etar]

-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.

[WanderingPhilospher]

-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

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

[MrFreeDragon]

-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

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.