Reverse Nakamoto Consensus

Abstract

POW consensus is problematic due to 51% attacks. Even BTC is potentially vulnerable as it shifts from rewards to fees.[1][2]  Much higher security can be obtained by replacing hashrate with stake-rate in a way that adheres to Nakamoto consensus, preventing POS problems. POW security comes from a high ratio of dedicated to non-dedicated hashrate. Dedication is achieved by capital investment in equipment that isn't useful for other purposes, including other coins. Electrical and depreciation costs reduce security by reducing the amount of speculative capital spent on equipment.[2][3][4] Capital in stake is potentially as dedicated as capital in equipment and there is 50x more capital in stake available for securing the chain.[5] But stake does not produce a hashrate in proportion to the capital. Hashrate proves the capital in equipment was occupied during the vote, preventing the capital from voting twice. A Verifiable Delay Function (VDF) can be used to provide a time denominator to get stake-rate, preventing the need for stakers (as in traditional POS) to have time locks that require registration and centralization. Another difference between equipment and stake capital is that stake capital is on the chain prior to the leader elections (aka lotteries) whereas equipment capital proves its existence during each election. This difference results in POS systems having to deal with grinding attacks that can taint randomness in leader elections. The solution is to reverse Nakamoto consensus by beginning with a nonce that all stake-miners must use and ending with block creation. POW must still be used to create and distribute coins (stake) because the only known proof of unique identity that's necessary in  distributed consensus is proof of cost. The amount of proven cost is proportional to the amount of "identity weight" necessary in decentralized elections and lotteries. Two difficulty algorithms must be used: one for the above reverse Nakamoto POS-VDF that provides consensus on transactions and one for the POW that creates and distributes coin. Interestingly, the POW for coin creation can utilize a rental market and waste electricity, both of which decrease security when POW is used for consensus. Isolating coin creation with self-hashing txns allows solo POW mining, making pools obsolete. Isolating consensus with reverse POS-VDF can copy BTC's deflating emission rate, but it can also enable a truly stable-value coin (without reference to a fiat). Stakers are not paid for securing the consensus because running a node is the only cost and because paying for consensus results in centralization (such as pools, private ASIC manufacturing, and node centralization in POS). "Freedom (aka decentralization) is not free" and "paying voters to vote subverts the vote."

This is a simplified and updated version of my previous VDF-POS-POW article that gives greater detail in some areas. See also POW Consensus as Registered Voters with Digital Signatures for how Nakamoto consensus can be viewed within the framework of classical Byzantine consensus.

Time-occupied equipment in POW & POS-VDF prevents double-voting.

POS is clumsy because it requires registration, time-locks, and placing the stake at risk in order to keep stake from "double-voting" in block-leader elections. This is not a problem in POW because the equipment is automatically time-occupied in elections in a way that makes it costly to double-vote. A VDF may help POS by keeping the stake time-occupied in the same way.

Reversing Nakamoto consensus is needed because stake is already on the chain.

When the VDF is used in an obvious, straightforward way (as in Chia), the random number output by the VDF that elects the leader can be hacked because its seed can be varied without cost (a grinding attack). All POS has this problem that must be dealt with. But randomness without a taintable seed comes natural to POW.  This is because the POS stake (or Chia's space) is on the chain prior to elections whereas POW equipment value is off-chain, proving its existence during each election. The solution is to reverse Nakamoto consensus, beginning with a nonce the staking "miner" can't choose, and ending with block creation.

Capital in POW & POS substitutes for identity to prevent Sybil attacks.

Backing up, the capital required to establish stake (POS) or equipment (POW) substitutes for establishing unique identity when participating in block-leader elections. We need proven unique identities (or substitute it with proof of capital) to prevent Sybil attacks. But proof of capital alone does not prevent that "identity" from voting twice over time in a future or past election. As discussed above, POW handles this automatically, but POS needs a VDF. The stake in this POS-VDF does not need to be put explicitly at risk (as in other POS systems) for the same reason POW equipment is already "at risk" of losing value if there is enough collusion to conduct a 51% attack. But POS-VDF requires orders of magnitude more collusion in terms of capital required (compared to POW) to conduct an attack if the majority of coin holder participate in block-leader elections.

Electrical costs reduce POW consensus security

In the above I only mentioned the capital cost of POW equipment, so I need to address a common misconception that electrical costs are part of POW security. It is well-established in research that electrical and depreciation costs reduce POW security to the extent they reduce capital that could have been spent on mining equipment that will not be able to find alternate sources of revenue. Proof of security in POW comes from a high ratio of dedicated to un-dedicated hashrate, and only mining equipment that can't find alternative sources of revenue can be assumed to be dedicated. If proof of electrical costs were the only source of security, a 51% attack that costs half the reward+fees would be enough to gain 100% of the reward+fees and enable additional profits from double spending. But expensive, electrically-efficient equipment like ASICs that will recoup their costs over many blocks is very expensive to compete with. BTW I've argued with Bob McElrath over this view.

POW for Generating Coin with Self-hashing TXNs

This eliminates the need for pools. Coins in this scheme are created by POW using a self-hashing txn that replaces coinbase txns. Block headers have a difficulty/block (aka a maxTarget/target) for consensus and a difficulty/coin (aka a maxTarget/coin/target) for coin creation. A self-hashing txn has a destination address, a block height that is close to the block in which it will be included, the quantity of coin being mined, and a nonce. The miner hashes the txn while changing the nonce until the hash is < Target*coin /maxTarget/requestedCoin. Validators confirm the txn meets this requirement before accepting a block that includes it. The POW for coin creation can and maybe should be the "opposite" of the ideal POW for consensus. It can and maybe should focus on proving electricity (or depreciation) was wasted instead of proving the most capital in non-depreciating equipment. The goal is to minimize and equalize the barriers to entry, not giving an advantage to proprietary equipment. But a problem is that some locations have free electricity. Whatever the case, hopefully a rental market will equalize the barrier to entry.

Stable without a peg to any fiat

The above coin generation can be based on a standard exponential decrease like BTC. A part of BTC fluctuations is the result of sudden halvings (it jumps after halvings), so a continuous equation can be used:

h = height
T = target solvetime
HalfLife = HL = 4*365*24*3600; // 4-yr half life in seconds
TotalCoins = TC = 21E6;
// Replace T/HL with half life in blocks if you want.
RewardPerBlock = T*TC*ln(2)/HL*0.5^(h*T/HL)

However, the protocol could allow the staking POS-VDF winners of blocks to increase or decrease the difficulty per coin in the block after theirs by 0.01%. If the stakers (coin holders) want a stable-valued coin, a stable-valued coin will result. If they attempt to make the value of their holdings increase by making difficulty per coin too hard too quickly, they can't expect new adopters who will have a stable-valued clone to choose from. If they make difficulty too easy, the value of their coin holdings' will drop from inflation and again late adopters will not like the coin. Their best option seems to be to simply seek a store of value, allowing all future newcomers the same cost of entry, automatically adjusting for Moore's law.

A Simple DAG can be used to get fast confirmations

Reverse Nakamoto Consensus

• Normal POW sequence is 
1. Get random seed from previous block (it's hash)
2. Create block, out of many options
3. Suffer a delay
4.  Determine nonce & length of delay. 
5. Create random seed for next block (it's hash)
• vPOW sequence is 
1. Get random seed from previous block (it's VDF-output) 
2. Determine nonce ("Seed") & length of delay
3. Suffer the delay
4. Create block, out of many options
5. Create random seed for next block (it's VDF-output)

VDF definition (Verified Delay Function)

• Stakers calculate: setup(security parameter, TimeDelay) = pp 
• 5 GHz servers calculate time-delay function: eval(pp, seed) = a unique y & proof π 
• Validators: verify(pp, y, seed, π) = True or False
• I can the y value "VDF-output".

Reversing Nakamoto Consensus:

1. Staker hashes a concatenation of an existing UTXO (that is at least 500 blocks in the past) & the previous block's VDF-out to get a Seed. He normalizes a hash of the Seed for a 0 to 1 value to get a RandValue. 
2. ST = solvetime = 2*RandValue*TargetSolvetime*Difficulty/(UTXO qty)
   Note: this is better than a Poisson by having a flat probability distribution. This allows faster (but smaller) blocks because it prevents an excess of collisions in solutions for fast solve times that the Poisson causes. 
3. Stakers with fast STs calculate VDF's pp=setup(security parameter,ST) & send pp & Seed to a fast VDF server to cause a delay in calculating eval(pp,Seed) which returns y = VDF-output & π proof
4. If staker is first, he creates the block. The header includes the UTXO, staker's signature for proof the UTXO is his (requires spending UTXO to a new UTXO?), previous block hash, the seed, VDF-output & π, and merkle root. If he is allowed to select a timestamp instead of simply adding the solvetime to the previous block (which will cause block time to get far away from real time which should not be a problem), a grinding attack becomes possible which I address below.. He hashes the header once to get the block hash.
5. Notice the private key of the UTXO connects the block to the proof of "work" (sum of difficulties for the POS-VDF), but the block is not part of the VDF randomization seed. This is a practical way of seeing why reverse Nakamoto consensus works and is better than other POS..
6. Validators confirm validity of all the header's elements. 
7. If a miner sees two or more different blocks with the same VDF output and correctly signed by the winner, he only works on the first valid block he sees. See "Multiple block attack" below.

Notes:

• Precision errors in VDF are corrected by difficulty because stakers assign the timestamps.
• Exploiting the VDF This is probably the biggest security risk. VDFs are new and if an attacker finds a way to speed it up 100x or 1000x, a fork to fix it will leave the chain prior to the fork vulnerable.
• Randomness is preserved. Current and previous stakers can't control solvetime or VDF-output. Randomness comes from staker (instead of miner) population and previous VDF-output, so it can't be tainted (subject to grinding).
• Chain work rule remains sum of difficulties. CAP & Byzantine problems are solved as in POW. The chain with highest sum of difficulties wins because it proves the largest number of stakers were present (fewest network partitions) and double-voting (rewriting history) is not possible w/o going through equal time-cost multiplied by stake.
• Stake-key re-use of old keys that the attacker has bought from old stakers to do a medium to long range attack (since the staker selling his keys had better have spent his UTXOs) is not possible because the attacker has to still wait on the VDF cycles. 

Multiple UTXO grinding attack is stopped by 500 block rule.

An attacker can privately mine duplicates of a block and create many different UTXO's for the same input coin (stake), which can enable him to affect the seed to randomness infuture blocks, increasing his chances of having a fast solvetime. This is alleviated by not allowing recent UTXOs. This is a little like a time-lock, which I claimed could be eliminated by reversing Nakamoto consensus. It is needed to prevent a grinding attack which I said was not possible. The theoretical foundations I gave are not in error because to do the reverse Nakamoto consensus perfectly, the seed for the VDF would have to go all the way back to the POW-based self-hashing transaction that created the coin as opposed to the UTXOs. But that is not practical because it means most generated coins can never be transferred if we want secure consensus. Notice the typical POS staker registration that would cause a large communication overhead and/or centralization is not needed for this "time lock".

Attacker trying multiple VDF-outputs
Nodes can compare who has the fastest VDF time before the VDF has to be performed so they might be able to weed out alternatives before they propagate very far. But if an attacker can see many VDF-outputs for slightly longer solvetimes he can try all of them to see which ones will allow him to have a faster solvetime, so that the sum of his solvetime and the previous solvetime that was slightly faster than the other one other miners are building on will be faster than the "main" chain. A 20% miner considering 5 different VDF-output can significantly increase his odds of finding blocks. Chia's solution is for everyone is to consider all the fast alternatives but I have studied this aspect yet.  

Timestamps are subject to grinding

By selecting a timestamp between > 10 different values, miners can increase their chances of winning the block after the next block by > 10x (timestamp affects next difficulty which affects the seed after that block).  It's possible to require the timestamp to be set to the previous timestamp plus the VDF calculated solvetime even if VDF solutions are faster or slower than expected. This can be done in a scheme where stakers who win blocks adjust a factor in the block header (by say 0.001%) that keeps the VDF solvetimes close to real time. This is different from difficulty's affect on solvetimes which will respond a lot faster. This works as long as it does not affect the solvetime for the next say 100 blocks, which I'll discuss below. This scheme is necessary if the VDF-POS-POW scheme is to be used with a DAG.  The timestamp grinding solution below requires step-like difficulty changes instead of "continuous" which DAGs need to rank txns to prevent double spending.

If miners must be allowed to set the timestamp, let's consider the consequences.  Choosing a timestamp does not affect a miner's chances for the 2nd generation (the next block) more than anyone else because it does not change the seed to that block, but it does affect the seed to the block after that (the 3rd). So a miner can run many parallel VDFs for all the timestamps he can assign, and for each of those VDF-outputs he does it again, and then again for the 3 generation. This allows him to choose optimum solvetimes for 3rd and 4th generation (he can see the solvetime for his 4th before having to suffer it).  100 different timestamps could possibly affect the output of a fast-responding difficulty algorithm, giving the attacker 100x higher stake. Doing this for 3 generations would require 100^3 = 1 M parallel VDFs which might be feasible. By this scheme he can't affect the 1st or 2nd generations, but he multiplies the power of his stake by 100 in 3rd generation. If a largish staker gets a lucky fast solvetime in the 1st generation, he can be sure he will also get 3rd and 4th blocks by this method, giving him a 50% chance to get all 4 blocks if he has 25% stake-rate (this is a 2x effect because he does not control 1st or 2nd generation solvetimes). Chia may have a worse situation where the 2nd generation can be affected by an assigned timestamp.

To address this, Chia is using a 28 hour delay in difficulty in a 4.5 day averaging window. Delaying a response in difficulty like this, as a large percentage of the averaging window, causes catastrophic oscillations unless it's the largest coin for a POW. This occurred in nearly all Cryptonote/Monero clones which had only about a 1.5 hour delay with a 1 day averaging window.  This is not a delay like BTC's two weeks. BTC applies the calculated difficulty immediately after the 2-week calculation, so it's not the kind of delay that causes oscillations.   I informed Chia in Twitter about this. This warning applies if their "farmers" have a profit motive like POW, or if they're not the largest coin for their proof of space, but they are, so they should be safe, but it seems like a better option should be tried. My scheme here has no rewards, so stakers are not motivated to come and go so I could use Chia's method, but I would like to avoid it.

If miner's can assign timestamps, and Chia's method is not used, BTC's algorithm (without the Zeitgeist and timespanLimit attack holes) can be used and adjusted every 200 blocks. But the difficulty should only be allowed to increment in tranches like +/- 5%, 10%, 15% to reduce the amount of grinding.  Otherwise a big staker could get several blocks at the transition. If difficulty could be set to 100 different options, then a 25% staker could have a 70% chance of getting perhaps 10 blocks. This is done by not choosing the fastest solution, but by choosing a solution that would result in the next 10 blocks being solved quick on average (requiring 100 concurrent VDFs at the beginning and having to re-write the public chain because it will take some time).

Another way to restrict the grinding is to make the timestamp range that nodes allow (FTL and MTP) as tight as possible.

Multiple block creation attack stopped
The other "attack" is a direct result of reverse Nakamoto consensus. The winning block is formed AFTER the winner is determined. In other words, the winner can immediately create hundreds or thousands of valid blocks after winning, and submit them to different parts of the network. The solution is for all miners to simply accept and work on only the first valid block they see for that VDF output. The "mutated" blocks will all have the same VDF output, so miners seeing these block will get different solvetimes by selecting a different block. The chain work rule will naturally sort out any problems. Rejecting all similar valid blocks that have the same VDF output does not work because a duplicate could be delayed and nodes would have to reject the current chain back to that point.

[1] See equations 7 and 8.
https://s3.amazonaws.com/tld-documents.llnassets.com/0013000/13402/bis%20report.pdf

[2] See page 13
https://faculty.chicagobooth.edu/eric.budish/research/Economic-Limits-Bitcoin-Blockchain.pdf
Thoughtful PhD reviewers consider it simple and correct:
https://medium.com/orbs-network/the-economic-limits-of-the-blockchain-847f79b452db
https://www.aier.org/article/sound-money-project/economic-limits-bitcoin
https://promarket.org/founder-blockchain-discusses-new-research-inherent-limitations-bitcoin/
https://twitter.com/jenniferdoleac/status/1011052217980391424

[3] Even Nick Szabo tweeted about the importance of capital in equipment, and keeping a high ratio of dedicated equipment.
https://twitter.com/NickSzabo4/status/1092891074555633664

[4] Alt coins intuitively are aware of this definition of security: they have frequently reduced total hashrate in an attempt to increase the dedicated to non-dedicated hashrate. They try to find a unique POW and try to avoid anything that increases non-dedicated hashrate like ASICs, Nicehash, and botnets. They seem to always regret merged mining.

[5] It was estimated in the above paper that BTC mining equipment cost up to $2 B in June 2018 when the market cap had dropped to $130 B.