Consensus in cryptocurrencies with hybrid and Multi-PoW mining
I happened to participate in the development of a mining mechanism for cryptocurrency, allowing you to use different hashing algorithms to build a blockchain. The goal is to enable miners with any equipment (ASIC, GPU, CPU) to support the network, covering the entire possible audience of network participants. In the article, I will tell you what results we have come to, about mining in bitcoin and some other cryptocurrencies using hybrid mining.
Apart from the fact that mining is rewarded and the reward is the main source of coin issuance in most cryptocurrencies, the most significant function of this mechanism is to achieve consensus among network participants. Consensus is ensured by a simple law - when branching a blockchain (fork), the chain is considered to be true, during the construction of which the largest number of hashes (work) was performed.
To build multi-hybrid mining, two tasks need to be solved - calculation of the target for each of the algorithms and finding a comparison mechanism that allows you to do the most difficult thing - to compare chains consisting of blocks with different algorithms and, as a result, very different in magnitude of work.
Multihybrid mining is an undefined term, in the article it is used to denote mining with proof of work (POW) on several algorithms. In the English and Russian cryptocommunities, the generally accepted name is Multi-PoW. It will be considered on the example of Verge cryptocurrency with five algorithms . Hybrid mining is a commonly accepted term applied to cryptocurrencies using POW and proof of deposit / equity (POS) storage. We will consider it on the example of one of the pioneers of such a solution - Novacoin.
To understand the mining mechanism, you need to understand the following fundamental concepts in cryptocurrencies - work and purpose (target). The goal is a numerical value defining the upper bound of hashes suitable for creating a block in a chain. Work - statistically the average number of searches needed to find a hash of a smaller or equal target.
The main objective of the target is to be set to such a value that the block release time occurs in a given time interval. For Bitcoin, the interval is 10 minutes. Target recount in bitcoin occurs every 2016 blocks. To set a new target, bitcoin determines the average hash rate - the amount of network work per unit time for the previous 2016 blocks. Calculates the expected work in 10 minutes and taking a target for it, sets its value for the next 2016 blocks. For Bitcoin Target Calculation in view of the equality of the target (and, accordingly, the work) of the previous 2016 blocks, after reductions and approximations it is reduced to a rather simple formula.
In addition to cryptocurrencies, the task of target, work and hash rate (hash generation speed) is solved by pools . The pool does not know the direct hash value of an individual miner. Obtaining all hashes is impossible due to bandwidth limitations and pointless - checking them for costs is equal to mining. The pool receives responses from miners with a target insufficient to form a block, determines the share of the miner in the pool, hashrate and sets such a target for each miner so that the responses from them do not take up all the traffic. Throwing
graph of 12 faceted dice by a playerwhen hashrate 1 cast / sec in 100 seconds. Each point is the value of the drawn face, the right Y axis is the number of values that fell into the target. It can be seen that 20 shots fall into target 2 - throws with a value of 1 and 2 are suitable. The performance rating will be 20 * 12/2 = 120 shots, with target 6 the work is 53 * 12/2 = 106. The main property used is for any Target in the condition of sufficient statistics get close to the exact value of the work and hashrate of the participant.
A cryptocurrency with several algorithms, like a pool, should evaluate the hash of the participant algorithm and choose a target that would provide the desired time interval between blocks. The correct target calculation mechanism, in addition to the interval, should provide the proper shares of different blocks in the blockchain.
It is worth making a digression into history to understand the features of calculating the target in cryptocurrencies launched after bitcoin. In the old days, the brave pioneers of altcoinstruction took the bitcoin code, made minimal changes and launched the “Bitcoin killer”. There were even online generators of code repositories for new altcoins. This approach led to a number of problems, one of which concerned the calculation of the target and arose in the following scenario. A miner was connected to cryptocurrency mining whose hash rate was significantly larger than the other participants. Since the target was rarely recounted, such a miner created blocks with a very short interval and managed to create a weekly number of blocks in a few hours, and accordingly collect a weekly reward. Upon reaching the block on which the target was recalculated, the miner went to another altcoin with a suitable hash rate. With the increased target, the remaining miners could not generate one block at a reasonable time, not to mention the generation of all blocks before the new recalculation of the target and left the altcoin. The blockchain coins eventually stopped. The main solution to this problem was to recalculate the target of each block.
At first glance, the calculation of the target in Novacoin is not much different from the calculation in bitcoin. Novacoin correctly separated the calculation of POS and POW. The final formula for calculating the POS block target in Novacoin is as follows
The calculation of POW is almost the same, except that Novacoin claims a different frequency for the POW and POS blocks and it is calculated at intervals of 10 minutes to 30 depending on the position in the blockchain. You can see that if the network drops the POW or POS hash sharply, the target will remain valid until a new block appears on the mining mechanism that has lost power.
Target calculation in Verge uses the Dark Gravity Wave mechanism, which is a development of the ideas put by Kimoto Gravity Well. Without going into the mathematics of all these methods, the goal of these, no doubt poetically named mechanisms, is one - to ensure the conversion of the target quickly enough to respond to changes in the network hash rate. Despite some ingenuity of the code , its mathematics comes down to fairly simple formulas. Verge calculates the average target of 12 blocks of the selected algorithm, in which the last block is counted twice:
The mathematics of calculating the target in projects with mixed proofs / algorithms differs markedly from the original one in bitcoin. The second side of the coin of the target mechanism and work is the solution of the consensus problem - the definition of the blockchain branch which is taken as the true one in case of a dispute. The fundamental problem for mixed blockchains lies in the impossibility of choice when using the comparison of the sums of the work of blocks for all algorithms / proofs. Obviously, algorithms / evidence having inherently a higher hashrate with such primitive logic will dominate the blockchain.
In Novacoin, despite the use of a certain trust score in comments and variable names, with a detailed analysis of the logic, this turns out to be nothing more than a job. Calculation for POScoincides with the formula of work exactly, and the calculation for POW can be considered as work with a certain decreasing constant coefficient . The remaining additional calculations look like an additional balancing order of blocks to the target mechanism. It should be noted that this is not the best solution. As will be shown later, only a target is sufficient for balancing blocks. In addition, POS and POW blocks with a common parent can be unequal, although the fact of the appearance of valid blocks with a common parent should be defined as their equality.
Before considering the current state of the consensus mechanism, Verge will be informative to look into its past. In spring 2018, Verge survived several attacks. Without going into details of attack mechanics, the code of the timeresponsible for choosing a fork contains dubious logic. If we assume that the IsProofOfStake () function in the POW cryptocurrency can return the true value, then the addition of different algorithms will, as shown above, lead to the dominance of an algorithm with a higher hashrate. Otherwise, the choice is made simply by the length of the chain, which with a correctly calculated target (the purpose of which is the uniform appearance of blocks) can lead to the equality of branches with very different really done work.
In the current code, Verge uses constant coefficients for comparison . Assuming that these coefficients take into account a certain relevance of mining equipment capacities, the obvious weakness of this choice is the loss of relevance when new equipment appears.
The native properties of target mathematics and work allow us to build simpler and more understandable calculation models on the blockchain. Consider a model and code emulating a target calculation for a blockchain with four algorithms. Let two of them occupy one third of the blocks. For simplicity of modeling, we can assume that the block with the smallest interval from the previous one is the best for building a circuit. In real cryptocurrencies, such a choice corresponds to the most common scenario. The model also tests the increase and decrease in the hash rate of one of the algorithms.
The calculation of the target will be calculated from the arithmetic average of work and time on the statistics of the last 300 blocks. The final calculation formula:
Let us summarize in the table the initial and calculated values for 10,000 blocks.
I want to note that the calculated value of the circuit is calculated by the formula:
As you can see, the results of emulation quite well coincide with the calculation according to the source data.
Blocks graph 3850-4650 Blocks
graph 5599-6399
On the graphs of the change in work time it is seen how, the density of blocks increases and falls when the hashrate changes. In principle, this is a logical and logical behavior, but it is also quite appropriate to regulate it using techniques like the Dark Gravity Wave - increasing the influence of the last blocks, and others.
Turning to the question of determining the consensus of forks from blocks with different algorithms, it is worth noting the following basic property - blocks with a common previous block are equivalent to each other. Their targets and performance appraisal give equal rights to take a place in the chain. This observation immediately prompts the idea of using equivalence - using the amount of work, coefficients varying from the ratio of targets, etc. Omitting the consideration of the shortcomings of all such ideas, we will proceed to the method that most fully meets the requirements of the blockchain.
If we consider the geometric mean predictions of the work of all block algorithms, then the sum of such equivalent works is the best characteristic for comparing forks.
Such equivalent work has the following properties:
The equivalent operation mechanism significantly complicates the attack 51 on the blockchain. The formula for equivalent work, expressed through a hash rate, allows you to estimate the necessary power for an attack.
For example, an attack table, the time between blocks is 60. Suppose an attacker can provide only 50% of the hashrate in three algorithms.
To achieve equality with the network, he will have to have a hashrate superior to the network hashrate according to the first algorithm by 4 times.
The following graph shows the result of emulating an attack on a blockchain.
The attack begins on block 1000. The sum of equivalent jobs in the emulation for both branches differ slightly and show the equality of branches.
Summing up, it can be noted that consensus mechanisms in cryptocurrencies with mixed algorithms / proofs can be mathematically justified and such cryptocurrencies are more difficult for attack 51. I wish
everyone a happy blockchain and thank you for your attention to the topic.
Apart from the fact that mining is rewarded and the reward is the main source of coin issuance in most cryptocurrencies, the most significant function of this mechanism is to achieve consensus among network participants. Consensus is ensured by a simple law - when branching a blockchain (fork), the chain is considered to be true, during the construction of which the largest number of hashes (work) was performed.
To build multi-hybrid mining, two tasks need to be solved - calculation of the target for each of the algorithms and finding a comparison mechanism that allows you to do the most difficult thing - to compare chains consisting of blocks with different algorithms and, as a result, very different in magnitude of work.
Multihybrid mining is an undefined term, in the article it is used to denote mining with proof of work (POW) on several algorithms. In the English and Russian cryptocommunities, the generally accepted name is Multi-PoW. It will be considered on the example of Verge cryptocurrency with five algorithms . Hybrid mining is a commonly accepted term applied to cryptocurrencies using POW and proof of deposit / equity (POS) storage. We will consider it on the example of one of the pioneers of such a solution - Novacoin.
To understand the mining mechanism, you need to understand the following fundamental concepts in cryptocurrencies - work and purpose (target). The goal is a numerical value defining the upper bound of hashes suitable for creating a block in a chain. Work - statistically the average number of searches needed to find a hash of a smaller or equal target.
Work and aim on the fingers
Consider the example of a roll of a 20-sided D&D cube. We will distribute the dice to each D&D player on the planet and ask them to roll. Half of the dice will have values from 1 to 10, the second from 11 to 20. Assume that for the desired event in the game the value should be from 1 to 10. Let the players continue to roll until everyone throws the desired value. With each throw, the number of remaining players is halved and it turns out that the average number of dice rolls per player will be calculated according to the following formula:
The main objective of the target is to be set to such a value that the block release time occurs in a given time interval. For Bitcoin, the interval is 10 minutes. Target recount in bitcoin occurs every 2016 blocks. To set a new target, bitcoin determines the average hash rate - the amount of network work per unit time for the previous 2016 blocks. Calculates the expected work in 10 minutes and taking a target for it, sets its value for the next 2016 blocks. For Bitcoin Target Calculation in view of the equality of the target (and, accordingly, the work) of the previous 2016 blocks, after reductions and approximations it is reduced to a rather simple formula.
In addition to cryptocurrencies, the task of target, work and hash rate (hash generation speed) is solved by pools . The pool does not know the direct hash value of an individual miner. Obtaining all hashes is impossible due to bandwidth limitations and pointless - checking them for costs is equal to mining. The pool receives responses from miners with a target insufficient to form a block, determines the share of the miner in the pool, hashrate and sets such a target for each miner so that the responses from them do not take up all the traffic. Throwing
graph of 12 faceted dice by a playerwhen hashrate 1 cast / sec in 100 seconds. Each point is the value of the drawn face, the right Y axis is the number of values that fell into the target. It can be seen that 20 shots fall into target 2 - throws with a value of 1 and 2 are suitable. The performance rating will be 20 * 12/2 = 120 shots, with target 6 the work is 53 * 12/2 = 106. The main property used is for any Target in the condition of sufficient statistics get close to the exact value of the work and hashrate of the participant.
A cryptocurrency with several algorithms, like a pool, should evaluate the hash of the participant algorithm and choose a target that would provide the desired time interval between blocks. The correct target calculation mechanism, in addition to the interval, should provide the proper shares of different blocks in the blockchain.
It is worth making a digression into history to understand the features of calculating the target in cryptocurrencies launched after bitcoin. In the old days, the brave pioneers of altcoinstruction took the bitcoin code, made minimal changes and launched the “Bitcoin killer”. There were even online generators of code repositories for new altcoins. This approach led to a number of problems, one of which concerned the calculation of the target and arose in the following scenario. A miner was connected to cryptocurrency mining whose hash rate was significantly larger than the other participants. Since the target was rarely recounted, such a miner created blocks with a very short interval and managed to create a weekly number of blocks in a few hours, and accordingly collect a weekly reward. Upon reaching the block on which the target was recalculated, the miner went to another altcoin with a suitable hash rate. With the increased target, the remaining miners could not generate one block at a reasonable time, not to mention the generation of all blocks before the new recalculation of the target and left the altcoin. The blockchain coins eventually stopped. The main solution to this problem was to recalculate the target of each block.
At first glance, the calculation of the target in Novacoin is not much different from the calculation in bitcoin. Novacoin correctly separated the calculation of POS and POW. The final formula for calculating the POS block target in Novacoin is as follows
The calculation of POW is almost the same, except that Novacoin claims a different frequency for the POW and POS blocks and it is calculated at intervals of 10 minutes to 30 depending on the position in the blockchain. You can see that if the network drops the POW or POS hash sharply, the target will remain valid until a new block appears on the mining mechanism that has lost power.
Target calculation in Verge uses the Dark Gravity Wave mechanism, which is a development of the ideas put by Kimoto Gravity Well. Without going into the mathematics of all these methods, the goal of these, no doubt poetically named mechanisms, is one - to ensure the conversion of the target quickly enough to respond to changes in the network hash rate. Despite some ingenuity of the code , its mathematics comes down to fairly simple formulas. Verge calculates the average target of 12 blocks of the selected algorithm, in which the last block is counted twice:
The mathematics of calculating the target in projects with mixed proofs / algorithms differs markedly from the original one in bitcoin. The second side of the coin of the target mechanism and work is the solution of the consensus problem - the definition of the blockchain branch which is taken as the true one in case of a dispute. The fundamental problem for mixed blockchains lies in the impossibility of choice when using the comparison of the sums of the work of blocks for all algorithms / proofs. Obviously, algorithms / evidence having inherently a higher hashrate with such primitive logic will dominate the blockchain.
In Novacoin, despite the use of a certain trust score in comments and variable names, with a detailed analysis of the logic, this turns out to be nothing more than a job. Calculation for POScoincides with the formula of work exactly, and the calculation for POW can be considered as work with a certain decreasing constant coefficient . The remaining additional calculations look like an additional balancing order of blocks to the target mechanism. It should be noted that this is not the best solution. As will be shown later, only a target is sufficient for balancing blocks. In addition, POS and POW blocks with a common parent can be unequal, although the fact of the appearance of valid blocks with a common parent should be defined as their equality.
Before considering the current state of the consensus mechanism, Verge will be informative to look into its past. In spring 2018, Verge survived several attacks. Without going into details of attack mechanics, the code of the timeresponsible for choosing a fork contains dubious logic. If we assume that the IsProofOfStake () function in the POW cryptocurrency can return the true value, then the addition of different algorithms will, as shown above, lead to the dominance of an algorithm with a higher hashrate. Otherwise, the choice is made simply by the length of the chain, which with a correctly calculated target (the purpose of which is the uniform appearance of blocks) can lead to the equality of branches with very different really done work.
In the current code, Verge uses constant coefficients for comparison . Assuming that these coefficients take into account a certain relevance of mining equipment capacities, the obvious weakness of this choice is the loss of relevance when new equipment appears.
The native properties of target mathematics and work allow us to build simpler and more understandable calculation models on the blockchain. Consider a model and code emulating a target calculation for a blockchain with four algorithms. Let two of them occupy one third of the blocks. For simplicity of modeling, we can assume that the block with the smallest interval from the previous one is the best for building a circuit. In real cryptocurrencies, such a choice corresponds to the most common scenario. The model also tests the increase and decrease in the hash rate of one of the algorithms.
The calculation of the target will be calculated from the arithmetic average of work and time on the statistics of the last 300 blocks. The final calculation formula:
Let us summarize in the table the initial and calculated values for 10,000 blocks.
| algo | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| hashrate | 40 | 80 | index <4000: 20 4000> index <6000: 150 index> 6000: 20 | 100 |
| interval | 60 | |||
| blocks | 3333 | 3333 | 1666 | 1666 |
| work | 24000000 | 48000000 | 27600000 | 60,000,000 |
| algo | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| interval | 59 | 59 | 57 | 59 |
| blocks | 3306 | 3320 | 1691 | 1683 |
| work | 23847014 | 47085487 | 27028272 | 60499076 |
Blocks graph 3850-4650 Blocks graph 5599-6399On the graphs of the change in work time it is seen how, the density of blocks increases and falls when the hashrate changes. In principle, this is a logical and logical behavior, but it is also quite appropriate to regulate it using techniques like the Dark Gravity Wave - increasing the influence of the last blocks, and others.
Turning to the question of determining the consensus of forks from blocks with different algorithms, it is worth noting the following basic property - blocks with a common previous block are equivalent to each other. Their targets and performance appraisal give equal rights to take a place in the chain. This observation immediately prompts the idea of using equivalence - using the amount of work, coefficients varying from the ratio of targets, etc. Omitting the consideration of the shortcomings of all such ideas, we will proceed to the method that most fully meets the requirements of the blockchain.
If we consider the geometric mean predictions of the work of all block algorithms, then the sum of such equivalent works is the best characteristic for comparing forks.
![$ work_ {equal} = \ sqrt [k_1] {work_ {algo_1}} \ cdot \ sqrt [k_2] {work_ {algo_2}} \ cdot ... \ cdot \ sqrt [k_n] {work_ {algo_n}} $](https://habrastorage.org/getpro/habr/formulas/ac0/dbc/eb7/ac0dbceb7acad988e4d7578a401319d0.svg)
Such equivalent work has the following properties:
- when the hash rate of all algorithms is changed n times, the chain consensus estimate will also change n times
- by increasing the hashrate of one of the algorithms and decreasing the other n times with equal shares in mining, the consensus estimate of the chain will be equal
- with equal proportions of algorithms and equal hash rates of these algorithms, the equivalent operation and operation of any algorithm will be equal
The equivalent operation mechanism significantly complicates the attack 51 on the blockchain. The formula for equivalent work, expressed through a hash rate, allows you to estimate the necessary power for an attack.
![$ work_ {equal} = \ sqrt [k_1] {{k_1} \ cdot {t} \ cdot {hashrate_ {algo_1}}} \ cdot \ sqrt [k_2] {{k_2} \ cdot {t} \ cdot {hashrate_ { algo_2}}} \ cdot ... \ cdot \ sqrt [k_n] {{k_n} \ cdot {t} \ cdot {hashrate_ {algo_n}}} $](https://habrastorage.org/getpro/habr/formulas/6f4/924/719/6f49247195817f0b2c90ce41efcecd49.svg)
For example, an attack table, the time between blocks is 60. Suppose an attacker can provide only 50% of the hashrate in three algorithms.
| algo | 1 | 2 | 3 | 4 | equal |
|---|---|---|---|---|---|
| part | 3 | 3 | 6 | 6 | |
| net hashrate | 40 | 80 | 20 | 100 | 11862 |
| attacker hashrate | 160 | 40 | 10 | fifty | 11862 |
To achieve equality with the network, he will have to have a hashrate superior to the network hashrate according to the first algorithm by 4 times.
The following graph shows the result of emulating an attack on a blockchain.
The attack begins on block 1000. The sum of equivalent jobs in the emulation for both branches differ slightly and show the equality of branches.
Summing up, it can be noted that consensus mechanisms in cryptocurrencies with mixed algorithms / proofs can be mathematically justified and such cryptocurrencies are more difficult for attack 51. I wish
everyone a happy blockchain and thank you for your attention to the topic.