Take the 2-minute tour ×
Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It's 100% free, no registration required.

(Following up to this question.)

In order to put a bitcoin beyond use, the answer was to select a made up address. As this isn't a formal destruction of bitcoins, there's a risk that the private keys could be found to spend those "destroyed" bitcoins.

If someone suggests an address, people might suspect that this address was selected because that person painstakingly looked for an address that looked like a made up address.

How can an address for bitcoin destruction be selected that everyone can be reasonably sure no-one's going to know the private keys to spend the destroyed bitcoins?

share|improve this question

5 Answers 5

up vote 19 down vote accepted

Start with an invalid public key

Bitcoin addresses are the pubkeyhash (not pubkey) plus version and checksum information, encoded in base 58.

Bitcoin address = version + RIPEMD-160(SHA-256( Public Key )) + checksum

The steps for converting a public key to an address can be found here: https://en.bitcoin.it/wiki/Address

Since the address uses the pubkeyhash not the actual pubkey we can exploit this by hashing an invalid pubkey (one which can't possibly exist) and thus produce a valid address from an invalid pubkey.

So to start we find an invalid public key. All valid public keys begin with 0x04 if uncompressed and 0x02 or 0x03 if compressed. A pubkey beginning with any other value is undefined and thus there is no possible signature that can be created to satisfy that key requirement. Since spending coins requires signing the transaction with the correct private key, an address which has no known private key is unspendable. By using a public key which is known to not have a private key others can confirm that no private key exists.

A valid Bitcoin public key (not address):

04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f

An invalid public key

0x0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

There are other ways to produce a known invalid public key. ECDSA keys must be exactly 65 bytes if uncompressed or 33 bytes if compressed so a key with a different length will also be invalid. For uncompressed keys the y value must be correctly produced from the x value. The point must also lie on the curve. It also can't be above the modulus for the curve. So there are a lot of ways to produce provably invalid keys but it best to choose one which is obviously invalid. This is probably the simplest obviously invalid public key.

0x00

This public key is invalid for a number of reasons (not produced by private key multiplied by the generator, not located on the curve, not a valid point, but even simpler it doesn't have a valid prefix and is not the correct length).

The important thing is this isn't just some probably invalid key it is a provably invalid key.

You should test your invalid public key against the reference client to ensure the client reports it as invalid as well. The validity of keys is a consensus issue so this will not change short of a hard fork.

Produce a valid (but unspendable) address from your invalid public key

You may wonder why we want the address to be valid. All clients should validate addresses given by users to avoid accidental loss of funds. So an invalid address is also unspendable but most users will find it impossible to send funds to the address. A P2PkH address is the pubkeyhash with version and checksum information encoded in base58.

When you provide an address to a Bitcoin client it decodes the address back down to the 'raw' pubkeyhash. So producing a valid address means starting with a valid pubkeyhash. This isn't a problem because the hash of anything is a valid hash. Clients don't know what pubkey is hashed to produce the pubkeyhash as the underlying pubkey is not provided and hashing functions are one way.

The Bitcoin network only verifies that an address is in the right form, length, and has the right checksum when "validating it". Producing an address from a pubkey is beyond the scope of this question but there are utilities and the link above provides the steps. The resulting pubkeyhash and encoded address will be seen as valid by the network and client but it requires a provably impossible private key to spend funds sent to that address.

Now with just the address (and decoded pubkeyhash) a user can't verify that the underlying pubkey is invalid so you should publish the raw pubkey along with the address. Users can recreate the address using any bitcoin client or tool and will produce the same address you provide. Users now have a trustless way to verify that the coins indeed are unspendable. Any coins sent to the address can never be spent and are effectively destroyed.

Hash collision

Technically it is possible but improbable for more than one public key to have the same Bitcoin address. This is called a hash collision. If public key p1 and public key p2 both hash to the same address A then privates keys for either of these public keys can spend the funds. However the likely of this happening is very low. Unless RIPEMD hash algorithm is broken the probability of finding two public keys which generate the same hash (Bitcoin address) is 1 in 2^160 which is far beyond our computational power to locate.

A few words on why you should use a 'Nothing Up My Sleeve' number:

Using a "nothing up my sleeve number" (such as a single zero, all zeroes, single repeating digit, sequential numbers, digits of pi, etc) is not required as any invalid public key is equally unspendable but it would improve public confidence that you haven't already found a collision (as improbable as that is).

If you just take a random invalid key like say:

00000fdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f

Some may question why you chose this specific key. The fear would be that you choose this key not randomly but because you have stumbled upon a collision between this key and a valid key. There is no way to prove the key is random thus the fear will always remain. Cryptographic functions (like RIPEMD or SHA-256) often use "nothing up my sleeve values" to provide security that a constant was not chosen to enable some cryptographic flaw or "backdoor" in the algorithm. For example SHA-256 uses constants for the initial values of the block segments. Technically these could be any random number but that would lead to concern that the 'random' number isn't actually random. So SHA-256 uses first 32 bits of the fraction portion of the cube root of the first 8 prime numbers. This allows verification when a pseudo random number is needed. It is very unlikely there is some magical property between the fractional portion of the cube root of sequential prime numbers that undermines SHA-256.

http://en.wikipedia.org/wiki/Nothing_up_my_sleeve_number

Update (03/31/2015)

It is easier to do this now by using an OP_RETURN (null data) output and it doesn't bloat the UTXO with outputs that can't be spent but the network is unaware they can't be spent. Any funds sent to an output which contains OP_RETURN are provably unspendable and the network will drop the output from the UTXO. The UTXO (unspent tx output set) is a critical resources which is necessary for validating new transactions and blocks so destroying/burning coins using UTXO is a more responsible use of this shared resource.

share|improve this answer
    
I think there is an error in the formula in your first paragraph. As explained on this wiki page, only a single SHA-256 hash is used for generating the hash-160. For the checksum, however, (the first 4 bytes of) a double SHA-256 hash is used. –  Steven Roose Jan 22 '14 at 22:14
    
That is correct. Fixed. –  DeathAndTaxes Jan 23 '14 at 4:53

There are four basic ways, and they all work:

  1. Come up with an address that passes the basic sanity checks but is internally invalid. You can know for sure that no key could possibly match this address.

  2. Put strings of characters in the address that are way beyond what anyone could generate in a vanity address. For example, if the Bitcoin address has "FourScoreAndSevenYearsAgo" in it, it's clearly beyond anyone's capability to find a corresponding private key.

  3. Use a public key that's obviously made up, such as one that consists only of zero bytes or that contains all consecutive digits of Pi. It's clearly beyond anyone's capability to find a corresponding private key. (For this one to work, you need to disclose the public key.)

  4. Use a hash of the public key that's obviously made up. This works the same as the option above, but the difficulty would be in even finding a public key with such a hash, much less finding the corresponding private key.

share|improve this answer
    
Isn't point 1 technically wrong as DeathAndTaxes and ThePiachu have demonstrated? We can't know for sure that no one knows a valid key matching the address-hash since there's an infinite number of valid keys slotted into a limited amount of possible hash values. –  Pacerier Mar 10 '14 at 14:15
    
@Pacerier The address would be internally invalid if we pick point 1. No key could match that address. You can slot an infinite number of things into a finite number of slots and still know for sure that some slots are empty. There are an infinite number of integers and a finite number of English words for categories, yet no integer falls into the category denominated by the word "angel". –  David Schwartz Mar 10 '14 at 14:16

If you want to be pretty sure nobody can retrieve the Bitcoins:

  1. Look at the wiki article on Addresses.
  2. Start at point 3 with an obviously fake number (like, "0000000000000000000000000000000000000000")
  3. Continue with points 4-9.
  4. You get a "valid" address for destroying Bitcoins.

What is the catch? As normally you'd generate the public key from a private key and hash it a couple times, in order to retrieve coins from the address you generated, one would have to find such a specific number in point 1, that after points 2 and 3 would generate your bogus number. The chance of you finding one is about 1 in 2^160, which is impossible at current computation speeds. The more orderly the number you used in point 3 is, the more people would believe that it is an obviously fake address.

share|improve this answer

An alternative to generating an address is to use a valid address known to be almost impossible to retrieve coins from i.e. https://blockchain.info/address/1BitcoinEaterAddressDontSendf59kuE.

This is a good as destroyed because if anyone could reverse engineer the private key for this address, then due to the vanity length, they could use the same method to reverse engineer the private key for any address. Or they were lucky in the same way as winning the lottery jackpot each week for a year is lucky.

share|improve this answer

You may generate address with vanitygen and destroy the private key ( don't save it ) > /dev/null

Download it here: https://github.com/samr7/vanitygen

Read more about it here: https://en.bitcoin.it/wiki/Vanitygen

E.g.

# ./vanitygen 1
Difficulty: 1
Pattern: 1                                                                     
Address: 1GZa7XXKg9wKoDWu2QUvEBDqFzqe2A6gzz
Privkey: 5KUkhGFoPhUNZghsza3xSREsAhMTKBxfd6V7u543zwNZcfTXAq1

# ./vanitygen 1
Difficulty: 1
Pattern: 1                                                                     
Address: 13UBCaV11DhS61YTUx9LPWuaiJxF6LxyAF
Privkey: 5JyTCQoh6kdPBEpc7bZwFd9Gnb2N37zjTjvPeY3Ve61GaCRxF41

# ./vanitygen 1
Difficulty: 1
Pattern: 1                                                                     
Address: 1NSQ5Kv3vzknqvFZwu6Gkq1X8VySycg7vt
Privkey: 5K4k6VRabmWVujxSD6eQx7ovQoR8FjGi8oz5NrfBuszxFRR71tT

Just use the Address, don't save the Privkey.

share|improve this answer
    
This fails the "How can an address for bitcoin destruction be selected that everyone can be reasonably sure no-one's going to know the private keys to spend the destroyed bitcoins?" requirement. How do I know that you didn't save the private key, or remember it? –  mca May 26 '14 at 4:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.