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

HCP

legendary

Activity: 2086

Merit: 4314

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

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.

WanderingPhilospher

full member

Activity: 1050

Merit: 219

Shooters Shoot...

Quote

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://bitcointalksearch.org/topic/pollards-kangaroo-ecdlp-solver-5244940

PrimeNumber7

copper member

Activity: 1624

Merit: 1899

Amazon Prime Member #7

Quote from: ?? on ??

Quote from: PrimeNumber7 on October 31, 2021, 01:18:09 PM

Quote from: WanderingPhilospher on October 31, 2021, 01:02:54 PM

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

full member

Activity: 1050

Merit: 219

Shooters Shoot...

Quote from: PrimeNumber7 on October 31, 2021, 01:18:09 PM

Quote from: WanderingPhilospher on October 31, 2021, 01:02:54 PM

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.

Quote

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://bitcointalksearch.org/topic/bitcoin-challenge-transaction-1000-btc-total-bounty-to-solvers-updated-5218972

PrimeNumber7

copper member

Activity: 1624

Merit: 1899

Amazon Prime Member #7

Quote from: WanderingPhilospher on October 31, 2021, 01:02:54 PM

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

full member

Activity: 1050

Merit: 219

Shooters Shoot...

Quote from: PrimeNumber7 on October 31, 2021, 07:05:00 AM

Quote from: HCP on October 31, 2021, 03:50:42 AM

Quote from: PrimeNumber7 on October 30, 2021, 11:04:44 PM

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.

CoinMagus

newbie

Activity: 16

Merit: 1

Quote from: PrimeNumber7 on October 31, 2021, 07:05:00 AM

Quote from: HCP on October 31, 2021, 03:50:42 AM

Quote from: PrimeNumber7 on October 30, 2021, 11:04:44 PM

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.

PrimeNumber7

copper member

Activity: 1624

Merit: 1899

Amazon Prime Member #7

Quote from: HCP on October 31, 2021, 03:50:42 AM

Quote from: PrimeNumber7 on October 30, 2021, 11:04:44 PM

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.

HCP

legendary

Activity: 2086

Merit: 4314

Quote from: PrimeNumber7 on October 30, 2021, 11:04:44 PM

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

copper member

Activity: 1624

Merit: 1899

Amazon Prime Member #7

Quote from: HCP on October 29, 2021, 07:18:25 PM

Quote from: a.a on October 24, 2021, 03:40:45 PM

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?

Quote from: PrimeNumber7 on October 25, 2021, 12:54:12 AM

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? Huh

The Puzzle #64 address only has a balance of 0.64020585 BTC Huh

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? Huh

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.

superkatchu

newbie

Activity: 5

Merit: 2

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.

HCP

legendary

Activity: 2086

Merit: 4314

Quote from: a.a on October 24, 2021, 03:40:45 PM

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?

Quote from: PrimeNumber7 on October 25, 2021, 12:54:12 AM

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? Huh

The Puzzle #64 address only has a balance of 0.64020585 BTC Huh

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? Huh

NotATether

legendary

Activity: 1568

Merit: 6660

bitcoincleanup.com / bitmixlist.org

Quote from: BlackHatCoiner on October 25, 2021, 03:08:20 PM

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

pooya87

legendary

Activity: 3444

Merit: 10558

Quote from: BlackHatCoiner on October 25, 2021, 03:08:20 PM

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

BlackHatCoiner

legendary

Activity: 1512

Merit: 7340

Farewell, Leo

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.

Quote from: davidjjones on October 25, 2021, 11:41:59 AM

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.

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!

davidjjones

newbie

Activity: 25

Merit: 14

Quote

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.

Stroncow

jr. member

Activity: 38

Merit: 13

Quote from: davidjjones on October 25, 2021, 10:26:33 AM

Quote

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.

davidjjones

newbie

Activity: 25

Merit: 14

Quote

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 !?

Stroncow

jr. member

Activity: 38

Merit: 13

Quote from: davidjjones on October 25, 2021, 05:18:58 AM

Quote

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?

davidjjones

newbie

Activity: 25

Merit: 14

Quote

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.

Topic: 64. Can the Transfer of the Inventor of the Puzzle Be Manipulated? (Read 490 times)