Wait Pollard rho runtime is based on the order of the group not the size of the private key. Maybe there's more to it? This strikes me as more of a hidden number problem. But to make it work you need to observe something using that small number. A transaction might have been enough.

The exact details are beyond me but knowing the public key cuts the required private keys you need to test in half. Public keys are included in the transaction but normal keys have enough bits they're effectively protected even with their raw entropy cut in half. 128 bits are still more than you can effectively brute force but the 33 bits left for this challenge is far easier which let the attacker snipe the reward by exploiting the low fee offered on the original solve message sent to the transaction pool.

Half of 2^66 is 2^65

I meant the entropy in bits is cut by half.

It's very easy to make sqrt(n) DLP solvers for known subranges.

Here is a trivial one:

In advance, make a table of all the pubkeys xG for secret key s = (0,2^33].

When you get a target key T, compute T - (2^33)xG for x = (0,2^33] and look up the result in the table.

When you get a hit, you've found the private key for T it's (2^33)x + s.

Of course, this is a trivialized example, many optimizations are possible and you can specialize any generic DL solver to work in a known range.

But that's not the range in question, this one has 66 bits. You're describing a meet in the middle attack but the runtime would be too high

My example is specifically for a 66-bit range. There are two loops in my post, one removes 2^33 multiples of 2^33, the other builds a table to check for values with a 33-bit range. My example will find a solution in a 66-bit range using only 2^34 point operations and 2^33 table lookups.

Work thought it, I think it'll be more informative than me simply repeating myself further. If you're still confused, ask specific questions and I'll be glad to answer.

Oh right nevermind. For about 300GB of data. I would assume this is what they did them