64. Can the Transfer of the Inventor of the Puzzle Be Manipulated?

[NotATether]

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'.

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

[1715517624]

1715517624

[1715517624]

1715517624

[HCP]

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?

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.

Where did this value of 1.2 BTC come from?

The Puzzle #64 address 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?

[superkatchu]

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.

[PrimeNumber7]

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?

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.

Where did this value of 1.2 BTC come from?

The Puzzle #64 address 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?

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.

[HCP]

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.

[PrimeNumber7]

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 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.

[CoinMagus]

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 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.

[WanderingPhilospher]

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 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.

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.

[PrimeNumber7]

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.

[WanderingPhilospher]

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:

Code:

Kangaroo v2.1
Start:8000000000000000
Stop :FFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^63
Jump Avg distance: 2^30.98
Number of kangaroos: 2^19.32
Suggested DP: 9
Expected operations: 2^32.86
Expected RAM: 84.5MB
DP size: 12 [0xFFF0000000000000]
GPU: GPU #0 NVIDIA GeForce GTX 1060 6GB (10x128 cores) Grid(20x256) (57.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^19.32 kangaroos [4.5s]
[210.13 MK/s][GPU 210.13 MK/s][Count 2^30.96][Dead 0][12s (Avg 37s)][64.1/98.2MB]
Key# 0 [1S]Pub:  0x0311CEF632C14F4EF26CB1CE5D79B28E2988DC108F44EE0CDF9E6E6EFC7231C72C
       Priv: 0x9CCE5EFDACCF6808

Done: Total time 18s

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.

Where did this value of 1.2 BTC come from?

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

[PrimeNumber7]

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:

Code:

Kangaroo v2.1
Start:8000000000000000
Stop :FFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^63
Jump Avg distance: 2^30.98
Number of kangaroos: 2^19.32
Suggested DP: 9
Expected operations: 2^32.86
Expected RAM: 84.5MB
DP size: 12 [0xFFF0000000000000]
GPU: GPU #0 NVIDIA GeForce GTX 1060 6GB (10x128 cores) Grid(20x256) (57.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^19.32 kangaroos [4.5s]
[210.13 MK/s][GPU 210.13 MK/s][Count 2^30.96][Dead 0][12s (Avg 37s)][64.1/98.2MB]
Key# 0 [1S]Pub:  0x0311CEF632C14F4EF26CB1CE5D79B28E2988DC108F44EE0CDF9E6E6EFC7231C72C
       Priv: 0x9CCE5EFDACCF6808

Done: Total time 18s

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.

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.

[WanderingPhilospher]

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

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

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

[HCP]

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



Using just the GTX1080, Kangaroo solved it in 26s.



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



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