Bitcoin Forum

Note: Google Translate is used.

My computer has been searching for about a year, and I'm not hopeful.

However, today it occurred to me that the transfer of the person who finds the 64th puzzle may be cancelled.

In other words, after the transfer process starts, the public key will be revealed and thieves who do not deserve it will find the public key within minutes with Kangoroo. Then they will open a double trade with RBF by spending high, the transfer of the person who finds it will be cancelled.

It occurred to me that the thief would figure it out in about 3 minutes.

The average bitcoin transfer confirmation takes 10 minutes and can be canceled without 3 confirmations. (I could be wrong, please correct me.)

How can you get 3 confirmations in 5 minutes in Bitcoin transfer?

In order to spend any bitcoin, you need the private key associated with the address.

It is not trivial to get the private key from the public key, in fact, there is no known way to calculate the private key from the public key. Quantum computing may change this, however, we are still a long way away from a Quantum Computer being able to get the private key from the public key.

It can decode 64 bit range with Kangoroo in a maximum of 5 minutes. In other words, the range and public key are certain, and it is clear in how many minutes it will be resolved. I would be glad if you look at it here.

Yeah probably possible. On the other hand, why would you listen for potentially few years on the nodes with ready to crack hardware to get 1.2 btc to make a potentially successful double spent attack?

if I find the 64th puzzle, I need to try the method that can handle the bitcoin transfer time in 5 minutes.

How much is paid for the transfer, confirmation can be obtained within 5 minutes?

Even though the average time between blocks is around 10 minutes, you can never be certain if your transaction will be mined within that timeframe. Sometimes, no block is found for 30-40 minutes. You can also get lucky and there might be a few blocks mined one after another in a short period of time. As for the fee, 1 sat/vbyte has been enough to get a transaction confirmed quickly for quite some time now. You should check mempool.space (https://mempool.space/) beforehand. It seems to have very accurate estimates.

That's what you get when solving "puzzles", there is always a risk of someone else solving it whether on their own or based on your solution. But if you don't want a transaction to be replaced easily then don't mark it with RBF! and pay the high priority fee.
Spending the same output of a transaction that wasn't marked by RBF would make it a double spend and majority of nodes won't relay the double spend transaction.

Are you sure, 3 min doesn't sound right for 64-bit key.

You don't need 3 confirmations, 1 is enough. More is for protection against 51% attacks which can not happen in bitcoin due to the huge amount of money it requires.

You must be referring to this puzzle (https://bitcointalk.org/index.php?topic=5218972.0). When I previously responded, it was unclear to me that you were not referring to a transaction whose inputs were not being spent by a private key that was generated with 160 bits of entropy. I am not sure your math is correct, but if it is:

If you were to solve one of these puzzles, you can firstly not enable RBF, so nodes should not accept a double-spend transaction by default. This should make it unlikely that a pool will even know about any competing transaction after someone learns of the private key based on the public key. Although someone could have an existing agreement with a miner to allow them to confirm competing/double-spend transactions.

You can avoid the above by contacting a miner directly and asking them to confirm your transaction without having the transaction previously broadcast publicly. There would still be the risk that the miner would calculate the private key and confirm a competing transaction themselves.

Other than the above, you can also obtain sufficient hash power in order to find a block on your own, and you can confirm the transaction without it being publicly broadcasted.

1.2 BTC is currently worth close to $75k. Someone could potentially create a program that listens for a transaction that spends one of a set of outputs, rents a VPS and GPUs on GCS, and executes a script that will find the private key, and create a competing transaction.

I do not know much about this but if people can have agreements with miners for double-spend transactions, that seems "sketchy".

Yeah, this would never happen. They could listen for that output, rent a VPS and GPUs...but they would have to rent 10,000 V100s for 14 hours to solve for the 1.2 BTC...I am sure by then, the transaction would be complete, plus, I am sure renting 10,000 V100s for 14 hours would exceed $75K.

First, you have to know that finding a private key with Kangaroo in range 8000000000000000 to FFFFFFFFFFFFFFFF takes less than 10 seconds with a gpu like RTX 2080ti as I tested.
Replacing a tx in such a situation was also a question for me:
https://bitcointalk.org/index.php?topic=5361673.0

Thank you, now I know 1 confirmation is enough.

There is no miner that I know of and I have no idea how the miner will manually confirm the transaction.

Yes, I'm sure they'll find it in such a short time. They can create RBF in 1 minute in total. Do you have an idea as a solution to this?

Setting highest fee and CPFP fee bumping are the only techniques that you can use to increase your chance.

RBF activation and deactivation option is available in Bitcoin Core.

If I transfer the private key to Bitcoin Core and disable the RBF option from there, will there be a definitive solution if I start the transfer process from there?

There is no guarantee for such transaction that private key will be leaked in less than a minute but you have to disable RBF, set highest fee and pray to God that the tx will be confirmed before any attack.
You haven't found the private key yet, so what are you worried about !?

This thread broke my motivation to keep searching. I'm thinking of pausing the search if there isn't any definitive solution.

The attackers are unlikely to succeed if you make a transaction with the highest fee and non-RBF.
But if you feel you're wasting time and money on the puzzle 64 just ignore it! and focus on the puzzle 120 which you are more likely to find and there is almost no risk of attacking for it.

That's a good question. I guess that there would be many competitors who'd one make a more generous offer to the miners than the other. They could reach paying half the reward to the miner, just to ensure that their transaction will become valid and not the others'.

And I have a feeling there are machines watching the mempool for these keys.

Or even better: Do something productive and stop searching for tricky ways to become richer, which are highly unlikely to succeed while they're costing you much of your time!

Good point. I wonder if anyone has ever done some calculations to see how much money were wasted searching for solutions to this puzzle in total and how much money they could have earned if they mined some cryptocurrency (there are CPU/GPU mineable altcoins).

None of the key crackers I know have the connections to bribe mining pools just to include their own transactions (let alone exclude others).

Where did this value of 1.2 BTC come from? ???

The Puzzle #64 address (https://blockchair.com/bitcoin/address/16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN) only has a balance of 0.64020585 BTC ???

Or is the 1.2 BTC the total value of all the "prizes" that have been claimed so far... and someone is theorising that an attacker may have attempted to setup a monitoring rig to try and steal all the prizes? ???

Doubt. The creator of this puzzle is a very early adopter (if not even satoshi) and he probably has many, many more BTC than this puzzle is worth right now.

I got it from the OP. As are the other metrics mentioned unless stated otherwise.

I haven’t looked at the OPs math.

The Tesla V100 costs about $0.21 per 5 minutes to rent from GCS. I don’t know if google has the capacity, but someone could rent ~357k GPUs for 5 minutes for $75k. I don’t know if this would be sufficient to find the private key. You can rent ~176k for 5 minutes for half that.

If you can figure out how to quickly calculate addresses on a TPU (ASIC that is designed for matrix multiplication), you can rent ~880k TPUs for 5 minutes for $75k. If performing calculations that TPUs are optimized for, the efficiency of a TPU is at least a factor of 10 more efficient than a GPU. Although I don’t know if google will allow you to scale that many TPUs.

Given that the private key range is known for each puzzle, I am not sure I understand the advantage that someone will have once the public key is known.

For Pollard's Kangaroo, you need to know the public key that you're trying to match.

OP was theorising that once they publish their transaction, someone could use Pollard's Kangaroo to trivially solve the private key in a matter of minutes and then publish their own transaction stealing their prize.

I'm not overly familiar with the performance of this particular algorithm or the available scripts for it... but if the actual winner just disables RBF and sends with a "decent" fee, the odds of their prize being "stolen" would be pretty minimal, I would think.

It was reported (https://bitcointalk.org/index.php?topic=1306983.msg51848002#msg51848002) that one Tesla V100 can check 715 M keys per second by using bitcrack. Assuming you can get google to rent you 176k V100's, I calculate a 1 in 488 chance that you will find the private key within 5 minutes. It was reported on that same post that a V100 can make 1430 Million "kangaroo jumps" per second (about 2x as many private keys tas than it can check using bitcrack). Assuming that the scope of what needs to be searched is the same, this would give someone a 1 in 244 chance of finding the private key within 5 minutes.

I am not sure how many V100 google has on its platform but 176k is a lot, but I calculate that many V100s as having a retail price of about $1.1 billion. If you spend more than 5 minutes trying to crack the private key, you will be spending more money than the value of the coin in the address.

I hope this is an accurate calculation, crossword 64 and above will also minimize the suspicion that there will be a thief.

You have to know how kangaroo program works. A single V100 can solve a 64 bit key using kangaroo in mere seconds. One cannot use kangaroo to crack #64 now because the pub key is not known. But once someone broadcasts to transfer the BTC from #64's address, the pub key will be exposed and someone can use a single GPU to solve for the private key in seconds. That is what the OP is saying. As others have stated, using the RBF with decent fee, will help from others "stealing" #64s key.

Do you have a reference for saying that a single V100 can solve a 64 bit (of entropy) key in seconds?

If what you are saying is true, it would be advisable to not use RBF. The RBF would need to be set to False and a decent fee that is sufficient to be included in the next block should be used.

I looked at some of the documentation for kangaroo, but have not looked at the math closely.

Right, however the RBF works, you want to make sure that you tell it to not replace by higher fee.

As for the performance, here is a quick run of a 64 bit key using a much slower GTX 1060 6GB card:


A V100 is at least 10x faster than the 1060 used in this test.

The new BSGS Cuda program can complete a 64 bit range using a RTX 3090 in 1-2 seconds as well.

---

The 1.2 BTC value came from the 120 bit challenge in this overall challenge. There is BTC in each range, from 1 bit to 160 bits. Every 5th range, 5, 10, 15, 20, ..., 100, 105, 110, 115, 120, etc., has the public key exposed, which allows for the use of programs such as BSGS or Kangaroo.

More info here:
https://bitcointalk.org/index.php?topic=5218972.0 (https://bitcointalk.org/index.php?topic=5218972.0)

Thanks for that.

Do you have any resources that explain how kangaroo works? I was able to find some papers that discuss the math regarding optimizing the kangaroo method, but not anything that explains how it works in a way I can understand.

Probably more importantly, do you have a formula that would allow someone to predict how long it should take to calculate a private key with a given number of bits of entropy? For example, going from 64 bits of entropy to 65 bits of entropy means there is 2x the number of potential private keys, would you expect to take approximately 2x the time to find a 65 bit private key as it took you to find a 64 bit key? I have read comments that the checksum may result in false positives when using kangaroo.

A good resource is JLPs github kangaroo page:
https://github.com/JeanLucPons/Kangaroo (https://github.com/JeanLucPons/Kangaroo)

and if you want a deep dive, check out the BTC topic here:

https://bitcointalk.org/index.php?topic=5244940.0 (https://bitcointalk.org/index.php?topic=5244940.0)

Just as a test I ran Kangaroo using CPU only... (6 core, 12 threads Ryzen 5 3600)... It solved the #63 puzzle in 2:40
https://talkimg.com/images/2023/11/14/zz4yD.png


Using just the GTX1080, Kangaroo solved it in 26s. :o :o :o
https://talkimg.com/images/2023/11/14/zz5bf.png


Obviously the #64 puzzle is significantly larger than #63... but then I tried the #65 puzzle (which is even larger) and the GTX1080 solved that in only 1:34
https://talkimg.com/images/2023/11/14/zz9SZ.png


Having such a small range, and the pubkey really does make cracking these private keys very trivial.