[ARCHIVE] Bitcoin challenge discusion

[cactus87]

The next key should start with 1, because the rage is given already
it is 2^n-1->2ⁿ-1, not 1->2ⁿ-1

[1714905494]

1714905494

[almightyruler]

The next key should start with 1, because the rage is given already
it is 2^n-1->2ⁿ-1, not 1->2ⁿ-1

Okay, I've re-read the OP, and it seems I missed that the keys were generated randomly from a specific range for that key, rather than a 256 bit number with the upper bits masked out.

I'm sure I saw the person who created the transaction (whose nick I cannot remember now) say something about masking, but it wouldn't be the first time my memory had failed.


-----

Edit: I found the text from the creator. (I cannot vouch for authenticity)

A few words about the puzzle.  There is no pattern.  It is just consecutive keys from a deterministic wallet (masked with leading 000...0001 to set difficulty).  It is simply a crude measuring instrument, of the cracking strength of the community.

So I remembered correctly: the creator specifically mentions masking (of deterministic keys), rather than generating random numbers from specific ranges.

Based on the binary representation here https://rya.nc/forensic-bitcoin-cracking.html , it seems that all keys up to at least #37 have their top bit set, so if it's truly masked as the creator stated, it would be a massive coincidence (like flipping heads 37 times) that all have that bit set.

(Perhaps each key was masked PLUS the top bit set?)

[crofrihosl]

--

Public key for #64 = ?

[almightyruler]

--

Public key for #64 = ?

From the OP:

2019-05-31 - the creator of the "puzzles" creates outgoing transactions with the value of 1satoshi for addresses #65, #70, #75, #80, #85, #90, #95, #100, #105, #110, #115 , #120, #125, #130, #135, #140, #145, #150, #155, #160 with the aim of probably comparing the difficulty of finding a private key for the address from which such a transaction was carried out, and one that There is no transaction.

#64 has never been spent (an outbound transaction), so there's no public key known yet.

If brute force is the only way to creak a P2PKH address with no outbound transactions, then at some point it may become more viable to crack the lower ranges of #160 to #256 (public keys known) than to brute force the "easier" challenges of #156 to #159 (public keys unknown).

[PrivatePerson]

It is impossible to add to the algorithm a kangaroo so that it does not search by public key, but by address? Suppose this takes longer, but you can search for keys for addresses without an outgoing transaction. Or is the kangaroo algorithm not suitable for this?

[Firebox]

It is impossible to add to the algorithm a kangaroo so that it does not search by public key, but by address? Suppose this takes longer, but you can search for keys for addresses without an outgoing transaction. Or is the kangaroo algorithm not suitable for this?

For this case you have a VanitySearch.

[BurtW]

It is impossible to add to the algorithm a kangaroo so that it does not search by public key, but by address? Suppose this takes longer, but you can search for keys for addresses without an outgoing transaction. Or is the kangaroo algorithm not suitable for this?

The Kangaroo algorithm requires that you know the public key in order for it to work.  Knowing the Bitcoin address, which is the hash of the public key, cannot be used.  You need to know the actual public key or you cannot use the Kangaroo algorithm.  If you are interested in exactly how the Kangaroo algorithm works you can check out our thread here:

https://bitcointalk.org/index.php?topic=5173445.0

Or, just read about it here:

Pollard Kangaroo algorithm

[almightyruler]

It is impossible to add to the algorithm a kangaroo so that it does not search by public key, but by address? Suppose this takes longer, but you can search for keys for addresses without an outgoing transaction. Or is the kangaroo algorithm not suitable for this?

For this case you have a VanitySearch.

To add further detail...

When the pubkey is known, all you have to do is find an efficient way (more efficient than brute force) to "reverse" secp256k1 and obtain the private key.

When the pubkey is unknown, you must also find a way to reverse two cryptographic hash functions (RIPEMD160 and SHA256). This is going to be near impossible, since when you feed data to a cryptographic hash function, the output does not resemble the input in any way. It's deliberately modified, mixed, and mashed together into a sea of random looking bits.

You would need to:

1. Break (ie discover and exploit an inherent weakness in the algorithm itself) RIPEMD160 to find an input of precisely 256 bits that matches the address you're trying to crack.
2. Break SHA256 to find an input of precisely 264 bits (for a compressed public key) or 520 bits (uncompressed) that results in the 256 bit value which was created from step #1.
3. That input value from step #2 is the public key. (It probably won't be the same public key used by the rightful owner, however, I think a collision at this point would be sufficient to claim funds?). But then you still have to crack the pubkey to find the 256 bit private key...

Step #3 is already computationally impossible.

[MrFreeDragon]

The main idea of The Kangaroo algorithm could be explain by the example of birth dates paradox.

Imagine that you take the group of 23 persons, so there is more than 50% probability that 2 persons were born on the same date. If you take the group of 50 persons, the probability that 2 of them were born on the same date is at least 97%. For group of 100 persons, such probability is 99.99996%.

So, to find 2 persons with the same date of birth you do not need to ask 366 persons. You can easility take the group of 50 persons (which is 7 times less) and highly likely (with 97%) find within this goup 2 persons with the same date of birth.

In bitcon with (or withount) public key is the same idea. If you do not know the public key the directway is to bruteforce the whole range. But if the public key is known, you can highly likely find the private key just making the squre root of the total range operations.


Example: for 40bit key (41 bin digits) the range is 2^40 = 1 099 511 627 776. This could be bruteforced with the speed 350Mkey/sec for approx. 52 minutes. But with the Kangaroo method the calcualtions range is only  1 048 576, and highly likely you will find the key. Highly likely means that not 100%, but very close to 100%.

For #105 key the approximate range with Kangaroo is 4 503 599 627 370 496 which could resolved with 300MKey/sec speed for 175 days (almost 6 months). But with the 5 times more speed (1,500MKey/sec) it could resolved just for 1-1.5 months. But again, "resolved" here means that "more likely resolved" with not 100% but very close to it.

[almightyruler]

I wonder how many people are deliberately working on brute forcing a harder output, say #66 or #67, to increase their chances of being able to find the solution before someone else claims it? If you work on <current>+1, then you could already be a quarter to halfway through the search space for the "new" key, by the time the solution for <current> is discovered.

[itod]

I wonder how many people are deliberately working on brute forcing a harder output, say #66 or #67, to increase their chances of being able to find the solution before someone else claims it? If you work on <current>+1, then you could already be a quarter to halfway through the search space for the "new" key, by the time the solution for <current> is discovered.

This is a good point. If you are searching for <current>+1 and starting from the beginning of the keyspace you are racing against the fastest guy in the world, whoever he is. It is more than likely you are not the fastest guy because you haven't found the <current> highest private key, have you? Doing this is enormous waist of the resources, only one guy needs to have faster calculator than you, and it is more than likely bunch of guys already checked private keys you are currently checking thinking they were the fastest. But they were not, they were only thinking they were fastest because only single one can be fastest, all others are heating their homes with wasted electricity.

[MeBender]

I wonder how many people are deliberately working on brute forcing a harder output, say #66 or #67, to increase their chances of being able to find the solution before someone else claims it? If you work on <current>+1, then you could already be a quarter to halfway through the search space for the "new" key, by the time the solution for <current> is discovered.

This is a good point. If you are searching for <current>+1 and starting from the beginning of the keyspace you are racing against the fastest guy in the world, whoever he is. It is more than likely you are not the fastest guy because you haven't found the <current> highest private key, have you? Doing this is enormous waist of the resources, only one guy needs to have faster calculator than you, and it is more than likely bunch of guys already checked private keys you are currently checking thinking they were the fastest. But they were not, they were only thinking they were fastest because only single one can be fastest, all others are heating their homes with wasted electricity.

Unless you are using -r and hoping to get lucky 

[usama12]

#64

9000000000000000   -     900008c8cdbfc000
fe38B13505B26867   -     fe38b4e9a9e18000
fe08b4e9a9e18000   -      fe38b28c4dcdf000
f908b4e9a9e18000   -      f908b83fef996800
e908b4e9a9e18000  -      e908b8e3fd70a800
f200000000000000   -      f20007dc504d4000
a0dea1390507f800   -      a0decf332bc7f800
f4430518eaddc000   -      f44309cb5f5dc000
d39b97986985a000  -      d39bf99dea45a000
c89526398b87e000  -      c895840b4507e000
de1df04147b1b000  -       de1df13e0f31b000
e3ef4e58aa31b000   -      e3efc87af531b000
cde0b6b3a7640000  -      cde0c690b6a40000

This ranges are already scanned.
 

[crofrihosl]

#64

9000000000000000   -     900008c8cdbfc000
fe38B13505B26867   -     fe38b4e9a9e18000
fe08b4e9a9e18000   -      fe38b28c4dcdf000
f908b4e9a9e18000   -      f908b83fef996800
e908b4e9a9e18000  -      e908b8e3fd70a800
f200000000000000   -      f20007dc504d4000
a0dea1390507f800   -      a0decf332bc7f800
f4430518eaddc000   -      f44309cb5f5dc000
d39b97986985a000  -      d39bf99dea45a000
c89526398b87e000  -      c895840b4507e000
de1df04147b1b000  -       de1df13e0f31b000
e3ef4e58aa31b000   -      e3efc87af531b000
cde0b6b3a7640000  -      cde0c690b6a40000

This ranges are already scanned.
  

what do you use ? and what is your speed?

i try this and no luck yet

Code:

VanitySearch-1.15.2_bitcrack -stop -t 2 -r 500 -s  000000000000000000000000000000000000000000000000cdf0d690b6af0000 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN

[usama12]

#64

9000000000000000   -     900008c8cdbfc000
fe38B13505B26867   -     fe38b4e9a9e18000
fe08b4e9a9e18000   -      fe38b28c4dcdf000
f908b4e9a9e18000   -      f908b83fef996800
e908b4e9a9e18000  -      e908b8e3fd70a800
f200000000000000   -      f20007dc504d4000
a0dea1390507f800   -      a0decf332bc7f800
f4430518eaddc000   -      f44309cb5f5dc000
d39b97986985a000  -      d39bf99dea45a000
c89526398b87e000  -      c895840b4507e000
de1df04147b1b000  -       de1df13e0f31b000
e3ef4e58aa31b000   -      e3efc87af531b000
cde0b6b3a7640000  -      cde0c690b6a40000

This ranges are already scanned.
  

what do you use ? and what is your speed?

i try this and no luck yet

Code:

VanitySearch-1.15.2_bitcrack -stop -t 2 -r 500 -s  000000000000000000000000000000000000000000000000cdf0d690b6af0000 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN

I am using bitcrack on RTX 2080 Ti and  has speed of 1130 Mkeys/s. I am scanning from last 4 days. Now I am thinking to scan random.

[MrFreeDragon]

I am using bitcrack on RTX 2080 Ti and  has speed of 1130 Mkeys/s. I am scanning from last 4 days. Now I am thinking to scan random.

One more participant in the digital lottery  

The chances to find the key (randomly) during the priod of 10,000 years with the speed 1130MKey/sec are (1 130 000 * 60 * 60 * 24 * 365 * 10 000) / (2^63) = 0.038636 ≈ 3.8%

For 80 years (like for the whole your life) it just 0.031% [but actually some less because your random could generate the same keys during these 80 years]

For comparison, there are 16,000,000 thunder storms annually, 25,000,000 cloud lightings come to earth. Such lightings kill approximately 55 humans during a year. Considering the average life of 80 years, te chances to be killed by a storm lighting are 1:3000, so it is like 0.033%, which is more than the chances to find a key for #64 with the speed 1130MKey/s for 80 years  

So, do you really expect to be killed by a lighting storm during your life? Oh no, you beleive this will never happen because the chances are very very low.

But why do you beleive to find the key to #64 where the chances for the same period (80 years) are less? - the answer is in our mind which rejects the statistics: positive events are expected to happen (even with very very low chances), but negative events we just not beleive could happened.

[iparktur]

I am using bitcrack on RTX 2080 Ti and  has speed of 1130 Mkeys/s. I am scanning from last 4 days. Now I am thinking to scan random.

One more participant in the digital lottery  

For 80 years (like for the whole your life) it just 0.031% [but actually some less because your random could generate the same keys during these 80 years]

For comparison, there are 16,000,000 thunder storms annually, 25,000,000 cloud lightings come to earth. Such lightings kill approximately 55 humans during a year. Considering the average life of 80 years, te chances to be killed by a storm lighting are 1:3000, so it is like 0.033%, which is more than the chances to find a key for #64 with the speed 1130MKey/s for 80 years  

Perhaps these 55 people thought so too?

[MrFreeDragon]

One more participant in the digital lottery  

For 80 years (like for the whole your life) it just 0.031% [but actually some less because your random could generate the same keys during these 80 years]

For comparison, there are 16,000,000 thunder storms annually, 25,000,000 cloud lightings come to earth. Such lightings kill approximately 55 humans during a year. Considering the average life of 80 years, te chances to be killed by a storm lighting are 1:3000, so it is like 0.033%, which is more than the chances to find a key for #64 with the speed 1130MKey/s for 80 years  

Perhaps these 55 people thought so too?

Here is the list of some of them (not all 55 for every year, but some famous people):

https://www.ranker.com/list/famous-people-who-died-of-lightning/reference

[crofrihosl]

--sinip--
The chances to find the key (randomly) during the priod of 10,000 years with the speed 1130MKey/sec are (1 130 000 * 60 * 60 * 24 * 365 * 10 000) / (2^63) = 0.038636 ≈ 3.8%
--sinip--

if someone took the key space 2^256
and start ruining his bots with speed 200 address/sec (generating and testing for tx and balance 200/s)

what is his chance to find an address with tx or balance from all addresses that ever used?
 

to be honest i start working on similar project but need to increase speed and few option to working on

[BurtW]

--sinip--
The chances to find the key (randomly) during the priod of 10,000 years with the speed 1130MKey/sec are (1 130 000 * 60 * 60 * 24 * 365 * 10 000) / (2^63) = 0.038636 ≈ 3.8%
--sinip--

if someone took the key space 2^256
and start ruining his bots with speed 200 address/sec (generating and testing for tx and balance 200/s)

what is his chance to find an address with tx or balance from all addresses that ever used?
 

to be honest i start working on similar project but need to increase speed and few option to working on

For all practical purposes:  no chance at all.