Bitcoin Forum
February 19, 2025, 10:32:41 PM *
News: Latest Bitcoin Core release: 28.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: « 1 ... 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 [154] 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 ... 371 »
  Print  
Author Topic: Bitcoin puzzle transaction ~32 BTC prize to who solves it  (Read 255914 times)
james5000
Jr. Member
*
Offline Offline

Activity: 69
Merit: 2


View Profile
August 08, 2023, 03:34:31 AM
Last edit: August 08, 2023, 04:01:02 AM by james5000
 #3061

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?  Wink

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

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!! Cheesy

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
Newbie
*
Offline Offline

Activity: 27
Merit: 9


View Profile
August 08, 2023, 05:49:41 AM
 #3062

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. Smiley
vneos
Newbie
*
Offline Offline

Activity: 27
Merit: 9


View Profile
August 08, 2023, 09:16:07 AM
 #3063

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. Smiley
frozenen
Newbie
*
Offline Offline

Activity: 29
Merit: 0


View Profile
August 08, 2023, 09:23:39 AM
 #3064

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
Member
**
Offline Offline

Activity: 287
Merit: 21

the right steps towerds the goal


View Profile
August 08, 2023, 09:59:11 AM
 #3065

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

1BGvwggxfCaHGykKrVXX7fk8GYaLQpeixA
lordfrs
Jr. Member
*
Offline Offline

Activity: 57
Merit: 1


View Profile
August 08, 2023, 10:45:14 AM
 #3066

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

If you want to buy me a coffee

Btc = 3246y1G9YjnQQNRUrVMnaeCFrymZRgJAP7

Doge = DGNd8UTi8jVTVZ2twhKydyqicynbsERMjs
citb0in
Hero Member
*****
Offline Offline

Activity: 910
Merit: 782


Bitcoin g33k


View Profile
August 08, 2023, 11:03:59 AM
 #3067

Quote from: lordfrs
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


  _      _   _       __  _          _  _   __
 |_) |  / \|/   (_  / \ | \  / |_ |_) (_ 
 |_) |_ \_/ \_ |\   __) \_/ |_ \/  |_ | \ __)
--> citb0in Solo-Mining Group <--- low stake of only 0.001 BTC. We regularly rent about 5 PH/s hash power and direct it to SoloCK pool. Wanna know more? Read through the link and JOIN NOW
vsv68
Newbie
*
Offline Offline

Activity: 8
Merit: 0


View Profile
August 08, 2023, 01:53:05 PM
 #3068

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
Jr. Member
*
Offline Offline

Activity: 69
Merit: 2


View Profile
August 08, 2023, 02:00:23 PM
 #3069

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

exactly that, there is no way to be greater than 2^65 as the friend said yesterday
james5000
Jr. Member
*
Offline Offline

Activity: 69
Merit: 2


View Profile
August 08, 2023, 02:08:02 PM
Last edit: August 08, 2023, 03:31:28 PM by james5000
 #3070

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

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
Jr. Member
*
Offline Offline

Activity: 69
Merit: 2


View Profile
August 08, 2023, 04:06:38 PM
Last edit: August 08, 2023, 04:36:18 PM by james5000
 #3071

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!!!! Grin

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

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()

al3xcjc
Newbie
*
Offline Offline

Activity: 1
Merit: 0


View Profile
August 08, 2023, 07:31:28 PM
 #3072

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

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.




No, the code doesn't directly involve scalar multiplication for generating private keys. Instead, it generates private keys by randomly shuffling bits to create a binary string, which is then converted to a hexadecimal representation. The generated private key is then used to create a public key and subsequently generate a Bitcoin address.

In the context of Bitcoin, scalar multiplication is a fundamental operation used in elliptic curve cryptography (ECC). Scalar multiplication is used to derive a public key from a private key, and it's a core operation in generating Bitcoin addresses. However, the code doesn't explicitly perform scalar multiplication. It generates private keys in a way that doesn't directly reflect the typical method used in Bitcoin.

Here's how scalar multiplication is generally used in Bitcoin address generation:

A private key is randomly generated using a secure random number generator.
Scalar multiplication is performed on the elliptic curve with the private key and a predefined generator point to compute the corresponding public key point.
The x-coordinate of the resulting public key point is used to create a Bitcoin address.
In the code, the process of generating private keys is unrelated to scalar multiplication. Instead, it generates private keys through a random bit shuffling approach, converts them to hexadecimal format, and then processes them to create public keys and Bitcoin addresses.
albert0bsd
Hero Member
*****
Offline Offline

Activity: 1119
Merit: 718



View Profile
August 08, 2023, 07:34:08 PM
 #3073

My only sugestion for you get more speed is to work with some precalculated table of publickeys for some specific number of bits...

Lets to said that we want to process subranges of of 3 o 4 bytes [24 or 32 bits] (Less significative bits)
if the target puzzle is 66 bits you will have some main range of [42 or 34 bits] (Most significative bits)

Code:
[Main range 42 or 34 bits][Subrange 24 or 32 bits]

if you want to have Ratio from 40% to 60% that means you only need 33 +/6 bits in "1"

So that +/- 6 variations of bits maybe only need to checked in each subrange... or only +/- 4 bits in the subrange and +/- 2 bits in the main rarange

Example for a Subrange of 3 Bytes [24 bits], half is 12 bits +/- 4 will be checked all those with from 8 bits to 16 bits in "1"

For this example we need to calcualte all the publickeys under 24 bits that its privatekeys have only bewteen 8 to 16 bits in "1",
2^24 are 16777216 keys, you will only need to stetore (Surprise) 94 % of them in memory

Once that you already have that table in memory you only need is to Select a KEY from the Main range and performe a Point Addition againts all the previous table

That should gain some speed...
albert0bsd
Hero Member
*****
Offline Offline

Activity: 1119
Merit: 718



View Profile
August 08, 2023, 08:12:44 PM
 #3074

The generated private key is then used to create a public key and subsequently generate a Bitcoin address.

That is exactly what scalar multiplication means...
james5000
Jr. Member
*
Offline Offline

Activity: 69
Merit: 2


View Profile
August 08, 2023, 08:33:41 PM
 #3075

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

one more problem in this method is the keys repeat   Embarrassed
citb0in
Hero Member
*****
Offline Offline

Activity: 910
Merit: 782


Bitcoin g33k


View Profile
August 08, 2023, 08:35:20 PM
 #3076

you should get rid of the bad idea that a ratio of 40/60 or vice-versa of zeros and ones exists. That is simply absurd. Pure waste of time. With the method mentioned here you would never have discovered the puzzles 11,12,13,14,17,18,19,24,25,31,48,49,51,56,57.

  _      _   _       __  _          _  _   __
 |_) |  / \|/   (_  / \ | \  / |_ |_) (_ 
 |_) |_ \_/ \_ |\   __) \_/ |_ \/  |_ | \ __)
--> citb0in Solo-Mining Group <--- low stake of only 0.001 BTC. We regularly rent about 5 PH/s hash power and direct it to SoloCK pool. Wanna know more? Read through the link and JOIN NOW
james5000
Jr. Member
*
Offline Offline

Activity: 69
Merit: 2


View Profile
August 08, 2023, 08:39:24 PM
 #3077

you should get rid of the bad idea that a ratio of 40/60 or vice-versa of zeros and ones exists. That is simply absurd. Pure waste of time. With the method mentioned here you would never have discovered the puzzles 11,12,13,14,17,18,19,24,25,31,48,49,51,56,57.

please what method do you suggest then? I observed many calculating, looking for errors etc... one or two try to improve, after all I'm not quite right, but it is something new and clearly an advantage in the search.
citb0in
Hero Member
*****
Offline Offline

Activity: 910
Merit: 782


Bitcoin g33k


View Profile
August 08, 2023, 08:56:46 PM
 #3078

you should get rid of the bad idea that a ratio of 40/60 or vice-versa of zeros and ones exists. That is simply absurd. Pure waste of time. With the method mentioned here you would never have discovered the puzzles 11,12,13,14,17,18,19,24,25,31,48,49,51,56,57.

please what method do you suggest then? I observed many calculating, looking for errors etc... one or two try to improve, after all I'm not quite right, but it is something new and clearly an advantage in the search.

this method is just as useless as the previous proposed ones. It's all right for ideas to come in, but you should get caught up in it and chase after something that makes no sense in this context. It is exactly the same as the clumsy attempt to guess the position of the searched key within the searched bit range. It is simply impossible, because there are always outliers (as the past and thus our existing knowledge proves). People try to create a pattern, in the process they get lost in the chaos Wink

  _      _   _       __  _          _  _   __
 |_) |  / \|/   (_  / \ | \  / |_ |_) (_ 
 |_) |_ \_/ \_ |\   __) \_/ |_ \/  |_ | \ __)
--> citb0in Solo-Mining Group <--- low stake of only 0.001 BTC. We regularly rent about 5 PH/s hash power and direct it to SoloCK pool. Wanna know more? Read through the link and JOIN NOW
james5000
Jr. Member
*
Offline Offline

Activity: 69
Merit: 2


View Profile
August 08, 2023, 10:11:43 PM
 #3079

muticore mode added to python code

https://github.com/Jamerson1000/million-python
elvis13
Newbie
*
Offline Offline

Activity: 26
Merit: 2


View Profile
August 10, 2023, 12:17:58 PM
 #3080

james5000
How to run it in Ubuntu?
Write a command.
Pages: « 1 ... 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 [154] 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 ... 371 »
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!