Are bitcoins indestructible?

[remotemass]

When bitcoins are lost you can consider them destroyed because there is absolutely no way to restore them.

That is not true because you can find that lost coins - by accident, for instance - when you create a bitcoin address.
It is very unlikely and a bit like searching for gold in the desert but still, you know, you can find a grain of gold in a beach of sand, can't you? I mean, it is possible within the laws of Physics...

[1715098048]

1715098048

[DeathAndTaxes]

It's going to take awhile for bitcoins to be destroyed by mining. Which miner in their right mind would do that?

Which wasn't the question asked.

The question was are bitcoins indestructible?  The answer is no.  It would be like asking is cash indestructible?  and someone answers no you can destroy it by burning it then saying, well who would do that?  I don't know who would do that and for what purpose, it may never be done except in accident however none of that changes the answer to the question "are bitcoins indestructible?", that answer beyond any debate is definitively ... no.

[Dabs]

Yes. Correct. I just thought I'd add a little to the discussion. It's not a big issue for almost everyone else. I don't see more than a few thousand coins ever being destroyed that way, even if intentional.

[zebedee]

An address is a hash of the public key (w/ checksum) not the public key itself.

It is entirely possible that there is no public key which produces the address above.

Massively unlikely though given that the pigeonhole priniciple shows that there are on average 2^96 public keys mapping to each bitcoin address.  Quite unlikely (read: impossible) any address misses all of its expected 2^96 hits.

[manuel]

How do people know somebody doesn't have the private key to that [1BitcoinEaterAddressDontSendf59kuE] address all along and they're just sitting on the coins?

Because the person that created the address 1BitcoinEaterAddressDontSendf59kuE never had the private key.  They simply started with the string "1BitcoinEaterAddressDontSend" and then added the correct checksum "f59kuE" onto the end of the string (it is a bit more complicated than that but you get the point).

Since they never had the private key no one will ever have the private key so any coins sent to that address are lost forever.

Ouch.... 

Luckily it only has 1.6 BTC right?  Or did I look that up wrong?

[BurtW]

How do people know somebody doesn't have the private key to that [1BitcoinEaterAddressDontSendf59kuE] address all along and they're just sitting on the coins?

Because the person that created the address 1BitcoinEaterAddressDontSendf59kuE never had the private key.  They simply started with the string "1BitcoinEaterAddressDontSend" and then added the correct checksum "f59kuE" onto the end of the string (it is a bit more complicated than that but you get the point).

Since they never had the private key no one will ever have the private key so any coins sent to that address are lost forever.

Ouch....  

Luckily it only has 1.6 BTC right?  Or did I look that up wrong?

https://blockchain.info/address/1BitcoinEaterAddressDontSendf59kuE

1.60652869 BTC ($ 1,420.11 at the time of this post)

[kjj]

Bitcoins are very abstract.  The definition of "destroyed" gets fuzzy here.

Blocks claiming less than the full possible reward most closely fit, in my opinion, the concept of destroyed.  These coins can only be recovered by a change in the protocol.*  Also in this category is the permanently unspendable coins from one or the other of the two blocks that had identical coinbase transactions.

Coins sent to keyless addresses are the second best fit.  No one has ever known a privkey that could redeem those coins, and so we have no reason to believe that such a key exists.

Coins sent to keys that were generated but then lost is the weakest fit.  We know that a key to that address has existed in the past, and so there is every reason to believe that the key could be found again.  Thermodynamics blocks us from doing so, but math itself doesn't bar our way.

* Such a change may not be completely crazy, but is still really unlikely.  It wouldn't hurt much to allow miners to claim some fraction of the coins lost through this method in the past.  Of course, it wouldn't help much either...

[manuel]

Bitcoins are very abstract.  The definition of "destroyed" gets fuzzy here.

Blocks claiming less than the full possible reward most closely fit, in my opinion, the concept of destroyed.  These coins can only be recovered by a change in the protocol.*  Also in this category is the permanently unspendable coins from one or the other of the two blocks that had identical coinbase transactions.

What is "coinbase"?  How do you get a block that has "less than the full possible reward"?

Coins sent to keyless addresses are the second best fit.  No one has ever known a privkey that could redeem those coins, and so we have no reason to believe that such a key exists.

Coins sent to keys that were generated but then lost is the weakest fit.  We know that a key to that address has existed in the past, and so there is every reason to believe that the key could be found again.  Thermodynamics blocks us from doing so, but math itself doesn't bar our way.

* Such a change may not be completely crazy, but is still really unlikely.  It wouldn't hurt much to allow miners to claim some fraction of the coins lost through this method in the past.  Of course, it wouldn't help much either...

How do you get a valid address with a key that "doesn't exist"?  How is an address where nobody ever had the key any different than an address where somebody had the key but has really absolutely permanently lost it.  Let's say they generated it in volatile memory, wrote it on paper, shut down the computer and then burned the paper...  how is that any different to a valid address where nobody ever really had the key?

And on that note how do you make a valid address but without ever getting the private key?  Aren't valid addresses generated from private keys?  I mean when I import a private key it knows the address without me telling it just from the private key.

[kjj]

Bitcoins are very abstract.  The definition of "destroyed" gets fuzzy here.

Blocks claiming less than the full possible reward most closely fit, in my opinion, the concept of destroyed.  These coins can only be recovered by a change in the protocol.*  Also in this category is the permanently unspendable coins from one or the other of the two blocks that had identical coinbase transactions.

What is "coinbase"?  How do you get a block that has "less than the full possible reward"?

Normally, a transaction has 1+ inputs and 1+ outputs.  Each block has a special transaction in it that has no inputs, which is used to reward the miner.  Where the input would normally be is a freeform field named "coinbase".  The term is also commonly (but incorrectly) used to mean the generation transaction itself.  (My bad.)

Once upon a time, a guy mined two blocks using the exact same address for the reward.  Both of those generation transactions were identical, so they had the same hash.  In bitcoin, the hash is a, ahem, "unique" identifier, so spending one of them spends both of them.  Thus, 50 coins "destroyed".

This won't happen again because blocks are now required to have their height in the coinbase field, which makes them unique even if they are otherwise identical.

And the network only checks that the generation transaction's value is less than or equal to the subsidy + the fees.  Nothing stops you from making a block that claims less than the full reward, but doing so is silly, and nowadays, expensive.  A few blocks in the past, however, claimed less reward than they could have, so the worldwide total will be slightly less than it could have been.

Coins sent to keyless addresses are the second best fit.  No one has ever known a privkey that could redeem those coins, and so we have no reason to believe that such a key exists.

Coins sent to keys that were generated but then lost is the weakest fit.  We know that a key to that address has existed in the past, and so there is every reason to believe that the key could be found again.  Thermodynamics blocks us from doing so, but math itself doesn't bar our way.

* Such a change may not be completely crazy, but is still really unlikely.  It wouldn't hurt much to allow miners to claim some fraction of the coins lost through this method in the past.  Of course, it wouldn't help much either...

How do you get a valid address with a key that "doesn't exist"?  How is an address where nobody ever had the key any different than an address where somebody had the key but has really absolutely permanently lost it.  Let's say they generated it in volatile memory, wrote it on paper, shut down the computer and then burned the paper...  how is that any different to a valid address where nobody ever really had the key?

And on that note how do you make a valid address but without ever getting the private key?  Aren't valid addresses generated from private keys?  I mean when I import a private key it knows the address without me telling it just from the private key.

Any 256-bit string is a private key.  Multiply (in EC math) G by that private key, and you have a public key.  Hash that public key in a particular way and encode it and you have an address.  Neither the multiplication nor the hashing are reversible.  You can pick a random number, hash it and see what the address would have been, even though you don't have a private key that would work for it.  Or, you can skip right to the end and make an address without knowing what the public key should have been, much less the private key.

The address hash is 160 bits.  We do know that for every input, there is one output, but we don't know that for every possible 160-bit number there is necessarily an input that creates it.  The address in my hash, for example, has a pubkey that can be hashed to create it.  But we don't know if there is any pubkey that hashes down to the bitcoin eater address.

I'm not sure if EC multiplication has the same property or not.  I *think* that for every valid public key, we know that some private key matches it even if we don't know what that private key is.  A proper cryptographer could answer that for sure.

[BurtW]

And on that note how do you make a valid address but without ever getting the private key?  Aren't valid addresses generated from private keys?  I mean when I import a private key it knows the address without me telling it just from the private key.

I did this up thread here:

https://bitcointalk.org/index.php?topic=358010.msg3849442#msg3849442

And explained it to you up thread here:

https://bitcointalk.org/index.php?topic=358010.msg3858534#msg3858534

[jdbtracker]

It's impossible to send them to an invalid address, BUT it's entirely possible to send them to an address for which no one has the key.

Take for example: 1BitcoinEaterAddressDontSendf59kuE

Check it out on blockchain. If you can brute force the private key, the coins are yours. Is it impossible? Theoretically, no, but practically...

Let's say you had a super computer that was guessing 999 trillion keys per second. It would take you 3.5 billion years to exhaust just 10% of the keyspace, which means in 3.5 billion years you would have a 10% chance of having guessed the key. Good luck with those odds!

so... if we aimed all the Hashing power of the Bitcoin network on one address it would take 500 million years? Hey man It's only a matter of time before insane quantum computers just start cracking the codes by the second. I can imagine this will happen one day, when the Bitcoin network migrates to a new protocol based on quantum security. Those computers will tear Bitcoin apart when they finally are able to produce them in mass, and start migrating all the accounts to a new system like a block reward, Or just like the free market migrate by choice to something safer.

[kjj]

so... if we aimed all the Hashing power of the Bitcoin network on one address it would take 500 million years? Hey man It's only a matter of time before insane quantum computers just start cracking the codes by the second. I can imagine this will happen one day, when the Bitcoin network migrates to a new protocol based on quantum security. Those computers will tear Bitcoin apart when they finally are able to produce them in mass, and start migrating all the accounts to a new system like a block reward, Or just like the free market migrate by choice to something safer.

Quantum computers do not appear to be particularly adept at hashing.

[bardi.harborow]

Guys, you are missing OP_RETURN. If the output of a bitcoin transaction is "OP_RETURN" then the coins are impossible to spend.

[kjj]

Guys, you are missing OP_RETURN. If the output of a bitcoin transaction is "OP_RETURN" then the coins are impossible to spend.

Oh shit, that's right.  There are actually a whole bunch of coins locked up in scripts that have no possible solution.  Not just OP_RETURN, but also garbage from buggy systems over the years.

[BurtW]

Guys, you are missing OP_RETURN. If the output of a bitcoin transaction is "OP_RETURN" then the coins are impossible to spend.

Oh shit, that's right.  There are actually a whole bunch of coins locked up in scripts that have no possible solution.  Not just OP_RETURN, but also garbage from buggy systems over the years.

Well in theory at least the number of coins destroyed in this way could be calculated by scanning all unspent output.  Knowing this number you could then subtract it from the ending total and get a slightly more accurate ending total.

[DavidZ]

Could someone please point me to a good description of bitcoin mining for someone that has studied first year uni maths. ie not too dumbed down but not too advanced either.

[Speakeron]

so... if we aimed all the Hashing power of the Bitcoin network on one address it would take 500 million years? Hey man It's only a matter of time before insane quantum computers just start cracking the codes by the second. I can imagine this will happen one day, when the Bitcoin network migrates to a new protocol based on quantum security. Those computers will tear Bitcoin apart when they finally are able to produce them in mass, and start migrating all the accounts to a new system like a block reward, Or just like the free market migrate by choice to something safer.

Quantum computers do not appear to be particularly adept at hashing.

More specifically, using Grover's Algorithm, the time taken to find a preimage of a hash (i.e. a reverse hash) is the square-root of the time for a classical attack. e.g. a 256-bit hash becomes like a 128-bit hash. It's not considered a big problem since the times are still very long.

[kjj]

so... if we aimed all the Hashing power of the Bitcoin network on one address it would take 500 million years? Hey man It's only a matter of time before insane quantum computers just start cracking the codes by the second. I can imagine this will happen one day, when the Bitcoin network migrates to a new protocol based on quantum security. Those computers will tear Bitcoin apart when they finally are able to produce them in mass, and start migrating all the accounts to a new system like a block reward, Or just like the free market migrate by choice to something safer.

Quantum computers do not appear to be particularly adept at hashing.

More specifically, using Grover's Algorithm, the time taken to find a preimage of a hash (i.e. a reverse hash) is the square-root of the time for a classical attack. e.g. a 256-bit hash becomes like a 128-bit hash. It's not considered a big problem since the times are still very long.

Not to wander too far off topic, but Grover's solves circuits.  Circuit means the function must be completely unrolled in both time and space, so that there is no memory and no iteration, just logic gates.  A circuit for SHA-256 is far beyond our capabilities, much less double SHA-256.  I'm not sure we are even capable of designing such a thing.

Oh, and did I mention that all those trillions (quadrillions?  pentillions?  who knows?) of logic gates have to be reversible quantum gates?  And that they all have to be kept coherent?

[justusranvier]

Circuit means the function must be completely unrolled in both time and space, so that there is no memory and no iteration, just logic gates. 

sounds like a great design for a hardware wallet.

[manuel]

How do people know somebody doesn't have the private key to that [1BitcoinEaterAddressDontSendf59kuE] address all along and they're just sitting on the coins?

Because the person that created the address 1BitcoinEaterAddressDontSendf59kuE never had the private key.  They simply started with the string "1BitcoinEaterAddressDontSend" and then added the correct checksum "f59kuE" onto the end of the string (it is a bit more complicated than that but you get the point).

Since they never had the private key no one will ever have the private key so any coins sent to that address are lost forever.

My question is how do you know what to add to the end?