Consensus_Overview
0chain 1 introduces synchronous consensus protocol from the family of Dfinity-like protocols 2.
A round is the process of producing a single block, divided into one or more subrounds. In general, a block is produced in a single subround for all of the miners. However, if the process times out for a miner, the process restarts and a new subround begins. The two major entities involved are the miners and the sharders; the miners are responsible for the production and verification of blocks, whereas the sharders store the blocks. Generators (Leaders) are the miners that are currently taking part in block production are referred to as being in the active set. Other miners (Replicas) that have been selected to start at the next view change are referred to as the incoming miners or as the DKG miners.
Every round, certain miners are selected as the generators responsible for creating the block. There is a priority to the generators, so that the second generator’s block is only used if the first generator fails to produce a block. All miners serve as verifiers (notary), who replay the generators’ blocks to ensure they are valid and then produce signed verification tickets as their guarantee that the block is valid. The miners then tally the votes from all verifiers; once the block has received sufficient votes, the miners send out a notarization including the verification tickets received from other miners.
Miners are expected to store the state of the blockchain and a few recent blocks, but are not expected to store the full blockchain history. The state of the blockchain is stored as a Merkle-Patricia Trie (MPT). In contrast to miners, sharders do not participate in producing or voting for blocks, but are tasked with long-term storage of the blocks. Note that an individual sharder does not need to store all blocks, but only the subset of blocks assigned to them.
As any BFT consensus protocol 0chain consensus protocol holds two main properties under defined threat model:
- Liveness. Blockchain makes progress sequentially generating blocks and incrementing round.
- Safety. Eventually every honest node will have the same correct state. And additional finalization property
- Finalization. Eventually every honest node will agree on blockchain starting at genesis block upto last finalized block, which can’t be forked and every block generated in the future will extend this blockchain.
Consensus protocol is stable under less than one third participants which can act as adaptive adversarials. It means that these participants can act as one whole, coordinating their actions just in time with zero delay. It is as far as I know the strongest assumption.
Dfinity protocol 3 ensures three invariants.
- An honest leader’s block will be uniquely certified in an iteration.
- In each iteration, at least one block, but possibly many, will be notarized.
- At the end of round k, if all round-(k − 1) blocks extend the same Bk−2, then Bk−2 is uniquely extendable. i.e., no other iteration-(k − 2) block can be extended from then on.
We slightly improved the III invariant by adding Probabilistic Finality
We have synchronous protocol, but what does it mean in practice? In theory, it means that every node has bounded network latency and guaranteed to send or receive a message in this interval, in different papers this interval is called Delta.
It matters, because global network failure is not an option for us and normally can’t happen.
Note that 4:
- partial-synchrony protocols where this case is exceptional, but should be handled on protocol level protocol has global synchronization time (GST) to recover
- asynchronous protocols where this case is normal We use synchrony assumption to guard I invariant and to prove protocol liveness, more detailed look lemma1 [3]. Briefly speaking we need messages to reach every node in delta when notarization is achieved, it guarantees that in delta all honest nodes will stop voting for proposal and never go to the next rank proposal. Only one block will be notarized and it will be finalized eventually.
What if node is delayed, how can it get to the same round as the majority of nodes? Generally speaking there are two approaches used for synchronous protocols. First approach is connected to common timescale. The idea of a common synchronized clock is commonly used for wide variety distributed systems. Every node delayed for some reason can use some sort of clocks to compute its current round.
We use another approach. Like DiemBFT 5 and several other BFT protocols we use special synchronization event to find what round do network has at the moment, and get up to it if miner is delayed. Since notarization is a common agreement that more than 2/3 of participants know and trust current proposal and message is broadcasted in delta to every miner in the network, we use it as such a synchronization event. For a delayed miner it is guaranteed that not more than delta ago majority of network participants was synchronized on current round and more importantly current proposer is not too late to propose block since every honest participant will wait at least delta for our proposal before they switch to the next rank.
0chain consensus protocol is optimistic responsive 6. In general it means that honest miner can transit to the next round or sub-round without waiting for timeout to happen.
In practice, honest node do not need to wait Delta time to transit to the next round. As soon as they receive enough verifications for proposal, they create notarization and moves to the next round. As we told before, synchrony of network is achieved by protocol synchronization event, not by timescale, and network will eventually reach next round.
Optimistic responsiveness hugely increase blockchain progress speed in case of honest leader, letting it move at a speed of network latency without any delays. When leader is byzantine honest replicas rely on timeout to switch to the next ranked leader, this switch significantly slows blockchain down, but insures its safety. We assume that byzantine cases are rare and participants will be incentivize to behave accordingly, so byzantine cases won't occur often enough to significantly slow progress.
In best case protocol uses O(n * n) messages at a speed of network latency. At worst case, protocol with a small improvement uses O(n^2) messages with O(f * Delta) latency. Look attack section for more details on worst cases 2,3.
Finalization is the consensus point of protocol, finalized block and all its predecessors can't be reverted and they are the same for all honest network participants. Finalization is independent process and only needs information about notarized blocks. It uses several assumptions:
- Synchrony. It is guaranteed, that network sends messages in δ
- Liveness. At least one block is notarized in Δ+δ
Synchrony is the essence of finality protocol. It is needed to guarantee, that every honest replica knows all notarized blocks of round r1 at the moment they start to get notarization for round r2. Since r1 is now locked and can't be changed. Idea of lock-commit is very popular among consensus protocols and is used in Tendermint, Hotstuff and several others. Adversarial can't hide any fork it builds in shadow and reveal it eventually, since past round notarization set is locked.
Lock-commit together with synchrony guarantees that in round r2 (last notarized round) all honest replicas know what blocks were notarized in round r1 and that all honest replica this set is the same for every honest replica and it can't be modified anytime in the future. This fact simply means that all honest replicas has consensus on this set and to finalize block they need to chose single block deterministically. Since notarized blocks in r1 can have the same rank and can be extended by blocks in r2 in the future (we do not know r2 set yet) we finalize (commit) round r0.
Dfinity do not have fork choice rule as Casper and Hotstuff, it uses another approach to choose single block to finalize. At the end of round r2, if all round r1 notarized blocks extend the same block B0 of round r0, then B0 is uniquely extendable and this block should be notarized. If there is no uniquely extendable block on round r0 than finalization do not happen.
Finalization will happen eventually even if it is not possible to determine single block on r-2 now. The proposal send by honest proposer with highest rank (Leader) is the only block that will be notarized on this round and will eventually be finalized (in 2 rounds from it's notarization)
It is possible to finalize only blocks proposed by honest leader as soon as they are single and do not look for uniquely extendable block. In theory it can be done on r-1 round when we locked notarized set, due to synchrony assumption all honest replicas will receive notarization.
If malicious leader withheld proposal from small part of nodes, these nodes can fetch this block later when they get notarization.
If malicious leader equivocates this round will only be finalized through finalization of its sibling.
There are several requirements for finalization to work correctly:
- As soon as the first notarization for round is received, notarization of previous round is finished and verifications should be discarded
- Verification of round blocks stops at the same time
- Replica should verify every block of given rank
If replica will not verify every block on top rank it got, malicious leader can simply trigger round restart. Attack is pretty simple:
Adversarial leader will equivocate and send different blocks to different replicas. Replicas will verify this round and lock this rank, they won't verify worse ranks or other blocks on this rank. Replicas won't get enough verifications to make notarization and transfer to the next round, so the only way to make transfer is restart. Dfinity uses another approach and after notarization phase time-outs they move to the next rank and so on, so in their case round will be delayed for f*Δ time.
If replica will verify every block on current round another attack is possible first discussed in 3
Adversarial leader will send two different blocks to replicas, replicas will notarize both blocks. In the next round new adversarial will generate 2 proposals that extend different notarizations and so on. At worst case finalization will be delayed for f rounds. Which is not critical but pretty annoying. Solution made together with Dfinity organization and proposed in 3 lay in adding proof that leader equivocates, it can be useful for slashing miners when PoS will be implemented.
//No deterministic finality for f
(T0) Leader_0: send Proposal0_0 Proposal0_1
(T0 + δ + Δ) Replica_i: send Verification0_0 Verification0_1
(T0 + 3δ + Δ) Leader_1: Proposal1_0(block0_0) Proposal1_1(block0_1)
(T0 + 3δ + 2Δ) Replica_i: send Verification1_0 Verification1_1
. . . (f)
This attack is reasonable in case miners get some reward for proposing, usually fees of transactions and airdrop, it is not easy to execute but it is possible.
Imagine honest miner is a Leader of round r0, let's call it g0_0, and miner in the next rank g0_1 is in collusion with leader of the next round r1 - g1. In such situation if two notarizations are generated for round r0 for blocks generated by not0_0 and not0_1, leader in round r1 can extend not0_1 instead of heaviest notarized block not0_0 and remove this block from chain, depriving of reward g0_0.