Topic: Bitcoin puzzle transaction ~32 BTC prize to who solves it - page 202. (Read 244546 times)

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)


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

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.

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



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



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

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


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.

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.

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

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://bitcointalksearch.org/topic/m.62662714

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:


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

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

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 i give the exact percent of zeros and ones in 66 bit key, how much time it takes to solve?

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?

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.

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



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

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.

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.   


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.

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

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

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

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.

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


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


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?


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:


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


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


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

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.

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

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.