Alternatives for Proof of Work, Part 2: Proof of Activity, Proof of Burn, Proof of Capacity, and Byzantine Generals
This is a guest post by Ray Patterson.
This blog post continues the series of articles on how various cryptocurrencies work. In the previous part we've given the overview on how Proof of Stake is different from Proof of Work and what issues its design causes. To learn more about how various Proof of Work algorithms work, check out "History of Proof of Work" post.
Proof of Work vs Proof of Stake: what else?
To sum up the arguments of the previous post, the energy efficiency of Proof of Stake is a double-edged sword. On the one hand, the energy is not spent, on the other, the decentralized consensus model seems unstable without these expenses.
What other reasoning can be found? The opinion that Proof of Stake "makes the rich even richer" has been expressed more than time. Indeed, the one who has more coins than others, will find blocks more often and get the largest profit by increasing the number of these coins. Actually, the same stands true for PoW: the one who invested most money in the hardware, gets the largest profit. It is natural.
However, things start to look different if we talk about a cryptocurrency that utilizes Proof of Stake from the first block and uses it to ensure emission. For example, the owner of 10% of all coins in the beginning, will be finding 10% of all blocks, i.e. receive 10% of the coins emitted. That is, if you buy 10 coins of 100 existing in the very beginning, you will have 100 thousand out of a million after some time passes. A good deal, indeed.
As you see, the problem with Proof of Stake arises when amount of the limited resources (coins) in the system is EXTREMELY limited. Absolute values become more important than relative, while blockchain security model operates with relative values by design ("half of the network powers should be controlled by the honest users").
Besides, Proof of Stake does not solve the issue of initial coins distribution. Well, it does, but "unjustly". There are still accusations of the pure proof-of-stake-based cryptocurrency NXT, as almost the whole stock of coins is allegedly distributed between a few dozens of people.
The conclusion is as follows: pure Proof-of-Stake system is not adjusted to surviving in the wild cryptocurrencies' environment. But what about "breeding" it with Proof of Work?
Hybrid systems. Proof of Activity
A standard hybrid scheme combining Proof of Work and Proof of Stake is practically implemented both in many clones of PeerCoin and in PeerCoin itself. The Proof-of-Work blocks are searched at the same time with the Proof-of-Stake blocks, i.e. blockchain includes both types of blocks.
What benefits does this system have? First of all, "rewriting the history" is significantly harder, i.e. Proof of Work blocks can serve as some kind of checkpoints, accounting for the total complexity of work in the whole chain. Transactions in the 'real work'-blocks are more credible from the sellers' point of view. Second, the Proof-of-Work blocks may be used for "honest" emission, and Proof of Stake may be regarded as "annual deposit income".
Still, the nothing-on-stake problem remains: you can search for Proof-of-Stake blocks on any level. Then the idea of using both approaches in a single block appears, in order to eat the Stake-cake and have the electric one. The dream of such electric cakes has been realized (but only on paper) in 2014 by Iddo Bentov et al, who called it Proof of Activity.
Proof of Activity operating principle
Proof of Activity operation is quite simple:
- First, the proof-of-work miner works, searching for the hash conforming with complexity... i.e. everything is as usual;
- Then, when the hash is found, miner transmits all data to the network, but it is still not a block. It is but a template. A number of such templates might appear.
- The block hash (256 pseudorandom bits) is interpreted as N numbers. Each number corresponds to some satoshi (e.g. if we number all emitted coins starting with the first block);
- Each satoshi, in its turn, corresponds to a single public key of its current owner. This way we define N random owners;
- The block "template" becomes a full-fledged block as soon as all N owners sign it (with the keys defined in step 4);
- If one of the signers is unavailable (or does not mine on personal considerations) - no problem. Proof-of-work miners keep working, generating new "templates" with different sets of signers-candidates;
- Sooner or later (depending on the percentage of users online) some block will be signed N times. The block-reward is shared between proof-of-work-miner and N signers.
- The protocol seems to require continuous data exchange. In order to reduce traffic, the block "template" does not include the transaction list. It is added by the last signer, when finalizing the block;
- If N=3 and only 10% of the users are online, then, obviously, proof-of-work miners will generate approximately 10*10*10 = 1000 "templates" before one of them is signed. However, if message size is about a hundred bytes, it is insignificant.
In Proof of Activity, each block is a product of combined effort of Proof-of-Work and Proof-of-Stake miners. The main point here is the fact that the signers only cut in after some work has been done by Proof-of-Work participants. In other words, even if some owner of 50% of all coins exists, he cannot control creation of new blocks on his own. First, when N is large, he has to consider other signers (if N = 3, his probability to be selected individually is 0.5*0.5*0.5 = 12.5%). Second, Proof-of-Work miners can simply ignore him, i.e. "throw away" the templates that allow the "monopolist" to sign the blocks.
As we mentioned, Proof of Activity is, for now, but a theory. Well, that is unfortunate...
A bit of exotica: Proof of Burn, Proof of Capacity
Naturally, Proof of Work and Proof of Stake were not the only proof-of-choose-your-names: you always do not have enough proof in the Internet.
Proof of Burn works exactly the way you thought: instead of burning electricity you should destroy your digital coins. No, you do not have to format your hard drive. You "burn" them by sending to such address where they cannot be redeemed. For example, to the address, which is a hash of a random number: chances for someone picking public and private keys for it are negligible.
Thus, by 'throwing away' your coins, you get the rights for life-time mining, which is a lottery among the owners of burnt coins. Naturally, the more you burn, the higher your chances. It is like buying a virtual Proof-of-Work hardware, which never degrades. Or as a Proof-of-Stake deposit you cannot get back.
This way, as the author himself notes, does not fit the early stage of cryptocurrency evolution. But it fits perfectly (from financial point of view as well) for "mature" period, when the majority of coins has been emitted.
Proof of Capacity is an implementation of a popular idea of "megabytes as resources". You do not have to burn anything, but you have to allocate significant volume of the hard drive space to start mining. Besides being energy efficient, this approach also provides botnet protection. It is quite hard to install on victim's PC a miner, which would secretly steal a couple terabytes.
The algorithm creates vast number of large chunks of data known as 'plots' by repeatedly hashing your public key and nonces. The last block header gives us the index number, which we us to take from each plot a scoop with this index. The more space we allocated, the more scoops we have. Then everything goes as usual: hash of the scoop and the last header should be less than some target (considering current difficulty). To cut it short, each your HDD megabyte is an additional lottery ticket in mining.
Such implementation is, putting it mildly, not ideal. First, there still is a problem of nothing on stake: you can momentarily scan all your terabytes to try your chances in alternative chain, like with Proof of Stake. It means that you can mine a number of alternate chains simultaneously without spending resources. Second, disk access takes significant time, so it might be more efficient to generate new chunks on the fly, using a simple ASIC. But then we get a simple Proof-of-Work algorithm.
There is a parallel concept with "megabytes", Proof of Storage, but the designated space in it is used by all participants as common cloud storage. The idea is quite interesting, but its description is too big to put it in this article. You can look at the design of the system on its website.
I believe there are dozens of different proof-of-look-mum-no-hands, known to only few people. Probably, there are pearls among them. I hope that readers would not regard me as a swine for omitting them.
Mathematical appendix: what does the Byzantine Empire have to do with all this?
In computer science, there is a problem called "Byzantine fault tolerance". It is stated as follows:
The objective of Byzantine fault tolerance is to be able to defend against Byzantine failures, in which components of a system fail with symptoms that prevent some components of the system from reaching agreement among themselves, where such agreement is needed for the correct operation of the system. Correctly functioning components of a Byzantine fault tolerant system will be able to provide the system's service assuming there are not too many faulty components.
What does it have to do with cryptocurrencies? Satoshi answers this question: using the Proof-of-Work mechanism, the generals can solve this problem (which is actually very hard in practice and completely insolvable for two generals!) as they need, in fact, a mechanism for decentralized consensus as a way to find out what the majority thinks and contribute themselves.
In cryptocurrency, the generals are network nodes, their messages are a chain of blocks. The true one is the longest (the one that appeared as a result of more work). There is an important note though: in Satoshi's model we get a random solution (if an attacker has hashrate of x%, he can fool the network with a probability of y%), while the classical problem implies determined algorithm. More details about the differences and the formal approach are available here.
Satoshi left the stage before Proof of Stake and other alternatives emerged, so we can hardly find out his opinion on their applicability to the Byzantine fault tolerance problem. Obviously, it is not quite simple: pure Proof of Stake is not as safe as pure Proof of Work (no free lunch). Other options, be it hybrid protocols or other approaches, can they manage this? The question is still open.
The images are taken from "Fictitious and Symbolic Creatures in Art", by John Vinycomb, 1909.