james5000
Jr. Member
Offline
Activity: 69
Merit: 2
|
 |
August 08, 2023, 03:34:31 AM Last edit: August 08, 2023, 04:01:02 AM by 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.  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. 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
Activity: 27
Merit: 9
|
 |
August 08, 2023, 05:49:41 AM |
|
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): 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:: 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
Newbie
Offline
Activity: 27
Merit: 9
|
 |
August 08, 2023, 09:16:07 AM |
|
I wrote a simple script for solving puzzle 66: https://github.com/allinbit/btc_puzzleIf it could be ported to gpu then it would be faster but I don't know anything about it. 
|
|
|
|
frozenen
Newbie
Offline
Activity: 29
Merit: 0
|
 |
August 08, 2023, 09:23:39 AM |
|
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
Activity: 287
Merit: 21
the right steps towerds the goal
|
 |
August 08, 2023, 09:59:11 AM |
|
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
Activity: 57
Merit: 1
|
 |
August 08, 2023, 10:45:14 AM |
|
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
|
 |
August 08, 2023, 11:03:59 AM |
|
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,824no 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
Activity: 8
Merit: 0
|
 |
August 08, 2023, 01:53:05 PM |
|
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#msg62662714I 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: 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
Activity: 69
Merit: 2
|
 |
August 08, 2023, 02:00:23 PM |
|
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): 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:: 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
Jr. Member
Offline
Activity: 69
Merit: 2
|
 |
August 08, 2023, 02:08:02 PM Last edit: August 08, 2023, 03:31:28 PM by james5000 |
|
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
Activity: 69
Merit: 2
|
 |
August 08, 2023, 04:06:38 PM Last edit: August 08, 2023, 04:36:18 PM by james5000 |
|
Using my method with multiprocessing, I reach #30 in that time. 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. 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... 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. 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
Activity: 1
Merit: 0
|
 |
August 08, 2023, 07:31:28 PM |
|
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
|
 |
August 08, 2023, 07:34:08 PM |
|
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) [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
|
 |
August 08, 2023, 08:12:44 PM |
|
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
Activity: 69
Merit: 2
|
 |
August 08, 2023, 08:33:41 PM |
|
one more problem in this method is the keys repeat 
|
|
|
|
citb0in
|
 |
August 08, 2023, 08:35:20 PM |
|
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
Activity: 69
Merit: 2
|
 |
August 08, 2023, 08:39:24 PM |
|
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
|
 |
August 08, 2023, 08:56:46 PM |
|
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 
|
_ _ _ __ _ _ _ __ |_) | / \ / |/ (_ / \ | \ / |_ |_) (_ |_) |_ \_/ \_ |\ __) \_/ |_ \/ |_ | \ __) --> 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
Activity: 69
Merit: 2
|
 |
August 08, 2023, 10:11:43 PM |
|
|
|
|
|
elvis13
Newbie
Offline
Activity: 26
Merit: 2
|
 |
August 10, 2023, 12:17:58 PM |
|
james5000 How to run it in Ubuntu? Write a command.
|
|
|
|
|