Bitcoin puzzle transaction ~32 BTC prize to who solves it

[COBRAS]

My question, how to use 512 pub for search another key  ?

Seriously?

I already explain some method: https://bitcointalk.org/index.php?topic=1306983.msg64646739#msg64646739

It is more or less the same with some twist. Just try to understand what are you doing. Good look to every one. I am going to publish my method once that the puzzle was redeemed.

About your method is interesting, yes. Thank you.

For what this privkey ?

0x659756abf6c17ca70e829a43c7752f1417002440be6ddd93e441f8d4b4a85653b20b4cdcc5c74 8207a0daa16191d07a425d8080c276f9412472e0429e61bc355

[albert0bsd]

Who want to solve this key?

Transformed/rotated public key: 0334a20e64c9a70138783b125ad81196c76585403905dda56a644ac83ac9620045   <<<<------------- This ONE

On range from 1 to 0x100000000000000000000 ?


Original key public key: 03a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7

[COBRAS]

Who want to solve this key?

Transformed/rotated public key: 0334a20e64c9a70138783b125ad81196c76585403905dda56a644ac83ac9620045

On range from 1 to 0x100000000000000000000 ?


Original key public key: 03a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7

Im try

[albert0bsd]

Congrats to the solver: 14q4SoQwENXXzsVT3GMwDrDUGiW5QZeiDg

Hope he explain what he do.

@Etar it was you?

[COBRAS]

Searching time: 251 s

Nice, near 5 minutes.., that is with some precalculated Distinguished points?

Code:
BTC Address(c): 1ECDLP8osCZHBB1LH5PVAUfFegeMgFb52q

minKey = 0x659756abf6c17ca70e0000000000000000000140be6ddd93e441f8d4b4a85653b20b4cdcc5c74 8207a0daa16191d07a425d8080c276f9412472e0429e61bc355
maxKey = 0x659756abf6c17ca70fffffffffffffffffffff40be6ddd93e441f8d4b4a85653b20b4cdcc5c74 8207a0daa16191d07a425d8080c276f9412472e0429e61bc355

@albertobsd, solved previously, looks like.

[WanderingPhilospher]

Who want to solve this key?

Transformed/rotated public key: 0334a20e64c9a70138783b125ad81196c76585403905dda56a644ac83ac9620045   <<<<------------- This ONE

On range from 1 to 0x100000000000000000000 ?


Original key public key: 03a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7

I know it's over. But this took 27 seconds to find (pre-compiled tames)

0x2d56cbf370cbeef9e80a

[albert0bsd]

0x2d56cbf370cbeef9e80a

Thank you key was: b40e7d34265ab9533a64622bd1a188fb8abb8829af545169abad49b46be5fe56

My method:
Take original public key: 03a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7

Code:

./keymath 03a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7 - 0x20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
Result: 036f778728f5a13be638ffb3935e4cc629b92c69612f7bb7921811a97b51bd8b66 

./keymath  036f778728f5a13be638ffb3935e4cc629b92c69612f7bb7921811a97b51bd8b66 / 0x1000000000000000000000000000000000000000000000000000000000000000
Result: 034c32bfc4e92bfdd9dcb7b6cd1c88da23cc588c0718440e10a297296da3b2713e 

./keymath  034c32bfc4e92bfdd9dcb7b6cd1c88da23cc588c0718440e10a297296da3b2713e - 0x40be6ddd93e441f8d4b4a85653b
Result: 03595f999c25e5afdd1ae1bfb1710924b26698eb51d3e2c131749fb54c018d896c 

./keymath  03595f999c25e5afdd1ae1bfb1710924b26698eb51d3e2c131749fb54c018d896c / 0x1000000000000000000000000000
Result: 0228239ee788ae6784f825e96e31110097929ef0b4348cd6041f5335a542d47f18 

./keymath  0228239ee788ae6784f825e96e31110097929ef0b4348cd6041f5335a542d47f18 - 0x659756abf6c17ca70000000000000000000000
Result: 02bfc064566b29109fa93495d1a47cd499889cd708674e0200a2cd5db57138741e 

./keymath  02bfc064566b29109fa93495d1a47cd499889cd708674e0200a2cd5db57138741e - 0xe00000000000000000000
Result: 03a4134422eef408a6f8cb1aa8256bfd20cb0852d1fa4a06de5f3e8134e87b3271 

./keymath  03a4134422eef408a6f8cb1aa8256bfd20cb0852d1fa4a06de5f3e8134e87b3271 - 1
Result: 03a1708bbb4e9b81a738eaca200d2b06a8f1d351aa3b07c8e255850500bef5ec2b 

./keymath  03a1708bbb4e9b81a738eaca200d2b06a8f1d351aa3b07c8e255850500bef5ec2b / 2
Result: 0334a20e64c9a70138783b125ad81196c76585403905dda56a644ac83ac9620045

This last is the Transformed/rotated key: 0334a20e64c9a70138783b125ad81196c76585403905dda56a644ac83ac9620045

Once that you solve that key now we do modmath operations in backwards order:

Code:

./modmath 0x2d56cbf370cbeef9e80a x 2
Result: 5aad97e6e197ddf3d014

./modmath 0x5aad97e6e197ddf3d014 + 1
Result: 5aad97e6e197ddf3d015

./modmath 0x5aad97e6e197ddf3d015 + 0xe00000000000000000000
Result: e5aad97e6e197ddf3d015 

./modmath 0xe5aad97e6e197ddf3d015 + 0x659756abf6c17ca70000000000000000000000
Result: 659756abf6c17ca70e5aad97e6e197ddf3d015 

./modmath 0x659756abf6c17ca70e5aad97e6e197ddf3d015 x 0x1000000000000000000000000000
Result: 59756abf6c17ca70e5aad97e6e197de6dce82297e44c3e998111c8b31eba787a 

./modmath 0x59756abf6c17ca70e5aad97e6e197de6dce82297e44c3e998111c8b31eba787a + 0x40be6ddd93e441f8d4b4a85653b
Result: 59756abf6c17ca70e5aad97e6e197de6dce826a3cb2a17d7c53155fe693fddb5

./modmath 0x59756abf6c17ca70e5aad97e6e197de6dce826a3cb2a17d7c53155fe693fddb5 x 0x1000000000000000000000000000000000000000000000000000000000000000
Result: b203305760937132c056b815b884815764e3801d87e4bd57647f458a85ca3b01 

./modmath 0xb203305760937132c056b815b884815764e3801d87e4bd57647f458a85ca3b01 + 0x20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
Result: b40e7d34265ab9533a64622bd1a188fb8abb8829af545169abad49b46be5fe56

Code:

Original key: b40e7d34265ab9533a64622bd1a188fb8abb8829af545169abad49b46be5fe56
Extended key: 0x659756abf6c17ca70e5aad97e6e197ddf3d01540be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355

[kTimesG]

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

[WanderingPhilospher]

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 will make a deal with you. You do the same challenge, or another, in an 80 bit range, with a wallet that has 8.0 bitcoin in it, and I guarantee you it will be replaced in less than 39 minutes 

[albert0bsd]

@kTimesG Thank you for your challenge it was really funny

I will make a deal with you. You do the same challenge, or another, in an 80 bit range, with a wallet that has 8.0 bitcoin in it, and I guarantee you it will be replaced in less than 39 minutes  

Hahahaha, yeah the 350$ don't attract much people. In any case those side-challenges/puzzles are really cool to learn.

[COBRAS]

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 will make a deal with you. You do the same challenge, or another, in an 80 bit range, with a wallet that has 8.0 bitcoin in it, and I guarantee you it will be replaced in less than 39 minutes 

Yes, do it please ))

[Etar]

Congrats to the solver: 14q4SoQwENXXzsVT3GMwDrDUGiW5QZeiDg

Hope he explain what he do.

@Etar it was you?

No. The script found the key in 158s, and then there was an error in processing of calculating fee. LoL

Code:

Searching time: 158 s
2024-11-02 01:44:19.349: Kangaroo private key: 0x2d56cbf370cbeef9e80a
2024-11-02 01:44:19.349: Real private key: 0x659756abf6c17ca70e5aad97e6e197ddf3d01540be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
2024-11-02 01:44:19.350: Real private key 256: 0xb40e7d34265ab9533a64622bd1a188fb8abb8829af545169abad49b46be5fe56
f8cff579d1262612ba8afb053c457464ecea8e51d30b32fd002f7de958efb872 fee 866 size 485 1.7855670103092784 sat/byte
Traceback (most recent call last):

[Etar]

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

@kTimesG, thanks for the competition, it was interesting.
I didn't write any additional tools for this puzzle. I used what was already on hand.
If we were talking about tens of thousands of dollars, then of course i would have to work.
The only thing I changed JLP Kangaroo v1.7 so that it would only produce wild kangaroos.
Hash table with DP=20 weighs about 7GB, and loading time is 34s.

Code:

LoadWork: [HashTable 7449.0/9315.7MB] [34s]

My transformation steps:

Code:

03a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7 - minrange = 03634641685eca3f8284bcd4ddf233dac92a551bb5ff74a0b3fd587d4da7c13eea
03634641685eca3f8284bcd4ddf233dac92a551bb5ff74a0b3fd587d4da7c13eea / (2^361) = 0334a20e64c9a70138783b125ad81196c76585403905dda56a644ac83ac9620045
0334a20e64c9a70138783b125ad81196c76585403905dda56a644ac83ac9620045 in range 1..2^80
The private key from the kangaroo was 0x2d56cbf370cbeef9e80a
(0x2d56cbf370cbeef9e80a * (2^361) +  minrange)%N = 0xb40e7d34265ab9533a64622bd1a188fb8abb8829af545169abad49b46be5fe56

[COBRAS]

Congrats to the solver: 14q4SoQwENXXzsVT3GMwDrDUGiW5QZeiDg

Hope he explain what he do.

@Etar it was you?

No. The script found the key in 158s, and then there was an error in processing of calculating fee. LoL

Code:

Searching time: 158 s
2024-11-02 01:44:19.349: Kangaroo private key: 0x2d56cbf370cbeef9e80a
2024-11-02 01:44:19.349: Real private key: 0x659756abf6c17ca70e5aad97e6e197ddf3d01540be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
2024-11-02 01:44:19.350: Real private key 256: 0xb40e7d34265ab9533a64622bd1a188fb8abb8829af545169abad49b46be5fe56
f8cff579d1262612ba8afb053c457464ecea8e51d30b32fd002f7de958efb872 fee 866 size 485 1.7855670103092784 sat/byte
Traceback (most recent call last):

 (which will be available tomorrow).

Bro, provide your script ? pls

[Etar]

Bro, provide your script ?

This is a jlp kangaroo, with precalculated tame kangaroos.
You can make them yourself. By running a kangaroo in the required range with the -m 3 parameter in a loop with a false public key. In this way you will accumulate a lot of DPs.
After that, you will only need wild kangaroos.

[COBRAS]

Bro, provide your script ?

This is a jlp kangaroo, with precalculated tame kangaroos.
You can make them yourself. By running a kangaroo in the required range with the -m 3 parameter in a loop with a false public key. In this way you will accumulate a lot of DPs.
After that, you will only need wild kangaroos.

Bro,I talk about this scrypt:

" Most likely, the sha-256 hash is simply a hash of the text that contains instructions on how to correctly convert a public key to a range of 80 bits an so on (which will be available tomorrow)."

? ))

[Etar]

Bro,I talk about this scrypt:
" Most likely, the sha-256 hash is simply a hash of the text that contains instructions on how to correctly convert a public key to a range of 80 bits an so on (which will be available tomorrow)."
? ))

Copy the instructions that kTimesG posted and paste to the https://emn178.github.io/online-tools/sha256.html and and get the hash a6c39217128593909a1fcc0fd92c07a6f5abd32c36a8e7cf4e91f1a8f0651db0
I don't understand why you need it hash. This sha-256 hash was made to show that the instruction was not rewritten and was posted in its original form. Specifically, the hash has nothing to do with the solving.

[COBRAS]

Bro,I talk about this scrypt:
" Most likely, the sha-256 hash is simply a hash of the text that contains instructions on how to correctly convert a public key to a range of 80 bits an so on (which will be available tomorrow)."
? ))

Copy the instructions that kTimesG posted and paste to the https://emn178.github.io/online-tools/sha256.html and and get the hash a6c39217128593909a1fcc0fd92c07a6f5abd32c36a8e7cf4e91f1a8f0651db0
I don't understand why you need it hash. This sha-256 hash was made to show that the instruction was not rewritten and was posted in its original form. Specifically, the hash has nothing to do with the solving.

So, how to correct convert pubkey to smaler range ?

[kTimesG]

So, how to correct convert pubkey to smaler range ?

You were given three separate methods already, what more do you want?! Unless you are looking for even more users to ignore you forever.

It's literally just one addition (sub) and one multiplication in the EC group to switch between any internal subinterval and a sequential interval. Basic DLP concepts 101.

Seems no one claimed the mempool TX replacement, maybe one of the guys "with a plan". Though it doesn't explain why it took so much time, since the 80-bit key could be broken in seconds with enough DPs available. I was rather expecting a bot war since at least 2 users (Etar and albert0bsd) were doing the correct steps.

Thanks to all who were interested!

[albert0bsd]

To be honest I am really disappointed that the solver don't announce itself...

I know bitcoin should be anonymous, but what kind of Ungrateful person is he to not said at least thanks to ktimesG for his time and dedication to this topic.

@COBRAS You should better dedicate to another not-technical topic, as far i see this is not for you.

For anyone who really don't understand where are those 80 missing bits here we go:

Code:

minKey = 0x659756abf6c17ca70e0000000000000000000140be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
maxKey = 0x659756abf6c17ca70fffffffffffffffffffff40be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355

if we remove all hexadecimal characters that match and keep only those who don't match we get:

Code:

e00000000000000000001
fffffffffffffffffffff

Those are 21 characters, each hexadecimal characters need 4 bits, then those 21 are 84 bits... so we need to remove those bits that are the same in both ranges

Code:

    E (hex) = 1110 (binary)
    F (hex) = 1111 (binary)
    1 (hex) = 0001 (binary)

from the left side we have E and F.
1110
1111
The first three are always 1 so we need to remove those 3

From the right side we have 1 and F
1111
0001

Only 1 bit (righest one) match so we also need to remove that

So from those 84 bits we need to remove 3 on the left and 1 on the right.

Using python:

Code:

>>> bin(int("e00000000000000000001",16))
'0b111000000000000000000000000000000000000000000000000000000000000000000000000000000001'
>>> bin(int("fffffffffffffffffffff",16))
'0b111111111111111111111111111111111111111111111111111111111111111111111111111111111111'

Real missing bits:
111 >> 0000000000000000000000000000000000000000000000000000000000000000000000000000000 0 << 1
111 >> 1111111111111111111111111111111111111111111111111111111111111111111111111111111 1 << 1