Pollard's kangaroo ECDLP solver

[zielar]

Here is the latest state of my work:


And a few questions:
1. Someone mentioned the percentage of chances of not finding the correct key. What percentage is it?
2. How to increase the likelihood of finding the correct key? By reducing "dp"?
3. Does increasing NB_JUMP have any effect on the work results ?? If so, to what value?
4. Does increasing NB_RUN have any effect on work results ?? If so, to what value?
5. Is the minimum next DP_COUNT threshold at which I should expect the key known? can it appear at any time?
6. ... or should I not expect him anymore?
7. After analyzing the posts of colleagues above - is the application written so as to eliminate ACTIONALLY "empty" jumps [ie e.g. eliminating the possibility that two clients are jumping the same, or repeats jumps that have already taken place?]

I am asking because I want to assess the sense of further work without making any changes

P.S. I start the server without -i save.work, because each subsequent restart that occurs - is the result of my manual shutdown to change the progress save file when it already takes over 1GB, as well as save progress every 600 seconds. Since yesterday - it does not disappoint.

[1714161463]

1714161463

[1714161463]

1714161463

[1714161463]

1714161463

[1714161463]

1714161463

[Jean_Luc]

No there is not yet feedback to eliminate dead kangaroo and when 2 kangaroos collide in the same herd they starts to produce a new dead at each dp but this is normal only one DP is added to the hash table.

An other things is when you reach ~sqrt(n) jumps, kangaroo starts to walk their neighbor.

As there is no feedback, the number of dead will increase a lot. At this stage, it is better to restart clients.

If 2 clients choose a same starting position you have dead kangaroos since the beginning.
Here I need to improve the seed which is at the second, so if 2 clients starts at the same second they will be identical and dead will increase at high speed immediatly when they starts.

To evaluate the chance of falling in a above trap, you need to know the total number of kangaroo which is used to determine the DP overhead.

I will also add a kangaroo counter in the server to help.

I will publish a release with server fix, -o option, idle client closure timeout to 1 hours, and add a kangaroo counter.

The probability to find the key at ~2*sqrt(n) jumps is roughly 50% and should be roughly 80% at 4*sqrt(n) jumps (this does dot take in consideration the DP overhead).

Edit: If you change NB_JUMP, you break the compatibility with previous work file.
Edit2: If you decrease DPbit, you will still be able to use the previous work file, a DP with 20 leading 0 bits is also a DP with 18 leading 0 bits...

[MrFreeDragon]

Jean_Luc, how many jumps zielar reached in his work? The screenshot shows the total count 0 2^-inf - how to understand the real number of jumps?

If 2 clients choose a same starting position you have dead kangaroos since the beginning.
Here I need to improve the seed which is at the second, so if 2 clients starts at the same second they will be identical and dead will increase at high speed immediatly when they starts.

For better random, some entropy should be added (like the entropy taken from the computer digital fingerprint). Different machines will have different finger prints.

[j2002ba2]

An other things is when you reach ~sqrt(n) jumps, kangaroo starts to walk their neighbor.

Kangaroos should collide at ~sqrt(n)/NumKangaroos jumps. Otherwise something is very wrong.

[Jean_Luc]

The total number of jumps is equal to number of DP * 2^dpbit => 2^(28+28.7) = 2^56.6 (2 times more)
But I don't the total number of kangaroo to evaluate the overhead ?
For the seed I will switch to cryptosecure rng.

Kangaroos should collide at ~sqrt(n)/NumKangaroos jumps. Otherwise something is very wrong.

Right, i mean total number of jumps.

[Jean_Luc]

I published the 1.6.

[zielar]

I published the 1.6.

Many thanks.
I will update clients and server after returning in about two hours because I'm out of reach.  I am asking for tips and suggestions on how best to solve it?  Which startup command should I use for each client and which one for the server?

[HardwareCollector]

How many jump do you have in total at the moment for #110?

This is my -winfo from fully merged job to this time:

could you share your work file?

I don't see a problem ... As soon as I start working on #115 :-)

In all of the experiments that I’ve done with Jean_Luc’s software, I don’t recall going that long (~4.6(sqrt(N)) without some sort of a collision with a properly chosen DP mask, something might be wrong there. But what I find even more interesting is your choice of a very high 28-bit mask, how did you decide that this was the proper choice for your setup?

Out of courtesy, I will give you until this coming Sunday to finish. If not, I will enter the race with 128 RTX 2080 Tis and 2TB of RAM (22-bit DP mask), and with that setup, my worst case is five days based on experimentation with my own implementation with distributed hash tables.

I wish you the best of luck and I hope that you succeed, we can learn a lot from your data on how to choose the optimal DP point mask.

[WhyMe]

I published the 1.6.

Many thanks.
I will update clients and server after returning in about two hours because I'm out of reach.  I am asking for tips and suggestions on how best to solve it?  Which startup command should I use for each client and which one for the server?

Dude, with your insane power you just have to wait less than few days to scan the full range of keys, what do you want more ?

[Etar]

I published the 1.6.

GPUEngine: CudaGetDeviceCount CUDA driver version is insufficient for CUDA runtime version
compiled with 10.2?

[Jean_Luc]

Yes I switched to Visual Studio 2019 and Cuda 10.2.
Unfortunately I can't build Cuda 10 in the next few days.

[zielar]

In  all of the experiments that I’ve done with Jean_Luc’s software, I don’t recall going that long (~4.6(sqrt(N)) without some sort of a collision with a properly chosen DP mask, something might be wrong there. But what I find even more interesting is your choice of a very high 28-bit mask, how did you decide that this was the proper choice

DP = 28 suggested the application, so I did as suggested, because I was not informed enough to determine this value myself at a lower level

Dude, with your insane power you just have to wait less than few days to scan the full range of keys, what do you want more ?

clear assurance that continuing to work in the current mode will result in a key result

[Jean_Luc]

I like the race between HardWareCollector and zielar

To choose the DP mask, you first have to calculate your kangaroo number.

460000Mkeys with 2080 Ti (default setting) at ~1.2GKs
=> 383 boards * 2^21.09 = 2^29.6 kangaroo
DP28 => overhead = 2^29.6 * 2^28 = 2^57.6

The overhead here is greater than the expected number of iteration.
As said by HC, DP28 is too large for so much kangaroo and 109bit range.

I recall choose nbKangaroo * 2^dpbit the smallest possible comparing 2^55.5

Edit:
And avoid restarting clients, each time you restart a client, you add more kangaroos and stop others (you break paths)

Edit 2:
The suggested DP is a bad approximation and depend on number of kangaroo, so it differs from a configuration to an other.

[Etar]

I recall choose nbKangaroo * 2^dpbit the smallest possible comparing 2^55.5

So the best choice in this case was using DP=26 ?

Code:

range 2^ 109.0
expected OP 2^ 55.5
DPbit: 26
total GPU: 383
Kangaroos per GPU 2^ 21.09
totalkangaroo 2^ 29.671200581924957
Nkangaroo*2^DPbit = 2^ 55.67120058192496

Edit: but when for ex. we want create pool to do job toghether, we don`t know how many kangaroos will be totaly, because we don`t know how many GPU will be used.
How calculate correct DP in that case?

[Jean_Luc]

If somebody found a key, I would really appreciate that 1 satoshi from the solved address is given to
1FoundByJLPKangaroo111Bht3rtyBav8
Thanks


@etar
If you choose DP=26 you still have a large overhead (you will need 2 times more iterations), DP=24 should be ok but needed RAM will also growth.

[Jean_Luc]

Edit: but when for ex. we want create pool to do job toghether, we don`t know how many kangaroos will be totaly, because we don`t know how many GPU will be used.
How calculate correct DP in that case?

If you launch a server and you wait for an arbitrary number of kangaroo you cannot choose an optimal DP.
So it could be good to choose it according to the RAM you have on the server but you may fall in RAM overflow if too much kangaroo participate.
In that case, the server should be much improved: it must manage kangaroos and distribute kangaroo to clients. This is a hard task.

[PietCoin97]

@jean luc maybe you can manage it to create a community server and when key will be found everyone get the piece for the work he have done.

And you will get your dev fee btc too

[MrFreeDragon]

If somebody found a key, I would really appreciate that 1 satoshi from the solved address is given to
1FoundByJLPKangaroo111Bht3rtyBav8
Thanks
-snip-

Is this the address you control the private key, or did you just create "beautiful" address? So funds sent there will be burned...

[Jean_Luc]

If somebody found a key, I would really appreciate that 1 satoshi from the solved address is given to
1FoundByJLPKangaroo111Bht3rtyBav8
Thanks
-snip-

Is this the address you control the private key, or did you just create "beautiful" address? So funds sent there will be burned...

A beautiful address

@jean luc maybe you can manage it to create a community server and when key will be found everyone get the piece for the work he have done.

And you will get your dev fee btc too

Quite a hard task to make it secure and to develop...

[PietCoin97]

Alright so before you create server you will apply multi pub key?

You told after fixing the server crash problems you will add multi key support.