Bitcoin puzzle transaction ~32 BTC prize to who solves it

[Akito S. M. Hosana]

Well, well, I have disregarded the mathematical principles.

Code:

import random
import time

# Parameters
start = 1
end = 100000  # Reduced range for better chance of finding matches
num_people = 23
g = 2  # Base for the kangaroo jumps
p = 1000000007  # Large prime modulus

# Function for generating random jumps (analogous to a hash function)
def f(x, k):
    return random.randint(1, k)

# Pollard's Kangaroo-like method for matching birthdays
def kangaroo_match(birthdays, start, end):
    a = start
    b = end
    N = len(birthdays)
    k = 10  # Upper bound on the step/jump size

    # Tame kangaroo setup
    x_tame = 0
    y_tame = birthdays[0]  # Start with the first birthday as the tame kangaroo
    visited = {y_tame}  # Track visited positions

    for _ in range(N):
        # Make a jump with the tame kangaroo
        x_tame += f(y_tame, k)
        y_tame = (y_tame + random.randint(1, 10)) % end  # Jump in a reduced range
        visited.add(y_tame)

        # Check if we have a match
        if y_tame in birthdays:
            print(f"Match found by tame kangaroo at: {y_tame}")
            return y_tame

    # Wild kangaroo setup
    x_wild = 0
    y_wild = random.randint(start, end)  # Start wild kangaroo with a random position

    start_time = time.time()

    # Searching for a match
    while x_wild < b - a + x_tame:
        # Make a jump with the wild kangaroo
        x_wild += f(y_wild, k)
        y_wild = (y_wild + random.randint(1, 10)) % end  # Jump in a reduced range

        if y_wild in visited:
            print(f"Match found by wild kangaroo at: {y_wild}")
            end_time = time.time()
            print(f"Execution time: {end_time - start_time} seconds")
            return y_wild

    end_time = time.time()
    print(f"Execution time: {end_time - start_time} seconds")
    print("No match found.")
    return None

# Challenge function to test the search
def challenge():
    # Generate random birthdays
    birthdays = [random.randint(start, end) for _ in range(num_people)]
    print("Generated birthdays:", birthdays)

    # Run kangaroo match
    match = kangaroo_match(birthdays, start, end)
    if match:
        print(f"[+] Secret match found: {match}")
    else:
        print("[-] The kangaroos came back empty-handed...")

# Run the challenge
challenge()

[WanderingPhilospher]

A further note for everyone, unless something drastically improves with being able to use a public key, such as BSGS, Kangaroo, etc., the 67, 68, and 69 wallets, are all easier reached (time wise) now versus 135.

The lower puzzles are now very risky ... Even if someone manages to crack one of them still they could be easily stolen.

It's better not to find a solution than get it and then being robbed right away.

I gave a step by step on how to safely transfer the lower bit wallets.

IF I find one, and IF that service is still around then, I would hit submit and sleep like a baby.

[nomachine]

A further note for everyone, unless something drastically improves with being able to use a public key, such as BSGS, Kangaroo, etc., the 67, 68, and 69 wallets, are all easier reached (time wise) now versus 135.

The lower puzzles are now very risky ... Even if someone manages to crack one of them still they could be easily stolen.

It's better not to find a solution than get it and then being robbed right away.

It's already been written how by @WanderingPhilospher. The only reliable way to safeguard against such threats is to use the MARA Slipstream Service, which adds an extra layer of security. I will go for this service without much thought if I hit something. I have no other choice, and if I do have one, the risk is greater than this.

[ssb883]

A further note for everyone, unless something drastically improves with being able to use a public key, such as BSGS, Kangaroo, etc., the 67, 68, and 69 wallets, are all easier reached (time wise) now versus 135.

The lower puzzles are now very risky ... Even if someone manages to crack one of them still they could be easily stolen.

It's better not to find a solution than get it and then being robbed right away.

Hello. I just found out about this puzzle.

If the funds are to be transferred to a different wallet, can you or anyone else explain in layman's how can they be stolen?

[Shelby0901]

Hello Shelby,

I have some ideas and tools that could help us collaborate to solve the puzzle. Puzzle 67 is smaller and easier than 135. I've coded a tool that can split the 67-bit space into 900 parts, allowing you to run 900 processes simultaneously, each working on a different part using keyhunt-cuda.

Let me know if you're interested in working together!

DM me.

Hey! Tried DM ing you and this is what I get "User 'b0dre' has not chosen to allow messages from newbies. You should post in their relevant thread to remind them to enable this setting"

[Shelby0901]

What about 135 puzzle? I have managed to reduce 135 bits down to 120 bits how long would it take?.

Why did you stop the reducing at 120 bits? I'd go full-blown to 1 bit. Let us know if it's a zero or not.

The possible public keys exponentially grow.. By the time i reduce 3 digits from the end if have 1 trillion plus possible public keys

Really? That's a lot of keys. So let me formulate the question another way: once you reduce 135 to 120 bits, is that equivalent or not to having 32768 public keys, of which one of them corresponds to a 120-bit key, while the rest of 32767 correspond to 256-bit keys?

If so, how do you pick the one public key to search for, to have a good reason of calling this as a "reduction" and not an "expansion"?

I really want someone to work with..

Ask @kTimesG for that. He has the software, and you have the hardware. Good luck!

Using 900 RTX 4090, it will take 583 days to break 135, using my software (~ 5.6 Gk/s on a single 4090). It was worth it for 130, but 135, not so much, costs are higher than the reward. We need either much higher computing power, or some advancements in EC math (some fast parallel XGCD would help, since this is the current bottleneck - all threads except one are idle, waiting for a batched inversion to finish). Doing multiple XGCD in parallel (like what JLP version does) is actually a lot slower than doing one "master" batched inversion. Ehm...

@kTimesG
How did you come up with total number of ops at 2^67.783 ?? That is an odd number that I have not seen before. Interesting.

For @Shelby0901, you need to do the math first, and see where you come out ahead, if you have access to x amount of hardware for y amount of hours.

With my Kangaroo, it does 7.5 BK/s on a single RTX 4090, an RTX 3090 gets 5.6 BK/s. Decent speed, but let's not get caught up in Kangaroo, solely.

Instead, we have to look at the lowest 2 challenges / wallets, 67 and 135, which boil down to 66 bits and 134 bits. Now we can look at speeds for programs, brute force and Kangaroo, using the RTX 4090 as the "standard", or for the fact that is what you will have access to.

With my Kangaroo program, it would take roughly 500 days to solve the 135 wallet, with 900 RTX 4090s.
My brute force program averages about 5.1 BK/s with a single 4090. The first average to find the key is around 50% (68% is the next average, if not found by 50%~) of overall keys, so around 2^65 keys checked to find the private key for 67. Let's do the math...93 days to first average of finding the 67 wallet, using 900 RTX 4090s.

So, a 12 hour use of those 900 x RTX 4090s, would get you closer to solving 67 versus 135, IMO.

But, either way you go, you need to plan ahead and think about items such as:
cracking program to use
server
client
how you will load the client and cracking program on all of those machines and hit "start"; will you have access to be able to SSH into each machine?

Pre-plan as much as you can, because you don't want your 12 hours to start and then have to jump through hoops to get them all connected and running.

I wish you luck! And that goes for everybody still seeking these wallets.
A further note for everyone, unless something drastically improves with being able to use a public key, such as BSGS, Kangaroo, etc., the 67, 68, and 69 wallets, are all easier reached (time wise) now versus 135.

Hey can DM

[kTimesG]

How did you come up with total number of ops at 2^67.783 ?? That is an odd number that I have not seen before. Interesting.

1.72 * sqrt(2**134) = 2^67.78

I did not include the DP overhead, because it depends on a lot of factors.

For all the haters and frustrated multiple-account-owners pretending I'm Digaran and that I have multiple accounts and so on (even though any mod can confirm the contrary): get a life.

Also, as I stated a lot of times, there are so many ways to improve on efficiency than what is already out there publicly, that only a limited mind can think there's nothing to drastically improve on.

Here's a basic kicker: JLP doesn't use the 3-kangaroo method. So there's 15% increase in efficiency basically for free just by implementing this detail alone. But guys still attack that check.cpp shows some fake speed., and hence the entire algo is broken. Nevermind the absurdidities around "birthday paradox". I'll grab my popcorn and be silent whenever I read again such a wonderful exposition like the earlier one.

Here's another kicker: Kangaroo doesn't rely on the birthday paradox. That would be Gaudry-Schost. Seriously, it is stated in the paper itself that this is the difference between Kangaroo and that one, they have totally different analysis methods. But what can I ask from someone who doesn't understand the principles, and copy pastes whatever bogus shit ChatGPT spills out? Do they think I can't tell the style of GPT output, while they accuse me of using it? Ugly as hell.

In other news, congrats if you really do have 8+ Gk/s on a single 4090. You must have really found some method to speed up the CUDA code, I have some hunches you used Montgomery or something to achieve this. I feel that there still a lot of juice left to squeeze out of those teraflops, but it's not exactly like spinning a magic circle, when we also have a job or life to attend to.

[AlanJohnson]

A further note for everyone, unless something drastically improves with being able to use a public key, such as BSGS, Kangaroo, etc., the 67, 68, and 69 wallets, are all easier reached (time wise) now versus 135.

The lower puzzles are now very risky ... Even if someone manages to crack one of them still they could be easily stolen.

It's better not to find a solution than get it and then being robbed right away.

Hello. I just found out about this puzzle.

If the funds are to be transferred to a different wallet, can you or anyone else explain in layman's how can they be stolen?

Very easy... Confirming a tx on btc blockchain takes some time to process (sometimes quite long time).
Sending btc from address exposes  their public key. Normally it's not a problem - but with artifically reduced private keys to lower bit range (like 67 bit) it's a matter of seconds to crack the private key from the exposed public key (with kangaroo or BSGS method)

Cracking the private key gives the attacker the opportunity to use RBF (replace by fee) to redirect the transaction to another address.

Nobody know how many bots constantly monitoring mempool and waiting to one of those public keys show up - then they will start to crack the private keys and use RBF to steal btc (some of them probably can constantly monitoring even the replaced transaction to replace it again with higher fee in case other bot is trying to steal it to --- that all leads to some sort of bot wars).

So if you somehow manage to crack the puzzle with low bit range think twice before moving it cause for sure someone will try to steal it from you. If you simply transfer it  they will be stolen for 100% and all your effort will bring you nothing but frustration...  Puzzle 66 was already stole (at least it looks so).

 

[RetiredCoder]

Here's another kicker: Kangaroo doesn't rely on the birthday paradox. That would be Gaudry-Schost.

Correct.
But in practice, nobody implements original kangaroo with only few kangs. Practical implementation always contains a lot of kangs with random start points and they don't go far, so it's exact or similar to Gaudry-Schost and it does use birthday paradox.

[mcdouglasx]

Here's another kicker: Kangaroo doesn't rely on the birthday paradox. That would be Gaudry-Schost.

Correct.
But in practice, nobody implements original kangaroo with only few kangs. Practical implementation always contains a lot of kangs with random start points and they don't go far, so it's exact or similar to Gaudry-Schost and it does use birthday paradox.

https://github.com/JeanLucPons/Kangaroo?tab=readme-ov-file#how-it-works

"Due to the birthday paradox, a collision happens (in average) after 2.08*sqrt(k2-k1)"

You can make up whatever you want, but without the Kangaroo birthday paradox or any other implementation, they'll just be pretty paperweights.

[mcdouglasx]

but it's not exactly like spinning a magic circle, when we also have a job or life to attend to.

Excellent! 
I think now it's time for some magic circles, don't hesitate!

multi user detected, try harder.

[RetiredCoder]

https://github.com/JeanLucPons/Kangaroo?tab=readme-ov-file#how-it-works

JLP did a great job by making his work open-source.
Though when I see K=2.08, or 3-4GH on 4090, or his code, or that annoying bug with displayed speed higher than real speed, problems with handling large db, etc... Yeah, it definitely looks like free open source  
Anyway, it's a great start point.

[kTimesG]

but it's not exactly like spinning a magic circle, when we also have a job or life to attend to.

Excellent! 
I think now it's time for some magic circles, don't hesitate!

multi user detected, try harder.

Are you not tired of this yet? Let me help you. I am @RetiredCoder, you catched me again. I am also the guy with the magic circle that everyone (except you) seems to know about. Oh and I'm also @mcdouglasx, just to annoy everyone who reads this. I'm also your mom, please come downstairs, your school lunchbox is ready.

Here's another kicker: Kangaroo doesn't rely on the birthday paradox. That would be Gaudry-Schost.

Correct.
But in practice, nobody implements original kangaroo with only few kangs. Practical implementation always contains a lot of kangs with random start points and they don't go far, so it's exact or similar to Gaudry-Schost and it does use birthday paradox.

There isn't a single paper that says to use random starting points when we have multiple kangaroos per herd; on the contrary, they start from well-defined positions. To use random start points is an arbitrary decision: first of all, on average, it degrades the expected runtime; second, it's used for spin-off strategies, like in Bernstein's pre-computation paper "Computing discrete logs faster".

It's debatable if walking forward and hitting a collision is the same as the birthday paradox, which requires all the balls are in the same urn. The common factor is conceptual only: probability of success.

https://github.com/JeanLucPons/Kangaroo?tab=readme-ov-file#how-it-works

"Due to the birthday paradox, a collision happens (in average) after 2.08*sqrt(k2-k1)"

You can make up whatever you want, but without the Kangaroo birthday paradox or any other implementation, they'll just be pretty paperweights.

That statement, just like JLP's entire kangaroo implementation in general, is not reviewed or confirmed by any real expert, and it might be a very contextual statement relative to his implementation and personal opinions at that time, influenced by whatever he was reading or thinking. Also, I don't understand, now you defend Kangaroo or what are you doing?

[3dmlib]

But, either way you go, you need to plan ahead and think about items such as:
cracking program to use
server
client
how you will load the client and cracking program on all of those machines and hit "start"; will you have access to be able to SSH into each machine?

ttdpool and ttdclient already have this. Fastest client, secure server and startup scripts.

[RetiredCoder]

There isn't a single paper that says to use random starting points when we have multiple kangaroos per herd; on the contrary, they start from well-defined positions. To use random start points is an arbitrary decision: first of all, on average, it degrades the expected runtime; second, it's used for spin-off strategies, like in Bernstein's pre-computation paper "Computing discrete logs faster".

Well, papers are about theory mostly.
Again, in practical implementation you have to use random start points because you don't know exact number of GPUs you will use during solving (because it's a long process and some GPUs can be turned on and off, or added/removed), also sometimes some GPUs will start new kangs.

[mcdouglasx]

That statement, just like JLP's entire kangaroo implementation in general, is not reviewed or confirmed by any real expert, and it might be a very contextual statement relative to his implementation and personal opinions at that time, influenced by whatever he was reading or thinking. Also, I don't understand, now you defend Kangaroo or what are you doing?

I have never been against kangaroo, it's just that it's already reached its useful life, that's what I'm saying, there's no way to speed it up if it's not with more computing power,
the rest is smoke.
It's not me saying it, it's what the math says, and you'll say I see that it solves bits 80 faster, yes I know it seems coherent to reach your conclusion, however you made it less efficient in terms of the probability of collisions.
and that's why bit 135 will not be found with this.

To whom it may be interested in testing the following, don't believe me, just do it yourself.
try the modified kangaroo in a bit that takes you 2 hour to decipher.
then replicate it with the original kangaroo (slower) and you'll see that it solves it in less time.

[WanderingPhilospher]

But, either way you go, you need to plan ahead and think about items such as:
cracking program to use
server
client
how you will load the client and cracking program on all of those machines and hit "start"; will you have access to be able to SSH into each machine?

ttdpool and ttdclient already have this. Fastest client, secure server and startup scripts.

You have lost your mind coming on this forum and spreading lies lol. Just stop.

Yeah, TTD is the fastest in skipping keys, generating wrong private keys, and losing your money. Yes, I agree, it is the fastest in those things. So please don't come on here trying to advertise for them and spread half truths.

I know, the owner does not take testing seriously at all, I've got receipts, so don't come at me with some BS.

To whom it may be interested in testing the following, don't believe me, just do it yourself.
try the modified kangaroo in a bit that takes you 2 hour to decipher.
then replicate it with the original kangaroo (slower) and you'll see that it solves it in less time.

This actually makes no sense. The modified kangaroo programs out there that increased the search range to 254/256 bits, did not do anything to increase speed / efficiency. Unless you have ran both and extracted the data in the workfiles, do not comment on it and spread false info.
I have not seen one modified JLP program, for increased bit range search size, that had speed increases. All they did was make the workfiles, double the size. Instead of only increasing the distance entries, they increased the points and distance entries; so now the workfiles are double the size.
You can run all of your tests you want to, but math is math, it doesn't lie. If I have a kangaroo program that is 3 times faster than yours, I will find the number of average DPs needed to solve, 3 times faster than yours. Efficiency does not equate to being able to search higher bit ranges, you dig?

[mcdouglasx]

This actually makes no sense. The modified kangaroo programs out there that increased the search range to 254/256 bits, did not do anything to increase speed / efficiency. Unless you have ran both and extracted the data in the workfiles, do not comment on it and spread false info.
I have not seen one modified JLP program, for increased bit range search size, that had speed increases. All they did was make the workfiles, double the size. Instead of only increasing the distance entries, they increased the points and distance entries; so now the workfiles are double the size.
You can run all of your tests you want to, but math is math, it doesn't lie. If I have a kangaroo program that is 3 times faster than yours, I will find the number of average DPs needed to solve, 3 times faster than yours. Efficiency does not equate to being able to search higher bit ranges, you dig?

That's what I preach, you can't mess with the birthday paradox without losing efficiency, if your software doesn't do this right for you, at least you're not looking for a fish in the sky. My comments are directed towards @ktimesg's crazy proposals. If you read the context you'll understand.
In fact, it is wrong to increase the jumps, you only lose efficiency, it is an exact science, I demonstrate it in my previous script.

[kTimesG]

That's what I preach, you can't mess with the birthday paradox without losing efficiency, if your software doesn't do this right for you, at least you're not looking for a fish in the sky. My comments are directed towards @ktimesg's crazy proposals. If you read the context you'll understand.
In fact, it is wrong to increase the jumps, you only lose efficiency, it is an exact science, I demonstrate it in my previous script.

What do you understand by "efficiency"? It's not the same thing as "speed" or "complexity", rather a more overall indicator that accounts for a multitude of factors, of which one is the practical techniques that are being used; another one is what problem you are trying to solve.

Why is it wrong to increase the jump (I guess you meant average jump size)? You're pretty much dismissing all existing research with this statement, and the math looks pretty legit IMHO (with well defined proofs for why it's optimal to use a specific average jump size to minimize the expected number of operations, etc.). By your (assumed) logic, and continuing it in reverse, we should basically run a brute-force search, one point after the other, right? So as not to mess with the damn birthday paradox, losing efficiency... am I wrong? But the joke's on you: messing around with the way you intend to use some theory, only ends up to decrease the efficiency. If you want better "birthday paradox" results, then you lose efficiency, because you do more operations. It does not matter the way you split the interval, or whether you make the jump sizes smaller or larger, or if you increase the DP to abnormal magnitude, or if you decide to go with storing trillions of points in the cloud, or if you decide to randomize starting points instead of having a central database of working state, the end result is the same: sub-optimal. And this is an objective measurable metric, not some personal opinion.

Maybe, enlighten us about your exact science. Let's talk theory, not "you'll never find 135 using this or that", this is not the main point here anymore. Let's have some fun on the realm of exact science!

[Woz2000]

TTD #1 for 64, TTD #1 for 66, yet 'someone else' has found the key both times. Have you ever wondered why?
Fastest client? How?
Secure Server? Has it been audited?
Startup scripts. Nice!

But, either way you go, you need to plan ahead and think about items such as:
cracking program to use
server
client
how you will load the client and cracking program on all of those machines and hit "start"; will you have access to be able to SSH into each machine?

ttdpool and ttdclient already have this. Fastest client, secure server and startup scripts.