Consensus Algorithms: Proof of Share and Proof of Work
Blockchain is a distributed system in which there can be thousands of participants. Unlike conventional distributed databases, the blockchain almost always lacks a central administrator who configures network nodes, so it turns out that the blockchain's architecture is not just distributed, but decentralized . In this regard, for the blockchain, the task of distributed consensus is urgent:
“How can the nodes of the network achieve the same point of view on the blockchain's transaction log in a distributed network, provided that arbitrary nodes can“ fall ”or hang, guided only by the general rules for processing messages in the network?”
How consensus is achieved in blockchains, we will talk in our today's material.
')
/ image jgbarah CC
In any blockchain network , two basic types of messages are transmitted — transactions and blocks (which, in turn, are lists of transactions). Transactions are formed by the participants of the system and their consensus algorithm does not concern: in order to initiate, say, sending bitcoins, no agreement is needed, it is enough to know the correct key . Blocks are another matter. They are the main product of the consensus algorithm and determine the order in which transactions will be included in the transaction log.
Why do we need these difficulties? It turns out that without coordination between network nodes it is possible to re- spend double spending . Suppose Eva has 1 bitcoin. She can form two transactions, according to which this bitcoin passes to Alice and Bob. If Alice and Bob do not agree on their transaction history at all, both of them will accept Eva’s payment, since the transactions will be signed by Eva’s electronic signature, and before the transaction was completed, Eva actually had this bitcoin! Therefore, network members need to negotiate transaction logs. Then only one of Eve’s transactions will succeed, and the second will become incorrect — Eva’s funds will already be spent.
Is it possible to do without blocks, including transactions in the log separately? Theoretically, yes, but in practice, blocks save traffic and computing resources of network nodes. In addition, they have other advantages in the context of specific consensus algorithms - it turns out that with too frequent blocks, the work of the blockchain becomes unstable.
Blocks are created by a special category of blockchain nodes - the so-called consensus nodes. In the case of bitcoin and other cryptocurrencies, these nodes are called miners, since they are rewarded for their work (mining) by generating new portions of cryptocurrency. Miners are actively involved in the formation of the blockchain, constantly grouping incoming transactions into blocks and distributing them throughout the network.
The second type is audit nodes. They do not participate in the consensus process, but they have a full copy of the blockchain. “Auditors” regularly check the work of miners and are engaged in load distribution over the network, performing the function of a kind of content delivery network (CDN) for blockchain data.
The third type of nodes is light clients. They are called light because they do not have the full version of the blockchain and contain only the data that is important for the site. For this reason, they are a good option for the organization of a cryptocurrency wallet - the client will not give the whole picture of the network, but will allow to effectively track the user's balance. Light clients require less computational resources and memory, so they can work on mobile platforms.
/ Roles of nodes in the blockchain network. Consensus nodes and end customers can be “fenced off” from each other.
Bitcoin blockchain is one of the largest blockchains. According to bitnodes, on April 8, 2017, 7025 nodes with a full copy of the blockchain were observed in the bitcoin network. Most of these are audit nodes; There are not many productive miners in the network - a few dozen. Note that the number of nodes is several times less than the number of participants in the Bitcoin network (of which more than 13 million). This happens because users are not required to store a local copy of the blockchain to send transactions - it is enough to keep the private keys with which transactions are signed.
The task of distributed consensus is not specific to blockchains and has well proven solutions for many other distributed systems (for example, NoSQL databases). Even the task of consensus, in which nodes can behave "in a bad way" - the task of the Byzantine consensus - was first formulated in the 80s of the last century, and methods for its solution appeared in the late 90s.
But bitcoin and other blockchains differ from previous developments in network operation conditions. In conventional Byzantine consensus algorithms, network nodes have “identities” expressed through digital signatures or similar crypto primitives, and the list of nodes is known in advance or changes rarely, but predictably. In the bitcoin blockchain, the opposite is true.
Network members are not only unknown in advance, but can also be freely connected or disconnected from the network. At the same time, the blockchain, being a decentralized system, has certain properties: resistance to censorship (no one can forbid to mine cryptocurrency) and objectivity (to determine the current version of the transaction log, there is no need to trust certain authoritative sources - the root of trust is in the blockchain itself).
Because of this, the usual algorithms of the Byzantine consensus for the blockchain are not suitable. Therefore, many different algorithms have been proposed, among which there are two main categories: algorithms based on proof of work and share proof algorithms.
The proof of work was “invented” long before Bitcoin back in the early 90s and was used in a different context: to protect against spam. For example, one version of the proof of work ( Hashcash ) was proposed by the English cryptographer Adam Back (Adam Back), who is now the CEO of one of the largest blockchain startups .
In the case of proof of operation, the message hash combined with a special field ( nonce ) must be less than a certain value (or start with a certain number of zero bits). Nonce does not make sense for the message itself - this field is searched by the author of the proof until a suitable value is found. The title “proof of work” reflects the fact that in order to find a nonce, it is necessary to perform computational work, the expected amount of which is measurable. For example, if it is necessary for the first 16 bits of the hash to be zero, then on average, 65,536 nonce values should be iterated.
You can illustrate this with a Python program :
The specification of the expected amount of work is important. Theoretically, with strong luck, a suitable nonce can be found very quickly. If the program above is run with the message “Bl0Ckchain”, then it turns out that the value of nonce is 6571, which is ten times less than expected. Therefore, looking at the proof of work, we can only estimate the resources spent on it, however, for the high complexity of the proof (that is, the expected amount of work done) this estimate will be sufficiently accurate.
The proof of operation is similar to digital signatures - it ensures the integrity of the message, since the likelihood that the same nonce is suitable for different messages is very small. Evidence is also easily verified — just a single hash operation is enough. Unlike signatures, creating proof of work does not require knowledge of secrets, but “consumes” more computational resources. For example, in the above proof of work for a 32-bit blockchain message, it takes several hours of computation on an ordinary personal computer, but this proof is checked almost instantly.
Using PoW for consensus is perhaps the biggest innovation of the original bitcoin article. The corresponding consensus algorithm has received quite an academic name - the Nakamoto consensus. Satoshi (the author or authors of the article) proposed “signing” each block created by proof of work, the complexity of which depends on the total computational complexity of the Bitcoin network. This approach has several advantages:
The evidence of work is used by Bitcoin nodes to determine the state of the system. The actual transaction log is defined as a chain of blocks with the highest total complexity of evidence of work. Miners, respectively, should look for a block on top of this chain. But, theoretically, no one forbids creating new blocks on the basis of some old block (splitting sometimes happens - forks - blockchains, because two miners find a new block almost simultaneously). However, intentional forks are unprofitable economically, because the blocks from the side branches of the blockchain are not taken into account by anyone and do not bring any profit to their creators - just the cost of finding proof of work.
The Nakamoto Consensus provides two key blockchain requirements that we outlined earlier. Due to the fact that proof of work is not tied to the personalities of miners (as opposed to digital signatures / certificates), censorship resistance is ensured. And due to the fact that the evidence of the work is quickly checked and does not require anything to check except the blockchain, the objectivity of the protocol is achieved.
Nakamoto's consensus is resistant to attacks on the blockchain network, and its security has been studied theoretically quite well (unlike newer proposals for blockchains). The original article noted that the Bitcoin network will continue to function adequately, even if half of the miners begin malicious activity. If a malicious majority (the so-called 51% attack) appears among the miners, they will be able to ignore the blocks from all the other miners in order to pick up their entire reward on the network, or, for example, to cheat, re-spending money due to intentional forks of the blockchain. However, we note that even if all the miners in the network conspire, they will not be able to bypass the basic bitcoin security mechanisms — for example, they will not be able to steal the bitcoins of users.
Bitcoin is the most powerful network using proof of work. In one second, Bitcoin miners calculate more than three quintillion (3 ∙ 1018) hashes. 32-bit proof (which is calculated on a computer for several hours) is the minimum complexity in Bitcoin, which could be observed only at the very beginning of the network. This is due to the fact that the complexity of the proof is automatically adjusted so that the bitcoin network finds an average of one block in 10 minutes. As the network hashrate increases, so does the complexity - now the complexity of one proof is about 70 bits. Accordingly, the hex hash block entry should start with 17 zeros.
/ The power of the bitcoin network is growing exponentially. This provides a high network attack cost.
The Nakamoto consensus has a property that is perceived by many as a major flaw - to ensure safety, one must “work”, that is, produce proof of work. The calculations that are performed as part of PoW serve no useful purpose, and this is an architectural feature. It turns out that it is very difficult to come up with a proof of work that would perform a socially useful role. Therefore, it may seem that resources (first of all, electricity) are spent on mining for nothing (except for the fact that they are spent on security).
In addition, mining is still subject to the problem of centralization. More than 70% of bitcoin hashrate is currently located in one country - China. Many cryptocurrencies are trying to decentralize mining through the use of evidence of work, which is economically unprofitable to calculate on specialized equipment, but with this approach another problem arises - if you make Bitcoin mining profitable using home computers, then renting equipment to attack (or create a botnet for it) Much cheaper and easier.
Trying to solve these problems, the community offers many consensus algorithms that do not require “work”. The most popular category of such algorithms is based on proof-of-stake, PoS. The proof of a share is similar to the proof of work, but instead of performing a certain work, the author shows that he has a share in the system (for example, in the form of a non-zero cryptocurrency balance). It turns out that for mining with PoS, it is enough to “stock up” with cryptocurrency, after which you just get “interest” from it.
However, proof of share has an unpleasant disadvantage compared to PoW: since the proof of share is not based on the real world (computational power), but on something inside the blockchain itself (cryptocurrency balance), the task of building a reliable PoS algorithm turns out to be nontrivial.
In the simplest versions of the PoS consensus, problems arise with basic properties. It turns out that in them the most cost-effective behavior is reproduction of the forks of the blockchain to re-expend funds. More sophisticated proofs of share were created, with no obvious security holes; such algorithms return to the consensus the factor of economic responsibility at the expense of the obligatory pledge, which is confiscated in case of incorrect behavior of the participant.
The cryptographic community still has doubts about the possibility of robust algorithms with proof of proportion. It is possible that the planned transition to proof of Ethereum’s blockchain share, the second-largest public blockchain in the market, will dot the i.
In addition to proving a stake, blockchain enthusiasts are experimenting with other proof-of-* algorithms. For example, Bram Cohen, the creator of the BitTorrent protocol, recently suggested using proof of local-file storage (proof-of-space) for consensus in blockchains, that is, replacing the processing power in PoW with disk space. However, in terms of maturity, such initiatives are even more behind the proof of work algorithms than proof-of-stake.
PS And here is a small selection of our materials:
“How can the nodes of the network achieve the same point of view on the blockchain's transaction log in a distributed network, provided that arbitrary nodes can“ fall ”or hang, guided only by the general rules for processing messages in the network?”
How consensus is achieved in blockchains, we will talk in our today's material.
')
/ image jgbarah CCStructure and nodes of blockchain networks
In any blockchain network , two basic types of messages are transmitted — transactions and blocks (which, in turn, are lists of transactions). Transactions are formed by the participants of the system and their consensus algorithm does not concern: in order to initiate, say, sending bitcoins, no agreement is needed, it is enough to know the correct key . Blocks are another matter. They are the main product of the consensus algorithm and determine the order in which transactions will be included in the transaction log.
Why do we need these difficulties? It turns out that without coordination between network nodes it is possible to re- spend double spending . Suppose Eva has 1 bitcoin. She can form two transactions, according to which this bitcoin passes to Alice and Bob. If Alice and Bob do not agree on their transaction history at all, both of them will accept Eva’s payment, since the transactions will be signed by Eva’s electronic signature, and before the transaction was completed, Eva actually had this bitcoin! Therefore, network members need to negotiate transaction logs. Then only one of Eve’s transactions will succeed, and the second will become incorrect — Eva’s funds will already be spent.
Is it possible to do without blocks, including transactions in the log separately? Theoretically, yes, but in practice, blocks save traffic and computing resources of network nodes. In addition, they have other advantages in the context of specific consensus algorithms - it turns out that with too frequent blocks, the work of the blockchain becomes unstable.
Blocks are created by a special category of blockchain nodes - the so-called consensus nodes. In the case of bitcoin and other cryptocurrencies, these nodes are called miners, since they are rewarded for their work (mining) by generating new portions of cryptocurrency. Miners are actively involved in the formation of the blockchain, constantly grouping incoming transactions into blocks and distributing them throughout the network.
The second type is audit nodes. They do not participate in the consensus process, but they have a full copy of the blockchain. “Auditors” regularly check the work of miners and are engaged in load distribution over the network, performing the function of a kind of content delivery network (CDN) for blockchain data.
The third type of nodes is light clients. They are called light because they do not have the full version of the blockchain and contain only the data that is important for the site. For this reason, they are a good option for the organization of a cryptocurrency wallet - the client will not give the whole picture of the network, but will allow to effectively track the user's balance. Light clients require less computational resources and memory, so they can work on mobile platforms.
Bitcoin blockchain is one of the largest blockchains. According to bitnodes, on April 8, 2017, 7025 nodes with a full copy of the blockchain were observed in the bitcoin network. Most of these are audit nodes; There are not many productive miners in the network - a few dozen. Note that the number of nodes is several times less than the number of participants in the Bitcoin network (of which more than 13 million). This happens because users are not required to store a local copy of the blockchain to send transactions - it is enough to keep the private keys with which transactions are signed.
Consensus
The task of distributed consensus is not specific to blockchains and has well proven solutions for many other distributed systems (for example, NoSQL databases). Even the task of consensus, in which nodes can behave "in a bad way" - the task of the Byzantine consensus - was first formulated in the 80s of the last century, and methods for its solution appeared in the late 90s.
But bitcoin and other blockchains differ from previous developments in network operation conditions. In conventional Byzantine consensus algorithms, network nodes have “identities” expressed through digital signatures or similar crypto primitives, and the list of nodes is known in advance or changes rarely, but predictably. In the bitcoin blockchain, the opposite is true.
Network members are not only unknown in advance, but can also be freely connected or disconnected from the network. At the same time, the blockchain, being a decentralized system, has certain properties: resistance to censorship (no one can forbid to mine cryptocurrency) and objectivity (to determine the current version of the transaction log, there is no need to trust certain authoritative sources - the root of trust is in the blockchain itself).
Because of this, the usual algorithms of the Byzantine consensus for the blockchain are not suitable. Therefore, many different algorithms have been proposed, among which there are two main categories: algorithms based on proof of work and share proof algorithms.
Proof of Work - PoW
The proof of work was “invented” long before Bitcoin back in the early 90s and was used in a different context: to protect against spam. For example, one version of the proof of work ( Hashcash ) was proposed by the English cryptographer Adam Back (Adam Back), who is now the CEO of one of the largest blockchain startups .
In the case of proof of operation, the message hash combined with a special field ( nonce ) must be less than a certain value (or start with a certain number of zero bits). Nonce does not make sense for the message itself - this field is searched by the author of the proof until a suitable value is found. The title “proof of work” reflects the fact that in order to find a nonce, it is necessary to perform computational work, the expected amount of which is measurable. For example, if it is necessary for the first 16 bits of the hash to be zero, then on average, 65,536 nonce values should be iterated.
You can illustrate this with a Python program :
import itertools from hashlib import sha256 # little-endian to_long = lambda x: sum(ord(b) << (8*i) for i, b in enumerate(x)) # nonce . combine = lambda nonce, msg: str(nonce) + ":" + msg # def verify_pow(msg, nonce, difficulty): h = sha256(combine(nonce, msg)).digest() # difficulty ? return to_long(h) % (1 << difficulty) == 0 # def create_pow(msg, difficulty): for nonce in itertools.count(0): if verify_pow(msg, nonce, difficulty): return nonce msg = "blockchain" nonce = create_pow(msg, 16) combine(nonce, msg), sha256(combine(nonce, msg)).hexdigest() #43952:blockchain 000027b5022f88d2da21bd2802268966050f5a0b031058ce4562939c13727303 The specification of the expected amount of work is important. Theoretically, with strong luck, a suitable nonce can be found very quickly. If the program above is run with the message “Bl0Ckchain”, then it turns out that the value of nonce is 6571, which is ten times less than expected. Therefore, looking at the proof of work, we can only estimate the resources spent on it, however, for the high complexity of the proof (that is, the expected amount of work done) this estimate will be sufficiently accurate.
The proof of operation is similar to digital signatures - it ensures the integrity of the message, since the likelihood that the same nonce is suitable for different messages is very small. Evidence is also easily verified — just a single hash operation is enough. Unlike signatures, creating proof of work does not require knowledge of secrets, but “consumes” more computational resources. For example, in the above proof of work for a 32-bit blockchain message, it takes several hours of computation on an ordinary personal computer, but this proof is checked almost instantly.
sha256("5263268363:blockchain") = 000000007cf39dfc8fccae534b39b5f362c16891abca02d0e7b1dbd5a129ee17 PoW and consensus
Using PoW for consensus is perhaps the biggest innovation of the original bitcoin article. The corresponding consensus algorithm has received quite an academic name - the Nakamoto consensus. Satoshi (the author or authors of the article) proposed “signing” each block created by proof of work, the complexity of which depends on the total computational complexity of the Bitcoin network. This approach has several advantages:
- Nakamoto's consensus solves the main scourge of anonymous networks - Sibylla’s attacks , in which an attacker creates a bunch of fake nodes in order to “crush” the opinion of honest users with the resulting majority. To have an opinion in the Nakamoto consensus, you need to have real computing power that can not be faked, and which does not require any additional authentication - it itself binds the nodes to the real world.
- The proof cannot be forged and “transferred” to other blocks. Thus, miners cannot steal evidence from each other.
- Moreover, evidence cannot be prepared for future use - each block contains a link to the previous one, therefore, one can start working on evidence only after the appearance of the previous block in the network.
- Proofs of work provide honesty - each miner's reward is proportional to his computing power (hashrate). If the miner has a 10% hashrate of the entire network, then he will create an average of 10% of blocks and receive a 10% reward.
- Since real resources are being spent on creating evidence (which in the case of Bitcoin are measured in thousands of dollars per minute), miners have a completely new incentive to act within the framework of the protocol - dishonest behavior immediately deprives them of real money.
The evidence of work is used by Bitcoin nodes to determine the state of the system. The actual transaction log is defined as a chain of blocks with the highest total complexity of evidence of work. Miners, respectively, should look for a block on top of this chain. But, theoretically, no one forbids creating new blocks on the basis of some old block (splitting sometimes happens - forks - blockchains, because two miners find a new block almost simultaneously). However, intentional forks are unprofitable economically, because the blocks from the side branches of the blockchain are not taken into account by anyone and do not bring any profit to their creators - just the cost of finding proof of work.
The Nakamoto Consensus provides two key blockchain requirements that we outlined earlier. Due to the fact that proof of work is not tied to the personalities of miners (as opposed to digital signatures / certificates), censorship resistance is ensured. And due to the fact that the evidence of the work is quickly checked and does not require anything to check except the blockchain, the objectivity of the protocol is achieved.
Nakamoto's consensus is resistant to attacks on the blockchain network, and its security has been studied theoretically quite well (unlike newer proposals for blockchains). The original article noted that the Bitcoin network will continue to function adequately, even if half of the miners begin malicious activity. If a malicious majority (the so-called 51% attack) appears among the miners, they will be able to ignore the blocks from all the other miners in order to pick up their entire reward on the network, or, for example, to cheat, re-spending money due to intentional forks of the blockchain. However, we note that even if all the miners in the network conspire, they will not be able to bypass the basic bitcoin security mechanisms — for example, they will not be able to steal the bitcoins of users.
Bitcoin is the most powerful network using proof of work. In one second, Bitcoin miners calculate more than three quintillion (3 ∙ 1018) hashes. 32-bit proof (which is calculated on a computer for several hours) is the minimum complexity in Bitcoin, which could be observed only at the very beginning of the network. This is due to the fact that the complexity of the proof is automatically adjusted so that the bitcoin network finds an average of one block in 10 minutes. As the network hashrate increases, so does the complexity - now the complexity of one proof is about 70 bits. Accordingly, the hex hash block entry should start with 17 zeros.
PoW Alternatives
The Nakamoto consensus has a property that is perceived by many as a major flaw - to ensure safety, one must “work”, that is, produce proof of work. The calculations that are performed as part of PoW serve no useful purpose, and this is an architectural feature. It turns out that it is very difficult to come up with a proof of work that would perform a socially useful role. Therefore, it may seem that resources (first of all, electricity) are spent on mining for nothing (except for the fact that they are spent on security).
In addition, mining is still subject to the problem of centralization. More than 70% of bitcoin hashrate is currently located in one country - China. Many cryptocurrencies are trying to decentralize mining through the use of evidence of work, which is economically unprofitable to calculate on specialized equipment, but with this approach another problem arises - if you make Bitcoin mining profitable using home computers, then renting equipment to attack (or create a botnet for it) Much cheaper and easier.
Trying to solve these problems, the community offers many consensus algorithms that do not require “work”. The most popular category of such algorithms is based on proof-of-stake, PoS. The proof of a share is similar to the proof of work, but instead of performing a certain work, the author shows that he has a share in the system (for example, in the form of a non-zero cryptocurrency balance). It turns out that for mining with PoS, it is enough to “stock up” with cryptocurrency, after which you just get “interest” from it.
However, proof of share has an unpleasant disadvantage compared to PoW: since the proof of share is not based on the real world (computational power), but on something inside the blockchain itself (cryptocurrency balance), the task of building a reliable PoS algorithm turns out to be nontrivial.
In the simplest versions of the PoS consensus, problems arise with basic properties. It turns out that in them the most cost-effective behavior is reproduction of the forks of the blockchain to re-expend funds. More sophisticated proofs of share were created, with no obvious security holes; such algorithms return to the consensus the factor of economic responsibility at the expense of the obligatory pledge, which is confiscated in case of incorrect behavior of the participant.
The cryptographic community still has doubts about the possibility of robust algorithms with proof of proportion. It is possible that the planned transition to proof of Ethereum’s blockchain share, the second-largest public blockchain in the market, will dot the i.
In addition to proving a stake, blockchain enthusiasts are experimenting with other proof-of-* algorithms. For example, Bram Cohen, the creator of the BitTorrent protocol, recently suggested using proof of local-file storage (proof-of-space) for consensus in blockchains, that is, replacing the processing power in PoW with disk space. However, in terms of maturity, such initiatives are even more behind the proof of work algorithms than proof-of-stake.
PS And here is a small selection of our materials:
Source: https://habr.com/ru/post/327468/
All Articles