You would need to check that the DP is actually valid though. That involves performing the entire walk. If you did this for every DP you would be re-doing the entire computation.
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.
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.
