The Bitcoin.it wiki article about proof of burn mentions "verifiably unspendable addres" and this method has been used by Counterparty to create XCP.
Is it actually possible to create an address that is "verifiably unspendable"? If yes, how? Or does "verifiable" just mean extremely hard, the way it is extremely hard to find a private key for any public key?
Or in other words: Are there valid Bitcoin addresses for which it's possible to mathematically prove that there is no private key?
Every valid ECDSA public key corresponds to some valid ECDSA private key. Bitcoin addresses are not actually public keys though, they are a 160-bit hash of a particular binary representation of the public key.
You asked:
Are there valid Bitcoin addresses for which it's possible to mathematically prove that there is no private key?
As far as I know, the answer to that is no. To construct such a proof, you would have to somehow consider the enormous set of all possible public keys, and prove that none of them have a binary representation whose 160-bit hash would match the Bitcoin address in question. The point of hash functions is that they cannot be easily inverted, so you can't just get a list of all the valid inputs that would result in the same hash.
The number of ECDSA public keys (approximately 2^256) is vastly greater than the number of Bitcoin addresses (2^160). So the average Bitcoin address actually corresponds to about 2^(256-160) = 2^(96) different public keys. So it seems like it would be hard to find an address that corresponds to 0 public keys.
Yes - the easiest way is to provide an algorithm for making bitcoin public address without knowing private key. That seems impossible but think about what makes valid bitcoin address - for example 1BitcoinEaterAddressDontSendf59kuE is valid. Last 6 digits are made just to make this valid address. With vanitygen which allows you to make some vanity prefixed: 1stackLmzFVj8ALj6mfBsbifRoD4miY36v. But with larger vanity part address is much harder to generate. In case of bitcoin eater on can prove that chance of finding private key for this sequence is so low that effectively this makes this verifiably unspendable.
