Overview of alternatives Proof of Work. Part 2. Proof of Activity, Proof of Burn, Proof of Capacity and Generals
We continue to translate cool articles from the site Bytecoin.org . Today is “ Alternatives for Proof of Work, Part 2: Proof of Activity, Proof of Burn, Proof of Capacity, and Byzantine Generals ” by Ray Patterson. Part 1 can be found here .
So, the energy efficiency of the Proof of Stake is a double-edged sword. On the one hand, energy is not wasted, on the other hand, without this expenditure, the distributed consensus model looks somewhat unstable.
What other arguments can be cited? Against PoS, it is often said that this scheme “makes the rich richer”. And in fact: the one with the most coins will find the most blocks and receive the most profits by increasing the number of these coins. In fact, in this form, this charge can be expressed in the face of PoW: the one who invested the most money in iron will receive more income, it is natural.
')
But the picture starts to look different if we are talking about cryptocurrency ... where the PoS starts working from the first block. And used to issue new money. Anyone who has, say, 10% of all coins at the start, will find 10% of all blocks, and then receive 10% of the issue. That is, having bought 10 coins out of 100 possible at the beginning, it will have 100 thousand from a million over time. Not a bad deal, huh?
As you can see, the problem with PoS occurs when there is a VERY limited amount of this very limited resource - coins. Absolute values become much more important than relative values - and yet the blockchain's security model operates with relative values (“half of the network capacity must be controlled by honest participants”).
In addition, PoS does not resolve the issue of the initial distribution of coins. That is, decides - but "unfair." Until now, the accusations towards the Pure PoS-based currency NXT, where almost the entire money supply has ended up in the hands of several dozen people, are not silent
The conclusion is this: a pure PoS system is not too adapted for surviving cryptocurrency in the wild. But what if you cross it with PoW?
The standard hybrid scheme combining PoW and PoS is, in fact, implemented in very many PeerCoin clones, as well as in itself. PoW blocks are searched on a par with PoS blocks, i.e. blockchain consists of blocks of both types.
What advantages does it give? Firstly, “rewriting history” is not at all so easy, that is, PoW-blocks can serve some kind of checkpoint, given the total complexity of the work in the entire chain. Transactions that are included in blocks with "real" work inspire greater confidence in the sellers. Secondly, through the PoW blocks, “honest” emission of new money can be made, and PoS can be considered as “annual income from a deposit”.
However, the problem with nothing-on-stake still remains: you can search for PoS-blocks at any height. An idea arises: to use both approaches in the same block at the same time, in order to feed the Stake-wolf, as it were, and to save the electric sheep. The dream of these electrowaters was realized (so far only on paper) in 2014 by Iddo Bentov et al and was called the Proof of Activity (PoA).
In PoA, each unit is a joint product of both PoW and PoS miner. And the main point here is that holders come into play only after some work has been done by the PoW members. In other words, even if there is a certain owner of 50% of the coins, he cannot single-handedly manage the creation of new blocks. First, for large values of N, he has to reckon with other holders (if N = 3, then the probability of "being selected" alone is 0.5 * 0.5 * 0.5 = 12.5%). Secondly, PoW-miners can simply ignore it: that is, to “throw out” those block blanks, which enable the “monopolist” to sign blocks.
As it was said, while PoA remains only a theoretical project. It's a pity…
Of course, besides PoW and PoS, other proof-of-choose-your-name was also offered: there is always not enough evidence on the Internet.
Proof of burn works exactly as you thought: instead of burning electricity, you need to destroy digital coins. No, you do not need to format the hard disk. "Burning" occurs by sending money to an address from which it is guaranteed you can not spend it. For example, to an address that is a hash of a random number, the chances of finding the corresponding public and private keys for it are negligible.
So, getting rid of your coins in this way, you get the right to life-long mining, which is also arranged as a lottery among all owners of the burned coins. And, of course, the more you burned - the greater your chances. In fact, it’s like buying a coin for a virtual PoW iron that never goes bad. Or as a PoS-deposit, which can not be returned.
Such a method, as the author himself notes, is not suitable for the early stage of cryptocurrency development. But it is good (including from an economic point of view) to serve "in mature years", when the main money supply has already been generated.
Proof of Capacity is an implementation of the popular idea “megabytes as resources”. You do not need to burn-destroy anything, but you need to allocate a substantial amount of disk space to join the mining. In addition to the energy efficiency of such a solution, there is another point: protection from the botnet. It is quite difficult to install a miner on the victim’s computer, which would quietly grab a couple of terabytes.
The algorithm creates many large blocks of data on the disk, which are obtained by multiple hashing from your public key and random numbers. From the last block header, we get the number-index, and take in each of our large data block a small piece with this index. The more places allocated - the more pieces we have. Further as usual: the hash from the piece and the last header should be smaller than the target (taking into account the current complexity). In short, each megabyte of your HDD is an additional lottery ticket in mining.
This implementation, to put it mildly, is not perfect. First of all, there remains the problem of nothing on stake: you can instantly run through all your terabytes to check your chances in an alternative chain, as in the case of PoS. That is, simultaneously mine several chains at once, without wasting extra resources. Secondly, disk accesses take a considerable amount of time and it is probably more efficient to simply generate new chunks on the fly using simple ASIC. Then we just get the PoW algorithm.
There is also a similar concept with “megabytes” - Proof-of-Storage , but there all the participants use the allocated space as a shared cloud storage. This idea is quite interesting, but one of its description will be too large for this article. You can get acquainted with the design of the system on the site .
I suspect that there are dozens of different proof-of-look-mum-no-hands that few have heard of. Perhaps among them there are pearls.
In computer science there is a task called “ The problem of the Byzantine generals ”. It is formulated as follows:
What does this have to do with cryptocurrencies? Satoshi himself gives the answer to this : with the help of the Proof of work mechanism, generals can cope with this task (which, generally speaking, is rather difficult in practice - and for two generals it is completely unsolvable!). In fact, they need an algorithm just to establish a distributed consensus - a way to find out “how most people think”, and to make their own contribution.
In cryptocurrency, generals are network nodes, and their messages are a chain of blocks: the true is the one that is longer (more precisely, over which more work was done). There is one important note: in Satoshi’s model, we get a probabilistic solution (“if an attacker has a hashrate of x%, then he can trick the network with probability y%”), while the classical problem involves a deterministic algorithm. You can read more about the differences and the formal approach here .
Satoshi left the scene before the Proof of Stake and other alternatives appeared on it, so we hardly know his opinion on their applicability to the task of the Byzantine generals. Obviously, things are not so simple: pure PoS, as we have seen, is not as safe as pure PoW (no free lunch). Other options — hybrid protocols or very different approaches — do they cope? The question is still open.
PoW vs PoS: what else?
So, the energy efficiency of the Proof of Stake is a double-edged sword. On the one hand, energy is not wasted, on the other hand, without this expenditure, the distributed consensus model looks somewhat unstable.
What other arguments can be cited? Against PoS, it is often said that this scheme “makes the rich richer”. And in fact: the one with the most coins will find the most blocks and receive the most profits by increasing the number of these coins. In fact, in this form, this charge can be expressed in the face of PoW: the one who invested the most money in iron will receive more income, it is natural.
')
But the picture starts to look different if we are talking about cryptocurrency ... where the PoS starts working from the first block. And used to issue new money. Anyone who has, say, 10% of all coins at the start, will find 10% of all blocks, and then receive 10% of the issue. That is, having bought 10 coins out of 100 possible at the beginning, it will have 100 thousand from a million over time. Not a bad deal, huh?
As you can see, the problem with PoS occurs when there is a VERY limited amount of this very limited resource - coins. Absolute values become much more important than relative values - and yet the blockchain's security model operates with relative values (“half of the network capacity must be controlled by honest participants”).
In addition, PoS does not resolve the issue of the initial distribution of coins. That is, decides - but "unfair." Until now, the accusations towards the Pure PoS-based currency NXT, where almost the entire money supply has ended up in the hands of several dozen people, are not silent
The conclusion is this: a pure PoS system is not too adapted for surviving cryptocurrency in the wild. But what if you cross it with PoW?
Hybrid systems. Proof-of-activity
The standard hybrid scheme combining PoW and PoS is, in fact, implemented in very many PeerCoin clones, as well as in itself. PoW blocks are searched on a par with PoS blocks, i.e. blockchain consists of blocks of both types.
What advantages does it give? Firstly, “rewriting history” is not at all so easy, that is, PoW-blocks can serve some kind of checkpoint, given the total complexity of the work in the entire chain. Transactions that are included in blocks with "real" work inspire greater confidence in the sellers. Secondly, through the PoW blocks, “honest” emission of new money can be made, and PoS can be considered as “annual income from a deposit”.
However, the problem with nothing-on-stake still remains: you can search for PoS-blocks at any height. An idea arises: to use both approaches in the same block at the same time, in order to feed the Stake-wolf, as it were, and to save the electric sheep. The dream of these electrowaters was realized (so far only on paper) in 2014 by Iddo Bentov et al and was called the Proof of Activity (PoA).
How does PoA work
PoA works quite simply:
Remarks:
- First, the PoW miner works: looking for a hash that satisfies the complexity ... everything is as usual.
- Having found such a hash, it sends all the data to the network, but this is not yet a block, but only a “stub”. There may be several such blanks.
- The hash of the block (256 pseudo-random bits) is interpreted as N numbers. Each number clearly corresponds to some Satoshi (for example, if we number all the emitted coins from the first block).
- Each Satoshi, in turn, is associated with a single public key of its current owner. That is, we have identified so N owners.
- The “stock” of the block turns into a full-fledged block as soon as all N owners put their signatures on this block (with the keys defined in step 4).
- If one of the signers is unavailable at this moment (or does not participate in mining for personal reasons), it does not matter. PoW-miners continue their work, generating all the new “blanks” with different sets of candidate holders.
- Sooner or later (depending on the percentage of participants online), a block will be signed N times. The block award is distributed between the PoW miner and all N holders.
Remarks:
- The protocol obviously requires constant data exchange. To reduce traffic, the “stocking” of the block does not include a list of transactions. They are recruited by the last holder, finalizing the block.
- If N = 3, and about 10% of users are online, then it is obvious that, on average, PoW miners will produce about 10 * 10 * 10 = 1000 “blanks” until some one is signed. But with a message size of the order of a hundred bytes, this is irrelevant.
In PoA, each unit is a joint product of both PoW and PoS miner. And the main point here is that holders come into play only after some work has been done by the PoW members. In other words, even if there is a certain owner of 50% of the coins, he cannot single-handedly manage the creation of new blocks. First, for large values of N, he has to reckon with other holders (if N = 3, then the probability of "being selected" alone is 0.5 * 0.5 * 0.5 = 12.5%). Secondly, PoW-miners can simply ignore it: that is, to “throw out” those block blanks, which enable the “monopolist” to sign blocks.
As it was said, while PoA remains only a theoretical project. It's a pity…
A bit of exotic
Of course, besides PoW and PoS, other proof-of-choose-your-name was also offered: there is always not enough evidence on the Internet.
Proof of burn works exactly as you thought: instead of burning electricity, you need to destroy digital coins. No, you do not need to format the hard disk. "Burning" occurs by sending money to an address from which it is guaranteed you can not spend it. For example, to an address that is a hash of a random number, the chances of finding the corresponding public and private keys for it are negligible.
So, getting rid of your coins in this way, you get the right to life-long mining, which is also arranged as a lottery among all owners of the burned coins. And, of course, the more you burned - the greater your chances. In fact, it’s like buying a coin for a virtual PoW iron that never goes bad. Or as a PoS-deposit, which can not be returned.
Such a method, as the author himself notes, is not suitable for the early stage of cryptocurrency development. But it is good (including from an economic point of view) to serve "in mature years", when the main money supply has already been generated.
Proof of Capacity is an implementation of the popular idea “megabytes as resources”. You do not need to burn-destroy anything, but you need to allocate a substantial amount of disk space to join the mining. In addition to the energy efficiency of such a solution, there is another point: protection from the botnet. It is quite difficult to install a miner on the victim’s computer, which would quietly grab a couple of terabytes.
The algorithm creates many large blocks of data on the disk, which are obtained by multiple hashing from your public key and random numbers. From the last block header, we get the number-index, and take in each of our large data block a small piece with this index. The more places allocated - the more pieces we have. Further as usual: the hash from the piece and the last header should be smaller than the target (taking into account the current complexity). In short, each megabyte of your HDD is an additional lottery ticket in mining.
This implementation, to put it mildly, is not perfect. First of all, there remains the problem of nothing on stake: you can instantly run through all your terabytes to check your chances in an alternative chain, as in the case of PoS. That is, simultaneously mine several chains at once, without wasting extra resources. Secondly, disk accesses take a considerable amount of time and it is probably more efficient to simply generate new chunks on the fly using simple ASIC. Then we just get the PoW algorithm.
There is also a similar concept with “megabytes” - Proof-of-Storage , but there all the participants use the allocated space as a shared cloud storage. This idea is quite interesting, but one of its description will be too large for this article. You can get acquainted with the design of the system on the site .
I suspect that there are dozens of different proof-of-look-mum-no-hands that few have heard of. Perhaps among them there are pearls.
Mathematical complement: what have the generals to do with it?
In computer science there is a task called “ The problem of the Byzantine generals ”. It is formulated as follows:
Byzantium. On the night before the great battle, the Byzantine army contains n legions. Each of them submits to his general. The whole Byzantine army has a commander in chief, leading the generals. The empire is in decline, and among the generals, including the commander in chief, there may be traitors. Throughout the night, each of the generals receives from the leader an order for action in the morning. This can be one of two options: “attack” or “retreat”. If all honest generals are attacking, they will win. If everyone retreats - they will be able to save the army. If a part attacks, and a part retreats - they suffer a defeat. If the commander in chief is a traitor, he can give different orders to different generals, therefore, his orders should not be carried out without question. If every general acts independently of the others, the results of the battle can also be disastrous. Therefore, generals need to exchange information with each other in order to come to an agreement.
What does this have to do with cryptocurrencies? Satoshi himself gives the answer to this : with the help of the Proof of work mechanism, generals can cope with this task (which, generally speaking, is rather difficult in practice - and for two generals it is completely unsolvable!). In fact, they need an algorithm just to establish a distributed consensus - a way to find out “how most people think”, and to make their own contribution.
In cryptocurrency, generals are network nodes, and their messages are a chain of blocks: the true is the one that is longer (more precisely, over which more work was done). There is one important note: in Satoshi’s model, we get a probabilistic solution (“if an attacker has a hashrate of x%, then he can trick the network with probability y%”), while the classical problem involves a deterministic algorithm. You can read more about the differences and the formal approach here .
Satoshi left the scene before the Proof of Stake and other alternatives appeared on it, so we hardly know his opinion on their applicability to the task of the Byzantine generals. Obviously, things are not so simple: pure PoS, as we have seen, is not as safe as pure PoW (no free lunch). Other options — hybrid protocols or very different approaches — do they cope? The question is still open.
Source: https://habr.com/ru/post/266619/
All Articles