11 ms·

Discussion thread here: https://bitcointalk.org/index.php?topic=1306983.msg64526037#msg64526037 https://bitcointalk.org/index.php?topic=1306983.msg64526037#...

by mrb 2y ago

Discussion thread here: https://bitcointalk.org/index.php?topic=1306983.msg64526037#msg64526037 https://bitcointalk.org/index.php?topic=1306983.msg64526037#... Bitcoin puzzles are private keys with just a few unknown bits so that anyone can bruteforce them to collect a reward. Puzzle 66 contained 66 unknown bits and had 6.6 BTC deposited into it by the initial puzzle creator. The private key was 0x000000000000000000000000000000000000000000000002832ed74f2b5e35ee or 256 bits with mostly zeroes but 66 random ones. The next Bitcoin puzzle, #67, has 67 unknown bits, and contains 6.7 BTC up for grabs: https://www.blockchain.com/explorer/addresses/btc/1BY8GQbnueYofwSuFAT3USAhGjPrkxDdW9 https://www.blockchain.com/explorer/addresses/btc/1BY8GQbnue... The previous puzzle by order of difficulty was #64 (not #65, because see below) and was solved on 9/9/2022, so about 2 years ago. In other words, it took about 2 years of compute time to run the 2^66 bruteforcing task. Puzzles that are multiple of 5 (#65 or #70) are special: they have twice more entropy. So that private key #65 doesn't have 65-bit of entropy but 130-bit of entropy. And the creator of the puzzle intentionally published their public key on the blockchain. When you know the public key, brutetforcing the n-bit private key only requires 2^(n/2) work. So puzzle #65 with a 130-bit key actually require bruteforcing up to only 2^65 keys.

wslh 2y ago
New to this puzzle! Do you have a more detailed resource to the puzzle? Is it basically brute forcing based on all public keys available on the Bitcoin blockchain? Could this be considered stealing?
- mrb 2y ago
  Sure, here is a nice little presentation on the puzzle: https://rya.nc/forensic-bitcoin-cracking.html https://rya.nc/forensic-bitcoin-cracking.html The main discussion thread on the bitcoin forum is this but it has a low signal-to-noise ratio: https://bitcointalk.org/index.php?topic=1306983.0 https://bitcointalk.org/index.php?topic=1306983.0 There is a secondary thread here: https://bitcointalk.org/index.php?topic=5218972.0 https://bitcointalk.org/index.php?topic=5218972.0 The point of the puzzle is indeed to brute force some private keys (not public keys), but not all, as 2^256 is computationally impossible. The private keys that have been discovered so far have obviously many zeros in them, so in practice you are never going to accidentally steal from a legitimate address with actually 256 bits of entropy. The creator of the puzzle is anonymous and never came forward (to my knowledge). The point of the puzzle is (1) to be a fun game, and (2) to be a publicly observable way of measuring current brute forcing capabilities.
  - wslh 2y ago
    First, a question: is there something similar for other blockchains? And, a clarification, when I said public keys I referred to public keys that match an unknown private key but I understand now (am I correct?) that this puzzle is purely brute forcing private keys with a lot of zeroes and then matching with the addresses in the blockchain (which would be a function from the public key).
    - mrb 2y ago
      I don't know if other blockchains have these puzzles. You are correct thas this puzzle is brute forcing private keys with a bunch of zeroes, from which a public key can be calculated.
    - thisconnect 2y ago
      Other bc's are centralized and don't need it as they can just revert or change their state.
ForHackernews 2y ago
Is this a "puzzle"? Throwing compute at brute-forcing a random number doesn't seem like solving a puzzle to me, it's basically how bitcoin works.
- aeturnum 2y ago
  I think the puzzle idea is that, if you could figure out a weakness in the hash, you could claim it faster than the brute force approach. So each prize that's claimed "on schedule" supports the idea that there aren't any widely known shortcuts. Obviously if you found a shortcut in the hash you might do other things first, but I think that's the idea.
  - IshKebab 2y ago
    Hmm yeah if I cracked Bitcoin then last thing I'd do is claim a prize that gave away the fact that I'd cracked Bitcoin.
    - mr_mitm 2y ago
      There is a difference between a weakness and complete breakage. You might have a small edge over brute force, but not enough to reverse any public key. This acts like a canary for weaknesses.
    - dylan604 2y ago
      some people just want the cred though. their name will be immortal and live through history as being something, or some such nonsense that feeds an ego. also, if you were the type that thinks bitcoin is lame, this could be a way of undermining the concept to the point that people no longer use it because it's not secure as it was touted
    - throwawaymaths 2y ago
      What you would do is claim the prize slightly ahead of schedule and wait to be slightly ahead of schedule for the next one.
    - 2y ago
deleted 2y ago
[deleted]
Sandworm5639 2y ago
Is it known who set it up and for what purpose?
n2d4 2y ago
For those curious, the reason why a public key lets you find a private key more efficiently is Pollard's rho algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_...
- CamperBob2 2y ago
  These keys are based on elliptic curves rather than products of primes, aren't they?
  - matthewdgreen 2y ago
    There is one rho algorithm for discrete logarithms and one for factoring. Published three years apart.
    - sltkr 2y ago
      Neither of which helps with elliptic curve cryptography.
      - arcastroe 2y ago
        the problem of finding discrete logarithms is the same problem as breaking elliptic curve cryptography.
        GTP 2y ago
        Technically, while the two problems share the same name, the one on elliptic curves is matematically different from the one over finite fields modulo a prime number.
        deleted 2y ago
        [deleted]
        AnotherGoodName 2y ago
mapt 2y ago
Am I correct in assuming that beyond a certain point, this is basically an existence proof for somebody having a quantum-supreme solution to Shor's Algorithm? "Here's $400,000 sitting on the table, hope nobody takes it" which triggers an alarm telling us to replace all our old prequantum cryptography.
- n2d4 2y ago
  Or someone "just" finding a fault in the cryptographic algorithms used in Bitcoin. Or whoever created the puzzles leaking their information.
  - sigmoid10 2y ago
    >Or whoever created the puzzles leaking their information. Or getting hacked. This is super common among people who are known to have high value wallets. Between physical attacks and zero days in everyday software, there's no chance to stay safe when you put that kind of target on your back.
    - owl57 2y ago
      Is it likely that these particular private keys were wiped ~immediately after creation?
    - Powdering7082 2y ago
      > there's no chance to stay safe when you put that kind of target on your back. Vitalik Buterin seems to be a counter example here, his net worth peaked around $1.46 billion. He has some interesting writing on how he stays secure. At one point the SHIBA token sent a huge amount of funds to his cold wallet and he details what he did to securely access those funds: https://decrypt.co/91000/ethereum-founder-vitalik-buterin-dumped-7-billion-shib-how-why https://decrypt.co/91000/ethereum-founder-vitalik-buterin-du... > The funds, he said, were initially in a cold wallet in the form of two numbers written on separate pieces of paper. Buterin said he had to combine the two numbers to get the private key. "One of those numbers was with me; the other number was with my family in Canada," he said. "So I had to call up my family in Canada and tell them to read their number to me." > Buterin said that he entered the numbers into the computer he purchased from Target after putting the two numbers together. "I sent my ETH out by generating a transaction and then on a computer that I bought from Tarjay [Target] for about $300 bucks for just this purpose." > Before disconnecting the laptop from the internet entirely, Buterin said he downloaded a program to generate QR codes. After generating the Ethereum transaction, he scanned the QR code with his phone, copied it to the laptop, and then put it into etherscan.io/push Tx. Finally, Buterin said he began sending out the tokens.
red_admiral 2y ago
Curious to know because I've never looked into this stuff: doesn't the _public_ key have to be available anyway so you can send the coins to the address in the first place and have that recorded on the ledger?
- tomtomtom777 2y ago
  A wallet address (where money is sent to) is the public key hashed. This money can than be spent with a transaction containing both the signature and the public key. This is one of the reasons it is advised never to reuse an address. After using it once, your private key may still be private but your public key is exposed, reducing security.
  - red_admiral 2y ago
    Thanks. The "hashed" part is what I was missing.
- aeonik 2y ago
  Once you have the private key, you would submit a transaction with that private key and authorize a transaction to a public key that you control, and doesn't have part of the private key available. You don't need the public key, and IIRC most algorithms allow you to derive the public key from the private key, though I'm not sure that's the case with Bitcoin. I have vague memories that there are algorithms where this is not that case, but it's been a while.
  - red_admiral 2y ago
    It's some kind of EC/DSA scheme, isn't it? Then from the private key you can indeed get the public key.
    - mistrial9 2y ago
      Is this true? from an ECDSA private key you could derive many possible public keys? asking for a friend
derangedHorse 2y ago
I think you're mixing up the concept of entropy. The entropy is the measure of randomness in the data and with more entropy, the harder cryptographic schemes are to break. Going back to your comment, the asserted 130 bits of entropy in the key would be harder to break than 65 bits. I'm also unclear on where you got the 'multiple of 5' bit about. It seems the keys corresponding to numbers divisible by 5 were used in a spend transaction by the puzzle creator. Using those addresses in spend transactions reveals the public key and saves compute that would be wasted hashing. It also enables direct attacks using Pollard's rho (which someone already posted a link for above). Src: https://bitcointalk.org/index.php?topic=1306983.msg51466379#msg51466379 https://bitcointalk.org/index.php?topic=1306983.msg51466379#... https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_... Another interesting discussion on bitcointalk about using Pollard's kangaroo: https://bitcointalk.org/index.php?topic=5244940.0 https://bitcointalk.org/index.php?topic=5244940.0
dheera 2y ago
It seems #125 is already solved? If so don't they have the power to solve #67, 68, 69?
HPsquared 2y ago
So exponential increase in difficulty, linear increase in reward. Unless the price goes exponential too! (Which was the case for a while)
- Cthulhu_ 2y ago
  Yes, but computer performance also goes up exponentially - especially when GPUs and ASICs were built and optimized for the maths needed for crypto - so in a sense they're keeping up. In theory.
- fidelramos 2y ago
  My take on this [0] is that Bitcoin price was growing exponentially with demand, or more exactly with the expected future demand. Cryptocurrency always have had a lot of speculation behind them, not unlike any startup, and that is OK. As shown by the graph [0], adoption slowed down after 2016 when BTC blocks got consistently full and transaction fees rose to $50 and more. I believe if BTC had scaled to support more transactions the price would be much higher today, as Bitcoin would likely be used as a means of payment across the Internet and in many physical stores at well. Discussions regarding the decentralization of larger blocks aside, something that is not clear to many people is that scaling a blockchain to handle more transactions doesn't mean a linear increase in energy use. In the case of BTC its Proof-of-Work algorithm operates over the root of the last block's Merkle tree, which is a hash of all the transactions in the block. Being a fixed-size hash it doesn't matter if the block contains 1,000, 1 million or 1 billion transactions. Arguably a more popular Bitcoin would be more valuable and therefore would attract more miners, increasing its energy consumption, but that just reinforces my original point. [0] https://x.com/ampajaro/status/1782850107529973990 https://x.com/ampajaro/status/1782850107529973990
  - GTP 2y ago
    I think you're describing Bitcoin Cash, but AFAIK it's worth less than original BTC. What you're not considering is the brand value of BTC being the first and most famous crypto currency.
    - 2y ago
keepamovin 2y ago
Wow, that thread is nuts. Scrolled up just a bit saw this. My new public key search system is almost ready. I had to reinvent my binary database system because, although the database was lightweight https://bitcointalk.org/index.php?topic=5475626 https://bitcointalk.org/index.php?topic=5475626, I had efficiency issues with binary search. This is now a thing of the past. I have designed a system that stores 100 million public keys in an 80 KB file, yes, what you read 80KB!(in the future it will be smaller) that meets maximum efficiency. We would only be limited by the current speed of Secp256k1 when generating the 100 million or more public keys while creating the database. I am finishing designing the search script after months of being stuck due to personal issues, I am finally back on track. I love these kind of mad inventor rabbit hole corners of the Internet. Kind of brings back the 90s for me when everything was exciting.
- orf 2y ago
  > This is now a thing of the past. I have designed a system that stores 100 million public keys in an 80 KB file That’s 0.0064 bits per public key - so either there are lots of duplicates, or something is amiss here? Edit: they don’t actually store the keys, so the quote is misleading.
  - keepamovin 2y ago
    “That quote is misleading” Hahaha! :)
  - bdamm 2y ago
    Presumably there is a generator function that maps key IDs into actual keys that can be re-computed at will.
    - orf 2y ago
      How could this work with less than 1 bit of data per key? Assuming there are no duplicates, which is a sensible assumption, you’d need a minimum of 100,000,000 bits to store 100,000,000 unique entries larger than 1 bit with even a perfect hash function.
Dylan16807 2y ago
Note: The size of the puzzle is the number of unknown bits plus one, because the top bit is always set. Puzzle #66 had 65 unknown bits.
danielfisher77 2y ago
[dead]

by mrb 2y ago

wslh 2y ago

New to this puzzle! Do you have a more detailed resource to the puzzle? Is it basically brute forcing based on all public keys available on the Bitcoin blockchain? Could this be considered stealing?

mrb 2y ago
Sure, here is a nice little presentation on the puzzle: https://rya.nc/forensic-bitcoin-cracking.html https://rya.nc/forensic-bitcoin-cracking.html The main discussion thread on the bitcoin forum is this but it has a low signal-to-noise ratio: https://bitcointalk.org/index.php?topic=1306983.0 https://bitcointalk.org/index.php?topic=1306983.0 There is a secondary thread here: https://bitcointalk.org/index.php?topic=5218972.0 https://bitcointalk.org/index.php?topic=5218972.0 The point of the puzzle is indeed to brute force some private keys (not public keys), but not all, as 2^256 is computationally impossible. The private keys that have been discovered so far have obviously many zeros in them, so in practice you are never going to accidentally steal from a legitimate address with actually 256 bits of entropy. The creator of the puzzle is anonymous and never came forward (to my knowledge). The point of the puzzle is (1) to be a fun game, and (2) to be a publicly observable way of measuring current brute forcing capabilities.
- wslh 2y ago
  First, a question: is there something similar for other blockchains? And, a clarification, when I said public keys I referred to public keys that match an unknown private key but I understand now (am I correct?) that this puzzle is purely brute forcing private keys with a lot of zeroes and then matching with the addresses in the blockchain (which would be a function from the public key).
  - mrb 2y ago
    I don't know if other blockchains have these puzzles. You are correct thas this puzzle is brute forcing private keys with a bunch of zeroes, from which a public key can be calculated.
  - thisconnect 2y ago
    Other bc's are centralized and don't need it as they can just revert or change their state.

ForHackernews 2y ago

Is this a "puzzle"? Throwing compute at brute-forcing a random number doesn't seem like solving a puzzle to me, it's basically how bitcoin works.

aeturnum 2y ago
I think the puzzle idea is that, if you could figure out a weakness in the hash, you could claim it faster than the brute force approach. So each prize that's claimed "on schedule" supports the idea that there aren't any widely known shortcuts. Obviously if you found a shortcut in the hash you might do other things first, but I think that's the idea.
- IshKebab 2y ago
  Hmm yeah if I cracked Bitcoin then last thing I'd do is claim a prize that gave away the fact that I'd cracked Bitcoin.
  - mr_mitm 2y ago
    There is a difference between a weakness and complete breakage. You might have a small edge over brute force, but not enough to reverse any public key. This acts like a canary for weaknesses.
  - dylan604 2y ago
    some people just want the cred though. their name will be immortal and live through history as being something, or some such nonsense that feeds an ego. also, if you were the type that thinks bitcoin is lame, this could be a way of undermining the concept to the point that people no longer use it because it's not secure as it was touted
  - throwawaymaths 2y ago
    What you would do is claim the prize slightly ahead of schedule and wait to be slightly ahead of schedule for the next one.
  - 2y ago

deleted 2y ago

[deleted]

Sandworm5639 2y ago

Is it known who set it up and for what purpose?

n2d4 2y ago

For those curious, the reason why a public key lets you find a private key more efficiently is Pollard's rho algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_...

CamperBob2 2y ago
These keys are based on elliptic curves rather than products of primes, aren't they?
- matthewdgreen 2y ago
  There is one rho algorithm for discrete logarithms and one for factoring. Published three years apart.
  - sltkr 2y ago
    Neither of which helps with elliptic curve cryptography.
    - arcastroe 2y ago
      the problem of finding discrete logarithms is the same problem as breaking elliptic curve cryptography.
      - GTP 2y ago
        Technically, while the two problems share the same name, the one on elliptic curves is matematically different from the one over finite fields modulo a prime number.
        deleted 2y ago
        [deleted]
        AnotherGoodName 2y ago

mapt 2y ago

Am I correct in assuming that beyond a certain point, this is basically an existence proof for somebody having a quantum-supreme solution to Shor's Algorithm? "Here's $400,000 sitting on the table, hope nobody takes it" which triggers an alarm telling us to replace all our old prequantum cryptography.

n2d4 2y ago
Or someone "just" finding a fault in the cryptographic algorithms used in Bitcoin. Or whoever created the puzzles leaking their information.
- sigmoid10 2y ago
  >Or whoever created the puzzles leaking their information. Or getting hacked. This is super common among people who are known to have high value wallets. Between physical attacks and zero days in everyday software, there's no chance to stay safe when you put that kind of target on your back.
  - owl57 2y ago
    Is it likely that these particular private keys were wiped ~immediately after creation?
  - Powdering7082 2y ago
    > there's no chance to stay safe when you put that kind of target on your back. Vitalik Buterin seems to be a counter example here, his net worth peaked around $1.46 billion. He has some interesting writing on how he stays secure. At one point the SHIBA token sent a huge amount of funds to his cold wallet and he details what he did to securely access those funds: https://decrypt.co/91000/ethereum-founder-vitalik-buterin-dumped-7-billion-shib-how-why https://decrypt.co/91000/ethereum-founder-vitalik-buterin-du... > The funds, he said, were initially in a cold wallet in the form of two numbers written on separate pieces of paper. Buterin said he had to combine the two numbers to get the private key. "One of those numbers was with me; the other number was with my family in Canada," he said. "So I had to call up my family in Canada and tell them to read their number to me." > Buterin said that he entered the numbers into the computer he purchased from Target after putting the two numbers together. "I sent my ETH out by generating a transaction and then on a computer that I bought from Tarjay [Target] for about $300 bucks for just this purpose." > Before disconnecting the laptop from the internet entirely, Buterin said he downloaded a program to generate QR codes. After generating the Ethereum transaction, he scanned the QR code with his phone, copied it to the laptop, and then put it into etherscan.io/push Tx. Finally, Buterin said he began sending out the tokens.

red_admiral 2y ago

Curious to know because I've never looked into this stuff: doesn't the _public_ key have to be available anyway so you can send the coins to the address in the first place and have that recorded on the ledger?

tomtomtom777 2y ago
A wallet address (where money is sent to) is the public key hashed. This money can than be spent with a transaction containing both the signature and the public key. This is one of the reasons it is advised never to reuse an address. After using it once, your private key may still be private but your public key is exposed, reducing security.
- red_admiral 2y ago
  Thanks. The "hashed" part is what I was missing.
aeonik 2y ago
Once you have the private key, you would submit a transaction with that private key and authorize a transaction to a public key that you control, and doesn't have part of the private key available. You don't need the public key, and IIRC most algorithms allow you to derive the public key from the private key, though I'm not sure that's the case with Bitcoin. I have vague memories that there are algorithms where this is not that case, but it's been a while.
- red_admiral 2y ago
  It's some kind of EC/DSA scheme, isn't it? Then from the private key you can indeed get the public key.
  - mistrial9 2y ago
    Is this true? from an ECDSA private key you could derive many possible public keys? asking for a friend

derangedHorse 2y ago

I think you're mixing up the concept of entropy. The entropy is the measure of randomness in the data and with more entropy, the harder cryptographic schemes are to break. Going back to your comment, the asserted 130 bits of entropy in the key would be harder to break than 65 bits. I'm also unclear on where you got the 'multiple of 5' bit about. It seems the keys corresponding to numbers divisible by 5 were used in a spend transaction by the puzzle creator. Using those addresses in spend transactions reveals the public key and saves compute that would be wasted hashing. It also enables direct attacks using Pollard's rho (which someone already posted a link for above). Src: https://bitcointalk.org/index.php?topic=1306983.msg51466379#msg51466379 https://bitcointalk.org/index.php?topic=1306983.msg51466379#... https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_logarithms https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm_for_... Another interesting discussion on bitcointalk about using Pollard's kangaroo: https://bitcointalk.org/index.php?topic=5244940.0 https://bitcointalk.org/index.php?topic=5244940.0

dheera 2y ago

It seems #125 is already solved? If so don't they have the power to solve #67, 68, 69?

HPsquared 2y ago

So exponential increase in difficulty, linear increase in reward. Unless the price goes exponential too! (Which was the case for a while)

Cthulhu_ 2y ago
Yes, but computer performance also goes up exponentially - especially when GPUs and ASICs were built and optimized for the maths needed for crypto - so in a sense they're keeping up. In theory.
fidelramos 2y ago
My take on this [0] is that Bitcoin price was growing exponentially with demand, or more exactly with the expected future demand. Cryptocurrency always have had a lot of speculation behind them, not unlike any startup, and that is OK. As shown by the graph [0], adoption slowed down after 2016 when BTC blocks got consistently full and transaction fees rose to $50 and more. I believe if BTC had scaled to support more transactions the price would be much higher today, as Bitcoin would likely be used as a means of payment across the Internet and in many physical stores at well. Discussions regarding the decentralization of larger blocks aside, something that is not clear to many people is that scaling a blockchain to handle more transactions doesn't mean a linear increase in energy use. In the case of BTC its Proof-of-Work algorithm operates over the root of the last block's Merkle tree, which is a hash of all the transactions in the block. Being a fixed-size hash it doesn't matter if the block contains 1,000, 1 million or 1 billion transactions. Arguably a more popular Bitcoin would be more valuable and therefore would attract more miners, increasing its energy consumption, but that just reinforces my original point. [0] https://x.com/ampajaro/status/1782850107529973990 https://x.com/ampajaro/status/1782850107529973990
- GTP 2y ago
  I think you're describing Bitcoin Cash, but AFAIK it's worth less than original BTC. What you're not considering is the brand value of BTC being the first and most famous crypto currency.
  - 2y ago

keepamovin 2y ago

Wow, that thread is nuts. Scrolled up just a bit saw this. My new public key search system is almost ready. I had to reinvent my binary database system because, although the database was lightweight https://bitcointalk.org/index.php?topic=5475626 https://bitcointalk.org/index.php?topic=5475626, I had efficiency issues with binary search. This is now a thing of the past. I have designed a system that stores 100 million public keys in an 80 KB file, yes, what you read 80KB!(in the future it will be smaller) that meets maximum efficiency. We would only be limited by the current speed of Secp256k1 when generating the 100 million or more public keys while creating the database. I am finishing designing the search script after months of being stuck due to personal issues, I am finally back on track. I love these kind of mad inventor rabbit hole corners of the Internet. Kind of brings back the 90s for me when everything was exciting.

orf 2y ago
> This is now a thing of the past. I have designed a system that stores 100 million public keys in an 80 KB file That’s 0.0064 bits per public key - so either there are lots of duplicates, or something is amiss here? Edit: they don’t actually store the keys, so the quote is misleading.
- keepamovin 2y ago
  “That quote is misleading” Hahaha! :)
- bdamm 2y ago
  Presumably there is a generator function that maps key IDs into actual keys that can be re-computed at will.
  - orf 2y ago
    How could this work with less than 1 bit of data per key? Assuming there are no duplicates, which is a sensible assumption, you’d need a minimum of 100,000,000 bits to store 100,000,000 unique entries larger than 1 bit with even a perfect hash function.

Dylan16807 2y ago

Note: The size of the puzzle is the number of unknown bits plus one, because the top bit is always set. Puzzle #66 had 65 unknown bits.

danielfisher77 2y ago

[dead]