Blockchain Research Newsletter #6: Proof-of-Burn

By Mikerah and John Adler

In this edition of the Blockchain Research Newsletter, we are covering a well-understood but informally defined concept, Proof-of-Burn. The concept of proofs of burn has been in used in Bitcoin and other blockchains extensively. However, until the work of Karantias et al., was poorly defined from a formalization point of view. Being able to formally define concepts enables researchers to discuss work without ambiguity, and more importantly provide proofs of various properties of a system. Moreover, in this paper, the authors provide a general Proof-of-Burn protocol that can be used for any cryptocurrency. They prove that their protocol is correct and secure under the random oracle model. In addition to providing this protocol, they go into depth about a particular use case for a Proof-of-Burn protocol: bootstrapping a new cryptocurrency.

Motivation

With fiat money, there is no way to show that you have destroyed (burned) a certain amount of money in a provable way. In fact, in the context of fiat money, what does burning money even mean? Burning actual legal tender will get you arrested in most countries and debit/credit cards are just numbers in a database that you can’t provably show that you can burn. Cryptocurrencies, however, give us a way to prove that a user cannot spend a certain amount of coin. Not only can you provably make money unspendable, this process can be binding — you can trace who the previous owner was — and can be censorship resistant, i.e., no one can prevent you from burning your own coins. There are a few use cases in which one might want to burn a part of their cryptocurrency holdings, e.g., as a Sybil resistance to join a particular application.

Proof-of-Burn

Roughly, a Proof-of-Burn protocol is a way to provably destroy your coins. More formally, a Proof-of-Burn protocol is defined as follows:For a given security parameter k, a Proof-of-Burn protocol consists of the following functions:

• A function called GenerateBurnAddr with a nonce and a tag as inputs, returns a burn address
• A function called VerifyBurn with a nonce, a tag and a burn address as inputs, returns whether or not the tag is correctly encoded with respect to the burn address.

Moreover, Proof-of-Burn protocols satisfy the following properties:

• Unspendability: Once burnt, coins are no longer spendable.
• Binding: A burn transaction commits to a single user-generated string called a tag.
• Uncensorability: Miners (or more generally, validators) cannot censor burn transactions

Further, the authors provide game-based security definitions for Proof-of-Burn protocols. These definitions are given in the context of a mathematical formalization of unspendability and binding. Although the formalization is outside the scope of this summary, we will provide some intuition for these formulations. Consider a challenger that might want to spend burned coins and commit to multiple tags. In the first case, the challenger wants to generate a tag, a transaction, a signature, and public key such that VerifyBurn and the transaction verification both return true. Thus, a Proof-of-Burn protocol is unspendable if there is negligible function for which the probability of this occurring is small. In the second case, the challenger wants to generate a 2 tags, t and t’, and a burn address such that t and t’ are different, and that VerifyBurn returns true on both t and t’ for the same burn address and nonce. Thus, a Proof-of-Burn protocol is binding if there exists some negligible function for which the probability of this occurring is small. With both of these definitions, we can define what it means for a proof of burn protocol to be secure. A Proof-of-Burn protocol is secure if it is both unspendable and binding.

Protocol

The authors provide a Proof-of-Burn protocol that satisfy all the properties previously discussed. This protocol was designed to work with Bitcoin’s Pay to Public Key Hash (P2PKH), although it can be modified to work with other blockchains.

The Proof-of-Burn protocol is constructed as follows:
GenerateBurnAddr(1^k, t):

th = H(t)
th’ = th XOR 1
return th’

VerifyBurn(1^k, t, th’):

return whether GenerateBurnAddr(1^k,t) is equal to th’

where H is a cryptographic hash function and XOR is the exclusive or function.

Conclusion

We have summarized what the authors have defined as a Proof-of-Burn protocol and what it means for it to be secure. Moreover, we went over a construction of a Proof-of-Burn protocol that the authors proposed that satisfy the various definitions given for secure Proof-of-Burn protocols. You can read the paper here if you want to deep dive into the mathematical details.