Introducing Proof of Double Forgery
by François Thoorens, Joshua Noack and Kristjan Košič
Proof-of-Stake (PoS) systems have long been known to have a ‘Nothing at Stake’ problem. In this article, we describe a new Delegated-Proof-of-Stake (DPoS) consensus rule that will not only help alleviate this problem, but also form a stronger consensus layer. We believe this is a groundbreaking innovation that can make DPoS networks safer and more secure.
The ARK Blockchain Platform incorporates a consensus mechanism that is our variation of the DPoS model originally designed by Daniel Larimer of Bitshares. The primary concept is the addition of a sensible weakening assumption in the consensus to make PoS possible. That assumption is to choose a maximum number N of block producers at any point in time.
Advancing From Proof-of-Work to Proof-of-Stake
Traditional Proof-of-Work (PoW) based networks (Bitcoin, Ethereum) utilize computational might of the machines working (miners) to solve hashing problems to form a hierarchy of weight within the network. With the advent of PoS, this weight calculation shifted from computational might to an economic model that determines an account’s standing within the network based on the number of tokens held, or their “stake” in the network’s success. In most PoS systems you must keep your wallet open and connected to the internet rather than utilizing a stand alone miner, turning your wallet into a node on the network.
The Delegated Proof-of-Stake Evolution
Delegated Proof-of-Stake or DPoS is a consensus model that further enhances the benefits of PoS. In this model, instead of individuals using wallet balances to determine whether their nodes forge blocks, a distributed collective of nodes called “delegates” control the ledger and validate and forge the blocks. This opens doors to sizable performance improvements, such as decreased transaction times, blockchain upgrade lead times and block size modifications.
There is no limit to the number of delegates that can exist in a DPOS environment. Each provides a valuable service by validating transactions, maintaining a copy of the ledger, and protecting the integrity of the data and the network. However, not all delegates are authorized to validate new blocks and add transactions to the ledger. In DPOS, only a select few have this authorization — they are called “forging delegates”, “witnesses”, “validators” or “block producers”.
Here are some real world examples of the number of Block Producers or Forging Delegates (N) for several currently running blockchain projects:
- Steem: 7
- EOS: 21
- Bitshares: 23
- Lisk (Crypti): 101
- ARK: 51
In ARK’s case, the number of forging delegates (block producers) is 51. These 51 delegates have the authorization to process transactions and add them to the ledger. Having forging delegates mitigates the risk of Long Range Attacks (LRA) and makes the incentive to forge an alternative chain less strong, but it does not eliminate the risk completely.
The power of continuous voting
At face value, the relatively small number of delegates, when compared to something like Bitcoin miners, would seem like a form of centralization of power, going against the nature of the industry and a push towards decentralization. To combat this potential negative, DPoS based networks allow all token holders to have a say in who is authorized to be a forging delegate, and who is not. This is done through a continuous voting process. The public voting mechanism present in DPoS helps to restore decentralization to the network.
A weakness of DPoS: Double Forgery
Double Forging is a weakness of the DPoS model and the ARK network has experienced disruptions due to this in the past. There is no mechanism in place that prevents an active delegate from forging several different blocks on the ARK blockchain during their time slot. The reason, common to all PoS like systems, is that it only requires minimal additional computing resources, which relates to the Nothing-At-Stake problem. This is avoided in PoW by requiring a huge amount of computational power to mine multiple chains at the same time .
Double forgery, in simple terms, means that when it is a delegate’s time to forge a block, he tries to forge additional, possibly different blocks, in his time slot and subsequently broadcasts these valid but different blocks. Since different delegates would get different blocks due to network propagation, it can cause some delegates to confirm that block-B1 is valid and end up following one chain while others would follow a second-B2, or third chain-B3, … Nth chain-BN, where B1 through BN are multiple versions of that same block from the same delegate. However, it should be noted, that even if a delegate tries to forge and broadcast different blocks, at no point does this mean the delegate will receive more rewards or sneak in some additional data into the blockchain, but as mentioned, it can weaken the network, open it up for long range attacks, and slow down propagation of the blocks until things stabilize and get back to normal.
So, why would a delegate forge several blocks in his time slot? There are several reasons:
- On accident. ARK experienced accidental double forgery several times with our legacy v1 code. This happened by failover script error or human error that sparked running two node instances with the same delegate passphrase at the same time. This led to two different servers creating blocks and broadcasting them to the network in the same time slot.
- On purpose, e.g. hostile takeover. A hostile delegate could try to forge an alternative chain in an attempt to overtake the correct blockchain history. In this situation, the hostile delegate could use a double forgery to slow down or halt the network (correct chain) in order to improve their chances of succeeding in the takeover attempt.
For the past few months, the development team and the community have worked on 2 aspects of the problem:
- Come up with a better strategy to make sure the network can agree as fast as possible on a correct block (aka: banning the misbehaving delegate).
- Improve DPoS consensus to include a punishment for a hostile takeover attempt.
As part of Casper research, Vitalik Buterin introduced Minimal Slashing Conditions in 2017. We have also worked out a similar condition for DPoS together with introducing a simple yet powerful punishment consensus rule to prevent double forgery.
Introducing the Proof of Double Forgery
During our dev meeting in Utrecht recently, ARK CEO François Thoorens, ARK CTO Kristjan Košič and ARK Core Developer Joshua Noack all sat down to brainstorm the problem and came up with a solution we call Proof of Double Forgery (PoDF).
Definition:
We define Proof of Double Forgery PoDF when we receive a couple or more (>2) blocks B1, B2, that are following the rules of double forgery detection (see point i. below). We also introduce a punishment variable S. S is related to number of blocks we allow for the chain to rebuild itself. Meaning we introduce moving checkpoints by not allowing a chain rebuild below a certain height. This is part of the new AIP-P2P protocol improvement and it will be introduced as a separate topic.
i.) The rules to detect the double forgery are the following:
1. Matching slots — active delegate is allowed to forge in this time slot. PublicKey(B1) is allowed to forge at slot(B1). Also `currentSlot < S` means that the double forged block is not from the past and is limited by S.
slot(B1) = slot(B2)slot(B1) — currentSlot < S // currentSlot is linked to when the consensus rule is applied ie slot(B)
2. Same block producer — both blocks are signed with the same keys, belonging to an active delegate, as defined in i.1.
publicKey(B1) = publicKey(B2) //same keys3. Valid blocks — both blocks pass the signature verification process.
verification(B1) = verification(B2) = true4. Different block ids — block hashes are different.
Hash(B1) != Hash(B2) // Block Hashes are differentIntroduction of an additional Consensus Rule
To apply the Proof of Double Forgery, we need to apply a new rule at the consensus level.
- Forger of B3 detected double-forgery. He can append information to a block that delegate double-forged, adding (B1, B2) in the block header, before he distributes the block. PoDF block will be put at the height of the double forge and dismiss all the double forged blocks.
- If PoDF(B1, B2) = false, B3(next block) cannot validate. We need to validate that proof-of-double forgery is true by validating signatures of both block headers (B1, B2) — proving they are produced by the same delegate.
- Punishment: PublicKey(B1) cannot forge in the slots between slot(B), slot(B)+S
Additional specifications / requirements
Note 1: There is no rule to reorganize the chain by the PoDF in order to remove this block. This is to prevent a delegate from intentionally triggering a reorganization of the chain and performing a double spend attack.
Note 2: If the PoDF is to old (ie: older than S, or not in the exact same time slot) it is not possible to include it in the blockchain. This is to prevent from double punishment or from possible schemes where delegates could ransom other delegates for errors in the past.
Note 3: We don’t propose to include a 52nd delegate into the active delegate list while one delegate is being punished. This could lead to additional Long Range Attack attacks or Sour Milk Attacks.
Note 4: PoDF may also mitigate the Sour Milk Attack vector as well, explained in this article by Pascal Thellman. “A sour milk attack is where base validators push their peers to doubt honest peers by publishing genuine and fraudulent blocks to peers concurrently. At the same time, these base nodes coordinate with other malicious peers to do the same, muddling the ability of honest peers to discern between valid and invalid blocks.”
ELI5
Intuitively the idea is that all nodes accepting B3 (integrating PoDF(B3, B3')) can reach a consensus on a punishment. In case of multiple forgery take over, pushing this double forgery block information will help the whole network to disregard all blocks from the malicious delegate (by public key) and prevent hiccups on reorganization triggers which were experienced in the past.
What’s next
An AIP is being worked out to be released rather soon. The specification is not yet set in stone, and we encourage the community to comment and design attacks on this consensus rule and provide feedback and concerns under the AIPs discussion link: https://github.com/ArkEcosystem/AIPs/issues/56.
