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.
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