The methods described by DeathAndTaxes are appropriate. The OP_RETURN method is clearly the best if you want to adhere to the bitcoin recommendations.
However, I would like to present an alternative method where you can provably burn coins and also include sufficient information in the address. We used this method in the first versions of OpenBazaar and it is called an "almost-collision coin burning".
The de facto standard for burning coin in bitcoin is through an OP-RETURN script. This script has the important advantage that it contributes to bitcoin’s network scalability, as it allows full nodes to prune their UTXO when proof of burn transactions are detected. The mechanism employed to achieve that is simple: While a UTXO is maintained for all unspent regular transactions, when an OP-RETURN transaction is received by a full node, the full node can avoid adding that transaction to the UTXO completely, as the OP-RETURN script constitutes a proof that the amount remains unspendable and hence no future transaction can attach this dangling output to its input; it is hence a permanent dangling output edge.
OP-RETURN scripts work by having the first operator of the bitcoin script be an OP-RETURN, indicating an immediate exception in the execution of the script, hence making spending impossible. After the initial OP-RETURN operator, the rest of the script data can contain information about why the coin was burned, so that different applications can demand different burning, and so that the association with an account is possible. For example, in OpenBazaar’s case, it is important to associate the burned amount with an OpenBazaar GUID, which can be included as non-executable code after the OP-RETURN. The fact that this code is non-executable follows from that it will never be executed due to the earlier exception. However, the OP-RETURN approach lacks certain usability properties that we wished to preserve in our OpenBazaar implementation. In particular, for simplicity of implementation and usage, as well as for separation of concern reasons, we decided that OpenBazaar does not need to include a bitcoin wallet implementation. Instead, the user can use any existing wallet software they wish. Hence, to make payments required by OpenBazaar, either for product purchases or for burn transactions, the user would have to utilize their wallet directly.
Today, wallets do not have the ability to create OP-RETURN scripts in any usable way. The only way to create burn transactions are through manual issuing of script commands by the user, which can be confusing or impossible to execute for an average user without a programming background. Furthermore, the OP-RETURN script must be associated with an OpenBazaar GUID, something that makes the inclusion of this ability in existing wallets harder. While a wallet software could offer an API to do that, we are not aware of such implementations just yet.
For these reasons, we designed an alternative mechanism for coin burning which uses simple standard pay-to-pubkey-hash transactions. These transactions are treated normally by the bitcoin full nodes, hence they are propagated as required. Furthermore, it is easy for regular wallets to create such transactions, and users can easily understand the process and make the payment without worrying that an unnecessary amount of money will be transferred and without requiring special programming knowledge.
Our schema for burning is based on the following cryptographic assumption, a resistance to an almost-collision: It is computationally infeasible to calculate two hash pre-image values x1, x2 such that:
||H(x1)- H(x1)|| < ε
Where the norm denotes the Hamming distance of two strings and ε is a small constant, in our case 1. This assumption is strongly supported by the fact that a hash function is cryptographically secure; if this equation did not hold, a collision would have been found, modulo one bit, which indicates the hash is broken up to almost all of its bits.
Under this assumption for H = RIPEMD160, our schema asks for the burner to take the ECDSA public key associated with their OpenBazaar identity and turn it into a bitcoin address by following the regular schema for 1-prefixed bitcoin addresses. Regular bitcoin addresses are generated from regular bitcoin ECDSA keys as shown in the standard bitcoin address generation algorithm.
To generate an address that is provably unspendable, the burner starts with their ECDSA OpenBazaar public key and applies the same process. However, the burner perturbates the first SHA256 hash by one bit before piping it to the RIPEMD160 hash. Specifically, they flip the last bit of the hash output. The rest of the process follows identically. Finally, the burner transfers the amount of coin they wish to burn to this generated address. I will now illustrate the properties of correctness, uniqueness, and security for this scheme.
Correctness. To verify the correctness of the burn, a third party performs the same transformation as the burner. They begin from the public ECDSA key of the OpenBazaar node whose trust they wish to verify and follow the bitcoin address generation process, applying the same perturbation as the burner after the SHA256 stage. Arriving at the final bitcoin address, the verifier then checks the blockchain for money that was sent to this address. This concludes that the burn an honest burner performs will be correctly verified by an honest verifier. (This is a significant advantage when compared to alternative schemes that do not contain why-burned information such as nothing-up-my-sleeve addresses.)
Uniqueness. Under the assumption that RIPEMD160 is hard to reverse and the fact that SHA256 is a cryptographically secure hash function, assumptions already made by bitcoin, the uniqueness of burn address for each OpenBazaar key follows directly.
Security. For this scheme to be secure, we must prove that the burned money cannot actually be spent by anyone. Indeed, if the money were spendable, the spender would have to know the private key associated with a public key which hashes to the perturbed SHA256 value. However, this would allow the generation of an almost-collision in RIPEMD160, as the public key that can be used for spending the burned money and the public key of the OpenBazaar identity would constitute pre-images of hashes that only differ by one bit. From the almost-collision resistance assumption, we conclude that this is computationally infeasible.
The almost-collision method of coin burning introduces scalability challenges for the bitcoin software. We were not concerned with such challenges in OpenBazaar for two reasons. First, we felt a failure for bitcoin to scale given the massive motivated community use of our primitive constitutes a security problem for bitcoin itself, which must be addressed without requiring players to behave fairly to the system. This is a problem for bitcoin, not OpenBazaar. If bitcoin is susceptible to denial-of-service attacks with such means, the use of bitcoin as a payment system must be reconsidered.
Second, most importantly because we support the bitcoin ecosystem and wish to provide suggestions for solving its scalability issues, they can in fact be eliminated if proof-of-burn transactions are accompanied by the pre-image before perturbation. The accompanying pre-image constitutes proof that the money is unspendable, similar to the way OP-RETURN scripts constitute proof of unspendability. As these pre-images will be publicly available on the OpenBazaar network, in case OpenBazaar becomes largely adopted, full bitcoin nodes can utilize the OpenBazaar network to detect prunable UTXO outputs which perform proof-of-burn through almost-collision pay-to-pubkey-hash scripts. Regardless, the optimizability of the payment network is of little concern to its financially motivated users and its technical implementation details remain an open research problem.
Overall, however, once the OP_RETURN method becomes a usable alternative, the other methods of burning should be eliminated for elegance and scalability.
