Quote from: albert0bsd on Today at 12:39:31 AM

Congrats to the solver: 14q4SoQwENXXzsVT3GMwDrDUGiW5QZeiDg

So, who won?

Well, that was one hell of a long block to mine: 57 minutes.

I pushed the TX immediately after the block before it was mined. Also you posted the correct key that needed to be solved a couple of minutes after the TX was pushed, so basically no excuses. So... congrats on that, if it helps.

TBH I am disappointed it took 39 minutes for the TX to be replaced. I guess no one really cared after all. What if this was the real 80 bit puzzle being emptied, you'll never have 40 minutes.

I gathered some interesting information with this occasion.

Etar - why are you even loading the hashtable into memory? It's wasted time. What if you have 100 GB of DP data?

The brute-force option was fun to see, but of course totally unfeasible.

Correct steps for solving, and also a proof about the values that were expected to be used.

SHA-256 of the code below is the one I posted earlier, and the hash was quoted by other users.

Code:

minKey = 0x659756abf6c17ca70e0000000000000000000140be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
maxKey = 0x659756abf6c17ca70fffffffffffffffffffff40be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355

# PubKey:
# X: a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7
# Y: 1203ad05355adda4bb954e52adb62aaccbdbee069610cb20e566e26e9102b565
# BTC Address(c): 1ECDLP8osCZHBB1LH5PVAUfFegeMgFb52q

# Step 1: determine position and size of the middle (unknown) bits

range_mask = min_key ^ max_key # every 1 bit in result = input bits differed

# get number of zeroes
shift = range_mask.bit_length() - range_mask.bit_count()

# remove the right zeros
range_mask >>= shift

# if at least one 0 is still present, the mask is invalid (and we shifted at least one 1 as well)
if range_mask.bit_count() != range_mask.bit_length():
   raise ValueError('Invalid mask')

assert range_mask.bit_length() <= 80

assert shift == 361

# Step 2: normalize private key search interval to [1, max]

min_elem = min_key * G

# check that the middle (unknown) bits are not all 0
if min_elem == public_key:
   # if hidden bits are all 0, key normalization would result in PAI -> unsolvable
   private_key = min_key
   return

# subtract min_key from unknown private_key
elem = public_key - min_elem # guaranteed to be a valid point

# right-shift the unknown subtracted key ("divide" by the nth power of two)
# because we know the number of even bits, it's guaranteed the keyspace is reduced by 2**shift
shift_inv = pow(1 << shift, -1, secp256k1.N) # == inv(2**shift)
elem = shift_inv * elem

# IDLP PubKey:
# X: 0x34a20e64c9a70138783b125ad81196c76585403905dda56a644ac83ac9620045
# Y: 0x6f7db39f0310d65e68dc83fe9c538c4a62ef8e70db4b0d44adbabd5245dd23ff

# Step 3: solve the key, as it resides in the [1, 2**range_len - 1] interval
# this would be the input to kangaroo, BSGS, etc. which could internally adjust,
# if needed, the public key, working interval, etc.
idlp_key = solve_ecdlp(elem, 1, range_mask)

# reverse steps: left-shift the key, fill back subtracted value
private_key = min_key | (idlp_key << shift)

# if the solved key is correct, then the original key must also be correct
assert (private_key * G) == public_key # X0 == X1 and Y0 == Y1

# for brevity
assert idlp_key == 0x2d56cbf370cbeef9e80a
assert private_key == 0x659756abf6c17ca70e5aad97e6e197ddf3d01540be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
assert private_key % secp256k1.N == 0xb40e7d34265ab9533a64622bd1a188fb8abb8829af545169abad49b46be5fe56