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 16 down vote accepted

Creating an valid address based on 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. We can exploit this fact to create a invalid public key, that is one in which we can provably say there is no corresponding private key. 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

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

There is no private key which will produce a public key of 0. We can then generate a valid Bitcoin address from this invalid public key. The Bitcoin network only verifies that an address is in the right form, length, and has the right checksum when "validating it". Most of the time the public key is unknown so no check against the validity of the public key is performed.

Publish both the address and invalid public key to allow verification that the public key corresponds to the bitcoin address and that the public key is invalid. Any coins sent there can never be spent and third parties can verify this for themselves.

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.

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 used "nothing up my sleeve values" to dispel the fear that random seed is not random but chosen to enable some cryptographic flaw or "backdoor" in the algorithm.

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

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 at 22:14
    
That is correct. Fixed. –  DeathAndTaxes Jan 23 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 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 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 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.