Proof of burn
Proof of burn is a potential alternative to proof of work and proof of stake as a "scarce resource" to be exhibited by miners competing for the stream of rewards (minted coins and transaction fees) which a cryptocurrency's design makes available. The idea is that miners should show proof that they burned some coins - that is, sent them to a verifiably unspendable address. This is expensive from their individual point of view, just like proof of work; but unlike proof of work, it consumes no real resources from a whole economy perspective. This has interesting implications, discussed below.
There are likely many possible variants of proof of burn. This page currently describes Iain Stewart's version. Other people can add variant versions that still belong to the broad proof of burn idea.
Iain Stewart's version of proof of burn
Introduction and motivation
The key idea of proof-of-burn (this would also apply to proof-of-stake, by the way) is that when choosing the thing which is to qualify as a "difficulty", i.e. to require miners to exhibit proof that they've "done something that's tough to do", all that matters is that an individual miner finds the task expensive. (Well... it also matters that everyone else should find it cheap to verify that it has been done.) It doesn't need to be the case that real resources are consumed in the real economy.
With proof-of-work, it so happens that real resources are indeed consumed - mining rigs are produced, with human labour and materials as input, electricity is used, and all these things have to be bid away from their real-economy best alternative uses. (Or, if they're produced in addition to what would have been produced, the total of leisure time is less than it could have been. Something real is grabbed as input.) And while a cryptocurrency is being set up (i.e. [the fast early phase of] its initial distribution) - or, more precisely, while the first cryptocurrency is being set up; more on this distinction later! - no good alternative has been proposed. (And I'm not proposing one.) But once a cryptocurrency is up and running, with its initial distribution close to completed, new possibilities arise, for tasks to "feel expensive" to a miner but not actually "be expensive" from a god-like whole-economy perspective.
Proof-of-stake (of the "Cunicula variety", I mean) is in fact arguably already an example of such a task. It feels awfully expensive, to a miner, to save up a lot of bitcoins and become a big stakeholder; but from a whole-economy viewpoint, this is a swapping of assets' ownership labels around, it's not a burning of electricity or the like. However, I thought it would be interesting to invent a task that is absolutely, nakedly, unambiguously an example of the contrast between the two viewpoints. And yes, there is one: burning the currency!
By "burning" a tranche of bitcoins I just mean sending them to an address which is unspendable. The precise technical details of this will vary from cryptocurrency to cryptocurrency. With Bitcoin, any address which is [the RIPEMD160/SHA256 hash of] a script that evaluates to false will do. So, the script should do a "deliberately silly" thing - instead of things like "check such-and-such signature, and put the validity result on the stack", it should do something like "add 2 and 2, and now check if what's on top of the stack is equal to 5". (Or just "push 4, and check if it's equal to 5". Anything of that sort.) There are thus an unbounded number of such scripts, with entropy saturating RIPEMD160 since you can choose big numbers to taste. So, bitcoins sent to such a txout can never be redeemed on a future txin. (Barring the cracking of RIPEMD160 and the finding of an alternative matching script, that is. If that happens, the cryptocurrency is in big trouble anyway!)
With this definition of burning, it's not obvious to blockchain-watchers that some bitcoins have been burnt, at the time of burning. They've been sent to an address which doesn't stand out from any other. It's only later, when a miner who burned them earlier now wants to exhibit proof that "yes, these coins are burnt", that blockchain-watchers get their proof. (Which basically consists of exhibiting the script that manifestly always evaluates to false, and hashes to the address.) If it's thought desirable that the act of burning should be obvious right away, rather than later, then this can be achieved: burning merely needs to be defined as sending to some fixed unspendable address, with no variation - e.g. we could settle on the hash of "push 4, and check if it's equal to 5".
So, miners are creating candidate winning blocks by saying to the listening world, not "Look! I've done this many trillion hashes! [or struck lucky with fewer: you, the listening world, wouldn't know the difference... but this doesn't matter...]", but rather "Look! Two months ago I burned this many bitcoins!". In both cases, "this many" means an adjustable difficulty parameter, which the network adjusts from time to time (fortnightly, in today's Bitcoin) to squeeze out marginal miners (and keep more-efficient-than-marginal ones in profit) to just the extent needed to regulate block creation to a preferred pace (one per 10 minutes, in today's Bitcoin).
Why that phrase "Two months ago"? The broad principle is as follows. A miner mustn't be able to just burn some bitcoins right now and say "OK, I've burned them! Now let me have all those latest juicy transaction fees that have arrived in the past few minutes! Thanks!" That extremely recent act of burning could be undone in a block chain reorganisation; and then the same miner would be able to "re-burn" those same coins in an attempt to grab a block afresh, post-reorganisation. That would constitute a breakdown in the analogy of burning with proof-of-work hashing. A trillion proof-of-work hashes on a pre-reorg block are of no value on the post-reorg chain. A proof-of-work miner must simply shrug and say "Oh well, that's those expenses [electricity, mining rig rental / imputed rental,...] lost and gone... time to try again!" And that's the way things should be, for security - it should not be as cheap to extend the height of two or more competing chains as it is to focus on one. (And having decided to focus on one, a miner should incur a risk of lost expense if their choice turns out to be "the wrong one" in network consensus terms.)
The above point makes it clear why the act of burning should be a decent interval earlier than the act of exhibiting proof. Two months may be overdoing it, but the protocol should require it to be sufficiently far back that there's no practical possibility of it being undone. There are in fact some further issues, to do with making sure it's not cheap for a miner to re-exhibit their proof (of having performed a suitably substantial burn a suitably long time ago) on multiple competing chains. Details to follow.
Now then! How much burning will actually happen, under this protocol? The answer is straightforward enough, though its implications are quite broad and in some ways surprising. Miners will burn bitcoins at an average rate very close to the average rate that ordinary users are sending them fees (and any coin-minting still going on too of course), minus the miners' true real-resource costs (i.e. the hardware and electricity and the like for handling transactions and blocks and burn proofs - these costs will be far lower than the hashing costs incurred under proof-of-work, but of course still non-zero). This follows by the same sort of "approach to equilibrium" reasoning that tells us that miners will expend real resources on proof-of-work to roughly that extent - if they didn't, mining would be supra-normally profitable, and new entrants would be attracted into the trade. If burning coins, rather than buying a lot of kit from a mining rig supplier, is the expense incurred by a miner to compete for the revenue stream, the same economic principles apply.