Bitcoin puzzle transaction ~32 BTC prize to who solves it

[james5000]

I humbly request partnership with albertobsd to use multi-threading in this method in C++. If the creator of bitcrack could assist with the CUDA version I'm developing, we could potentially achieve speeds of 200-300Mk/s.

[1715540722]

1715540722

[1715540722]

1715540722

[1715540722]

1715540722

[vsv68]

The second day I watch what james5000 writes and it's very funny to me)
 It's especially funny to see how other people support him)
 I don’t want to offend anyone, but I get the impression that you didn’t study mathematics at school, your teacher should be very ashamed.
 The method suggested by james5000 would require you to try more than 2^65 combinations to solve a 66 bit key.
 It is impossible to go through such a number of combinations in a month, or even in a year!
 Please learn to count before you write like this, you look very stupid.
 I didn't mean to offend anyone, I'm sorry if I hurt your feelings, I just had to tell you that you are doing nonsense, I wish you all success!

[james5000]

The second day I watch what james5000 writes and it's very funny to me)
 It's especially funny to see how other people support him)
 I don’t want to offend anyone, but I get the impression that you didn’t study mathematics at school, your teacher should be very ashamed.
 The method suggested by james5000 would require you to try more than 2^65 combinations to solve a 66 bit key.
 It is impossible to go through such a number of combinations in a month, or even in a year!
 Please learn to count before you write like this, you look very stupid.
 I didn't mean to offend anyone, I'm sorry if I hurt your feelings, I just had to tell you that you are doing nonsense, I wish you all success!

lmfao 

As there are more than 2^65 possibilities for 66 bits, even though I'm skipping intervals.

For example:
Between the initial key and the second key, 2^33 keys are skipped, then 2^32, 2^31, and so on...
I believe you don't even need to calculate it to see that it's less than 2^65.

[frozenen]

Is your script supposed to show the speed while running for #30? how long should it take to find?

[james5000]

Is your script supposed to show the speed while running for #30? how long should it take to find?

this python code is very slow, only to show how works the ideia.

but the cuda code run all interval bits 1 = 16 for #30 in 2 minutes.

I understand that one might think that for #31 (since it's one more bit), it would take twice the time, i.e., 4 minutes. However, in reality, it would take just over 2 minutes because it's not exponential. I'll run some tests, and since everyone has access to the code, they can confirm.

[albert0bsd]

even though I'm skipping intervals.

We know that you are skipping those ranges that are some kind of unlikely to appper in random numbers... that is clear.

Let me show you this simulation for 64 bits, with 100 Million of iterations..

Code:

3 times 10 bits in 1,  this is 0.000000
3 times 11 bits in 1,  this is 0.000000
15 times 12 bits in 1,  this is 0.000000
69 times 13 bits in 1,  this is 0.000001
241 times 14 bits in 1,  this is 0.000002
841 times 15 bits in 1,  this is 0.000008
2677 times 16 bits in 1,  this is 0.000027
7459 times 17 bits in 1,  this is 0.000075
19405 times 18 bits in 1,  this is 0.000194
47167 times 19 bits in 1,  this is 0.000472
106263 times 20 bits in 1,  this is 0.001063
222505 times 21 bits in 1,  this is 0.002225
436048 times 22 bits in 1,  this is 0.004360
795798 times 23 bits in 1,  this is 0.007958
1357354 times 24 bits in 1,  this is 0.013574
2178202 times 25 bits in 1,  this is 0.021782
3259829 times 26 bits in 1,  this is 0.032598
4588566 times 27 bits in 1,  this is 0.045886
6064588 times 28 bits in 1,  this is 0.060646
7533079 times 29 bits in 1,  this is 0.075331
8784231 times 30 bits in 1,  this is 0.087842
9628995 times 31 bits in 1,  this is 0.096290
9933958 times 32 bits in 1,  this is 0.099340
9637041 times 33 bits in 1,  this is 0.096370
8782369 times 34 bits in 1,  this is 0.087824
7530503 times 35 bits in 1,  this is 0.075305
6064379 times 36 bits in 1,  this is 0.060644
4589388 times 37 bits in 1,  this is 0.045894
3260455 times 38 bits in 1,  this is 0.032605
2175369 times 39 bits in 1,  this is 0.021754
1356442 times 40 bits in 1,  this is 0.013564
794205 times 41 bits in 1,  this is 0.007942
435134 times 42 bits in 1,  this is 0.004351
222946 times 43 bits in 1,  this is 0.002229
106671 times 44 bits in 1,  this is 0.001067
46833 times 45 bits in 1,  this is 0.000468
19545 times 46 bits in 1,  this is 0.000195
7516 times 47 bits in 1,  this is 0.000075
2705 times 48 bits in 1,  this is 0.000027
842 times 49 bits in 1,  this is 0.000008
251 times 50 bits in 1,  this is 0.000003
80 times 51 bits in 1,  this is 0.000001
23 times 52 bits in 1,  this is 0.000000
5 times 53 bits in 1,  this is 0.000000
1 times 54 bits in 1,  this is 0.000000
1 times 55 bits in 1,  this is 0.000000

What that mean? for example if you want a ratio of the 50% of the bits are in 1

Code:

9933958 times 32 bits in 1,  this is 0.099340

That is is near of ~10% of the TIME the random numbers had 32 of 64 bits in 1

Now you want to test numbers only with some ratio between 40% to 60% right?

Code:

>>> 64*0.40
25.6
>>> 64*0.60
38.4

For this example of 64 bits you need to test those numbers who have 26 to 38 bits in 1 that is from 32 +/- 6

In this example  the values have the next probabilities:

Code:

3259829 times 26 bits in 1,  this is 0.032598
4588566 times 27 bits in 1,  this is 0.045886
6064588 times 28 bits in 1,  this is 0.060646
7533079 times 29 bits in 1,  this is 0.075331
8784231 times 30 bits in 1,  this is 0.087842
9628995 times 31 bits in 1,  this is 0.096290
9933958 times 32 bits in 1,  this is 0.099340
9637041 times 33 bits in 1,  this is 0.096370
8782369 times 34 bits in 1,  this is 0.087824
7530503 times 35 bits in 1,  this is 0.075305
6064379 times 36 bits in 1,  this is 0.060644
4589388 times 37 bits in 1,  this is 0.045894
3260455 times 38 bits in 1,  this is 0.032605

That is 0.896575 or near of ~90% of all the KEYS in the whole range FIT in those % of Ratios of 1.

That is the % for a 64 bits range, but i bet that the % is very similar for a 66 bit range and others..

I guarantee that with a rate of 300 Mk/s we break the 66, 67 and 68 in one week

From you previous quote I going to asume a puzzle per week, not 3 in a week.

Code:

>>>2**65/300000000/60/60/24/52 * 0.0000365333
1.0000006458749602

That is one week and you need 0.0000365333 of the range that is 0.00365333%

Let me ask it again, because the last time you completely ignore my question.

How do you plan to reduce that 90% of the whole range to only 0.00365333%?

For many ranges that you skip, i don't believe any reduction near to the 1% of the whole range...

BTW if some one spot some miscalculation or some incoherent formula please let me know i would be happy of getting wrong.

Repeat, your Idea have a lot of logic, but the calcualtios about your expected time doesn't match...

[james5000]

even though I'm skipping intervals.

We know that you are skipping those ranges that are some kind of unlikely to appper in random numbers... that is clear.

Let me show you this simulation for 64 bits, with 100 Million of iterations..

Code:

3 times 10 bits in 1,  this is 0.000000
3 times 11 bits in 1,  this is 0.000000
15 times 12 bits in 1,  this is 0.000000
69 times 13 bits in 1,  this is 0.000001
241 times 14 bits in 1,  this is 0.000002
841 times 15 bits in 1,  this is 0.000008
2677 times 16 bits in 1,  this is 0.000027
7459 times 17 bits in 1,  this is 0.000075
19405 times 18 bits in 1,  this is 0.000194
47167 times 19 bits in 1,  this is 0.000472
106263 times 20 bits in 1,  this is 0.001063
222505 times 21 bits in 1,  this is 0.002225
436048 times 22 bits in 1,  this is 0.004360
795798 times 23 bits in 1,  this is 0.007958
1357354 times 24 bits in 1,  this is 0.013574
2178202 times 25 bits in 1,  this is 0.021782
3259829 times 26 bits in 1,  this is 0.032598
4588566 times 27 bits in 1,  this is 0.045886
6064588 times 28 bits in 1,  this is 0.060646
7533079 times 29 bits in 1,  this is 0.075331
8784231 times 30 bits in 1,  this is 0.087842
9628995 times 31 bits in 1,  this is 0.096290
9933958 times 32 bits in 1,  this is 0.099340
9637041 times 33 bits in 1,  this is 0.096370
8782369 times 34 bits in 1,  this is 0.087824
7530503 times 35 bits in 1,  this is 0.075305
6064379 times 36 bits in 1,  this is 0.060644
4589388 times 37 bits in 1,  this is 0.045894
3260455 times 38 bits in 1,  this is 0.032605
2175369 times 39 bits in 1,  this is 0.021754
1356442 times 40 bits in 1,  this is 0.013564
794205 times 41 bits in 1,  this is 0.007942
435134 times 42 bits in 1,  this is 0.004351
222946 times 43 bits in 1,  this is 0.002229
106671 times 44 bits in 1,  this is 0.001067
46833 times 45 bits in 1,  this is 0.000468
19545 times 46 bits in 1,  this is 0.000195
7516 times 47 bits in 1,  this is 0.000075
2705 times 48 bits in 1,  this is 0.000027
842 times 49 bits in 1,  this is 0.000008
251 times 50 bits in 1,  this is 0.000003
80 times 51 bits in 1,  this is 0.000001
23 times 52 bits in 1,  this is 0.000000
5 times 53 bits in 1,  this is 0.000000
1 times 54 bits in 1,  this is 0.000000
1 times 55 bits in 1,  this is 0.000000

What that mean? for example if you want a ratio of the 50% of the bits are in 1

Code:

9933958 times 32 bits in 1,  this is 0.099340

That is is near of ~10% of the TIME the random numbers had 32 of 64 bits in 1

Now you want to test numbers only with some ratio between 40% to 60% right?

Code:

>>> 64*0.40
25.6
>>> 64*0.60
38.4

For this example of 64 bits you need to test those numbers who have 26 to 38 bits in 1 that is from 32 +/- 6

In this example  the values have the next probabilities:

Code:

3259829 times 26 bits in 1,  this is 0.032598
4588566 times 27 bits in 1,  this is 0.045886
6064588 times 28 bits in 1,  this is 0.060646
7533079 times 29 bits in 1,  this is 0.075331
8784231 times 30 bits in 1,  this is 0.087842
9628995 times 31 bits in 1,  this is 0.096290
9933958 times 32 bits in 1,  this is 0.099340
9637041 times 33 bits in 1,  this is 0.096370
8782369 times 34 bits in 1,  this is 0.087824
7530503 times 35 bits in 1,  this is 0.075305
6064379 times 36 bits in 1,  this is 0.060644
4589388 times 37 bits in 1,  this is 0.045894
3260455 times 38 bits in 1,  this is 0.032605

That is 0.896575 or near of ~90% of all the KEYS in the whole range FIT in those % of Ratios of 1.

That is the % for a 64 bits range, but i bet that the % is very similar for a 66 bit range and others..

I guarantee that with a rate of 300 Mk/s we break the 66, 67 and 68 in one week

From you previous quote I going to asume a puzzle per week, not 3 in a week.

Code:

>>>2**65/300000000/60/60/24/52 * 0.0000365333
1.0000006458749602

That is one week and you need 0.0000365333 of the range that is 0.00365333%

Let me ask it again, because the last time you completely ignore my question.

How do you plan to reduce that 90% of the whole range to only 0.00365333%?

For many ranges that you skip, i don't believe any reduction near to the 1% of the whole range...

BTW if some one spot some miscalculation or some incoherent formula please let me know i would be happy of getting wrong.

Repeat, your Idea have a lot of logic, but the calcualtios about your expected time doesn't match...

First of all, thank you very much for the time you've dedicated and the painstaking calculations!

I will conduct some tests. None of the formulas I used to calculate the total intervals provided me with the correct result. I resorted to brute forcing puzzle #30 just to confirm.

Initially, I attempted using the binomial coefficient. It worked well for #10, but for #30, it didn't yield the correct result, which is around 77 million reduced from about 500 million.

If you are aware of a formula to calculate the number of combinations for a fixed-length string with 14 bits set to 0 and 16 bits set to 1, I would be grateful if you could correct my calculations.

Code:

The binomial coefficient, also known as "n choose k" or "combination," is used to calculate the number of different ways to choose k unique elements from a set of n elements, without considering the order in which they are chosen. The formula for the binomial coefficient is given by:

C(n, k) = n! / (k! * (n - k)!)

Where:

n is the size of the total set (in this case, the length of the string)
k is the number of elements you want to choose (in this case, the number of zeros or ones)
To calculate the binomial coefficient for a fixed-length string with 14 zeros and 16 ones, we have n = 30 (14 zeros + 16 ones) and k = 14 (number of zeros). Substituting these values into the formula, we get:

C(30, 14) = 30! / (14! * (30 - 14)!)

Here, 30! represents the factorial of 30 (30 * 29 * 28 * ... * 1), 14! represents the factorial of 14, and (30 - 14)! represents the factorial of 16.

Calculating these factorials and substituting them into the formula, we get the value of the binomial coefficient:

C(30, 14) = 30! / (14! * 16!) ≈ 145,422,675

Therefore, there are approximately 145,422,675 different ways to combine a fixed-length string with 14 zeros and 16 ones.

[modma]

The problem isn't guessing a random number, it's narrowing down the search range to more probable keys. Thank you for posting the percentages; this way we can see that after 54, none have fewer than 40% of bits as 1 or 0, nor more than 60%. I believe we can accept this as a fact.

with all due respect. You tried to do at least something, but you have a basic gap in the logic.
You can see - but you cannot say that this rule will work for the next puzzle..
Try to understand it.
Literally - what happened before - does not affect what happens after. What happens after has nothing to do with what happened before.
Take it as an axiom.
Narrowing the range is so non-critical - that it will not put any pressure on the puzzle

[vsv68]

james5000 you have errors in your calculations.
Use this code:

Code:

import math

KEY_SIZE = 5
ONES = 2

n = KEY_SIZE - 1
r = ONES - 1

combinations = math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

print("KEY_SIZE =", KEY_SIZE)
print("ONES =", ONES)
print("Combinations:", combinations)

A simple example for KEY_SIZE = 5

ONES = 2
number of combinations 4:
10001
10010
10100
11000

ONES = 3
number of combinations 6:
10011
10101
11001
10110
11010
11100

ONES = 4
number of combinations 4:
10111
11011
11101
11110

total combinations 14

Let's say we are looking for the key 10111. You do not know how many units the key contains and to find this key by your method, you will first have to sort through all the ONES = 2, then all the ONES = 3, and only at step 11 will the desired key be found. If you search for the same key by a simple sequential search, it will be found at step 7, that is, faster than your method. Your method proved to be worse than a simple sequential search, in a 66-bit key your method will work for eternity....

[james5000]

vsv68, you're absolutely right...

In this way, we would need 11 steps for the key 10111 and a sequential search is indeed faster.

However, there's a small detail that needs to be reiterated, only keys with sufficient length will benefit from using this method. Hence, I suggest ignoring the small keys, as we are focused on the search for the #66 key, right?

For example, starting from #54, no key has less than 40% of bits set to 1 or more than 60% either.

In a sequential search, how many keys do we need to test to reach the minimum key of #65, for example?

bin = 10000000000000000000000000000000000001111111111111111111111111111      hex = 1000000000FFFFFFF

268,435,455 keys were skipped just by starting the search.

Now let's move on to the second key

bin = 10000000000000000000000000000000000010111111111111111111111111111      hex = 10000000017FFFFFF

We skipped another 134,217,728 keys with just one key.

In a sequential search, we would still be on the same key.

bin = 10000000000000000000000000000000000000000000000000000000000000010     hex = 10000000000000002

For small keys, we indeed don't benefit from this method, but do we really need to? 

Obviously, we can make mistakes in determining the number of bits set to 1 and bits set to 0. This is why we need to traverse these intervals faster and/or utilize the power of a GPU for parallel calculations, such as scanning 2 or 4 intervals simultaneously or subdividing an interval into smaller chunks that can be checked in parallel.

I have many ideas for improvements that can be made, but I need to proceed cautiously since I'm quite new to parallel programming. However, I already have code that doesn't involve additional iterations over the keys or calculating the powers that will be added. With each step, I'm amazed by the pattern that the numbers follow when we talk about bits.

Please don't focus on the Python code as a ready-to-use tool for searching. It serves to illustrate the idea, even if it's functional up to a certain number of bits. Focus on the patterns, and if you notice anything else, let's examine and discuss it.   

Code:

import math

KEY_SIZE = 5
ONES = 2

n = KEY_SIZE - 1
r = ONES - 1

combinations = math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

Wow, this was exactly the code I needed to calculate the combinations, thank you!!

Another thing we can consider is that no random key will start with 1000, 2000, 3000, 4000, 5000... among other patterns, agree?

Surely, we could start from the key:
bin = 10000000000000000100000000000000000000111111111111111111111111111 hex = 10000800007ffffff

Or better approaches, the sky's the limit.

This way, we eliminate a significant portion of the total keys and one of my next steps will be a way to skip these keys as well.

Just for the purpose of illustrating a code snippet that could be used to replace the iteration over the private key and power calculations, as we know that the points to be added are decreasing powers of 2 and the increment is increasing.

Code:

KEYSIZE = 30
ONES = 16

pows = []

increment = 1
position = 16

point = g

for j in range(position, -1, -1):
    for i in range(position, -1, -1):
        if i == j:
            # 2^i + increment
            pointToAdd = pows[i + 1]
            point = point + pointToAdd + increment

            for k in range(i - 1, -1, -1):
                # 2^k
                pointToAdd = pows[k + 1]
                point = point + pointToAdd

            if position == 0:
                position = ONES
            else:
                position -= 1

            if increment != 3:
                increment = 3
        else:
            # 2^i + 1
            pointToAdd = pows[i + 1]
            point = point + pointToAdd + 1

            for k in range(i - 1, -1, -1):
                # 2^k
                pointToAdd = pows[k + 1]
                point = point + pointToAdd

                

[vneos]

Let's outline what james5000 does from a mathematical point of view:

For puzzle 66, we have 66 binary digits, and following james5000's idea, we can set the number of digits of 0s and 1s within a specific range(the digits of 0 and 1 shall not exceed 41% of the 66 digits):

Code:

Number of 0    Number of 1
      27                  39
      28                  38
      29                  37
      30                  36
      31                  35
      32                  34
      33                  33
      34                  32
      35                  31
      36                  30
      37                  29
      38                  28
      39                  27

Now let's calculate the key space possibilities:

For a 66-bit binary number, where 0 has 27 bits and 1 has 39 bits, since the leftmost bit is fixed to be 1, we have 65 bits left to fill with 38 ones (since one 1 is already used for the leftmost bit) and 27 zeros.

Now, think of this as trying to choose locations for the 38 ones out of the remaining 65 bits. Once the positions for the ones are determined, the positions for the zeros are also fixed.

The number of ways to choose 38 locations out of 65 is given by the combination formula or "n choose k", represented as n!/(k!(n-k)!)

In this case, n = 65 and k = 38, so we got 65!/(38!x27!)

This formula calculates the number of ways to arrange 38 ones in a 65-bit string.

We then apply the formula to the remaining combinations, the probability of all keys is::

Code:

65!/(38!x27!) + 65!/(37!x28!) + 65!/(36!x29!) + 65!/(35!x30!) + 65!/(34!x31!) + 65!/(33!x32!) + 65!/(32!x33!) + 65!/(31!x34!) + 65!/(30!x35!) + 65!/(29!x36!) + 65!/(28!x37!) + 65!/(27!x38!) + 65!/(26!x39!)

Which equal to 3.287737502x10^19, is smaller than 2^65 and about 44.56% of 2^66. That means we only need to search 44.56% of the original key space to potentially find the private key for puzzle 66!

I don't know if my calculation process is correct. If there are any errors, please point them out. Thank you.

[vneos]

I wrote a simple script for solving puzzle 66: https://github.com/allinbit/btc_puzzle

If it could be ported to gpu then it would be faster but I don't know anything about it.

[frozenen]

james5000 the script does work and it eventually does find the pub key for #30 but it's super slow. I was thinking since you already did this in python, would it be hard to implement python opencl? pyopencl-2022.1.6-cp311-cp311-win_amd64 along with scrypt like what btcrecover uses?

[zahid888]

If i give the exact percent of zeros and ones in 66 bit key, how much time it takes to solve?

[lordfrs]

If i give the exact percent of zeros and ones in 66 bit key, how much time it takes to solve?

Assuming a 30-bit number with 14 bits being 0 and 16 bits being 1, in order to calculate all the combinations, we need to determine the positions of each 0 and 1.

First, let's determine the positions where the 14 bits are 0. For each of the 14 bits, you can either place a 0 or a 1. In this case, each 0 and 1 has 2 possible states. There are 2^14 = 16,384 different combinations for the 14 bits.

Next, let's determine the positions where the 16 bits are 1. Similarly, for each of the 16 bits, you can place a 0 or a 1. Each 0 and 1 has 2 possible states. There are 2^16 = 65,536 different combinations for the 16 bits.

To calculate all the combinations, combine these two steps. We know there are 16,384 different combinations for the 14 bits and 65,536 different combinations for the 16 bits. By multiplying these two numbers, we can find the total number of combinations:

16,384 * 65,536 = 1,073,741,824

Therefore, when there are 14 bits being 0 and 16 bits being 1 in a 30-bit number, there are a total of 1,073,741,824 different combinations.

You can calculate 66 bits..

[citb0in]

Therefore, when there are 14 bits being 0 and 16 bits being 1 in a 30-bit number, there are a total of 1,073,741,824 different combinations.

2^14*2^16 = 1,073,741,824
2^15*2^15 = 1,073,741,824
2^a*2^b = 1,073,741,824 (where a+b=30)
2^30 = 1,073,741,824

no matter of ones and zeros

[vsv68]

vneos
frozenen
zahid888
lordfrs
citb0in

Guys, tell me, can you read?  I already provided you a free python script that will show the exact number of combinations to iterate over, given a specific number of ones in the key:

https://bitcointalk.org/index.php?topic=1306983.msg62662714#msg62662714

I even gave a specific example where the discussed method works worse than a simple sequential enumeration!

but you stubbornly continue to write all sorts of garbage...

If you are too lazy to run the script, here are some results:

Code:

KEY_SIZE = 30
ONES = 14
Combinations: 67863915

KEY_SIZE = 30
ONES = 16
Combinations: 77558760


KEY_SIZE = 66
ONES = 30
Combinations: 2507588587725537680

KEY_SIZE = 66
ONES = 31
Combinations: 3009106305270645216

KEY_SIZE = 66
ONES = 32
Combinations: 3397378086595889760

KEY_SIZE = 66
ONES = 33
Combinations: 3609714217008132870

you will need to try a huge number of incorrect combinations before you find the right key.

[james5000]

Let's outline what james5000 does from a mathematical point of view:

For puzzle 66, we have 66 binary digits, and following james5000's idea, we can set the number of digits of 0s and 1s within a specific range(the digits of 0 and 1 shall not exceed 41% of the 66 digits):

Code:

Number of 0    Number of 1
      27                  39
      28                  38
      29                  37
      30                  36
      31                  35
      32                  34
      33                  33
      34                  32
      35                  31
      36                  30
      37                  29
      38                  28
      39                  27

Now let's calculate the key space possibilities:

For a 66-bit binary number, where 0 has 27 bits and 1 has 39 bits, since the leftmost bit is fixed to be 1, we have 65 bits left to fill with 38 ones (since one 1 is already used for the leftmost bit) and 27 zeros.

Now, think of this as trying to choose locations for the 38 ones out of the remaining 65 bits. Once the positions for the ones are determined, the positions for the zeros are also fixed.

The number of ways to choose 38 locations out of 65 is given by the combination formula or "n choose k", represented as n!/(k!(n-k)!)

In this case, n = 65 and k = 38, so we got 65!/(38!x27!)

This formula calculates the number of ways to arrange 38 ones in a 65-bit string.

We then apply the formula to the remaining combinations, the probability of all keys is::

Code:

65!/(38!x27!) + 65!/(37!x28!) + 65!/(36!x29!) + 65!/(35!x30!) + 65!/(34!x31!) + 65!/(33!x32!) + 65!/(32!x33!) + 65!/(31!x34!) + 65!/(30!x35!) + 65!/(29!x36!) + 65!/(28!x37!) + 65!/(27!x38!) + 65!/(26!x39!)

Which equal to 3.287737502x10^19, is smaller than 2^65 and about 44.56% of 2^66. That means we only need to search 44.56% of the original key space to potentially find the private key for puzzle 66!

I don't know if my calculation process is correct. If there are any errors, please point them out. Thank you.

exactly that, there is no way to be greater than 2^65 as the friend said yesterday

[james5000]

I wrote a simple script for solving puzzle 66: https://github.com/allinbit/btc_puzzle

If it could be ported to gpu then it would be faster but I don't know anything about it.

Your code uses scalar multiplication for all the keys, making it even slower.
The code is interesting, although for the processor it can take a long time, it needs to be on the video card itself.

[james5000]

Using my method with multiprocessing, I reach #30 in that time.

Code:

Found!
030d282cf2ff536d2c42f105d0b8588821a915dc3f9a05bd98bb23af67a2e92a5b
Time: 0 h, 14 m, 37 s

Using the VNEOS software, I obtained the time and it also provides us with the private key.

Code:

000000000000000000000000000000000000000000000000000000003d94cd64
hash160: d39c4704664e1deb76c9331e637564c257d68a08
Target hash found!
Time: 0 h, 5 m, 0 s

this is very very good, congratulations, buddy!!!!

however, I got lucky; I ran it again with the same parameters, and the time was...

Code:

000000000000000000000000000000000000000000000000000000003d94cd64
hash160: d39c4704664e1deb76c9331e637564c257d68a08
Target hash found!
Time: 0 h, 10 m, 8 s

even though it's faster, the time varies a lot. Scalar multiplication isn't very slow, but as you mentioned, it's a lottery. Someone might get lucky on #66.

just a suggestion to make parameter swapping easier.

Code:

import hashlib
import ecdsa
import random
from multiprocessing import Process, Event

def binary_to_hex(bin_string):
    return hex(int(bin_string, 2))[2:].zfill(len(bin_string) // 4)

def worker(key_size, num_ones, stop_event):

    target_hash = "20d45a6a762535700ce9e0b216e31994335db8a5"

    while True:
        if stop_event.is_set():
            break

        bits = ['0'] * (key_size - num_ones) + ['1'] * (num_ones - 1)
        random.shuffle(bits)

        bits.insert(0, '1')
        private_key_bin = ''.join(bits)

        private_key_bin = '0' * (256 - key_size) + private_key_bin
        private_key_hex = binary_to_hex(private_key_bin)

        sk = ecdsa.SigningKey.from_string(bytes.fromhex(private_key_hex), curve=ecdsa.SECP256k1)
        public_key = sk.get_verifying_key().to_string().hex()

        compressed_public_key = '02' + public_key[0:64] if int(public_key[-2:], 16) % 2 == 0 else '03' + public_key[0:64]
        compressed_public_key_bytes = bytes.fromhex(compressed_public_key)

        ripemd160_hash = hashlib.new('ripemd160')
        ripemd160_hash.update(hashlib.sha256(compressed_public_key_bytes).digest())
        hashed_compressed_public_key = ripemd160_hash.digest().hex()

        if hashed_compressed_public_key == target_hash:
            print(private_key_hex)
            print("hash160:", hashed_compressed_public_key)
            print("Target hash found!")

            stop_event.set()
            break

def main():
    num_processes = 4
    processes = []
    stop_event = Event()

    for _ in range(num_processes):
        process = Process(target=worker, args=(66, 35, stop_event))
        processes.append(process)

    for process in processes:
        process.start()

    for process in processes:
        process.join()

    if stop_event.is_set():
        for process in processes:
            process.terminate()

if __name__ == '__main__':
    main()