Introduction
This thread is a continuation of Hyperchain staking mechanism with different intent.
To create the technical specification of hyperchains we need to define potential issues, attacks and describe why our mitigations work. We need to define what does it take to hack the network - similar to 51% attacks on PoW cryptocurrencies.
The version of leader elections proposed in Hyperchain election process - #45 by Vikram is susceptible to a variant of nothing at stake attack. Voting power calculation and delegation needs to be implemented really carefully as in some cases it will allow to circumvent protections against those attacks.
The Goal
Define the leader election process and the consensus mechanism to make the network as much secure as possible. This is with the intent to create a technical specification/whitepaper on hyperchains which would allow to start working on an implementation - probably via a plugin to the erlang node.
Motivation
The existing PoF mechanism found in aeternity’s BitcoinNG is completely insufficient for securing hyperchains as this forum thread will show. Determining voting power based on the current account balance is a no go as this circumvents the proposed improved PoF mechanism. Voting power delegation introduces another nasty attack vector which works around PoF. The mitigations Hyperchains employ need to be secure in three cases:
- when syncing a new node
- when syncing after downtime
- after syncing when listening for gossiped transactions/blocks/events on the parent chain.
Types of possible attacks applicable to hyperchains
- Nothing at stake attacks - it is easy to produce new key or micro blocks by a leader
- Avoiding punishment for malicious actions - commiting fraud, getting punished, not losing anything, commiting fraud again…
- Long range attacks - might be a issue when syncing - I think the current approach is safe from them - let’s discuss it here
- Tainting assets when doing atomic swaps - might become an issue depending on what wallet/exchange implementors will do
Describing the possible attacks
Nothing at stake
Notation: Circles are microblocks, Squares are keyblocks
Let’s assume in this section that we use a safe leader election function and a safe voting power calculation scheme and we have no PoF - due to the nature of BitcoinNG three attacks arise:
Microforks
Description
When a malicious leader is elected microblocks are really cheap to produce - it is possible for the adversary to create such a situation:
"M" keyblock
___ |------O <-- O <-- O
| | <-- O <-- O <-- O <--|------O
|___| |------O <-- O
Resolution
Commitments of the delegates will point to the “M” keyblock and the voting power calculation is performed at “M” - this means that the next leader is elected deterministically regardless of which microfork the next leader supports.
This means that when the new leader is elected the situation looks like this:
"M" keyblock ___ PoF
___ |------O <-- O <-- O | | <-- O <-- O
| | <-- O <-- O <-- O <--|------O |-----|___|
|___| |------O <-- O <------------|
We reuse the existing PoF mechanism from aeternity mainnet but we need to modify two things to make it safe:
- On mainnet the PoF mechanism can be activated only by the next leader - this is unsafe as I will show in the next section - to make it safe we need to allow to submit PoF up to a grace period - G
- The punishments for PoF need to be much more severe than the current one - otherwise when M gets reelected later he can commit fraud again - the cost of fraud needs to be as high as possible - imagine stealing a million dolars for only 5 cents!
Generational forks
Description
This kind of attack is not a problem in PoW based BitcoinNG as producing keyblocks is really hard. On the contrary keyblocks on hyperchains are really, really cheap - a malicious leader might flood the network with invalid keyblocks:
K2a K2b K2c K2d
| | | |
V V V V
K1 <-- O <-- O < -- O <-- O
K2a, K2b, K2c, K2d were emitted by a malicious leader - please note that the adversary can do anything at this point and might also create microforks. Even if the leader election function is fair and has desirable properties there is a problem with selecting the next leader who might resolve this situation as it is unclear to which fork to commit - this essentially splits the network in many parts. To resolve this situation a SINGLE leader must be agreed upon using an additional mechanism. Due to network propagation delays and connectivity issues some nodes might not notice that a generational fork was created and not respond accordingly. New nodes or the ones catching up after downtime need to be aware that a generational fork was created and apply the appropriate resolution.
Resolution - Notifying the network about fraud
After a generational fork, new nodes need to be aware that such event occurred in the past without syncing all orphaned forks and only by syncing the winning chain. Nodes which do not notice the generational fork in time need to get notified. Our main source of truth are the commitments on the parent chain - commitments might optionally contain a fraud report which cryptographically proves that the previous leader was malicious. When a node spots a generational fork either via gossip or through a commitment with a fraud report - it shall validate/create a proof and submit a commitment with a fraud report to the parent chain in case he might participate in resolving this situation.
Resolution - Generational fraud commitment
The voting power of the delegates depend on the particular keyblock pointed to by the commitment - when submitting fraud commitments delegates need to indicate the latest child keyblock considered by them to be valid - this MUST point to the generation from which a generational fork starts. Attached there is a proof containing two signed child keyblock headers which were signed by the same leader and generate a generational fork. We forbid rollbacking the malicious generation - this might break applications which build on hyperchains. The committer needs to submit in the commitment which fork he wants to support - if he gets elected(the staking power is calculated based on the latest valid child keyblock) then he needs to build on the fork which he supported. This election always bans the delegate which started a generational fork.
Resolution - Block importance
Not all delegates might notice in time that a generational fork occurred, some of them might commit to one of the forks and think they won the election and later receive a keyblock by the leader elected to resolve the fork. We introduce a canonical metric of block importance and the nodes need to always support the most important block. This is similar to “Follow the most difficult chain” in PoW cryptocurrencies. The most difficult chain might not always be the longest one. For now we use the following difficulty formula:
Difficulty(Genesis) = 0
Difficulty(Block) =
Difficulty(Prev(Block))
+
(
If no PoGF(Proof of Generational Fraud) then
Sum of the voting power of delegates who committed to the previous generation
Else
(Sum of the voting power of delegates who committed to the previous generation)
+
(Sum of the voting power of delegates who committed to resolve the generational fork)
)
If two forks happen to have the same difficulty then the block with the lower header hash becomes the preferred one.
The formula ensures that keyblocks pointing to a PoGF are always strongly preferred over ordinary keyblocks - deletages who detect generational forks are always preferred over poorly connected/bootstraping/syncing delegates.
Resolution - [RFC] What if the leader does not show up?
Delegates resubmit their commitments and elect a new leader for this task - the network stalls for a while. This is prone to a lot of race conditions and the old leader might reappear and submit his keyblock. It is indistinguishable whether the leader is selfish and delays the block publication or the leader is offline or his block gets censored by adversaries or he is just poorly connected with the rest of the network. We need to decide what to do when we received a keyblock from the old leader when some part of the network received a block from the new leader. For now we will only accept past blocks if they are not older than 2-3 generations and rely on the difficulty mechanism to resolve conflicts. We need to spend more time on this issue but fortunately we can postpone it until the development phase starts.
Resolution - What if the leader himself creates generational forks?
Fortunately after he created a generational fork the old malicious leader is already punished by the staking contract - the punishment is applied in each of the forks - we can just use the same mechanism to punish him.
Resolution - [RFC] Commitment size
Reporting PoGF might be expensive as we need to store a lot of data(possibly multiple independent PoGF) and storage on the parent chain might be really expensive - if minimizing the storage used on the parent chain is a priority(which might be a case for BTC/ETH) then commitments on the parent chain contain only hashes of commitment objects stored and synchronized only on the child hyperchain or in some external service like IPFS. In case of some parent networks such as ETH additional optimizations might be applicable.
A malicious leader is elected multiple times and combines the previous two primitives
Description
This attack scenario assumes a combination of the above - after creating a microfork it is still possible for the leader to get reelected - we ban him from elections either via PoGF or PoF so it is possible to create a generational fork on top of a microfork as we ban him only after a leader different than him gets elected.
Leader Alice
___
Leader Alice | |
___ |------O <-- O <-- O <----- |___|
| | <-- O <-- O <-- O <--|------O ___
|___| |------O <-- O <----------- | |
|___|
Resolution
First we use PoGF and then we emit an optional PoF in a microblock. PoF is optional as he will be punished by PoGF.
Network propagation delays
If a peer has an outdated view of the chain due to bad connectivity or just because of race condition it is possible he will commit to an outdated keyblock:
Alice's view of the chain:
... <- K1
Majority view of the chain:
... <- K1 <- K2
If Alice doesn’t notice K2 in time it is possible that she publishes a commitment to K1. If she doesn’t receive K2 before her commitment is included and the leader election cycle is over she might publish a keyblock as she thinks she became the new leader:
Alice's view of the chain:
... <- K1 <- KA
Majority view of the chain:
... <- K1 <- K2
<- KA
In this situation the difficulty calculation mechanism comes to rescue - the network will prefer K2 as the majority of the delegates commited to this block. After Alice eventually receives K2 she will prefer it over KA and abandon her fork.
Long range attack
We accept gossiped blocks only when the blocks don’t create forks older than X generations - If the parent chain has decent finality guaranties this results in transaction finalization in only max(X * hyperchain_election_interval, parent_finalization_time).
This essentially protects the network against large rollbacks. When syncing new nodes a long range attack would be feasible but it would be obvious that such a attack is under way - In order to efectivelly fool new nodes in thinking that the competing chain is the main one the adversaries would need to submit commitments for it since the beginning of the hyperchain. Everyone will notice ahead of time that a malicious carter prepared a secret chain and it is kept secret from the rest of the network - if that is the case the HC administrators might prepare a node with the malicious chain banned.
Botstraping problem
When syncing new nodes we need to evaluate and validate chains provided by other nodes. Hyperchains are not immune to Long range attacks when syncing new nodes but fortunately they provide more protection to this kind of attack compared to classical PoS solutions. It is really easy to spot secret malicious chains by looking at the commitments on the parent chain.
Tainting assets
Crypto exchanges and users using atomic swaps services need to evaluate each hyperchain individually - only hyperchains with a healthy amount of delegates should be enlisted by crypto exchanges or supported by atomic swap services. If the security of a particular hyperchain is questionable(such as a hyperchain with 1-2 active validators) then it can’t be trusted - allowing such HC on exchanges opens the door to fraud like in this example:
1. Alice swaps 1 AliceChain token for 1 BobChain token
2. Alice has no money left as the rest is locked in the staking contract
3. As Alice has more than 50% of the voting power she rewrites history and rollbacks the swap
4. Alice swaps 1 AliceChain token for 1 BobChain token
5. GOTO 1 unitl the swap service runs out of BobChain tokens :3
Additional care must be made around consorcium/private chains.
Avoiding punishments
Even when we are protected against nothing at stake attacks with PoF and PoGF, some voting power calculation/delegation schemes cimcurvent the built in protections entirely. Lets assume for now a simple scheme and analyze how we might overcome PoF or PoGF:
1. Eliglible delegates are the top 100 most wealthy token holders
2. Fraud(either PoF or PoGF) burns all the money of the fraudster
The voting power calculation always happens on the block pointed to by the commitment. This scheme allows to avoid PoF/PoGF by transferring away all of your funds in the generation where you commited fraud. For instance:
1. Mallory becomes a leader
2. She transfers away their funds to her second account(in all the generational forks)
3. She creates a microfork or a generational fork
4. The next leader punishes Mallory but unfortunetally the funds were already transfered to another account
5. Mallory uses her second account to commit fraud again :(
This example shows that funds which determine the voting power MUST be locked for some period of time. Delegates might want to still use their accounts for regular transfers so we cannot rely on the current account balance. The stake must be locked by a special staking contract - this is the main reasoning behind Hyperchain staking mechanism Withdrawals and Deposits need to be delayed by few generations - this allows the PoF or PoGF to actually punish the stakeholder. This thread won’t talk a lot about this contract - details on it should be discussed in the linked forum thread.
Voting Power delegation introduces another nasty attack vector. Let’s analyze the following scheme:
1. Eliglible delegates are the top 100 most wealthy stake holders taking into account vote delegation in the staking contract
2. Fraud(either PoF or PoGF) burns all the stake of the fraudster locked in the contract
3. Your voting power might be delegated to another stakeholder
This opens doors for the following scenario:
1. Mallory delegates all of her stake to a fresh account controlled by her
2. Her fresh account get's elected
3. Her fresh account commits fraud
4. Mallory looses nothing as all her funds are locked in her first account and only her second account is punished
5. Mallory might commit fraud as long as she likes!
To mitigate this issue we EITHER forbid voting power delegation OR we burn/redistribute all the delegated tokens. It will be up for the particular hyperchain to decide which approach to take. The beauty of the staking contract approach is that this behaviour will be easily customizable by administrators and it is even possible to change it down the line if enough voting power agrees to this.
RFC
This thread together with Hyperchain staking mechanism will work as the initial technical specification of hyperchains - the whitepaper will be based on those. The more eyes look at this thread the better @contributor @yani.chain