zawy12
commented
3 years ago In the above I talk about using height in place of work. Let me clarify how it's possible and the limitation.
Using multiple POWs makes the difficulty algorithm (DA) and calculating chain work problematic. Pigeon, Raven, and Myriadcoin (which I think Digibyte and Pyrk copied) seem to have gotten the issues worked out. (Update: Digibyte's multishield does it in a theoretically perfect way.)
It is possible to stick with height. The problem occurred because the current DA was >10% behind schedule. This allowed the attacker to start off using long solvetimes to lower the difficulty and still end up with a higher height in the same amount of time. There is a certain sequence of timestamps attackers can use that allow various DAs to emit more blocks than the normal random solvetimes. ETH's DA could be tricked to issue 75% too many blocks with the same amount of work. SMA algos can be tricked into emitting 50% too many. WTEMA/ASERT can be tricked into 38% too many. Digishield is halfway between SMA and WTEMA. DGW is just a simple moving average in disguise. LWMA is the only one I can't trick over short time scales, so it seems to be the only one where you can use height in place of chain work with only a little bit of error. Difficulty would be determined by scanning the previous blocks until N=300 blocks with the POW the miner wants to use are encountered. The nBits target in headers would be based on the POW and its value calculated based only on previous blocks that used that POW. The target solvetime between blocks for each of the 5 POWs would be 5 * 30 = 150 seconds. Chain work would just be the height.
But this needs to be combined with a limit on reorg depth because even LWMA can be tricked if you back in time far enough. But this needs to be combined with a limit on reorg depth because even LWMA can be tricked if you go back in time far enough. If a private mine goes to an old-enough block, made easier if the DA responds fast, you can get a large number of blocks at very little cost and end up with a higher height if you choose the timestamps correctly. The public chain is at a disadvantage because it has random solvetimes. The attacker seems to completely lose his advantage only if the DA averaging window goes back in time further than his attack. (and the allowable timestamp restrictions MTP and FTL are strict)
I don't know what the exact numbers are, so the following is just an estimation for LWMA. The attacker might be able to make solves per hash 0.5% faster than normal random solvetimes in an LWMA by setting the timestamps exactly equal-distance apart (equal to the target block time). If the LWMA has N=300 then he can make his 1st 150 timestamps say 5x the target block time apart to make difficulty something like 1/4 normal what it was. Then he would start with the equal-distance timestamps which recovers the time in the long solvetimes. He would have to start with a block in the distant past that is more than 150 * 5 / 0.005 = 150,000 blocks in the past to initially lower difficulty like this and then end up at a slightly higher height as the public chain in the same amount of time with 1/4 the hashrate. So you would have to outlaw reorgs that are more than say 10,000 blocks. But this requirement allows a Sybil attack on reconnecting nodes that can force a chain fork, so you have to have trusted nodes which is an unwanted centralization.
LWMA strongly needs a monotonic timestamp requirement.
Update: Digibyte's Multishield calculates the chain work correctly (without all the problems I discuss) by simply calculating the chain work of the most recently solved block as being the geometric mean of the most recent difficulty of each POW. If 5 POWs are allowed, you multiply 5 difficulties (necessarily scaled down) and take the 5th root. See this issue for more which primarily discusses the 1st type of Multi-POW in the list of 3 below.
Multiple POWs can be used in 3 ways:
This article is about the 3rd type. The security of the 1st type is reduced to the weakest POW [partial correction: see the update above]. It's not clear to me that even randomly sorting the POWs in versions of the 2nd type give good protection against ASICs. The 2nd type is "typical POW" in the sense does not have any extra protection against a 51% attack if the coin is small compared to a larger coin using a similar list of POWs. The 3rd type may be able to avoid these problems as described below, possibly providing much more protection than POW-based options.
How security is increased An attacker has to have access to a large quantity of hashrate for all the POWs in order to do a 51% attack (to get more than a few sequential blocks). To protect against short-range selfish mining, ideally the POW would change every block. But I do not know if all the desired POWs can immediately switch back and forth from other coins for 1 block (as desired) when it's their POW. If the majority of the worldwide hashrate for a given POW can switch coins quickly at no cost, then the potential hashrate for each POW is as large as the reward+fees justify.
It should be strong as long as a large majority of the POWs are not easily "rentable" in some way (e.g. NH, AWS, or botnets). If a lot of coins follow this scheme it increases the security of them all by giving miners more coins to switch between. A single coin could have 100 distinct chains running the exact same POW scheme (each with the same reward+fees) to enable 100x higher tx/sec but have the same security as if they were all a single chain with a security on each chain supported by the sum of their reward+fees. Merchants would run a wallet that supports all of them. In contrast, if any other POW coin were to split itself (using the same POW or not), security would be divided with the division of the reward+fees.
The POWs chosen should not allow a GPU or other type of equipment to easily (quickly) switch from one of the POWs to another. The block time and number of POWs may need to be reduced enough to help prevent this. This increases the CAPEX in the equipment that's being applied, fundamentally increasing the POW security. Ideally, a wide variety of mature ASIC POWs would be available to use, and most of the ASICs would be created by a different manufacturer, in a different country.
Drawback This scheme leeches off the equipment that other coins support. If all coins used this method, or if a single big coin had a split chain as above, big actors could be expected to have control of a variety of equipment, reducing the security back down to BTC levels.
Review of Nakamoto consensus security To get high security, coins need to have a rewards+fees per time that supports a dedicated hashrate that is greater than any potential collusion of "non-dedicated" hashrate that can be owned, rented, stolen, or re-purposed from other equipment. "Dedicated hashrate" means miners who perceive it's not in their best interest to attack the coin because it would lower the sum of their future income by lowering the value of their equipment (by hurting that type of equipment's primary source of income). The CAPEX in equipment motivates miners to do what's best for the current and future value of the coin. This motivates them to not collude. This is why Nakamoto consensus does not devolve into a harmful pair of equally matched ~50% attackers always at each others' throats (as seen in 2-party democracies) and why miners in all secure coins can be used to reach off-chain consensus for 0-conf and tx-specific orphaning.
Dedicated CAPEX in POW equipment is an off-chain stake. Unlike POS stake that is on the chain before consensus rounds, it enables "permissionless" voting in a way only Nakamoto consensus can achieve. Stake pre-existing on the chain is also why POS schemes that attempt to mimic POW consensus have to do consensus backwards, starting with an ultimately-centralized-randomization scheme to substitute for POW's nonce, and it has to be acquired before creating the block (in POW the nonce determination comes after the block is formed and it's the randomization seed). POW also requires the equipment CAPEX stake to be occupied in time which can't be done in POS, unless VDFs become reliable. This prevents the grinding problems seen in POS.
Electrical waste reduces consensus security The best POW technology allows the smallest increase in CAPEX to result in the largest reduction in OPEX (e.g., electrical costs and equipment depreciation from technological obsolescence). This allows miner speculation about the future value of the coin to maximize the amount of CAPEX that will be forcibly married (dedicated) to the future of the coin, assuming similarly large source of future income for the equipment do not develop.
Electrical waste can create coin value This paragraph is off-topic, but it will round out the POW theoretical discussion. POS coins usually should use POW to create and distribute coin, but the type of POW needed for coin creation is the "opposite" of that needed for consensus. Instead of random solvetimes based on dedicated CAPEX, it needs non-random solvetimes based on rentable OPEX. Is it therefore a mistake for coins like BTC to combine the functions into one POW? Random solvetimes in consensus are needed to prevent orphans and not give large hashrates a disproportionate advantage. Predictable solvetimes are needed in coin creation so that you do not get a $100 reward after spending somewhere between $5 and $500 worth of hashing. This prevents the need for pools and everyone can simply submit a tx with a proof of hashing quantity to get the indicated amount of coin. This can be done by using a VDF-type technology, a simple scheme I thought of, or something like this.
This Multi-POW scheme seems to violate the normal security rules This scheme reverses the irony that coins usually notice: they usually end up with a lower hashrate when seeking higher security. This scheme removes the irony, purposefully seeking the things that normally hurt small and medium-sized coins: popular POWs, ASICs, on-off mining, and merge mining. It no longer seems to depend on having a high ratio of dedicated to non-dedicated CAPEX, but still seeks the highest possible total CAPEX from all external sources, but using them against each other to prevent a loss in security. It does not seem to require any dedicated CAPEX. It just requires that a collusion of miners can't get > 51% of at least one of the POWs.
Determining Difficulty and Chain Work Difficulty and chain work are calculated as usual only in the 2nd type. The other two require keeping each POW's input data to the difficulty algorithm separate, or using a conversion factor between them to put them on the same scale. The conversion should not be hard-coded by the devs because some POWs' software and/or equipment will advance a lot more quickly than others, causing some blocks to be solved much more quickly or slowly. It also can throw off the chain work calculation. The conversion factor between difficulties is potentially not needed (see below) but if it's used, it should be determined by looking back over a long window of difficulties for the given POW. A POW is chosen as the baseline standard and the other POWs' "chain work" is expressed in terms of it. The difficulty for each POW would be stored in each header as usual. This means it would change a lot from block to block based on which POW is required. The adjusted (corrected or consistent) difficulty for a given block (the chain work for that block) would be the baseline POW's chain work (sum of its and only its difficulties) for the past say 10,000 blocks divided by the given block's POW difficulties also summed over the past 10,000 blocks, multiplied by the given block's unadjusted difficulty. This method is correct if we define chain work as the value society was willing and able to apply to the block discovery. It takes into account everything for the different POWs like current efficiency of the code and equipment, joules and memory required, equipment expense, and market inefficiencies.
More details on "work" and why reward+fees is the best proxy for chain work
[ update: this section is very high level and difficult even for me to follow, 5 months later. It's not wrong or written inefficiently. It's just trying to pack in a lot of important but tangent ideas. But the conclusion is simple: the chain work assigned to each POW is the reward+fees. This is typically just equal to chain height which is a metric for chain work that I believe caused problems in coins. If that's an issue I need to solve, this article is incomplete.]
Market inefficiencies result in some POWs getting more profit than others, so it may be argued they did not "work" as much as the other POWs being used. But this is the same as saying lucky or smart investors do not deserve large gains, or that a block found quickly should be paid less reward and assigned less work. We can't use physics to define the work (energy) as a means to determine the difference between the POWs because we only know the amount mathematical entropy that was reduced (from 256 to the log2(target)). If we could know the heat generated per bit change and the number of bit changes per hash we would know the electrical energy lost. But that's an OPEX which is higher if the CAPEX is lower (inefficient equipment) which is ideal for POW coin generation for POS systems, but we only want to fund only CAPEX work for POW consensus, not penalize it. CAPEX is an "energy" that was used in the equipment creation which can be determined by its dollars cost because a kWh costs about $0.13. But we can't determine the CAPEX/OPEX ratio for any particular hash. ( Ideally, we would like to fund only the dedicated CAPEX.) So we have to fund both which is only determinable by assuming miner profit margin is constant which means CAPEX+OPEX is proportional to reward+fees so that we can use reward+fees as a proxy.
Height can be equal to chain work by using ASERT or EMA It is generally believed that height can't be used to determine the most work, so it is said we have to be careful to sum difficulties to get chain work., but notice reward+fees is approximately just the height. So is is wrong to say chain work=reward+fees? No, height is inaccurate only if the difficulty algorithm is not precise or the timestamp limits are too lenient. The above process for determining chain work is not necessary if chain height can be made to concur with chain work which is a different way of saying reward+fees is valid. This appears to be the case if 1) timestamps are required to be sequential, 2) the future time limit is significantly less than the target solvetime, 3) if EMA or ASERT difficulty algorithm is used, and 4) a small adjustment based on the timestamp is used. It is my belief that unlike other algorithms, ASERT (closely approximated by EMA) does not allow a timestamp or hashrate manipulation that can result in a greater height with fewer hashes, with an error determined by the amount of timestamps leeway.
Preventing a stuck chain from a large miner leaving It may get stuck from a large miner no longer participating. This can be solved by exponentially reducing the required difficulty over time if the timestamp indicates a solvetime is taking > 7x the target solvetime. This requires a moderately tight future time limit that's allowed on timestamps to prevent fake timestamps from lowering the difficulty. It also requires timestamps be at least +1 second after the previous timestamp.