How to generate a valid bitcoin address for destroying bitcoins? (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?
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.