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.
Technical sketch of proof of burn: "Burnt coins are mining rigs!"
The key insight is that verifiably, publicly burning some coins of a known-total-stock-issued currency is the same as "remurrage" (opposite of "demurrage" - it may not be a correct word, but it's a nice back-formation) on the remainder. That is, if there are verifiably 21 million issued-and-not-burned coins, and then you go to sleep and wake up later and there are now only 20 million issued-and-not-burned coins, that's the same as if some magic genie multiplied all wake-up-time nominal bitcoin figures by 21/20. Another way to see the identity of real effect would be to redefine "burning n bitcoins" to mean, not "sending n to an unspendable address", but rather "scattering" the n bitcoins, i.e. sending them to every existing [non-zero-balance] address, in proportion to the balance [sum of unspent txouts] already stored in each. This would be a horribly gigantic transaction to actually do explicitly, but the point is, burning can be thought of "as if" done that way. (Slogan: Quantity-deflation is remurrage in disguise, in exactly the same way that quantity-inflation is demurrage in disguise.)
So, what that means is, if while you're sleeping you (a non-miner) hold 1 bitcoin purely passively, i.e. it just sits undisturbed on the blockchain, well, when you wake up, it's as if you've received a "dividend" (of 5% in the particular numeric example above) on top of the general economy-tracking price we expect of a constant-quantity currency. In a world with actual, visibly performed remurrage, this is made explicit - your balance is now 21/20, with the nominal circulation [issued-and-not-burned, and remurraged for good measure] constant at 21 million. You can go and spend the 1/20 "dividend" on some treat, and still have the same fraction (1 out of 21 million) of the money stock as when you went to sleep.
In a world without any attempt at explicit remurrage, the real facts of the situation are (of course!) the same, but their nominal expression is not perhaps so instantly obvious. Your nominal holding is unchanged at 1; but this is now 1 part in 20 million of the whole money stock, not the 1 part in 21 million it was before. So, you can go and spend 1/21 of it on some treat, taking your nominal balance down to 20/21, and that nominal balance is the same (1 out of 21 million) fraction of the money stock as when you went to sleep.
So, basically, if you're holding bitcoins and trying to hold an "economy-tracking amount", no more and no less, you find you can go out into the market and use the fraction of your holdings that counts as "dividend above and beyond economy-tracking" on some treat or other. (Indeed, "you can go out..." should read "you must go out...", if you're really determined to pursue precisely that tracking strategy.)
Who's selling you the real resources embodied in the "treat"? And what's their motive? Well, transaction fee payers presumably like to re-stock their bitcoin real balances to roughly the same [economy-tracking] level as before, on average - they're paying for the fee processing as a service. These fees are then burned by miners. (Well, not literally the fees themselves - the fees themselves are collected by miners, but the way they achieve this is to burn an approximately equal amount, as explained earlier.) So, ordinary Bitcoin users, to achieve their desired re-stocking, have to either produce slightly more, or consume slightly less, or a proper or improper mixture thereof, than they would have needed to in a hypothetical (presumably impracticable) alternative world where they pay no fees for their everyday transactions (and some magic mining-god just altruistically and reliably creates a blockchain out of all the transactions, without charging anybody anything). [This follows directly from their re-stocking desire, and has nothing to do with proof-of-burn specifically. That is, they have to do this regardless of whether the protocol is proof-of-work, proof-of-stake, proof-of-burn or whatever.] It's that extra gap between production and consumption - "extra" on top of whatever gap people are already choosing as a real saving[/dis-saving] strategy - that goes on to the market, for you and all other bitcoin holders to bid off the market by spending on your "treat".
This whole stable pattern of spending habits is, perhaps surprisingly, the same pattern of real resource allocation as would have happened if Cunicula's proof of stake (with close to 100% stake / 0% work admixture) had been in operation, and all bitcoin holders, large and small, had enthusiastically thrown their bitcoins (that is, their stream of bitcoin days destroyed) into the stake-claiming process. The fraction of fees they'd collect if they did that would be just like the "dividend" as I called it above - it would be like explicit remurrage, except instead of being automatic, it would require each holder's active participation (i.e. they couldn't just go to sleep, unless they left some sort of "trusted bot" running and using their private keys to sign their stream of bitcoin days destroyed). So, if you like, proof-of-burn is like automated, 100%-stakeholder-participation Cunicula-style proof-of-stake!