Quote from: SimonNeedsBitcoin on Today at 04:48:31 AM

It seems that this kind of robot can really steal the bonus very quickly. Although I don’t believe it can be done in 2 seconds, it seems that it can be done within a minute or even tens of seconds. Broadcasting in a public mining pool is indeed very dangerous.

Good, progress.

Now, let's take it one step forward.

Having the pubKey of Puzzle #71 means solving the ECDLP in a 70-bits interval.

Algorithms such as BSGS or Kangaroo will thus require around 2**36 EC group operations, when starting from a zero setup.

Let's take RCKangaroo as a base reference (just for example sake, it is NOT an optimized solver).

With that demo program, an RTX 4090 can do around 8 Gop/s EC (group operations per second).

So, the ECDLP will be broken in around 8.5 seconds.

Let's now actually take it one step further and solve it much faster than that.

If you investigate why the ECDLP of a 70-bit interval is solved in only 2 * 2**35 steps, you will notice that 2**35 of those steps start off from a known private key. So the solving equation can be expressed like this:

intervalSize = numRequiredOpsA * numRequiredOpsB
(example: 2**70 = 2**35 * 2**35)

where you can twiggle around with the right-hand numbers.

Mathematically, the optimal (minimal) effort occurs when those two numbers have the same magnitude, because that is when the sum of the numbers is at a minimum.

However, if one wants to accelerate the solving by trading off the initial effort, we can reqrite things like this:

intervalSize = bigNumberA * smallNumberB
(example: 2**70 = 2**70 * 1)

In this example, somebody precomputes and stores all the keys of the interval, and when the public key becomes available, then the solving side only takes one step (a lookup).

D. J. Bernstein wrote a great paper on how we can take advantage of this in the ECDLP context. It turns out, that we can do something like this if we want:

bigNumberA = 2**40
smallNumberB = 2**30

In this example, we can spend a decent amount of time working out and storing data for whatever 2**56 private keys that we wish. Once we have this data prepared, when the public key is revealed, we'd only need 2**14 steps to find the associated private key.

Now, let's revisit the solve times, on a RTX 4090 (just for fun):

Precomputing time: 2**40 steps = 138 seconds
Solving time: 2**30 steps = 0.13 seconds

Maybe this should make people understand why puzzles 71 to 100+ are basically sitting ducks, and can be solved in a matter of minutes (in total).