Author

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

member
Activity: 420
Merit: 10
“Tackling Climate Change Using Blockchain”
These addresses could be just random addresses created by the bot who seem to have been programmed by somebody knowledgeable about bitcoin to send to other addresses. This could have been done for recreation or for some purpose like safe keeping the coins from hackers. We will never know until one person will come in and say I have done this! Anyway thank you for your post.
full member
Activity: 282
Merit: 114
ok.. i have 32GB ram so I would like to try that. Thank You for all informations arulbero!
legendary
Activity: 1948
Merit: 2097
https://gist.github.com/jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89

In practice, you will not compile an executable script for this task (where you also need to change #define GSTEP (1 << 25)) to #define GSTEP (1UL << 60)

In the original version of the script it looks like this:
Code:
2 ^ 25 * 2 * 8/1024/1024 = 512 MB #Required RAM memory
For the current level:

2 ^ 60 * 2 * 8/1024/1024 = 17592186044416 MB (seventeen trillion five hundred ninety-two billion one hundred eighty-six million forty-four thousand four hundred sixteen megabytes) #Required RAM

So ... if you do not have this amount of RAM - you will not use this method.

Look at the original code:

https://gist.github.com/jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89
Code:
/* giant steps are 2^25 */
#define GSTEP (1<<25)

#define NUMPUBKEYS 51
unsigned char rawpubkeys[NUMPUBKEYS][33] ...

As you can see, to search the key #51 (from 2^50 to 2^51) you need a number of giant steps (and baby steps) equal to 2^25 (not to 2^51!)

if you look at the hash table:
Code:
typedef struct hashtable_entry {
    uint32_t x;
    uint32_t exponent;
} hashtable_entry;

#define HASH_SIZE (2*GSTEP)
hashtable_entry table[HASH_SIZE];

each entry size is 32 bit + 32 bit = 64 bit = 8 byte. The size of the hash table is 2*GSTEP, 2^26 entries.

So for the original script:

8 byte * 2^26 = 2^29 bytes, 512 MB.

If you change GSTEP from 2^25 to 2^26, you can find the keys #51 and #52 too (if you have more than 1 GB).

It is not correct at all saying that at the current level we need 2^60 giant steps / 2^60 baby steps!

I did many other modifications to the code. I can have a max number of giant steps (for my RAM) equal to 2^30, if I need to search in a bigger space than 2^60 I have to split then the baby step lists ( I generate first a hash table with a part of the list, then I delete it and I create another one, and so on). This way the program becomes very slow, I can retrieve a key in a 2^60 space in a very short time, but not over the 2^70 (unless I accept to wait days to have the result).
full member
Activity: 282
Merit: 114
@zielar: it is possible, I used the baby step giant step algorithm to retrieve the key #60 in about 80 seconds. And I have 32 GB ram.

space search for each key of the puzzle transaction:

key #1 : from 1 to 1   (2^0 -> 2^1 - 1)
key #2 : from 2 to 3   (2^1 -> 2^2 - 1)
key #3 : from 4 to 7   (2^2 -> 2^3 - 1)
key #4 : from 8 to 15 (2^3 -> 2^4 - 1)
....
key #60: from 2^59 to 2^60 - 1

Let's say for semplicity that our space search in this case is 2^60 (actually is only half, 2^59).

P is the public key, we want to find the private key k. If G is the generator of the curve, the private key k is the number :

k*G = P

baby-step-giant-step (--> http://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/):

you create two lists, the first one (the baby steps list) in a hash table stored in the Ram and the second one (the giant steps list) dynamic:

a) (baby steps list): each baby step is equal to 1 (the distance between 2 consecutive elements is 1*G) and we store all these public keys: (0G), 1*G, 2*G, 3*G, 4*G, 5*G, ..., 2^30*G (because sqrt(2^60) = 2^30) in a hash table

b) (giant steps list): each giant step is equal to the sqrt(space size), in our case sqrt(2^60) = 2^30, namely the distance between 2 elements is 2^30*G . We generate on fly this list:

P, P - 2^30*G, P - 2*2^30*G,  P - 3*2^30*G,  P - 4*2^30*G,  P - 5*2^30*G, .....,  P - (2^30 - 1)*2^30*G

and we check if there is a element in the giant-steps list equal to an element in the baby-steps list.

If for example  P - 5*2^30*G = 1000*G, then P = 5*2^30*G + 1000*G

--> P = (5*2^30 + 1000) * G  --> private key k = (5*2^30 + 1000)


2 lists, 2^30 elements * 2^30 elements = 2^60 comparisons without doing 2^60 operations, this is the trick.

Hash table: 2^30 entries, each entry has the coordinate x of the public key (256 bit) + the number of the private key (max 32 bit). I'm using only the first 32 bits of the x instead of 256 bits (there are only few false collisions looking at the first 32 bits and I check these collisions), then I need to store (32 + 32) * 2^30 bit, 2^36 bit, 64 GByte.

With some other optimizations (the search space is actually 2^59 and not 2^60 + other properties of the secp256 k1 curve), with 32 GB I can run the program.

When the search space is greater than 60 bit, let's say 62 bit, I can't store all the 2^31 public keys of the baby steps list in the Ram, then I split 2^31 in 2 lists of 2^30 elements, A e B, then first I check the entire giant steps list against the list A, and if there is no match, I generate the list B and I generate again the giant steps list.

I do not quite understand if I interpret your answer well, and if so, not really ... So how does your output code look like that you can compile without using that amount of RAM?
legendary
Activity: 1948
Merit: 2097
@zielar: it is possible, I used the baby step giant step algorithm to retrieve the key #60 in about 80 seconds. And I have 32 GB ram.

space search for each key of the puzzle transaction:

key #1 : from 1 to 1   (2^0 -> 2^1 - 1)
key #2 : from 2 to 3   (2^1 -> 2^2 - 1)
key #3 : from 4 to 7   (2^2 -> 2^3 - 1)
key #4 : from 8 to 15 (2^3 -> 2^4 - 1)
....
key #60: from 2^59 to 2^60 - 1

Let's say for semplicity that our space search in this case is 2^60 (actually is only half, 2^59).

P is the public key, we want to find the private key k. If G is the generator of the curve, the private key k is the number :

k*G = P

baby-step-giant-step (--> http://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/):

you create two lists, the first one (the baby steps list) in a hash table stored in the Ram and the second one (the giant steps list) dynamic:

a) (baby steps list): each baby step is equal to 1 (the distance between 2 consecutive elements is 1*G) and we store all these public keys: (0G), 1*G, 2*G, 3*G, 4*G, 5*G, ..., 2^30*G (because sqrt(2^60) = 2^30) in a hash table

b) (giant steps list): each giant step is equal to the sqrt(space size), in our case sqrt(2^60) = 2^30, namely the distance between 2 elements is 2^30*G . We generate on fly this list:

P, P - 2^30*G, P - 2*2^30*G,  P - 3*2^30*G,  P - 4*2^30*G,  P - 5*2^30*G, .....,  P - (2^30 - 1)*2^30*G

and we check if there is a element in the giant-steps list equal to an element in the baby-steps list.

If for example  P - 5*2^30*G = 1000*G, then P = 5*2^30*G + 1000*G

--> P = (5*2^30 + 1000) * G  --> private key k = (5*2^30 + 1000)


2 lists, 2^30 elements * 2^30 elements = 2^60 comparisons without doing 2^60 operations, this is the trick.

Hash table: 2^30 entries, each entry has the coordinate x of the public key (256 bit) + the number of the private key (max 32 bit). I'm using only the first 32 bits of the x instead of 256 bits (there are only few false collisions looking at the first 32 bits and I check these collisions), then I need to store (32 + 32) * 2^30 bit, 2^36 bit, 8 GByte. The hash table actually has to have the double of the number of the keys in the baby steps list (to avoid collisions between two different "x" that share the same 32 bits), so I need at least 16 GByte.

With some other optimizations (the search space is actually 2^59 and not 2^60 + other properties of the secp256k1 curve), I can run the program.

When the search space is greater than 60 bit, let's say 62 bit, I can't store all the 2^31 public keys of the baby steps list at once in the Ram, then I split 2^31 in 2 lists of 2^30 elements, A e B, then first I check the entire giant steps list against the list A, and if there is no match, I generate the list B and I generate again the giant steps list.
full member
Activity: 282
Merit: 114
Congratulations to the person who found the #60. and thanks to Arulbero for the answer.

I couldn't fix the code on https://gist.github.com/jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89 to get from #52 and above  Grin

or to get only one of the address.

The implementation of the Step By Step method at the current level is impossible due to the amount of resources that are needed for this. Although in theory below I have listed for you the remaining RAW PUBLIC KEYS values:
Code:
   { 0x02,0x8c,0x6c,0x67,0xbe,0xf9,0xe9,0xee,0xbe,0x6a,0x51,0x32,0x72,0xe5,0x0c,0x23,0x0f,0x0f,0x91,0xed,0x56,0x0c,0x37,0xbc,0x9b,0x03,0x32,0x41,0xff,0x6c,0x3b,0xe7,0x8f }, /* 51 */
    { 0x03,0x74,0xc3,0x3b,0xd5,0x48,0xef,0x02,0x66,0x7d,0x61,0x34,0x18,0x92,0x13,0x4f,0xcf,0x21,0x66,0x40,0xbc,0x22,0x01,0xae,0x61,0x92,0x8c,0xd0,0x87,0x4f,0x63,0x14,0xa7 }, /* 52 */
    { 0x02,0x0f,0xaa,0xf5,0xf3,0xaf,0xe5,0x83,0x00,0xa3,0x35,0x87,0x4c,0x80,0x68,0x1c,0xf6,0x69,0x33,0xe2,0xa7,0xae,0xb2,0x83,0x87,0xc0,0xd2,0x8b,0xb0,0x48,0xbc,0x63,0x49 }, /* 53 */
    { 0x03,0x4a,0xf4,0xb8,0x1f,0x8c,0x45,0x0c,0x2c,0x87,0x0c,0xe1,0xdf,0x18,0x4a,0xff,0x12,0x97,0xe5,0xfc,0xd5,0x49,0x44,0xd9,0x8d,0x81,0xe1,0xa5,0x45,0xff,0xb2,0x25,0x96 }, /* 54 */
    { 0x03,0x85,0xa3,0x0d,0x84,0x13,0xaf,0x4f,0x8f,0x9e,0x63,0x12,0x40,0x0f,0x2d,0x19,0x4f,0xe1,0x4f,0x02,0xe7,0x19,0xb2,0x4c,0x3f,0x83,0xbf,0x1f,0xd2,0x33,0xa8,0xf9,0x63 }, /* 55 */
    { 0x03,0x3f,0x2d,0xb2,0x07,0x4e,0x32,0x17,0xb3,0xe5,0xee,0x30,0x53,0x01,0xee,0xeb,0xb1,0x16,0x0c,0x4f,0xa1,0xe9,0x93,0xee,0x28,0x01,0x12,0xf6,0x34,0x86,0x37,0x99,0x9a }, /* 56 */
    { 0x02,0xa5,0x21,0xa0,0x7e,0x98,0xf7,0x8b,0x03,0xfc,0x1e,0x03,0x9b,0xc3,0xa5,0x14,0x08,0xcd,0x73,0x11,0x9b,0x5e,0xb1,0x16,0xe5,0x83,0xfe,0x57,0xdc,0x8d,0xb0,0x7a,0xea }, /* 57 */
    { 0x03,0x11,0x56,0x94,0x42,0xe8,0x70,0x32,0x6c,0xee,0xc0,0xde,0x24,0xeb,0x54,0x78,0xc1,0x9e,0x14,0x6e,0xcd,0x9d,0x15,0xe4,0x66,0x64,0x40,0xf2,0xf6,0x38,0x87,0x5f,0x42 }, /* 58 */
    { 0x02,0x41,0x26,0x7d,0x2d,0x7e,0xe1,0xa8,0xe7,0x6f,0x8d,0x15,0x46,0xd0,0xd3,0x0a,0xef,0xb2,0x89,0x2d,0x23,0x1c,0xee,0x0d,0xde,0x77,0x76,0xda,0xf9,0xf8,0x02,0x14,0x85 }, /* 59 */
    { 0x03,0x48,0xe8,0x43,0xdc,0x5b,0x1b,0xd2,0x46,0xe6,0x30,0x9b,0x49,0x24,0xb8,0x15,0x43,0xd0,0x2b,0x16,0xc8,0x08,0x3d,0xf9,0x73,0xa8,0x9c,0xe2,0xc7,0xeb,0x89,0xa1,0x0d }, /* 60 */
In practice, you will not compile an executable script for this task (where you also need to change #define GSTEP (1 << 25)) to #define GSTEP (1UL << 60)

In the original version of the script it looks like this:
Code:
2 ^ 25 * 2 * 8/1024/1024 = 512 MB #Required RAM memory
For the current level:
Code:
2 ^ 60 * 2 * 8/1024/1024 = 17592186044416 MB (seventeen trillion five hundred ninety-two billion one hundred eighty-six million forty-four thousand four hundred sixteen megabytes) #Required RAM
So ... if you do not have this amount of RAM - you will not use this method.
jr. member
Activity: 47
Merit: 13
Congratulations to the person who found the #60. and thanks to Arulbero for the answer.

I couldn't fix the code on https://gist.github.com/jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89 to get from #52 and above  Grin

or to get only one of the address.
jr. member
Activity: 108
Merit: 2
and address 60 has been solved today ! who can give the private key ?

Code:
Private key : 0000000000000000000000000000000000000000000000000fc07a1825367bbe
Public key  :
x: 48e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d
y: d094fcabf8995e2a25c73298a9f7419720db622daff89c67fd5535f6ac29720f
 

PrKey WIF c.: KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYkzijLsc5qE43yZ5eLV
Address c.  : cdf8e5c7503a9d22642e3ecfc87817672787b9c5
Address c.  : 1Kn5h2qpgw9mWE5jKpk8PP4qvvJ1QVy8su
thank you so much ! and congrats to whoever solved it !
legendary
Activity: 1948
Merit: 2097
and address 60 has been solved today ! who can give the private key ?

Code:
Private key : 0000000000000000000000000000000000000000000000000fc07a1825367bbe
Public key  :
x: 48e843dc5b1bd246e6309b4924b81543d02b16c8083df973a89ce2c7eb89a10d
y: d094fcabf8995e2a25c73298a9f7419720db622daff89c67fd5535f6ac29720f
 

PrKey WIF c.: KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYkzijLsc5qE43yZ5eLV
Address c.  : cdf8e5c7503a9d22642e3ecfc87817672787b9c5
Address c.  : 1Kn5h2qpgw9mWE5jKpk8PP4qvvJ1QVy8su
jr. member
Activity: 108
Merit: 2
and address 60 has been solved today ! who can give the private key ?
jr. member
Activity: 115
Merit: 1
How can one get the BCH pk?
Someone can help me with answers.....Thanks.

Yeah, the PK is the same and you could take these $70 instead of asking Smiley

p.s. I guess there are other bitcoin forks. But it's a bit lazy to check...
newbie
Activity: 26
Merit: 1
The pool has started the next TX. We're still in beta but taking new members via telegram.

Was the pk of TX59 gotten from your pool? If yes what about the BCH pk and how are they related? Whats your pool all about?
member
Activity: 166
Merit: 16
I notice that the puzzle address also has BCH in it. How is it possible to swipe the BCH? is the BTC private key same as that of the BCH? How can one get the BCH pk?
Someone can help me with answers.....Thanks.

Thanks for commenting Cheesy Now the person who claimed the prize will make sure to swipe the bch too before revealing the private key here!

Whats the range for the 60th address? Need to upgrade my blind monk script


(DEC) 576460752303423488-1152921504606846976

Thanks! Isn't that a bit shorter than the one before I think? Shouldn't it be 800000000000000-1FFFFFFFFFFFFFFFF instead of 1000000000000000?

in hex 10 = 16 8=8 - if it will make you feel better you could do 0800000000000000- 0FFFFFFFFFFFFFFF which would be 1 shy of the whole range and I can pretty much guarantee it would not be in that last one. (I have pretty good odds there eh? hehe)
jr. member
Activity: 37
Merit: 6
The pool has started the next TX. We're still in beta but taking new members via telegram.
sr. member
Activity: 938
Merit: 452
Check your coin privilege
I notice that the puzzle address also has BCH in it. How is it possible to swipe the BCH? is the BTC private key same as that of the BCH? How can one get the BCH pk?
Someone can help me with answers.....Thanks.

Thanks for commenting Cheesy Now the person who claimed the prize will make sure to swipe the bch too before revealing the private key here!

Whats the range for the 60th address? Need to upgrade my blind monk script


(DEC) 576460752303423488-1152921504606846976

Thanks! Isn't that a bit shorter than the one before I think? Shouldn't it be 800000000000000-1FFFFFFFFFFFFFFFF instead of 1000000000000000?
newbie
Activity: 26
Merit: 1
I notice that the puzzle address also has BCH in it. How is it possible to swipe the BCH? is the BTC private key same as that of the BCH? How can one get the BCH pk?
Someone can help me with answers.....Thanks.
jr. member
Activity: 108
Merit: 2
member
Activity: 166
Merit: 16
Whats the range for the 60th address? Need to upgrade my blind monk script


(DEC) 576460752303423488-1152921504606846976
jr. member
Activity: 34
Merit: 5
0x7496CBB87CAB44F
jr. member
Activity: 108
Merit: 2
congratulations to whoever found the key, and i really would like to see the private key, Smiley
Jump to: