== Bitcoin challenge transaction: ~1000 BTC total bounty to solvers! ==UPDATED==

[ttdclient]

Just wanted to let the community know that our pool has now implemented a key finder bonus.  I know a lot of you have been wanting it and now it is here.

Current bonus is around $3300 at the time of writing this.

The bonus is calculated as 1% of the top ten contributor payout and the users in the current top ten are not eligible.

Have a great day and hope to see everyone on the pool.

http://www.ttdsales.com/66bit/

Chris

[kenshiro12241]

I wanted to ask if someone got the public key for #66 as i have tried to bruteforce it but my hardware is not capable of doing so, if someone can link any code or algorithm (or even the public key if you have it).

[kTimesG]

I wanted to ask if someone got the public key for #66 as i have tried to bruteforce it but my hardware is not capable of doing so, if someone can link any code or algorithm (or even the public key if you have it).

I think you have the answer already by looking whether #66 was emptied or not. That is, the creator surely has the public key as he surely has the private key. Otherwise, someone would have used kangaroos long time ago, if pubKey was known.

I think it's pointless to "brute-force" the pubKey. I assume what you are thinking is somewhere along the lines:
1. Find some 256-bit number X (32 bytes) that results in RIPE(SHA('03' | X)) = decodeBase58(address)
2. Use ECDLP solver on P(X, y(X)) since you know it has a known long prefix.

Flaws
- you assume that there's only one X that results in the first equality. Chances are 1 in 2**96 that you'll get an X corresponding to a 66-bit private key. There's 2**256 SHA hashes that map to 2**160 RIPE hashes, so 1 address can be obtained (in theory) in 2**96 ways.
One of those 2**96 X's is the one having a 66-bit key. Most of all others will be in the 256-bit range.
- you're limited by SHA256 computing power of the hardware. Assuming you're after finding a collision, and let's say you have some GPUs providing 10 GH/s you're still looking at around 100 years of more until you find such a collision, which only guarantees you some 1 in 2**96 rate of success.

So to speed-up your search by a factor of 2**96, you'll need to brute-force the private key in order to do (correctly):
RIPE(SHA('03' | P.x)) = decodeBase58(address)
where P is the public key of the private key.

It will still take you same amount of time due to SHA limit above, but you have the guarantee of success.

Good luck.

[kenshiro12241]

can you explain me how does kangaroo works, for example if i have a public key for a bitcoin address can i use kangaroo to brute-force it's private key?

[WanderingPhilospher]

can you explain me how does kangaroo works, for example if i have a public key for a bitcoin address can i use kangaroo to brute-force it's private key?

Enjoy the read!

https://github.com/JeanLucPons/Kangaroo

[kenshiro12241]

i have one more doubt, let's say i have a public key (not for the puzzle), what input should i give in the start and end range?

[WanderingPhilospher]

i have one more doubt, let's say i have a public key (not for the puzzle), what input should i give in the start and end range?

Unless you remember the range in which the private key was generated, you'll have to search the entire range. No one can predict/give you a correct answer.

[satashi_nokamato]

Could you share with us whatever you have done in those 3 years?  I mean this could be somewhat true that solving these puzzles could be addictive, but I'm curious to know what were you doing exactly? I just hope it wasn't sitting and watching the screen while brute force tools were running.  Knowing the ways you tried will definitely help others not to try them, you can at least do that.

[kTimesG]

i just came to this conclusion:
I ran hundreds of tests and simulations and found that if a number is divided into "chunks", the probability of hitting the target increases many times.

That's not how probabilities work. The sum of all probabilities is always the same no matter what way you "split" the possibilities.

I generate two random numbers, convert them to hex, concatenate them and pass them to a modified rotor-cuda so that it can iterate through the remaining 8 values.

That's a very complicated way to waste performance, instead of simply generating a single random number.
Numbers do not "convert to hex", they are numbers. Representations convert.

I never iterate over the full value of 00000000-ffffffff because the likelihood of there being 4 zeros or 4 "f" at the beginning is extremely small.

If in the first chunk we generate a number within 65536**2 (1 00000000 00000000), and not two separate values 0-65535, then the simulation shows that getting into a number within 4 billion is much more difficult than hitting two numbers 0-65535 twice. Mathematics often says the opposite, but i only believe the simulation, which showed me that in this case it is much more likely.

There's zero-proof for your statement. You believe in simulating what? A single observation out of a gazllion choices, each with identical probability?
Statistics work long-term, you can't have a conclusion from a single expected result.
A key with value 0xFFFFFFF....F has exactly the same chances as any other random key. It seems to me you are trying to say that randomness follows some "model", when in fact it's only definition is total impredictibility and any lack of rules or patterns.

Sorry for you addiction.

[kTimesG]

[quote author=kTimesG link=topic=5218972.msg63860000#
I don't need to prove to anyone what i see, but if it helps someone, the logic is simple:

Imagine a slot machine. It has 1 slot with 65536**2 options. One generation = one rotation.
The pseudocode is simple:

A true random source of 65536**2 range values can (and will) spit out a (42, 42, ...) sequence out just as equally likely as (0x7b03aa9f, 0x33bcf51c, ...). If your argument is that it's less likely for same sub-ranges to be part of a combined range, that is correct, but the sum of probabilities for all these cases is in the below 0.00000...01% of the entire count of possibilities - as demonstrated by your huge generated files. So, a lot of convoluted work to exclude a (relatively few) close to zero edge-cases.

[albert0bsd]

Perhaps the author was just joking with everyone and he opened all the wallets himself. Thinking out loud...

People used to said the same for puzzle 120, they said "The autor moved it for himself", in that case why increment 10 times the value of the puzzles again after 120 was solved?

Please keep for yourself that kind of "thinking"

[WanderingPhilospher]

The challenge creator already stated the reasons for the challenge.

Nothing else to say.

One should not spend beyond their means trying to find one of the private keys.

You can’t do that then say all of this is BS or creator is laughing. If anything, they would laugh in comfort, knowing BTC wallets are safe, for now.

[albert0bsd]

I don't see any violation of the forum rules in saying what i think.

And who mention anything about the rules?

All that I am just saying is stop spreading that bullshit.

How many times in the past some users comment "What if puzzle 64 is not in the expected range". Now we known that they just made a fool of themselves (Just saying out loud)

One should not spend beyond their means trying to find one of the private keys.

Exactly

[bogdanrobert]

I am not sure if somebody will solve 13zb1hQbWVsc2S7ZTZnP2G4undNNpdh5so in the current year.

But I wish you good luck  !

Currently I am using Rotor Cuda ... but without any result.
I have no clue about how I can divide the ranges.

[DrShams]

i wonder is it more probable to find a key through random approach or with consecutive trials ?

[holy_ship]

i wonder is it more probable to find a key through random approach or with consecutive trials ?

random mode adds probability to search same range more than once. also keyhunt speed slowly grows, at start it is 4exakeys/sec, after a week it is 6exakeys/sec (maybe it's just wrong counting, not real speed boost)

btw, keyhunt is suitable for puzzle 130?

[satashi_nokamato]

1 exakey per second means 1 and 18 zeros, a 4 GHz CPU could "count" up to a 11 digits number with no EC math involved, just pure counting per second. I would like to know how you can generate 4 exakey/s using keyhunt?

[kTimesG]

1 exakey per second means 1 and 18 zeros, a 4 GHz CPU could "count" up to a 11 digits number with no EC math involved, just pure counting per second. I would like to know how you can generate 4 exakey/s using keyhunt?

If you have a binary tree with 4 billion values, and you search if a specific one is in the tree, it takes at most 32 steps to do so. That means you searched 4 billion keys, but only did 32 CPU "goto next node" operations. So, in a sense, a speed of "4 billion keys / 32 cpu operations". You don't need to go through all of the nodes to know if something is in the tree or not.

Ofcourse, this is really misleading. Such exakeys/s numbers mean nothing in context of how big the parent keyspace really is, it's more like a click bait. You might as well apply the same logic to a pollard kangaroo evolving program and end up with ridiculous speeds as well the more data points you store, but it would not be a speed of group operations anymore, just like it's not for keyhunt.

[albert0bsd]

1 exakey per second means 1 and 18 zeros, a 4 GHz CPU could "count" up to a 11 digits number with no EC math involved, just pure counting per second. I would like to know how you can generate 4 exakey/s using keyhunt?

If you have a binary tree with 4 billion values, and you search if a specific one is in the tree, it takes at most 32 steps to do so. That means you searched 4 billion keys, but only did 32 CPU "goto next node" operations. So, in a sense, a speed of "4 billion keys / 32 cpu operations". You don't need to go through all of the nodes to know if something is in the tree or not.

Ofcourse, this is really misleading. Such exakeys/s numbers mean nothing in context of how big the parent keyspace really is, it's more like a click bait. You might as well apply the same logic to a pollard kangaroo evolving program and end up with ridiculous speeds as well the more data points you store, but it would not be a speed of group operations anymore, just like it's not for keyhunt.

Yeah exakeys is nothing compared with the keyspace that is begin scannig.

I really like the binary tree analogy as example it is good.

With BSGS the important number is the precalculated data in the bloom filter if we have 4 billion keys in a bloom filter we easily can know if the key is not in our bloom filter doing less than 20 hashes. so that means we  discard a subrange of 4 billion keys with only 20 CPU Operations.

https://andrea.corbellini.name/2015/06/08/elliptic-curve-cryptography-breaking-security-and-a-comparison-with-rsa/

[faiyaz_crysp]

I'm currently checking apps that I haven't checked before... and that's how I found PubHunt. I entered the 29 closest unresolved addresses without pubkey in the input... This way I achieve a scan of 6400Gkeys/s . What are the estimates that a pubkeys lookup for 29 addresses with this method and this program at this speed will yield the intended expectations more than a traditional key lookup? What are the real chances of success and effectiveness of this method?

Hi Zielar
Waouhh impressive this speed! If you could choose the beginning and end of the search range, you could find pubkey #66 between 2 and 4 months. On the other hand the search is carried out randomly it makes random hashes on the PK of #64 #66 #67 #68 #69 #71 and #72 it can be faster as well as much longer depending on luck. Too bad this program could be largely optimized like choosing the hash range #66 as well as the random or sequential mode with your speed you could come across #66 in 1 month or 2 depending on luck.

Edit
Looking more closely at the operation of this utility and your speed, the proba are these
in 10 days on all the beaches by inserting the 6 pubkeys (I calculated for the first 6 # not 29)  you have a one in 148 chance of having one of the keys
in 20 days 1/74  1.35%
in 40 days 1/37  2.75%
in 80 days 1/18  5.5%
in 160 days 1/9  11%
in 320 days 1/4  25%
it remains arbitrary because luck can enormously speed up the process

Is there any way to specify the bit range in this program ? I am newbie so any help would be appreciated
Thanks