Are you sure?

key #110 was solved with 2^30.55 DP in 2 days

A normal cpu can compute consecutive keys very fast, my cpu computes almost 30 Mkeys/s, let's say 2^24 keys/s; it would take less than 2 minutes to check 2^30 points

computing random points is slower, but even if it takes x100, we are talking about 3 hours for the entire hash table.

With a simple python script I can get 2^12 keys/s, but it is not tailored for the public keys with private keys so short (under 128 bit) it could reach at least 2^13 keys/s with keys so short.

If you need it I can put together a C program, I think at least 100k key/s are possible, then 2^30 points in less than 3 hours; what speed do you think you need? How much DPs you want to check per hour?

Could you split the work; have separate server/another CPU verifying the DPs, once it checks, it dumps the files; if invalid DP is found, it notifies main server?

Is it really that important a DP was generated by a walk? Why aren't any points that satisfy the DP criteria (bitmask) valid and usefull?
Edit: I understand now that each DP must be generated by a real Pollard Kangaroo walk for the synchronizing effect of the walk.

Maybe different approach for parallelizing the work:

Q = our target pubkey in 115 bit range

If you have 16 GPUs prepare a new set S of pubkeys:

for n = 0 to 16
  S[n] = (Q-n)/16

Now you have a set S with 16 new derived pubkeys where only one is in the range targetBitrange-4 (for 115 it is now in 111 bit range).
So it is true that 15 GPUs will work on pubkeys that are in a different range and this work is useless. But one GPU is working in the correct 111 bit range.

Would this be a benefit?

Edit:
BitCrack, I like your solution for verifying the work but maybe it can be faked too when there is a bad actor that wants to mess with the pool data?

Checking the DPs only for validity does not mean performing the entire work again. Kangaroos are jumping from one point to another based on visited x-coordinate, and as soon as kangaroo lands the x-coordinate with the determined pattern (i.e. coordinate with 25 leading zeros from total 256 bits for DP 25) this coordinate is saved to hashtable together with the distance. So we have saved distance and x-coordinate (only 2nd half of it with length 128 bit).

To check one tame point from hashtable we just need perform one elliptic curve multiplication - converting distance (i.e. private key) to public key and compare last 128 bits of x-coordinate with saved in hashtable. For wild points we should perform one elliptic curve multiplication and addition/subtraction - compute public key from the distance and add/subtract the received point with the target public key, and compare the resulted x-coordinate with hashtable. {ok, actually it is not one addition and multiplication it consists from 32 additions, but it depends on the used algorithm and pre-computed points}

Also no need to save the whole path of the kangaroos. Only the final distinguished point (DP) with the total distance is important.

But we should not make the whole job again to check the DP. Client should perform approximately 2^25 jumps (operations) in order to find one DP. On server side we need to perform just one operation.

Agree with arulbero

As far as I understand it is important that the DP is from a real kangaroo walk.

The difference:
As soon as a kangaroo hits a point (a point that is not qualified to be a DP by bitmask) that has been visited by a kangaroo of the other type, their walks are synchronized and the next DP they find will definately result in a collision and PK is found.
This is not the case with randomly selected points in the range that fullfill the DP bitmask criteria.


It is possible that there will be a collision with these kind of "not real walk" points though.

At picture 1 2080ti produce 2200DPs every 2seconds. the same 2^30.5(Nop) 20^20(Dpsize)=2^10.5 DP/s = 1176
If there will be for example 100 GPU 2080ti it is 110K DP/s need to be verified.
To prevent crash kangaroo server we need only check hash mask. But it is not enouch to prevent addiding job to bad actor.
Everyone can easy make forge DP where mask correct(0<=mask<1<<18), but distance and x-coordinate is fake.
Without verification this DP, actor will get +1DP to his account.
The same like in mining where each share from miner verified we need verify each DP.

In the end Jean Luc took the chance from all with the knowledge of creating a working Pollard Kangaroo for GPU and gave it to those with the power but no knowledge.
I am sure #115, #120 and #125 will go to zielar and no pool can compete. gg.

I agree with you, but I remember you that a proof of work is always a probabilistic task, we cannot redo the entire work to be sure that the entire work is correct.

My proposal:

let's say DP=25, we perform a check on 2 levels, a result and a process check:

level 1) result check

we check that each DP fulfils:
                   - has at least 25 zeros bits
                   - its private key is correct and lies in the correct interval

level 2) process check, proof that the points were generated with a correct path

- we check that there are at least 1/2000 of the points with x-coordinate with at least 25 + 10 zeros
- we redo only the complete path of each kangaroo that ends with a DP with at least 35 zeros

The second check is a valid proof of work, because to generate (in the correct way, with the correct jumps) a single DP with 35 zeros you need to generate correctly on average 2^10 = 1024 kangaroos with a end point with 25 zeroes, you can't fake it.

Obviously you can choose to modify + 10 zeros in +12 or +8, as you prefer.
In this way you need to redo only a small fraction on the entire work, but it is a very significative fraction, not a simple random sample.

There are no shortcuts to generate this correct fraction (DP = 35) of the entire work without doing the entire work, but the checker needs only to do a check on the fraction.

Sorry Jean Luc. I wrote a little offending. I put some resources into the search for #110 so I was little emotional for a moment. I apologize.

That means you need only 16 blocks of 255 (why 256?) precomputed points for a 128-bit privkey, only 15 adds, not too much respect to a single addition.

Split a 128-bit in 16 pieces (each piece has 128/16=8 bit -> 255 elements) and  compute only 16-1 = 15 group additions for each key.

Just for example, if you have a 128 bit key:

key = 10101010 10100000 11111111 01000010 ...  11101010

split in 16 pieces of 128/16=8 bits:

(10101010)*2^120 + (10100000)*2^112 + (11111111)*2^104 + (01000010)*2^96 + .... + (11101010)2^0